./Ultimate.py --spec ../../sv-benchmarks/c/properties/unreach-call.prp --file ../../sv-benchmarks/c/combinations/gcd_4+newton_3_7.i --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_da71d4ab-fde8-404d-b8fa-860e6ebdffbf/bin/utaipan-verify-sOmjnqqW8E/data/config -Xmx15G -Xms4m -jar /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_da71d4ab-fde8-404d-b8fa-860e6ebdffbf/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_da71d4ab-fde8-404d-b8fa-860e6ebdffbf/bin/utaipan-verify-sOmjnqqW8E/data -tc /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_da71d4ab-fde8-404d-b8fa-860e6ebdffbf/bin/utaipan-verify-sOmjnqqW8E/config/TaipanReach.xml -i ../../sv-benchmarks/c/combinations/gcd_4+newton_3_7.i -s /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_da71d4ab-fde8-404d-b8fa-860e6ebdffbf/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_da71d4ab-fde8-404d-b8fa-860e6ebdffbf/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 87bc0d62bd0ac2c8f0b3bcd924815b04302ef88419a4b535524b284cb471b329 --- Real Ultimate output --- This is Ultimate 0.3.0-dev-826ab2b [2024-11-14 02:41:59,358 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-11-14 02:41:59,451 INFO L114 SettingsManager]: Loading settings from /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_da71d4ab-fde8-404d-b8fa-860e6ebdffbf/bin/utaipan-verify-sOmjnqqW8E/config/svcomp-Reach-32bit-Taipan_Default.epf [2024-11-14 02:41:59,459 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-11-14 02:41:59,460 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-11-14 02:41:59,495 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-11-14 02:41:59,498 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-11-14 02:41:59,498 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-11-14 02:41:59,498 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2024-11-14 02:41:59,499 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2024-11-14 02:41:59,499 INFO L153 SettingsManager]: * User list type=DISABLED [2024-11-14 02:41:59,500 INFO L151 SettingsManager]: Preferences of Abstract Interpretation differ from their defaults: [2024-11-14 02:41:59,500 INFO L153 SettingsManager]: * Explicit value domain=true [2024-11-14 02:41:59,500 INFO L153 SettingsManager]: * Abstract domain for RCFG-of-the-future=PoormanAbstractDomain [2024-11-14 02:41:59,500 INFO L153 SettingsManager]: * Octagon Domain=false [2024-11-14 02:41:59,501 INFO L153 SettingsManager]: * Abstract domain=CompoundDomain [2024-11-14 02:41:59,501 INFO L153 SettingsManager]: * Check feasibility of abstract posts with an SMT solver=true [2024-11-14 02:41:59,501 INFO L153 SettingsManager]: * Use the RCFG-of-the-future interface=true [2024-11-14 02:41:59,502 INFO L153 SettingsManager]: * Interval Domain=false [2024-11-14 02:41:59,502 INFO L151 SettingsManager]: Preferences of Sifa differ from their defaults: [2024-11-14 02:41:59,502 INFO L153 SettingsManager]: * Call Summarizer=TopInputCallSummarizer [2024-11-14 02:41:59,502 INFO L153 SettingsManager]: * Simplification Technique=POLY_PAC [2024-11-14 02:41:59,502 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-11-14 02:41:59,502 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2024-11-14 02:41:59,503 INFO L153 SettingsManager]: * sizeof long=4 [2024-11-14 02:41:59,503 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2024-11-14 02:41:59,503 INFO L153 SettingsManager]: * sizeof POINTER=4 [2024-11-14 02:41:59,503 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-11-14 02:41:59,503 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2024-11-14 02:41:59,503 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2024-11-14 02:41:59,503 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2024-11-14 02:41:59,503 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-11-14 02:41:59,503 INFO L153 SettingsManager]: * sizeof long double=12 [2024-11-14 02:41:59,503 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-11-14 02:41:59,503 INFO L153 SettingsManager]: * Use constant arrays=true [2024-11-14 02:41:59,504 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2024-11-14 02:41:59,504 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2024-11-14 02:41:59,504 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2024-11-14 02:41:59,505 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2024-11-14 02:41:59,505 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-11-14 02:41:59,505 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2024-11-14 02:41:59,505 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2024-11-14 02:41:59,505 INFO L153 SettingsManager]: * Trace refinement strategy=SIFA_TAIPAN [2024-11-14 02:41:59,505 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2024-11-14 02:41:59,505 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2024-11-14 02:41:59,505 INFO L153 SettingsManager]: * Trace refinement exception blacklist=NONE [2024-11-14 02:41:59,505 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2024-11-14 02:41:59,505 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_da71d4ab-fde8-404d-b8fa-860e6ebdffbf/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 -> 87bc0d62bd0ac2c8f0b3bcd924815b04302ef88419a4b535524b284cb471b329 [2024-11-14 02:41:59,858 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-11-14 02:41:59,878 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-11-14 02:41:59,882 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-11-14 02:41:59,883 INFO L270 PluginConnector]: Initializing CDTParser... [2024-11-14 02:41:59,884 INFO L274 PluginConnector]: CDTParser initialized [2024-11-14 02:41:59,887 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_da71d4ab-fde8-404d-b8fa-860e6ebdffbf/bin/utaipan-verify-sOmjnqqW8E/../../sv-benchmarks/c/combinations/gcd_4+newton_3_7.i Unable to find full path for "g++" [2024-11-14 02:42:02,121 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-11-14 02:42:02,407 INFO L384 CDTParser]: Found 1 translation units. [2024-11-14 02:42:02,410 INFO L180 CDTParser]: Scanning /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_da71d4ab-fde8-404d-b8fa-860e6ebdffbf/sv-benchmarks/c/combinations/gcd_4+newton_3_7.i [2024-11-14 02:42:02,420 INFO L427 CDTParser]: About to delete temporary CDT project at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_da71d4ab-fde8-404d-b8fa-860e6ebdffbf/bin/utaipan-verify-sOmjnqqW8E/data/0df7df677/a8bf7acd93664fd2bd11afa8d8a1dfb5/FLAG70d55d073 [2024-11-14 02:42:02,445 INFO L435 CDTParser]: Successfully deleted /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_da71d4ab-fde8-404d-b8fa-860e6ebdffbf/bin/utaipan-verify-sOmjnqqW8E/data/0df7df677/a8bf7acd93664fd2bd11afa8d8a1dfb5 [2024-11-14 02:42:02,448 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-11-14 02:42:02,450 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2024-11-14 02:42:02,452 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-11-14 02:42:02,452 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-11-14 02:42:02,456 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-11-14 02:42:02,457 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 14.11 02:42:02" (1/1) ... [2024-11-14 02:42:02,459 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@24c8a64 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 02:42:02, skipping insertion in model container [2024-11-14 02:42:02,460 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 14.11 02:42:02" (1/1) ... [2024-11-14 02:42:02,476 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-11-14 02:42:02,656 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_da71d4ab-fde8-404d-b8fa-860e6ebdffbf/sv-benchmarks/c/combinations/gcd_4+newton_3_7.i[1224,1237] [2024-11-14 02:42:02,699 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_da71d4ab-fde8-404d-b8fa-860e6ebdffbf/sv-benchmarks/c/combinations/gcd_4+newton_3_7.i[2848,2861] [2024-11-14 02:42:02,700 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-14 02:42:02,715 INFO L200 MainTranslator]: Completed pre-run [2024-11-14 02:42:02,728 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_da71d4ab-fde8-404d-b8fa-860e6ebdffbf/sv-benchmarks/c/combinations/gcd_4+newton_3_7.i[1224,1237] [2024-11-14 02:42:02,750 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_da71d4ab-fde8-404d-b8fa-860e6ebdffbf/sv-benchmarks/c/combinations/gcd_4+newton_3_7.i[2848,2861] [2024-11-14 02:42:02,751 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-14 02:42:02,772 INFO L204 MainTranslator]: Completed translation [2024-11-14 02:42:02,773 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 02:42:02 WrapperNode [2024-11-14 02:42:02,773 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-11-14 02:42:02,774 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-11-14 02:42:02,774 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-11-14 02:42:02,774 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-11-14 02:42:02,780 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 02:42:02" (1/1) ... [2024-11-14 02:42:02,788 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 02:42:02" (1/1) ... [2024-11-14 02:42:02,816 INFO L138 Inliner]: procedures = 27, calls = 28, calls flagged for inlining = 6, calls inlined = 6, statements flattened = 83 [2024-11-14 02:42:02,816 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-11-14 02:42:02,816 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-11-14 02:42:02,816 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-11-14 02:42:02,817 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-11-14 02:42:02,825 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 02:42:02" (1/1) ... [2024-11-14 02:42:02,825 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 02:42:02" (1/1) ... [2024-11-14 02:42:02,828 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 02:42:02" (1/1) ... [2024-11-14 02:42:02,828 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 02:42:02" (1/1) ... [2024-11-14 02:42:02,836 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 02:42:02" (1/1) ... [2024-11-14 02:42:02,839 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 02:42:02" (1/1) ... [2024-11-14 02:42:02,841 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 02:42:02" (1/1) ... [2024-11-14 02:42:02,841 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 02:42:02" (1/1) ... [2024-11-14 02:42:02,843 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-11-14 02:42:02,845 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2024-11-14 02:42:02,845 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2024-11-14 02:42:02,845 INFO L274 PluginConnector]: RCFGBuilder initialized [2024-11-14 02:42:02,846 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 02:42:02" (1/1) ... [2024-11-14 02:42:02,853 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2024-11-14 02:42:02,876 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_da71d4ab-fde8-404d-b8fa-860e6ebdffbf/bin/utaipan-verify-sOmjnqqW8E/z3 [2024-11-14 02:42:02,890 INFO L229 MonitoredProcess]: Starting monitored process 1 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_da71d4ab-fde8-404d-b8fa-860e6ebdffbf/bin/utaipan-verify-sOmjnqqW8E/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) [2024-11-14 02:42:02,893 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_da71d4ab-fde8-404d-b8fa-860e6ebdffbf/bin/utaipan-verify-sOmjnqqW8E/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Waiting until timeout for monitored process [2024-11-14 02:42:02,916 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2024-11-14 02:42:02,916 INFO L130 BoogieDeclarations]: Found specification of procedure fp [2024-11-14 02:42:02,917 INFO L138 BoogieDeclarations]: Found implementation of procedure fp [2024-11-14 02:42:02,917 INFO L130 BoogieDeclarations]: Found specification of procedure f [2024-11-14 02:42:02,917 INFO L138 BoogieDeclarations]: Found implementation of procedure f [2024-11-14 02:42:02,917 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2024-11-14 02:42:02,917 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-11-14 02:42:02,917 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-11-14 02:42:02,917 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2024-11-14 02:42:02,918 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2024-11-14 02:42:03,001 INFO L238 CfgBuilder]: Building ICFG [2024-11-14 02:42:03,003 INFO L264 CfgBuilder]: Building CFG for each procedure with an implementation [2024-11-14 02:42:03,287 INFO L? ?]: Removed 25 outVars from TransFormulas that were not future-live. [2024-11-14 02:42:03,287 INFO L287 CfgBuilder]: Performing block encoding [2024-11-14 02:42:03,354 INFO L311 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-11-14 02:42:03,354 INFO L316 CfgBuilder]: Removed 1 assume(true) statements. [2024-11-14 02:42:03,355 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 14.11 02:42:03 BoogieIcfgContainer [2024-11-14 02:42:03,355 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2024-11-14 02:42:03,357 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2024-11-14 02:42:03,357 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2024-11-14 02:42:03,362 INFO L274 PluginConnector]: TraceAbstraction initialized [2024-11-14 02:42:03,363 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 14.11 02:42:02" (1/3) ... [2024-11-14 02:42:03,363 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@110a040f and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 14.11 02:42:03, skipping insertion in model container [2024-11-14 02:42:03,364 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 02:42:02" (2/3) ... [2024-11-14 02:42:03,364 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@110a040f and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 14.11 02:42:03, skipping insertion in model container [2024-11-14 02:42:03,364 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 14.11 02:42:03" (3/3) ... [2024-11-14 02:42:03,365 INFO L112 eAbstractionObserver]: Analyzing ICFG gcd_4+newton_3_7.i [2024-11-14 02:42:03,391 INFO L217 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2024-11-14 02:42:03,393 INFO L154 ceAbstractionStarter]: Applying trace abstraction to ICFG gcd_4+newton_3_7.i that has 4 procedures, 34 locations, 1 initial locations, 1 loop locations, and 2 error locations. [2024-11-14 02:42:03,469 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2024-11-14 02:42:03,486 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;@46fe8ab6, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2024-11-14 02:42:03,486 INFO L334 AbstractCegarLoop]: Starting to check reachability of 2 error locations. [2024-11-14 02:42:03,491 INFO L276 IsEmpty]: Start isEmpty. Operand has 34 states, 19 states have (on average 1.368421052631579) internal successors, (26), 21 states have internal predecessors, (26), 9 states have call successors, (9), 3 states have call predecessors, (9), 3 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2024-11-14 02:42:03,500 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 9 [2024-11-14 02:42:03,500 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 02:42:03,501 INFO L215 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1] [2024-11-14 02:42:03,502 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 02:42:03,509 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 02:42:03,510 INFO L85 PathProgramCache]: Analyzing trace with hash -1562687401, now seen corresponding path program 1 times [2024-11-14 02:42:03,518 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 02:42:03,519 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1965671587] [2024-11-14 02:42:03,519 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 02:42:03,521 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 02:42:03,632 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 02:42:03,853 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-14 02:42:03,853 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 02:42:03,854 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1965671587] [2024-11-14 02:42:03,854 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1965671587] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-14 02:42:03,854 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-14 02:42:03,855 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2024-11-14 02:42:03,856 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1435774617] [2024-11-14 02:42:03,857 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-14 02:42:03,861 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2024-11-14 02:42:03,861 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 02:42:03,880 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2024-11-14 02:42:03,880 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2024-11-14 02:42:03,882 INFO L87 Difference]: Start difference. First operand has 34 states, 19 states have (on average 1.368421052631579) internal successors, (26), 21 states have internal predecessors, (26), 9 states have call successors, (9), 3 states have call predecessors, (9), 3 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) Second operand has 3 states, 3 states have (on average 2.3333333333333335) internal successors, (7), 3 states have internal predecessors, (7), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-14 02:42:03,949 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 02:42:03,950 INFO L93 Difference]: Finished difference Result 49 states and 65 transitions. [2024-11-14 02:42:03,951 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2024-11-14 02:42:03,953 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 2.3333333333333335) internal successors, (7), 3 states have internal predecessors, (7), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 8 [2024-11-14 02:42:03,953 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 02:42:03,960 INFO L225 Difference]: With dead ends: 49 [2024-11-14 02:42:03,960 INFO L226 Difference]: Without dead ends: 31 [2024-11-14 02:42:03,963 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 3 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2024-11-14 02:42:03,968 INFO L432 NwaCegarLoop]: 30 mSDtfsCounter, 1 mSDsluCounter, 29 mSDsCounter, 0 mSdLazyCounter, 21 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 1 SdHoareTripleChecker+Valid, 59 SdHoareTripleChecker+Invalid, 21 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 21 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-14 02:42:03,970 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [1 Valid, 59 Invalid, 21 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 21 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-14 02:42:03,984 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 31 states. [2024-11-14 02:42:04,009 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 31 to 30. [2024-11-14 02:42:04,012 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 30 states, 16 states have (on average 1.1875) internal successors, (19), 18 states have internal predecessors, (19), 9 states have call successors, (9), 3 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 02:42:04,018 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 30 states to 30 states and 36 transitions. [2024-11-14 02:42:04,021 INFO L78 Accepts]: Start accepts. Automaton has 30 states and 36 transitions. Word has length 8 [2024-11-14 02:42:04,022 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 02:42:04,022 INFO L471 AbstractCegarLoop]: Abstraction has 30 states and 36 transitions. [2024-11-14 02:42:04,023 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 2.3333333333333335) internal successors, (7), 3 states have internal predecessors, (7), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-14 02:42:04,023 INFO L276 IsEmpty]: Start isEmpty. Operand 30 states and 36 transitions. [2024-11-14 02:42:04,024 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 10 [2024-11-14 02:42:04,025 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 02:42:04,025 INFO L215 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-14 02:42:04,026 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2024-11-14 02:42:04,027 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 02:42:04,027 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 02:42:04,028 INFO L85 PathProgramCache]: Analyzing trace with hash -1304220369, now seen corresponding path program 1 times [2024-11-14 02:42:04,029 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 02:42:04,029 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [721307382] [2024-11-14 02:42:04,029 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 02:42:04,030 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 02:42:04,062 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 02:42:04,195 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-14 02:42:04,195 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 02:42:04,195 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [721307382] [2024-11-14 02:42:04,195 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [721307382] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-14 02:42:04,195 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-14 02:42:04,196 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2024-11-14 02:42:04,196 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1157284272] [2024-11-14 02:42:04,196 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-14 02:42:04,197 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2024-11-14 02:42:04,197 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 02:42:04,198 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2024-11-14 02:42:04,198 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2024-11-14 02:42:04,198 INFO L87 Difference]: Start difference. First operand 30 states and 36 transitions. Second operand has 3 states, 3 states have (on average 2.6666666666666665) internal successors, (8), 3 states have internal predecessors, (8), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-14 02:42:04,233 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 02:42:04,233 INFO L93 Difference]: Finished difference Result 41 states and 49 transitions. [2024-11-14 02:42:04,234 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2024-11-14 02:42:04,235 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 2.6666666666666665) internal successors, (8), 3 states have internal predecessors, (8), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 9 [2024-11-14 02:42:04,235 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 02:42:04,236 INFO L225 Difference]: With dead ends: 41 [2024-11-14 02:42:04,236 INFO L226 Difference]: Without dead ends: 31 [2024-11-14 02:42:04,236 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 3 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2024-11-14 02:42:04,238 INFO L432 NwaCegarLoop]: 29 mSDtfsCounter, 0 mSDsluCounter, 27 mSDsCounter, 0 mSdLazyCounter, 14 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 56 SdHoareTripleChecker+Invalid, 14 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 14 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-14 02:42:04,238 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 56 Invalid, 14 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 14 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-14 02:42:04,241 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 31 states. [2024-11-14 02:42:04,250 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 31 to 31. [2024-11-14 02:42:04,251 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 31 states, 17 states have (on average 1.1764705882352942) internal successors, (20), 19 states have internal predecessors, (20), 9 states have call successors, (9), 3 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 02:42:04,252 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 31 states to 31 states and 37 transitions. [2024-11-14 02:42:04,253 INFO L78 Accepts]: Start accepts. Automaton has 31 states and 37 transitions. Word has length 9 [2024-11-14 02:42:04,253 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 02:42:04,253 INFO L471 AbstractCegarLoop]: Abstraction has 31 states and 37 transitions. [2024-11-14 02:42:04,253 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 2.6666666666666665) internal successors, (8), 3 states have internal predecessors, (8), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-14 02:42:04,253 INFO L276 IsEmpty]: Start isEmpty. Operand 31 states and 37 transitions. [2024-11-14 02:42:04,254 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 11 [2024-11-14 02:42:04,254 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 02:42:04,254 INFO L215 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-14 02:42:04,254 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2024-11-14 02:42:04,254 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 02:42:04,255 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 02:42:04,255 INFO L85 PathProgramCache]: Analyzing trace with hash 1240684428, now seen corresponding path program 1 times [2024-11-14 02:42:04,255 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 02:42:04,255 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2069298440] [2024-11-14 02:42:04,259 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 02:42:04,260 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 02:42:04,295 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 02:42:04,532 INFO L134 CoverageAnalysis]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-14 02:42:04,532 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 02:42:04,533 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2069298440] [2024-11-14 02:42:04,533 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2069298440] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-14 02:42:04,533 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1624416219] [2024-11-14 02:42:04,533 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 02:42:04,533 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 02:42:04,533 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_da71d4ab-fde8-404d-b8fa-860e6ebdffbf/bin/utaipan-verify-sOmjnqqW8E/z3 [2024-11-14 02:42:04,536 INFO L229 MonitoredProcess]: Starting monitored process 2 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_da71d4ab-fde8-404d-b8fa-860e6ebdffbf/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-14 02:42:04,538 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_da71d4ab-fde8-404d-b8fa-860e6ebdffbf/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2024-11-14 02:42:04,624 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 02:42:04,627 INFO L255 TraceCheckSpWp]: Trace formula consists of 66 conjuncts, 9 conjuncts are in the unsatisfiable core [2024-11-14 02:42:04,635 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-14 02:42:04,719 INFO L134 CoverageAnalysis]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-14 02:42:04,719 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-14 02:42:04,787 INFO L134 CoverageAnalysis]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-14 02:42:04,788 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1624416219] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-14 02:42:04,788 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [771076152] [2024-11-14 02:42:04,813 INFO L159 IcfgInterpreter]: Started Sifa with 10 locations of interest [2024-11-14 02:42:04,813 INFO L166 IcfgInterpreter]: Building call graph [2024-11-14 02:42:04,821 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2024-11-14 02:42:04,827 INFO L176 IcfgInterpreter]: Starting interpretation [2024-11-14 02:42:04,827 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2024-11-14 02:42:05,452 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 48 for LOIs [2024-11-14 02:42:05,556 INFO L180 IcfgInterpreter]: Interpretation finished [2024-11-14 02:42:06,234 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '335#(and (<= 1 |#StackHeapBarrier|) (= |__VERIFIER_assert_#in~cond| 0) (exists ((|v_ULTIMATE.start_main1_~g~0#1_BEFORE_CALL_1| Int)) (and (not (= (mod 63 |v_ULTIMATE.start_main1_~g~0#1_BEFORE_CALL_1|) 0)) (<= 0 (+ |v_ULTIMATE.start_main1_~g~0#1_BEFORE_CALL_1| 2147483648)) (<= |v_ULTIMATE.start_main1_~g~0#1_BEFORE_CALL_1| 2147483647))))' at error location [2024-11-14 02:42:06,235 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2024-11-14 02:42:06,235 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-14 02:42:06,235 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 4, 4] total 8 [2024-11-14 02:42:06,235 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1539216022] [2024-11-14 02:42:06,235 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-14 02:42:06,236 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2024-11-14 02:42:06,236 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 02:42:06,237 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2024-11-14 02:42:06,238 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=47, Invalid=163, Unknown=0, NotChecked=0, Total=210 [2024-11-14 02:42:06,239 INFO L87 Difference]: Start difference. First operand 31 states and 37 transitions. Second operand has 8 states, 8 states have (on average 2.125) internal successors, (17), 8 states have internal predecessors, (17), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-14 02:42:06,338 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 02:42:06,338 INFO L93 Difference]: Finished difference Result 43 states and 52 transitions. [2024-11-14 02:42:06,339 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-14 02:42:06,339 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 8 states have (on average 2.125) internal successors, (17), 8 states have internal predecessors, (17), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 10 [2024-11-14 02:42:06,339 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 02:42:06,340 INFO L225 Difference]: With dead ends: 43 [2024-11-14 02:42:06,340 INFO L226 Difference]: Without dead ends: 33 [2024-11-14 02:42:06,340 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 34 GetRequests, 19 SyntacticMatches, 0 SemanticMatches, 15 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 71 ImplicationChecksByTransitivity, 0.8s TimeCoverageRelationStatistics Valid=65, Invalid=207, Unknown=0, NotChecked=0, Total=272 [2024-11-14 02:42:06,341 INFO L432 NwaCegarLoop]: 28 mSDtfsCounter, 0 mSDsluCounter, 54 mSDsCounter, 0 mSdLazyCounter, 25 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 82 SdHoareTripleChecker+Invalid, 26 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 25 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-14 02:42:06,342 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 82 Invalid, 26 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 25 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-14 02:42:06,342 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 33 states. [2024-11-14 02:42:06,347 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 33 to 33. [2024-11-14 02:42:06,347 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 33 states, 19 states have (on average 1.1578947368421053) internal successors, (22), 21 states have internal predecessors, (22), 9 states have call successors, (9), 3 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 02:42:06,348 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 33 states to 33 states and 39 transitions. [2024-11-14 02:42:06,348 INFO L78 Accepts]: Start accepts. Automaton has 33 states and 39 transitions. Word has length 10 [2024-11-14 02:42:06,348 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 02:42:06,349 INFO L471 AbstractCegarLoop]: Abstraction has 33 states and 39 transitions. [2024-11-14 02:42:06,349 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 8 states have (on average 2.125) internal successors, (17), 8 states have internal predecessors, (17), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-14 02:42:06,349 INFO L276 IsEmpty]: Start isEmpty. Operand 33 states and 39 transitions. [2024-11-14 02:42:06,349 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 13 [2024-11-14 02:42:06,350 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 02:42:06,350 INFO L215 NwaCegarLoop]: trace histogram [3, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-14 02:42:06,370 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_da71d4ab-fde8-404d-b8fa-860e6ebdffbf/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Forceful destruction successful, exit code 0 [2024-11-14 02:42:06,554 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2,2 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_da71d4ab-fde8-404d-b8fa-860e6ebdffbf/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 02:42:06,554 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 02:42:06,555 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 02:42:06,555 INFO L85 PathProgramCache]: Analyzing trace with hash 345473004, now seen corresponding path program 2 times [2024-11-14 02:42:06,555 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 02:42:06,555 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [382361000] [2024-11-14 02:42:06,555 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 02:42:06,556 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 02:42:06,575 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 02:42:06,852 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-14 02:42:06,852 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 02:42:06,852 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [382361000] [2024-11-14 02:42:06,852 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [382361000] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-14 02:42:06,852 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1367901174] [2024-11-14 02:42:06,853 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-14 02:42:06,853 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 02:42:06,853 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_da71d4ab-fde8-404d-b8fa-860e6ebdffbf/bin/utaipan-verify-sOmjnqqW8E/z3 [2024-11-14 02:42:06,856 INFO L229 MonitoredProcess]: Starting monitored process 3 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_da71d4ab-fde8-404d-b8fa-860e6ebdffbf/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-14 02:42:06,859 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_da71d4ab-fde8-404d-b8fa-860e6ebdffbf/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2024-11-14 02:42:06,929 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2024-11-14 02:42:06,929 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-14 02:42:06,930 INFO L255 TraceCheckSpWp]: Trace formula consists of 70 conjuncts, 11 conjuncts are in the unsatisfiable core [2024-11-14 02:42:06,932 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-14 02:42:07,016 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-14 02:42:07,016 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-14 02:42:07,358 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-14 02:42:07,358 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1367901174] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-14 02:42:07,358 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [524117399] [2024-11-14 02:42:07,361 INFO L159 IcfgInterpreter]: Started Sifa with 10 locations of interest [2024-11-14 02:42:07,365 INFO L166 IcfgInterpreter]: Building call graph [2024-11-14 02:42:07,366 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2024-11-14 02:42:07,366 INFO L176 IcfgInterpreter]: Starting interpretation [2024-11-14 02:42:07,366 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2024-11-14 02:42:07,632 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 29 for LOIs [2024-11-14 02:42:07,677 INFO L180 IcfgInterpreter]: Interpretation finished [2024-11-14 02:42:08,245 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '545#(and (exists ((|v_ULTIMATE.start_main1_~g~0#1_BEFORE_CALL_2| Int)) (and (<= |v_ULTIMATE.start_main1_~g~0#1_BEFORE_CALL_2| 2147483647) (<= 0 (+ |v_ULTIMATE.start_main1_~g~0#1_BEFORE_CALL_2| 2147483648)) (not (= (mod 63 |v_ULTIMATE.start_main1_~g~0#1_BEFORE_CALL_2|) 0)))) (<= 1 |#StackHeapBarrier|) (= |__VERIFIER_assert_#in~cond| 0))' at error location [2024-11-14 02:42:08,246 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2024-11-14 02:42:08,247 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-14 02:42:08,247 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6, 6] total 14 [2024-11-14 02:42:08,247 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1194539077] [2024-11-14 02:42:08,247 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-14 02:42:08,247 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2024-11-14 02:42:08,248 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 02:42:08,248 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2024-11-14 02:42:08,248 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=96, Invalid=324, Unknown=0, NotChecked=0, Total=420 [2024-11-14 02:42:08,249 INFO L87 Difference]: Start difference. First operand 33 states and 39 transitions. Second operand has 14 states, 14 states have (on average 1.6428571428571428) internal successors, (23), 14 states have internal predecessors, (23), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-14 02:42:08,340 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 02:42:08,340 INFO L93 Difference]: Finished difference Result 44 states and 52 transitions. [2024-11-14 02:42:08,341 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2024-11-14 02:42:08,341 INFO L78 Accepts]: Start accepts. Automaton has has 14 states, 14 states have (on average 1.6428571428571428) internal successors, (23), 14 states have internal predecessors, (23), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 12 [2024-11-14 02:42:08,341 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 02:42:08,342 INFO L225 Difference]: With dead ends: 44 [2024-11-14 02:42:08,342 INFO L226 Difference]: Without dead ends: 34 [2024-11-14 02:42:08,342 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 41 GetRequests, 21 SyntacticMatches, 0 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 175 ImplicationChecksByTransitivity, 0.8s TimeCoverageRelationStatistics Valid=111, Invalid=351, Unknown=0, NotChecked=0, Total=462 [2024-11-14 02:42:08,343 INFO L432 NwaCegarLoop]: 28 mSDtfsCounter, 0 mSDsluCounter, 108 mSDsCounter, 0 mSdLazyCounter, 38 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 136 SdHoareTripleChecker+Invalid, 38 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 38 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-14 02:42:08,343 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 136 Invalid, 38 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 38 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-14 02:42:08,344 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 34 states. [2024-11-14 02:42:08,348 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 34 to 34. [2024-11-14 02:42:08,348 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 34 states, 20 states have (on average 1.15) internal successors, (23), 22 states have internal predecessors, (23), 9 states have call successors, (9), 3 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 02:42:08,349 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 34 states to 34 states and 40 transitions. [2024-11-14 02:42:08,349 INFO L78 Accepts]: Start accepts. Automaton has 34 states and 40 transitions. Word has length 12 [2024-11-14 02:42:08,349 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 02:42:08,349 INFO L471 AbstractCegarLoop]: Abstraction has 34 states and 40 transitions. [2024-11-14 02:42:08,350 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 14 states, 14 states have (on average 1.6428571428571428) internal successors, (23), 14 states have internal predecessors, (23), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-14 02:42:08,350 INFO L276 IsEmpty]: Start isEmpty. Operand 34 states and 40 transitions. [2024-11-14 02:42:08,350 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 14 [2024-11-14 02:42:08,350 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 02:42:08,350 INFO L215 NwaCegarLoop]: trace histogram [4, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-14 02:42:08,371 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_da71d4ab-fde8-404d-b8fa-860e6ebdffbf/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2024-11-14 02:42:08,554 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,3 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_da71d4ab-fde8-404d-b8fa-860e6ebdffbf/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 02:42:08,555 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 02:42:08,555 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 02:42:08,555 INFO L85 PathProgramCache]: Analyzing trace with hash 841571439, now seen corresponding path program 3 times [2024-11-14 02:42:08,555 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 02:42:08,555 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1619439807] [2024-11-14 02:42:08,556 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 02:42:08,556 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 02:42:08,568 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 02:42:08,851 INFO L134 CoverageAnalysis]: Checked inductivity of 10 backedges. 0 proven. 10 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-14 02:42:08,851 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 02:42:08,851 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1619439807] [2024-11-14 02:42:08,852 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1619439807] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-14 02:42:08,852 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [51017450] [2024-11-14 02:42:08,852 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2024-11-14 02:42:08,852 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 02:42:08,852 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_da71d4ab-fde8-404d-b8fa-860e6ebdffbf/bin/utaipan-verify-sOmjnqqW8E/z3 [2024-11-14 02:42:08,856 INFO L229 MonitoredProcess]: Starting monitored process 4 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_da71d4ab-fde8-404d-b8fa-860e6ebdffbf/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-14 02:42:08,858 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_da71d4ab-fde8-404d-b8fa-860e6ebdffbf/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2024-11-14 02:42:08,919 INFO L227 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2024-11-14 02:42:08,920 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-14 02:42:08,922 INFO L255 TraceCheckSpWp]: Trace formula consists of 72 conjuncts, 13 conjuncts are in the unsatisfiable core [2024-11-14 02:42:08,924 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-14 02:42:09,033 INFO L134 CoverageAnalysis]: Checked inductivity of 10 backedges. 0 proven. 10 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-14 02:42:09,034 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-14 02:42:09,617 INFO L134 CoverageAnalysis]: Checked inductivity of 10 backedges. 0 proven. 10 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-14 02:42:09,617 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [51017450] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-14 02:42:09,617 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [617631027] [2024-11-14 02:42:09,619 INFO L159 IcfgInterpreter]: Started Sifa with 10 locations of interest [2024-11-14 02:42:09,623 INFO L166 IcfgInterpreter]: Building call graph [2024-11-14 02:42:09,624 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2024-11-14 02:42:09,624 INFO L176 IcfgInterpreter]: Starting interpretation [2024-11-14 02:42:09,624 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2024-11-14 02:42:09,841 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 29 for LOIs [2024-11-14 02:42:09,878 INFO L180 IcfgInterpreter]: Interpretation finished [2024-11-14 02:42:10,535 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '766#(and (<= 1 |#StackHeapBarrier|) (= |__VERIFIER_assert_#in~cond| 0) (exists ((|v_ULTIMATE.start_main1_~g~0#1_BEFORE_CALL_3| Int)) (and (<= |v_ULTIMATE.start_main1_~g~0#1_BEFORE_CALL_3| 2147483647) (<= 0 (+ |v_ULTIMATE.start_main1_~g~0#1_BEFORE_CALL_3| 2147483648)) (not (= (mod 63 |v_ULTIMATE.start_main1_~g~0#1_BEFORE_CALL_3|) 0)))))' at error location [2024-11-14 02:42:10,535 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2024-11-14 02:42:10,536 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-14 02:42:10,536 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7, 7] total 17 [2024-11-14 02:42:10,537 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [875435195] [2024-11-14 02:42:10,537 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-14 02:42:10,537 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 17 states [2024-11-14 02:42:10,537 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 02:42:10,539 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2024-11-14 02:42:10,540 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=100, Invalid=452, Unknown=0, NotChecked=0, Total=552 [2024-11-14 02:42:10,541 INFO L87 Difference]: Start difference. First operand 34 states and 40 transitions. Second operand has 17 states, 17 states have (on average 1.5294117647058822) internal successors, (26), 17 states have internal predecessors, (26), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-14 02:42:10,933 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 02:42:10,934 INFO L93 Difference]: Finished difference Result 49 states and 61 transitions. [2024-11-14 02:42:10,934 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2024-11-14 02:42:10,934 INFO L78 Accepts]: Start accepts. Automaton has has 17 states, 17 states have (on average 1.5294117647058822) internal successors, (26), 17 states have internal predecessors, (26), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 13 [2024-11-14 02:42:10,934 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 02:42:10,936 INFO L225 Difference]: With dead ends: 49 [2024-11-14 02:42:10,936 INFO L226 Difference]: Without dead ends: 39 [2024-11-14 02:42:10,938 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 49 GetRequests, 22 SyntacticMatches, 0 SemanticMatches, 27 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 208 ImplicationChecksByTransitivity, 1.2s TimeCoverageRelationStatistics Valid=157, Invalid=655, Unknown=0, NotChecked=0, Total=812 [2024-11-14 02:42:10,939 INFO L432 NwaCegarLoop]: 28 mSDtfsCounter, 0 mSDsluCounter, 243 mSDsCounter, 0 mSdLazyCounter, 110 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 271 SdHoareTripleChecker+Invalid, 111 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 110 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-14 02:42:10,939 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 271 Invalid, 111 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 110 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-14 02:42:10,940 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 39 states. [2024-11-14 02:42:10,947 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 39 to 39. [2024-11-14 02:42:10,950 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 39 states, 25 states have (on average 1.16) internal successors, (29), 27 states have internal predecessors, (29), 9 states have call successors, (9), 3 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 02:42:10,951 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 39 states to 39 states and 46 transitions. [2024-11-14 02:42:10,953 INFO L78 Accepts]: Start accepts. Automaton has 39 states and 46 transitions. Word has length 13 [2024-11-14 02:42:10,953 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 02:42:10,954 INFO L471 AbstractCegarLoop]: Abstraction has 39 states and 46 transitions. [2024-11-14 02:42:10,954 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 17 states, 17 states have (on average 1.5294117647058822) internal successors, (26), 17 states have internal predecessors, (26), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-14 02:42:10,954 INFO L276 IsEmpty]: Start isEmpty. Operand 39 states and 46 transitions. [2024-11-14 02:42:10,955 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 15 [2024-11-14 02:42:10,955 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 02:42:10,956 INFO L215 NwaCegarLoop]: trace histogram [5, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-14 02:42:10,977 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_da71d4ab-fde8-404d-b8fa-860e6ebdffbf/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Ended with exit code 0 [2024-11-14 02:42:11,159 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,4 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_da71d4ab-fde8-404d-b8fa-860e6ebdffbf/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 02:42:11,160 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 02:42:11,160 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 02:42:11,160 INFO L85 PathProgramCache]: Analyzing trace with hash -959246260, now seen corresponding path program 4 times [2024-11-14 02:42:11,160 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 02:42:11,160 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1845906263] [2024-11-14 02:42:11,161 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 02:42:11,161 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 02:42:11,188 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-14 02:42:11,192 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1435101373] [2024-11-14 02:42:11,192 INFO L93 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2024-11-14 02:42:11,192 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 02:42:11,193 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_da71d4ab-fde8-404d-b8fa-860e6ebdffbf/bin/utaipan-verify-sOmjnqqW8E/z3 [2024-11-14 02:42:11,197 INFO L229 MonitoredProcess]: Starting monitored process 5 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_da71d4ab-fde8-404d-b8fa-860e6ebdffbf/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-14 02:42:11,199 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_da71d4ab-fde8-404d-b8fa-860e6ebdffbf/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2024-11-14 02:42:11,258 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 02:42:11,260 INFO L255 TraceCheckSpWp]: Trace formula consists of 74 conjuncts, 24 conjuncts are in the unsatisfiable core [2024-11-14 02:42:11,262 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-14 02:42:11,477 INFO L134 CoverageAnalysis]: Checked inductivity of 15 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-14 02:42:11,478 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-14 02:42:27,404 WARN L286 SmtUtils]: Spent 6.97s on a formula simplification that was a NOOP. DAG size: 140 (called from [L 388] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2024-11-14 02:42:31,267 INFO L134 CoverageAnalysis]: Checked inductivity of 15 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-14 02:42:31,267 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 02:42:31,268 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1845906263] [2024-11-14 02:42:31,268 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-14 02:42:31,268 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1435101373] [2024-11-14 02:42:31,268 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1435101373] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-14 02:42:31,268 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1527530002] [2024-11-14 02:42:31,270 INFO L159 IcfgInterpreter]: Started Sifa with 10 locations of interest [2024-11-14 02:42:31,270 INFO L166 IcfgInterpreter]: Building call graph [2024-11-14 02:42:31,270 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2024-11-14 02:42:31,270 INFO L176 IcfgInterpreter]: Starting interpretation [2024-11-14 02:42:31,270 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2024-11-14 02:42:31,419 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 29 for LOIs [2024-11-14 02:42:31,441 INFO L180 IcfgInterpreter]: Interpretation finished [2024-11-14 02:42:32,039 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '1026#(and (<= 1 |#StackHeapBarrier|) (exists ((|v_ULTIMATE.start_main1_~g~0#1_BEFORE_CALL_5| Int)) (and (<= 0 (+ |v_ULTIMATE.start_main1_~g~0#1_BEFORE_CALL_5| 2147483648)) (<= |v_ULTIMATE.start_main1_~g~0#1_BEFORE_CALL_5| 2147483647) (not (= (mod 63 |v_ULTIMATE.start_main1_~g~0#1_BEFORE_CALL_5|) 0)))) (= |__VERIFIER_assert_#in~cond| 0))' at error location [2024-11-14 02:42:32,039 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2024-11-14 02:42:32,039 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-14 02:42:32,040 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 12] total 22 [2024-11-14 02:42:32,040 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [723088186] [2024-11-14 02:42:32,040 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-14 02:42:32,040 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 22 states [2024-11-14 02:42:32,040 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 02:42:32,041 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 22 interpolants. [2024-11-14 02:42:32,041 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=106, Invalid=705, Unknown=1, NotChecked=0, Total=812 [2024-11-14 02:42:32,041 INFO L87 Difference]: Start difference. First operand 39 states and 46 transitions. Second operand has 22 states, 20 states have (on average 1.2) internal successors, (24), 20 states have internal predecessors, (24), 2 states have call successors, (2), 2 states have call predecessors, (2), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-14 02:42:32,397 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 02:42:32,397 INFO L93 Difference]: Finished difference Result 53 states and 61 transitions. [2024-11-14 02:42:32,398 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2024-11-14 02:42:32,398 INFO L78 Accepts]: Start accepts. Automaton has has 22 states, 20 states have (on average 1.2) internal successors, (24), 20 states have internal predecessors, (24), 2 states have call successors, (2), 2 states have call predecessors, (2), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 14 [2024-11-14 02:42:32,398 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 02:42:32,398 INFO L225 Difference]: With dead ends: 53 [2024-11-14 02:42:32,398 INFO L226 Difference]: Without dead ends: 36 [2024-11-14 02:42:32,399 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 41 GetRequests, 13 SyntacticMatches, 0 SemanticMatches, 28 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 119 ImplicationChecksByTransitivity, 12.4s TimeCoverageRelationStatistics Valid=112, Invalid=757, Unknown=1, NotChecked=0, Total=870 [2024-11-14 02:42:32,400 INFO L432 NwaCegarLoop]: 24 mSDtfsCounter, 6 mSDsluCounter, 229 mSDsCounter, 0 mSdLazyCounter, 174 mSolverCounterSat, 5 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 8 SdHoareTripleChecker+Valid, 253 SdHoareTripleChecker+Invalid, 179 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 5 IncrementalHoareTripleChecker+Valid, 174 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2024-11-14 02:42:32,400 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [8 Valid, 253 Invalid, 179 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [5 Valid, 174 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2024-11-14 02:42:32,400 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 36 states. [2024-11-14 02:42:32,404 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 36 to 36. [2024-11-14 02:42:32,405 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 36 states, 23 states have (on average 1.0434782608695652) internal successors, (24), 24 states have internal predecessors, (24), 8 states have call successors, (8), 4 states have call predecessors, (8), 3 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2024-11-14 02:42:32,405 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 36 states to 36 states and 39 transitions. [2024-11-14 02:42:32,406 INFO L78 Accepts]: Start accepts. Automaton has 36 states and 39 transitions. Word has length 14 [2024-11-14 02:42:32,406 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 02:42:32,406 INFO L471 AbstractCegarLoop]: Abstraction has 36 states and 39 transitions. [2024-11-14 02:42:32,406 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 22 states, 20 states have (on average 1.2) internal successors, (24), 20 states have internal predecessors, (24), 2 states have call successors, (2), 2 states have call predecessors, (2), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-14 02:42:32,406 INFO L276 IsEmpty]: Start isEmpty. Operand 36 states and 39 transitions. [2024-11-14 02:42:32,407 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 20 [2024-11-14 02:42:32,407 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 02:42:32,407 INFO L215 NwaCegarLoop]: trace histogram [5, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-14 02:42:32,427 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_da71d4ab-fde8-404d-b8fa-860e6ebdffbf/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Ended with exit code 0 [2024-11-14 02:42:32,610 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,5 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_da71d4ab-fde8-404d-b8fa-860e6ebdffbf/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 02:42:32,611 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 02:42:32,611 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 02:42:32,612 INFO L85 PathProgramCache]: Analyzing trace with hash 1792237802, now seen corresponding path program 1 times [2024-11-14 02:42:32,612 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 02:42:32,612 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [266776713] [2024-11-14 02:42:32,612 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 02:42:32,612 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 02:42:32,630 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-14 02:42:32,634 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [615888495] [2024-11-14 02:42:32,635 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 02:42:32,635 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 02:42:32,635 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_da71d4ab-fde8-404d-b8fa-860e6ebdffbf/bin/utaipan-verify-sOmjnqqW8E/z3 [2024-11-14 02:42:32,637 INFO L229 MonitoredProcess]: Starting monitored process 6 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_da71d4ab-fde8-404d-b8fa-860e6ebdffbf/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-14 02:42:32,638 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_da71d4ab-fde8-404d-b8fa-860e6ebdffbf/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2024-11-14 02:42:32,695 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 02:42:32,696 INFO L255 TraceCheckSpWp]: Trace formula consists of 83 conjuncts, 24 conjuncts are in the unsatisfiable core [2024-11-14 02:42:32,698 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-14 02:42:32,865 INFO L134 CoverageAnalysis]: Checked inductivity of 17 backedges. 2 proven. 15 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-14 02:42:32,866 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-14 02:42:45,133 INFO L134 CoverageAnalysis]: Checked inductivity of 17 backedges. 2 proven. 15 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-14 02:42:45,133 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 02:42:45,133 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [266776713] [2024-11-14 02:42:45,133 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-14 02:42:45,133 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [615888495] [2024-11-14 02:42:45,133 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [615888495] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-14 02:42:45,134 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [783942535] [2024-11-14 02:42:45,136 INFO L159 IcfgInterpreter]: Started Sifa with 13 locations of interest [2024-11-14 02:42:45,137 INFO L166 IcfgInterpreter]: Building call graph [2024-11-14 02:42:45,138 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2024-11-14 02:42:45,138 INFO L176 IcfgInterpreter]: Starting interpretation [2024-11-14 02:42:45,139 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2024-11-14 02:42:45,404 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 73 for LOIs [2024-11-14 02:42:45,552 INFO L180 IcfgInterpreter]: Interpretation finished [2024-11-14 02:42:46,977 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '1307#(and (<= 1 |#StackHeapBarrier|) (= |__VERIFIER_assert_#in~cond| 0) (or (exists ((|v_ULTIMATE.start_main1_~g~0#1_BEFORE_CALL_12| Int)) (and (<= 0 (+ |v_ULTIMATE.start_main1_~g~0#1_BEFORE_CALL_12| 2147483648)) (not (= (mod 63 |v_ULTIMATE.start_main1_~g~0#1_BEFORE_CALL_12|) 0)) (<= |v_ULTIMATE.start_main1_~g~0#1_BEFORE_CALL_12| 2147483647))) (exists ((|v_ULTIMATE.start_main1_~g~0#1_BEFORE_CALL_11| Int)) (and (not (= (mod 18 |v_ULTIMATE.start_main1_~g~0#1_BEFORE_CALL_11|) 0)) (or (exists ((|v___VERIFIER_assert_#in~cond_AFTER_CALL_8| Int)) (and (= (mod 63 |v_ULTIMATE.start_main1_~g~0#1_BEFORE_CALL_11|) 0) (= |v___VERIFIER_assert_#in~cond_AFTER_CALL_8| 1))) (exists ((|v___VERIFIER_assert_#in~cond_AFTER_CALL_7| Int)) (and (= (mod 63 |v_ULTIMATE.start_main1_~g~0#1_BEFORE_CALL_11|) 0) (= |v___VERIFIER_assert_#in~cond_AFTER_CALL_7| 1))))))))' at error location [2024-11-14 02:42:46,978 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2024-11-14 02:42:46,978 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-14 02:42:46,978 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 12] total 22 [2024-11-14 02:42:46,978 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [428258221] [2024-11-14 02:42:46,978 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-14 02:42:46,978 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 22 states [2024-11-14 02:42:46,979 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 02:42:46,979 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 22 interpolants. [2024-11-14 02:42:46,980 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=114, Invalid=814, Unknown=2, NotChecked=0, Total=930 [2024-11-14 02:42:46,980 INFO L87 Difference]: Start difference. First operand 36 states and 39 transitions. Second operand has 22 states, 20 states have (on average 1.35) internal successors, (27), 20 states have internal predecessors, (27), 2 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2024-11-14 02:42:47,279 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 02:42:47,282 INFO L93 Difference]: Finished difference Result 36 states and 39 transitions. [2024-11-14 02:42:47,282 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2024-11-14 02:42:47,283 INFO L78 Accepts]: Start accepts. Automaton has has 22 states, 20 states have (on average 1.35) internal successors, (27), 20 states have internal predecessors, (27), 2 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) Word has length 19 [2024-11-14 02:42:47,283 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 02:42:47,283 INFO L225 Difference]: With dead ends: 36 [2024-11-14 02:42:47,283 INFO L226 Difference]: Without dead ends: 18 [2024-11-14 02:42:47,284 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 56 GetRequests, 26 SyntacticMatches, 0 SemanticMatches, 30 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 147 ImplicationChecksByTransitivity, 8.0s TimeCoverageRelationStatistics Valid=120, Invalid=870, Unknown=2, NotChecked=0, Total=992 [2024-11-14 02:42:47,285 INFO L432 NwaCegarLoop]: 23 mSDtfsCounter, 2 mSDsluCounter, 304 mSDsCounter, 0 mSdLazyCounter, 193 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 327 SdHoareTripleChecker+Invalid, 193 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 193 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2024-11-14 02:42:47,285 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [2 Valid, 327 Invalid, 193 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 193 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2024-11-14 02:42:47,290 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 18 states. [2024-11-14 02:42:47,291 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 18 to 18. [2024-11-14 02:42:47,292 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 18 states, 9 states have (on average 1.0) internal successors, (9), 9 states have internal predecessors, (9), 6 states have call successors, (6), 2 states have call predecessors, (6), 2 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2024-11-14 02:42:47,292 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 18 states to 18 states and 21 transitions. [2024-11-14 02:42:47,293 INFO L78 Accepts]: Start accepts. Automaton has 18 states and 21 transitions. Word has length 19 [2024-11-14 02:42:47,293 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 02:42:47,293 INFO L471 AbstractCegarLoop]: Abstraction has 18 states and 21 transitions. [2024-11-14 02:42:47,293 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 22 states, 20 states have (on average 1.35) internal successors, (27), 20 states have internal predecessors, (27), 2 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2024-11-14 02:42:47,293 INFO L276 IsEmpty]: Start isEmpty. Operand 18 states and 21 transitions. [2024-11-14 02:42:47,294 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 26 [2024-11-14 02:42:47,294 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 02:42:47,294 INFO L215 NwaCegarLoop]: trace histogram [3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-14 02:42:47,309 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_da71d4ab-fde8-404d-b8fa-860e6ebdffbf/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Ended with exit code 0 [2024-11-14 02:42:47,495 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,6 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_da71d4ab-fde8-404d-b8fa-860e6ebdffbf/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 02:42:47,496 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 02:42:47,496 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 02:42:47,496 INFO L85 PathProgramCache]: Analyzing trace with hash 1817903574, now seen corresponding path program 1 times [2024-11-14 02:42:47,496 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 02:42:47,496 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1337210368] [2024-11-14 02:42:47,496 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 02:42:47,496 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 02:42:47,508 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-14 02:42:47,509 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-14 02:42:47,518 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-14 02:42:47,535 INFO L130 FreeRefinementEngine]: Strategy SIFA_TAIPAN found a feasible trace [2024-11-14 02:42:47,536 INFO L325 BasicCegarLoop]: Counterexample is feasible [2024-11-14 02:42:47,537 INFO L782 garLoopResultBuilder]: Registering result UNSAFE for location ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION (1 of 2 remaining) [2024-11-14 02:42:47,539 INFO L782 garLoopResultBuilder]: Registering result UNKNOWN for location __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION (0 of 2 remaining) [2024-11-14 02:42:47,539 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7 [2024-11-14 02:42:47,542 INFO L407 BasicCegarLoop]: Path program histogram: [4, 1, 1, 1, 1] [2024-11-14 02:42:47,559 INFO L173 ceAbstractionStarter]: Computing trace abstraction results [2024-11-14 02:42:47,563 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 14.11 02:42:47 BoogieIcfgContainer [2024-11-14 02:42:47,563 INFO L131 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2024-11-14 02:42:47,564 INFO L112 PluginConnector]: ------------------------Witness Printer---------------------------- [2024-11-14 02:42:47,564 INFO L270 PluginConnector]: Initializing Witness Printer... [2024-11-14 02:42:47,564 INFO L274 PluginConnector]: Witness Printer initialized [2024-11-14 02:42:47,565 INFO L184 PluginConnector]: Executing the observer RCFGCatcher from plugin Witness Printer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 14.11 02:42:03" (3/4) ... [2024-11-14 02:42:47,567 INFO L145 WitnessPrinter]: No result that supports witness generation found [2024-11-14 02:42:47,568 INFO L131 PluginConnector]: ------------------------ END Witness Printer---------------------------- [2024-11-14 02:42:47,569 INFO L158 Benchmark]: Toolchain (without parser) took 45118.95ms. Allocated memory was 117.4MB in the beginning and 234.9MB in the end (delta: 117.4MB). Free memory was 92.4MB in the beginning and 164.0MB in the end (delta: -71.5MB). Peak memory consumption was 48.1MB. Max. memory is 16.1GB. [2024-11-14 02:42:47,569 INFO L158 Benchmark]: CDTParser took 1.20ms. Allocated memory is still 117.4MB. Free memory is still 74.2MB. There was no memory consumed. Max. memory is 16.1GB. [2024-11-14 02:42:47,569 INFO L158 Benchmark]: CACSL2BoogieTranslator took 321.97ms. Allocated memory is still 117.4MB. Free memory was 92.2MB in the beginning and 80.5MB in the end (delta: 11.7MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. [2024-11-14 02:42:47,570 INFO L158 Benchmark]: Boogie Procedure Inliner took 41.80ms. Allocated memory is still 117.4MB. Free memory was 80.5MB in the beginning and 79.1MB in the end (delta: 1.4MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. [2024-11-14 02:42:47,570 INFO L158 Benchmark]: Boogie Preprocessor took 27.33ms. Allocated memory is still 117.4MB. Free memory was 79.1MB in the beginning and 77.9MB in the end (delta: 1.1MB). There was no memory consumed. Max. memory is 16.1GB. [2024-11-14 02:42:47,570 INFO L158 Benchmark]: RCFGBuilder took 510.11ms. Allocated memory is still 117.4MB. Free memory was 77.9MB in the beginning and 61.5MB in the end (delta: 16.4MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. [2024-11-14 02:42:47,571 INFO L158 Benchmark]: TraceAbstraction took 44205.97ms. Allocated memory was 117.4MB in the beginning and 234.9MB in the end (delta: 117.4MB). Free memory was 61.0MB in the beginning and 164.0MB in the end (delta: -103.0MB). Peak memory consumption was 22.9MB. Max. memory is 16.1GB. [2024-11-14 02:42:47,571 INFO L158 Benchmark]: Witness Printer took 4.34ms. Allocated memory is still 234.9MB. Free memory was 164.0MB in the beginning and 164.0MB in the end (delta: 21.6kB). There was no memory consumed. Max. memory is 16.1GB. [2024-11-14 02:42:47,573 INFO L338 ainManager$Toolchain]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * CDTParser took 1.20ms. Allocated memory is still 117.4MB. Free memory is still 74.2MB. There was no memory consumed. Max. memory is 16.1GB. * CACSL2BoogieTranslator took 321.97ms. Allocated memory is still 117.4MB. Free memory was 92.2MB in the beginning and 80.5MB in the end (delta: 11.7MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. * Boogie Procedure Inliner took 41.80ms. Allocated memory is still 117.4MB. Free memory was 80.5MB in the beginning and 79.1MB in the end (delta: 1.4MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. * Boogie Preprocessor took 27.33ms. Allocated memory is still 117.4MB. Free memory was 79.1MB in the beginning and 77.9MB in the end (delta: 1.1MB). There was no memory consumed. Max. memory is 16.1GB. * RCFGBuilder took 510.11ms. Allocated memory is still 117.4MB. Free memory was 77.9MB in the beginning and 61.5MB in the end (delta: 16.4MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. * TraceAbstraction took 44205.97ms. Allocated memory was 117.4MB in the beginning and 234.9MB in the end (delta: 117.4MB). Free memory was 61.0MB in the beginning and 164.0MB in the end (delta: -103.0MB). Peak memory consumption was 22.9MB. Max. memory is 16.1GB. * Witness Printer took 4.34ms. Allocated memory is still 234.9MB. Free memory was 164.0MB in the beginning and 164.0MB in the end (delta: 21.6kB). 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 - UnprovableResult [Line: 109]: Unable to prove that a call to reach_error is unreachable Unable to prove that a call to reach_error is unreachable Reason: overapproximation of someBinaryFLOATComparisonOperation at line 98, overapproximation of someBinaryDOUBLEComparisonOperation at line 108, overapproximation of someBinaryArithmeticFLOAToperation at line 102, overapproximation of someBinaryArithmeticFLOAToperation at line 104, overapproximation of someBinaryArithmeticFLOAToperation at line 87, overapproximation of someBinaryArithmeticFLOAToperation at line 92, overapproximation of someBinaryArithmeticFLOAToperation at line 100. Possible FailurePath: [L115] COND FALSE !(__VERIFIER_nondet_int()) [L118] CALL main2() [L97] float IN = __VERIFIER_nondet_float(); [L98] CALL assume_abort_if_not(IN > -1.4f && IN < 1.4f) [L82] COND FALSE !(!cond) [L98] RET assume_abort_if_not(IN > -1.4f && IN < 1.4f) [L100] CALL, EXPR f(IN) VAL [\old(x)=109] [L87] return x - (x*x*x)/6.0f + (x*x*x*x*x)/120.0f + (x*x*x*x*x*x*x)/5040.0f; [L100] RET, EXPR f(IN) VAL [IN=109] [L100] CALL, EXPR fp(IN) VAL [\old(x)=109] [L92] return 1 - (x*x)/2.0f + (x*x*x*x)/24.0f + (x*x*x*x*x*x)/720.0f; [L100] RET, EXPR fp(IN) VAL [IN=109] [L100] float x = IN - f(IN)/fp(IN); [L102] CALL, EXPR f(x) VAL [\old(x)=110] [L87] return x - (x*x*x)/6.0f + (x*x*x*x*x)/120.0f + (x*x*x*x*x*x*x)/5040.0f; [L102] RET, EXPR f(x) VAL [IN=109, x=110] [L102] CALL, EXPR fp(x) VAL [\old(x)=110] [L92] return 1 - (x*x)/2.0f + (x*x*x*x)/24.0f + (x*x*x*x*x*x)/720.0f; [L102] RET, EXPR fp(x) VAL [IN=109, x=110] [L102] x = x - f(x)/fp(x) [L104] CALL, EXPR f(x) VAL [\old(x)=111] [L87] return x - (x*x*x)/6.0f + (x*x*x*x*x)/120.0f + (x*x*x*x*x*x*x)/5040.0f; [L104] RET, EXPR f(x) VAL [IN=109, x=111] [L104] CALL, EXPR fp(x) VAL [\old(x)=111] [L92] return 1 - (x*x)/2.0f + (x*x*x*x)/24.0f + (x*x*x*x*x*x)/720.0f; [L104] RET, EXPR fp(x) VAL [IN=109, x=111] [L104] x = x - f(x)/fp(x) [L108] COND TRUE !(x < 0.1) VAL [IN=109] [L109] reach_error() VAL [IN=109] - UnprovableResult [Line: 27]: Unable to prove that a call to reach_error is unreachable Unable to prove that a call to reach_error is unreachable Reason: Not analyzed. - StatisticsResult: Ultimate Automizer benchmark data CFG has 4 procedures, 34 locations, 2 error locations. Started 1 CEGAR loops. OverallTime: 44.1s, OverallIterations: 8, TraceHistogramMax: 5, PathProgramHistogramMax: 4, EmptinessCheckTime: 0.0s, AutomataDifference: 1.4s, DeadEndRemovalTime: 0.0s, HoareAnnotationTime: 0.0s, InitialAbstractionConstructionTime: 0.0s, HoareTripleCheckerStatistics: 0 mSolverCounterUnknown, 11 SdHoareTripleChecker+Valid, 0.8s IncrementalHoareTripleChecker+Time, 0 mSdLazyCounter, 9 mSDsluCounter, 1184 SdHoareTripleChecker+Invalid, 0.7s Time, 0 mProtectedAction, 0 SdHoareTripleChecker+Unchecked, 0 IncrementalHoareTripleChecker+Unchecked, 994 mSDsCounter, 7 IncrementalHoareTripleChecker+Valid, 0 mProtectedPredicate, 575 IncrementalHoareTripleChecker+Invalid, 582 SdHoareTripleChecker+Unknown, 0 mSolverCounterNotChecked, 7 mSolverCounterUnsat, 190 mSDtfsCounter, 575 mSolverCounterSat, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Unknown, PredicateUnifierStatistics: 0 DeclaredPredicates, 227 GetRequests, 105 SyntacticMatches, 0 SemanticMatches, 122 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 720 ImplicationChecksByTransitivity, 23.3s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=39occurred in iteration=5, InterpolantAutomatonStates: 52, 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, 7 MinimizatonAttempts, 1 StatesRemovedByMinimization, 1 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TRACE_CHECK: 0.0s SsaConstructionTime, 0.3s SatisfiabilityAnalysisTime, 34.9s InterpolantComputationTime, 178 NumberOfCodeBlocks, 178 NumberOfCodeBlocksAsserted, 16 NumberOfCheckSat, 173 ConstructedInterpolants, 0 QuantifiedInterpolants, 3105 SizeOfPredicates, 13 NumberOfNonLiveVariables, 365 ConjunctsInSsa, 81 ConjunctsInUnsatCore, 15 InterpolantComputations, 2 PerfectInterpolantSequences, 4/115 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 RESULT: Ultimate could not prove your program: unable to determine feasibility of some traces [2024-11-14 02:42:47,628 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_da71d4ab-fde8-404d-b8fa-860e6ebdffbf/bin/utaipan-verify-sOmjnqqW8E/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Ended with exit code 0 Received shutdown request... --- End real Ultimate output --- Execution finished normally Using bit-precise analysis Retrying with bit-precise analysis ### Bit-precise run ### Calling Ultimate with: /usr/bin/java -Dosgi.configuration.area=/tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_da71d4ab-fde8-404d-b8fa-860e6ebdffbf/bin/utaipan-verify-sOmjnqqW8E/data/config -Xmx15G -Xms4m -jar /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_da71d4ab-fde8-404d-b8fa-860e6ebdffbf/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_da71d4ab-fde8-404d-b8fa-860e6ebdffbf/bin/utaipan-verify-sOmjnqqW8E/data -tc /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_da71d4ab-fde8-404d-b8fa-860e6ebdffbf/bin/utaipan-verify-sOmjnqqW8E/config/TaipanReach.xml -i ../../sv-benchmarks/c/combinations/gcd_4+newton_3_7.i -s /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_da71d4ab-fde8-404d-b8fa-860e6ebdffbf/bin/utaipan-verify-sOmjnqqW8E/config/svcomp-Reach-32bit-Taipan_Bitvector.epf --cacsl2boogietranslator.entry.function main --witnessprinter.witness.directory /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_da71d4ab-fde8-404d-b8fa-860e6ebdffbf/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 87bc0d62bd0ac2c8f0b3bcd924815b04302ef88419a4b535524b284cb471b329 --- Real Ultimate output --- This is Ultimate 0.3.0-dev-826ab2b [2024-11-14 02:42:50,520 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-11-14 02:42:50,648 INFO L114 SettingsManager]: Loading settings from /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_da71d4ab-fde8-404d-b8fa-860e6ebdffbf/bin/utaipan-verify-sOmjnqqW8E/config/svcomp-Reach-32bit-Taipan_Bitvector.epf [2024-11-14 02:42:50,658 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-11-14 02:42:50,659 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-11-14 02:42:50,695 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-11-14 02:42:50,699 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-11-14 02:42:50,699 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-11-14 02:42:50,699 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2024-11-14 02:42:50,700 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2024-11-14 02:42:50,700 INFO L153 SettingsManager]: * User list type=DISABLED [2024-11-14 02:42:50,700 INFO L151 SettingsManager]: Preferences of Abstract Interpretation differ from their defaults: [2024-11-14 02:42:50,700 INFO L153 SettingsManager]: * Explicit value domain=true [2024-11-14 02:42:50,700 INFO L153 SettingsManager]: * Octagon Domain=false [2024-11-14 02:42:50,700 INFO L153 SettingsManager]: * Abstract domain=CompoundDomain [2024-11-14 02:42:50,700 INFO L153 SettingsManager]: * Interval Domain=false [2024-11-14 02:42:50,701 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-11-14 02:42:50,701 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2024-11-14 02:42:50,703 INFO L153 SettingsManager]: * sizeof long=4 [2024-11-14 02:42:50,703 INFO L153 SettingsManager]: * sizeof POINTER=4 [2024-11-14 02:42:50,703 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-11-14 02:42:50,703 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2024-11-14 02:42:50,704 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2024-11-14 02:42:50,704 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2024-11-14 02:42:50,704 INFO L153 SettingsManager]: * Adapt memory model on pointer casts if necessary=true [2024-11-14 02:42:50,704 INFO L153 SettingsManager]: * Use bitvectors instead of ints=true [2024-11-14 02:42:50,704 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-11-14 02:42:50,704 INFO L153 SettingsManager]: * Memory model=HoenickeLindenmann_4ByteResolution [2024-11-14 02:42:50,704 INFO L153 SettingsManager]: * sizeof long double=12 [2024-11-14 02:42:50,704 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-11-14 02:42:50,705 INFO L153 SettingsManager]: * Use constant arrays=true [2024-11-14 02:42:50,705 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2024-11-14 02:42:50,705 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2024-11-14 02:42:50,705 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2024-11-14 02:42:50,705 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2024-11-14 02:42:50,706 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2024-11-14 02:42:50,707 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-11-14 02:42:50,707 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2024-11-14 02:42:50,707 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2024-11-14 02:42:50,707 INFO L153 SettingsManager]: * Trace refinement strategy=WALRUS [2024-11-14 02:42:50,707 INFO L153 SettingsManager]: * Command for external solver=cvc4 --incremental --print-success --lang smt [2024-11-14 02:42:50,707 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2024-11-14 02:42:50,708 INFO L153 SettingsManager]: * Trace refinement exception blacklist=NONE [2024-11-14 02:42:50,708 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode 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_da71d4ab-fde8-404d-b8fa-860e6ebdffbf/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 -> 87bc0d62bd0ac2c8f0b3bcd924815b04302ef88419a4b535524b284cb471b329 [2024-11-14 02:42:51,018 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-11-14 02:42:51,030 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-11-14 02:42:51,034 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-11-14 02:42:51,036 INFO L270 PluginConnector]: Initializing CDTParser... [2024-11-14 02:42:51,037 INFO L274 PluginConnector]: CDTParser initialized [2024-11-14 02:42:51,040 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_da71d4ab-fde8-404d-b8fa-860e6ebdffbf/bin/utaipan-verify-sOmjnqqW8E/../../sv-benchmarks/c/combinations/gcd_4+newton_3_7.i Unable to find full path for "g++" [2024-11-14 02:42:53,190 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-11-14 02:42:53,432 INFO L384 CDTParser]: Found 1 translation units. [2024-11-14 02:42:53,433 INFO L180 CDTParser]: Scanning /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_da71d4ab-fde8-404d-b8fa-860e6ebdffbf/sv-benchmarks/c/combinations/gcd_4+newton_3_7.i [2024-11-14 02:42:53,446 INFO L427 CDTParser]: About to delete temporary CDT project at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_da71d4ab-fde8-404d-b8fa-860e6ebdffbf/bin/utaipan-verify-sOmjnqqW8E/data/b4e6917c7/61b9c7595ce04740ae5162773a6f4ff5/FLAG595b8a808 [2024-11-14 02:42:53,466 INFO L435 CDTParser]: Successfully deleted /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_da71d4ab-fde8-404d-b8fa-860e6ebdffbf/bin/utaipan-verify-sOmjnqqW8E/data/b4e6917c7/61b9c7595ce04740ae5162773a6f4ff5 [2024-11-14 02:42:53,472 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-11-14 02:42:53,474 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2024-11-14 02:42:53,476 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-11-14 02:42:53,476 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-11-14 02:42:53,480 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-11-14 02:42:53,481 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 14.11 02:42:53" (1/1) ... [2024-11-14 02:42:53,482 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@6dc32769 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 02:42:53, skipping insertion in model container [2024-11-14 02:42:53,485 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 14.11 02:42:53" (1/1) ... [2024-11-14 02:42:53,503 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-11-14 02:42:53,672 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_da71d4ab-fde8-404d-b8fa-860e6ebdffbf/sv-benchmarks/c/combinations/gcd_4+newton_3_7.i[1224,1237] [2024-11-14 02:42:53,719 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_da71d4ab-fde8-404d-b8fa-860e6ebdffbf/sv-benchmarks/c/combinations/gcd_4+newton_3_7.i[2848,2861] [2024-11-14 02:42:53,720 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-14 02:42:53,747 INFO L200 MainTranslator]: Completed pre-run [2024-11-14 02:42:53,765 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_da71d4ab-fde8-404d-b8fa-860e6ebdffbf/sv-benchmarks/c/combinations/gcd_4+newton_3_7.i[1224,1237] [2024-11-14 02:42:53,788 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_da71d4ab-fde8-404d-b8fa-860e6ebdffbf/sv-benchmarks/c/combinations/gcd_4+newton_3_7.i[2848,2861] [2024-11-14 02:42:53,793 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-14 02:42:53,812 INFO L204 MainTranslator]: Completed translation [2024-11-14 02:42:53,813 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 02:42:53 WrapperNode [2024-11-14 02:42:53,814 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-11-14 02:42:53,815 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-11-14 02:42:53,815 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-11-14 02:42:53,816 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-11-14 02:42:53,826 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 02:42:53" (1/1) ... [2024-11-14 02:42:53,844 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 02:42:53" (1/1) ... [2024-11-14 02:42:53,869 INFO L138 Inliner]: procedures = 28, calls = 28, calls flagged for inlining = 6, calls inlined = 6, statements flattened = 80 [2024-11-14 02:42:53,872 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-11-14 02:42:53,873 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-11-14 02:42:53,873 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-11-14 02:42:53,873 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-11-14 02:42:53,881 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 02:42:53" (1/1) ... [2024-11-14 02:42:53,881 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 02:42:53" (1/1) ... [2024-11-14 02:42:53,886 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 02:42:53" (1/1) ... [2024-11-14 02:42:53,887 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 02:42:53" (1/1) ... [2024-11-14 02:42:53,900 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 02:42:53" (1/1) ... [2024-11-14 02:42:53,908 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 02:42:53" (1/1) ... [2024-11-14 02:42:53,910 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 02:42:53" (1/1) ... [2024-11-14 02:42:53,911 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 02:42:53" (1/1) ... [2024-11-14 02:42:53,913 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-11-14 02:42:53,914 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2024-11-14 02:42:53,914 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2024-11-14 02:42:53,915 INFO L274 PluginConnector]: RCFGBuilder initialized [2024-11-14 02:42:53,916 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 02:42:53" (1/1) ... [2024-11-14 02:42:53,926 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2024-11-14 02:42:53,944 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_da71d4ab-fde8-404d-b8fa-860e6ebdffbf/bin/utaipan-verify-sOmjnqqW8E/z3 [2024-11-14 02:42:53,957 INFO L229 MonitoredProcess]: Starting monitored process 1 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_da71d4ab-fde8-404d-b8fa-860e6ebdffbf/bin/utaipan-verify-sOmjnqqW8E/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) [2024-11-14 02:42:53,961 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_da71d4ab-fde8-404d-b8fa-860e6ebdffbf/bin/utaipan-verify-sOmjnqqW8E/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Waiting until timeout for monitored process [2024-11-14 02:42:53,988 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2024-11-14 02:42:53,988 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~intINTTYPE1 [2024-11-14 02:42:53,988 INFO L130 BoogieDeclarations]: Found specification of procedure fp [2024-11-14 02:42:53,988 INFO L138 BoogieDeclarations]: Found implementation of procedure fp [2024-11-14 02:42:53,988 INFO L130 BoogieDeclarations]: Found specification of procedure f [2024-11-14 02:42:53,988 INFO L138 BoogieDeclarations]: Found implementation of procedure f [2024-11-14 02:42:53,989 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-11-14 02:42:53,989 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-11-14 02:42:53,989 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2024-11-14 02:42:53,989 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2024-11-14 02:42:54,085 INFO L238 CfgBuilder]: Building ICFG [2024-11-14 02:42:54,087 INFO L264 CfgBuilder]: Building CFG for each procedure with an implementation [2024-11-14 02:43:03,040 INFO L? ?]: Removed 22 outVars from TransFormulas that were not future-live. [2024-11-14 02:43:03,040 INFO L287 CfgBuilder]: Performing block encoding [2024-11-14 02:43:03,052 INFO L311 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-11-14 02:43:03,052 INFO L316 CfgBuilder]: Removed 1 assume(true) statements. [2024-11-14 02:43:03,052 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 14.11 02:43:03 BoogieIcfgContainer [2024-11-14 02:43:03,052 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2024-11-14 02:43:03,059 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2024-11-14 02:43:03,059 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2024-11-14 02:43:03,064 INFO L274 PluginConnector]: TraceAbstraction initialized [2024-11-14 02:43:03,065 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 14.11 02:42:53" (1/3) ... [2024-11-14 02:43:03,066 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@6e3675be and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 14.11 02:43:03, skipping insertion in model container [2024-11-14 02:43:03,066 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 02:42:53" (2/3) ... [2024-11-14 02:43:03,067 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@6e3675be and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 14.11 02:43:03, skipping insertion in model container [2024-11-14 02:43:03,067 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 14.11 02:43:03" (3/3) ... [2024-11-14 02:43:03,069 INFO L112 eAbstractionObserver]: Analyzing ICFG gcd_4+newton_3_7.i [2024-11-14 02:43:03,085 INFO L217 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2024-11-14 02:43:03,087 INFO L154 ceAbstractionStarter]: Applying trace abstraction to ICFG gcd_4+newton_3_7.i that has 4 procedures, 46 locations, 1 initial locations, 1 loop locations, and 2 error locations. [2024-11-14 02:43:03,156 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2024-11-14 02:43:03,172 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;@408320d6, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2024-11-14 02:43:03,174 INFO L334 AbstractCegarLoop]: Starting to check reachability of 2 error locations. [2024-11-14 02:43:03,178 INFO L276 IsEmpty]: Start isEmpty. Operand has 46 states, 31 states have (on average 1.3870967741935485) internal successors, (43), 33 states have internal predecessors, (43), 9 states have call successors, (9), 3 states have call predecessors, (9), 3 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2024-11-14 02:43:03,186 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 12 [2024-11-14 02:43:03,186 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 02:43:03,187 INFO L215 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-14 02:43:03,187 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 02:43:03,192 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 02:43:03,194 INFO L85 PathProgramCache]: Analyzing trace with hash -1781341513, now seen corresponding path program 1 times [2024-11-14 02:43:03,204 INFO L118 FreeRefinementEngine]: Executing refinement strategy WALRUS [2024-11-14 02:43:03,206 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleMathsat [1281985972] [2024-11-14 02:43:03,207 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 02:43:03,208 INFO L173 SolverBuilder]: Constructing external solver with command: mathsat -theory.fp.to_bv_overflow_mode=1 -theory.fp.minmax_zero_mode=4 -theory.bv.div_by_zero_mode=1 -unsat_core_generation=3 [2024-11-14 02:43:03,208 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_da71d4ab-fde8-404d-b8fa-860e6ebdffbf/bin/utaipan-verify-sOmjnqqW8E/mathsat [2024-11-14 02:43:03,210 INFO L229 MonitoredProcess]: Starting monitored process 2 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_da71d4ab-fde8-404d-b8fa-860e6ebdffbf/bin/utaipan-verify-sOmjnqqW8E/mathsat -theory.fp.to_bv_overflow_mode=1 -theory.fp.minmax_zero_mode=4 -theory.bv.div_by_zero_mode=1 -unsat_core_generation=3 (exit command is (exit), workingDir is null) [2024-11-14 02:43:03,214 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_da71d4ab-fde8-404d-b8fa-860e6ebdffbf/bin/utaipan-verify-sOmjnqqW8E/mathsat -theory.fp.to_bv_overflow_mode=1 -theory.fp.minmax_zero_mode=4 -theory.bv.div_by_zero_mode=1 -unsat_core_generation=3 (2)] Waiting until timeout for monitored process [2024-11-14 02:43:03,366 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 02:43:03,372 INFO L255 TraceCheckSpWp]: Trace formula consists of 42 conjuncts, 4 conjuncts are in the unsatisfiable core [2024-11-14 02:43:03,411 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-14 02:43:03,512 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-14 02:43:03,513 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-14 02:43:03,513 INFO L136 FreeRefinementEngine]: Strategy WALRUS found an infeasible trace [2024-11-14 02:43:03,514 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleMathsat [1281985972] [2024-11-14 02:43:03,514 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleMathsat [1281985972] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-14 02:43:03,514 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-14 02:43:03,514 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2024-11-14 02:43:03,516 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [588239712] [2024-11-14 02:43:03,517 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-14 02:43:03,522 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2024-11-14 02:43:03,522 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy WALRUS [2024-11-14 02:43:03,542 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2024-11-14 02:43:03,543 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2024-11-14 02:43:03,545 INFO L87 Difference]: Start difference. First operand has 46 states, 31 states have (on average 1.3870967741935485) internal successors, (43), 33 states have internal predecessors, (43), 9 states have call successors, (9), 3 states have call predecessors, (9), 3 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) Second operand has 3 states, 3 states have (on average 3.3333333333333335) internal successors, (10), 3 states have internal predecessors, (10), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-14 02:43:03,660 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 02:43:03,661 INFO L93 Difference]: Finished difference Result 90 states and 123 transitions. [2024-11-14 02:43:03,663 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2024-11-14 02:43:03,664 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 3.3333333333333335) internal successors, (10), 3 states have internal predecessors, (10), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 11 [2024-11-14 02:43:03,664 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 02:43:03,671 INFO L225 Difference]: With dead ends: 90 [2024-11-14 02:43:03,671 INFO L226 Difference]: Without dead ends: 42 [2024-11-14 02:43:03,674 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 10 GetRequests, 9 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2024-11-14 02:43:03,677 INFO L432 NwaCegarLoop]: 50 mSDtfsCounter, 7 mSDsluCounter, 46 mSDsCounter, 0 mSdLazyCounter, 9 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 7 SdHoareTripleChecker+Valid, 96 SdHoareTripleChecker+Invalid, 10 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 9 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-14 02:43:03,679 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [7 Valid, 96 Invalid, 10 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 9 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-14 02:43:03,692 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 42 states. [2024-11-14 02:43:03,708 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 42 to 39. [2024-11-14 02:43:03,710 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 39 states, 25 states have (on average 1.2) internal successors, (30), 27 states have internal predecessors, (30), 9 states have call successors, (9), 3 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 02:43:03,713 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 39 states to 39 states and 47 transitions. [2024-11-14 02:43:03,715 INFO L78 Accepts]: Start accepts. Automaton has 39 states and 47 transitions. Word has length 11 [2024-11-14 02:43:03,716 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 02:43:03,716 INFO L471 AbstractCegarLoop]: Abstraction has 39 states and 47 transitions. [2024-11-14 02:43:03,716 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 3.3333333333333335) internal successors, (10), 3 states have internal predecessors, (10), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-14 02:43:03,716 INFO L276 IsEmpty]: Start isEmpty. Operand 39 states and 47 transitions. [2024-11-14 02:43:03,717 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 14 [2024-11-14 02:43:03,718 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 02:43:03,718 INFO L215 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-14 02:43:03,724 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_da71d4ab-fde8-404d-b8fa-860e6ebdffbf/bin/utaipan-verify-sOmjnqqW8E/mathsat -theory.fp.to_bv_overflow_mode=1 -theory.fp.minmax_zero_mode=4 -theory.bv.div_by_zero_mode=1 -unsat_core_generation=3 (2)] Ended with exit code 0 [2024-11-14 02:43:03,922 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 2 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_da71d4ab-fde8-404d-b8fa-860e6ebdffbf/bin/utaipan-verify-sOmjnqqW8E/mathsat -theory.fp.to_bv_overflow_mode=1 -theory.fp.minmax_zero_mode=4 -theory.bv.div_by_zero_mode=1 -unsat_core_generation=3 [2024-11-14 02:43:03,922 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 02:43:03,923 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 02:43:03,923 INFO L85 PathProgramCache]: Analyzing trace with hash -503368345, now seen corresponding path program 1 times [2024-11-14 02:43:03,923 INFO L118 FreeRefinementEngine]: Executing refinement strategy WALRUS [2024-11-14 02:43:03,924 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleMathsat [1508770550] [2024-11-14 02:43:03,924 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 02:43:03,924 INFO L173 SolverBuilder]: Constructing external solver with command: mathsat -theory.fp.to_bv_overflow_mode=1 -theory.fp.minmax_zero_mode=4 -theory.bv.div_by_zero_mode=1 -unsat_core_generation=3 [2024-11-14 02:43:03,924 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_da71d4ab-fde8-404d-b8fa-860e6ebdffbf/bin/utaipan-verify-sOmjnqqW8E/mathsat [2024-11-14 02:43:03,928 INFO L229 MonitoredProcess]: Starting monitored process 3 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_da71d4ab-fde8-404d-b8fa-860e6ebdffbf/bin/utaipan-verify-sOmjnqqW8E/mathsat -theory.fp.to_bv_overflow_mode=1 -theory.fp.minmax_zero_mode=4 -theory.bv.div_by_zero_mode=1 -unsat_core_generation=3 (exit command is (exit), workingDir is null) [2024-11-14 02:43:03,929 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_da71d4ab-fde8-404d-b8fa-860e6ebdffbf/bin/utaipan-verify-sOmjnqqW8E/mathsat -theory.fp.to_bv_overflow_mode=1 -theory.fp.minmax_zero_mode=4 -theory.bv.div_by_zero_mode=1 -unsat_core_generation=3 (3)] Waiting until timeout for monitored process [2024-11-14 02:43:04,019 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 02:43:04,022 INFO L255 TraceCheckSpWp]: Trace formula consists of 42 conjuncts, 4 conjuncts are in the unsatisfiable core [2024-11-14 02:43:04,024 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-14 02:43:04,090 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-14 02:43:04,090 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-14 02:43:04,090 INFO L136 FreeRefinementEngine]: Strategy WALRUS found an infeasible trace [2024-11-14 02:43:04,091 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleMathsat [1508770550] [2024-11-14 02:43:04,091 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleMathsat [1508770550] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-14 02:43:04,091 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-14 02:43:04,091 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2024-11-14 02:43:04,091 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [679662020] [2024-11-14 02:43:04,091 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-14 02:43:04,092 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2024-11-14 02:43:04,093 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy WALRUS [2024-11-14 02:43:04,093 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2024-11-14 02:43:04,094 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2024-11-14 02:43:04,095 INFO L87 Difference]: Start difference. First operand 39 states and 47 transitions. Second operand has 3 states, 3 states have (on average 4.0) internal successors, (12), 3 states have internal predecessors, (12), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-14 02:43:04,216 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 02:43:04,216 INFO L93 Difference]: Finished difference Result 55 states and 68 transitions. [2024-11-14 02:43:04,216 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2024-11-14 02:43:04,217 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 4.0) internal successors, (12), 3 states have internal predecessors, (12), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 13 [2024-11-14 02:43:04,217 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 02:43:04,218 INFO L225 Difference]: With dead ends: 55 [2024-11-14 02:43:04,218 INFO L226 Difference]: Without dead ends: 41 [2024-11-14 02:43:04,218 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 12 GetRequests, 11 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2024-11-14 02:43:04,219 INFO L432 NwaCegarLoop]: 42 mSDtfsCounter, 4 mSDsluCounter, 37 mSDsCounter, 0 mSdLazyCounter, 9 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 4 SdHoareTripleChecker+Valid, 79 SdHoareTripleChecker+Invalid, 10 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 9 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-14 02:43:04,220 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [4 Valid, 79 Invalid, 10 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 9 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-14 02:43:04,221 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 41 states. [2024-11-14 02:43:04,226 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 41 to 41. [2024-11-14 02:43:04,226 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 41 states, 27 states have (on average 1.1851851851851851) internal successors, (32), 29 states have internal predecessors, (32), 9 states have call successors, (9), 3 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 02:43:04,227 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 41 states to 41 states and 49 transitions. [2024-11-14 02:43:04,228 INFO L78 Accepts]: Start accepts. Automaton has 41 states and 49 transitions. Word has length 13 [2024-11-14 02:43:04,228 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 02:43:04,228 INFO L471 AbstractCegarLoop]: Abstraction has 41 states and 49 transitions. [2024-11-14 02:43:04,228 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 4.0) internal successors, (12), 3 states have internal predecessors, (12), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-14 02:43:04,228 INFO L276 IsEmpty]: Start isEmpty. Operand 41 states and 49 transitions. [2024-11-14 02:43:04,229 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 16 [2024-11-14 02:43:04,229 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 02:43:04,229 INFO L215 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-14 02:43:04,234 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_da71d4ab-fde8-404d-b8fa-860e6ebdffbf/bin/utaipan-verify-sOmjnqqW8E/mathsat -theory.fp.to_bv_overflow_mode=1 -theory.fp.minmax_zero_mode=4 -theory.bv.div_by_zero_mode=1 -unsat_core_generation=3 (3)] Ended with exit code 0 [2024-11-14 02:43:04,430 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 3 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_da71d4ab-fde8-404d-b8fa-860e6ebdffbf/bin/utaipan-verify-sOmjnqqW8E/mathsat -theory.fp.to_bv_overflow_mode=1 -theory.fp.minmax_zero_mode=4 -theory.bv.div_by_zero_mode=1 -unsat_core_generation=3 [2024-11-14 02:43:04,430 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 02:43:04,431 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 02:43:04,431 INFO L85 PathProgramCache]: Analyzing trace with hash 1727578948, now seen corresponding path program 1 times [2024-11-14 02:43:04,431 INFO L118 FreeRefinementEngine]: Executing refinement strategy WALRUS [2024-11-14 02:43:04,431 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleMathsat [1795722375] [2024-11-14 02:43:04,431 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 02:43:04,431 INFO L173 SolverBuilder]: Constructing external solver with command: mathsat -theory.fp.to_bv_overflow_mode=1 -theory.fp.minmax_zero_mode=4 -theory.bv.div_by_zero_mode=1 -unsat_core_generation=3 [2024-11-14 02:43:04,432 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_da71d4ab-fde8-404d-b8fa-860e6ebdffbf/bin/utaipan-verify-sOmjnqqW8E/mathsat [2024-11-14 02:43:04,434 INFO L229 MonitoredProcess]: Starting monitored process 4 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_da71d4ab-fde8-404d-b8fa-860e6ebdffbf/bin/utaipan-verify-sOmjnqqW8E/mathsat -theory.fp.to_bv_overflow_mode=1 -theory.fp.minmax_zero_mode=4 -theory.bv.div_by_zero_mode=1 -unsat_core_generation=3 (exit command is (exit), workingDir is null) [2024-11-14 02:43:04,436 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_da71d4ab-fde8-404d-b8fa-860e6ebdffbf/bin/utaipan-verify-sOmjnqqW8E/mathsat -theory.fp.to_bv_overflow_mode=1 -theory.fp.minmax_zero_mode=4 -theory.bv.div_by_zero_mode=1 -unsat_core_generation=3 (4)] Waiting until timeout for monitored process [2024-11-14 02:43:04,522 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 02:43:04,526 INFO L255 TraceCheckSpWp]: Trace formula consists of 44 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-14 02:43:04,529 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-14 02:43:04,814 INFO L134 CoverageAnalysis]: Checked inductivity of 1 backedges. 1 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-14 02:43:04,814 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-14 02:43:04,814 INFO L136 FreeRefinementEngine]: Strategy WALRUS found an infeasible trace [2024-11-14 02:43:04,814 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleMathsat [1795722375] [2024-11-14 02:43:04,815 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleMathsat [1795722375] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-14 02:43:04,815 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-14 02:43:04,815 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2024-11-14 02:43:04,815 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [645997291] [2024-11-14 02:43:04,815 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-14 02:43:04,815 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2024-11-14 02:43:04,816 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy WALRUS [2024-11-14 02:43:04,816 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2024-11-14 02:43:04,816 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2024-11-14 02:43:04,816 INFO L87 Difference]: Start difference. First operand 41 states and 49 transitions. Second operand has 3 states, 3 states have (on average 4.666666666666667) internal successors, (14), 3 states have internal predecessors, (14), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-14 02:43:04,932 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 02:43:04,933 INFO L93 Difference]: Finished difference Result 56 states and 68 transitions. [2024-11-14 02:43:04,933 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2024-11-14 02:43:04,933 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 4.666666666666667) internal successors, (14), 3 states have internal predecessors, (14), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 15 [2024-11-14 02:43:04,934 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 02:43:04,934 INFO L225 Difference]: With dead ends: 56 [2024-11-14 02:43:04,934 INFO L226 Difference]: Without dead ends: 43 [2024-11-14 02:43:04,935 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 14 GetRequests, 13 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2024-11-14 02:43:04,936 INFO L432 NwaCegarLoop]: 41 mSDtfsCounter, 0 mSDsluCounter, 36 mSDsCounter, 0 mSdLazyCounter, 11 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 77 SdHoareTripleChecker+Invalid, 11 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 11 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-14 02:43:04,936 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 77 Invalid, 11 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 11 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-14 02:43:04,937 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 43 states. [2024-11-14 02:43:04,942 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 43 to 43. [2024-11-14 02:43:04,942 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 43 states, 29 states have (on average 1.1724137931034482) internal successors, (34), 31 states have internal predecessors, (34), 9 states have call successors, (9), 3 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 02:43:04,943 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 43 states to 43 states and 51 transitions. [2024-11-14 02:43:04,944 INFO L78 Accepts]: Start accepts. Automaton has 43 states and 51 transitions. Word has length 15 [2024-11-14 02:43:04,944 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 02:43:04,944 INFO L471 AbstractCegarLoop]: Abstraction has 43 states and 51 transitions. [2024-11-14 02:43:04,944 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 4.666666666666667) internal successors, (14), 3 states have internal predecessors, (14), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-14 02:43:04,944 INFO L276 IsEmpty]: Start isEmpty. Operand 43 states and 51 transitions. [2024-11-14 02:43:04,945 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 18 [2024-11-14 02:43:04,945 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 02:43:04,945 INFO L215 NwaCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-14 02:43:04,950 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_da71d4ab-fde8-404d-b8fa-860e6ebdffbf/bin/utaipan-verify-sOmjnqqW8E/mathsat -theory.fp.to_bv_overflow_mode=1 -theory.fp.minmax_zero_mode=4 -theory.bv.div_by_zero_mode=1 -unsat_core_generation=3 (4)] Ended with exit code 0 [2024-11-14 02:43:05,146 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 4 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_da71d4ab-fde8-404d-b8fa-860e6ebdffbf/bin/utaipan-verify-sOmjnqqW8E/mathsat -theory.fp.to_bv_overflow_mode=1 -theory.fp.minmax_zero_mode=4 -theory.bv.div_by_zero_mode=1 -unsat_core_generation=3 [2024-11-14 02:43:05,146 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 02:43:05,146 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 02:43:05,147 INFO L85 PathProgramCache]: Analyzing trace with hash -2123758047, now seen corresponding path program 1 times [2024-11-14 02:43:05,147 INFO L118 FreeRefinementEngine]: Executing refinement strategy WALRUS [2024-11-14 02:43:05,147 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleMathsat [1988110579] [2024-11-14 02:43:05,147 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 02:43:05,147 INFO L173 SolverBuilder]: Constructing external solver with command: mathsat -theory.fp.to_bv_overflow_mode=1 -theory.fp.minmax_zero_mode=4 -theory.bv.div_by_zero_mode=1 -unsat_core_generation=3 [2024-11-14 02:43:05,147 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_da71d4ab-fde8-404d-b8fa-860e6ebdffbf/bin/utaipan-verify-sOmjnqqW8E/mathsat [2024-11-14 02:43:05,149 INFO L229 MonitoredProcess]: Starting monitored process 5 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_da71d4ab-fde8-404d-b8fa-860e6ebdffbf/bin/utaipan-verify-sOmjnqqW8E/mathsat -theory.fp.to_bv_overflow_mode=1 -theory.fp.minmax_zero_mode=4 -theory.bv.div_by_zero_mode=1 -unsat_core_generation=3 (exit command is (exit), workingDir is null) [2024-11-14 02:43:05,151 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_da71d4ab-fde8-404d-b8fa-860e6ebdffbf/bin/utaipan-verify-sOmjnqqW8E/mathsat -theory.fp.to_bv_overflow_mode=1 -theory.fp.minmax_zero_mode=4 -theory.bv.div_by_zero_mode=1 -unsat_core_generation=3 (5)] Waiting until timeout for monitored process [2024-11-14 02:43:05,223 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 02:43:05,227 INFO L255 TraceCheckSpWp]: Trace formula consists of 47 conjuncts, 8 conjuncts are in the unsatisfiable core [2024-11-14 02:43:05,230 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-14 02:43:05,610 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 2 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-14 02:43:05,610 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-14 02:43:05,858 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 2 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-14 02:43:05,859 INFO L136 FreeRefinementEngine]: Strategy WALRUS found an infeasible trace [2024-11-14 02:43:05,859 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleMathsat [1988110579] [2024-11-14 02:43:05,859 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleMathsat [1988110579] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-14 02:43:05,859 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleCvc4 [1552900169] [2024-11-14 02:43:05,859 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 02:43:05,859 INFO L173 SolverBuilder]: Constructing external solver with command: cvc4 --incremental --print-success --lang smt [2024-11-14 02:43:05,860 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_da71d4ab-fde8-404d-b8fa-860e6ebdffbf/bin/utaipan-verify-sOmjnqqW8E/cvc4 [2024-11-14 02:43:05,865 INFO L229 MonitoredProcess]: Starting monitored process 6 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_da71d4ab-fde8-404d-b8fa-860e6ebdffbf/bin/utaipan-verify-sOmjnqqW8E/cvc4 --incremental --print-success --lang smt (exit command is (exit), workingDir is null) [2024-11-14 02:43:05,867 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_da71d4ab-fde8-404d-b8fa-860e6ebdffbf/bin/utaipan-verify-sOmjnqqW8E/cvc4 --incremental --print-success --lang smt (6)] Waiting until timeout for monitored process [2024-11-14 02:43:06,023 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 02:43:06,025 INFO L255 TraceCheckSpWp]: Trace formula consists of 47 conjuncts, 8 conjuncts are in the unsatisfiable core [2024-11-14 02:43:06,027 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-14 02:43:06,303 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 2 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-14 02:43:06,303 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-14 02:43:06,453 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 2 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-14 02:43:06,453 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleCvc4 [1552900169] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-14 02:43:06,454 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [77600181] [2024-11-14 02:43:06,454 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 02:43:06,454 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 02:43:06,454 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_da71d4ab-fde8-404d-b8fa-860e6ebdffbf/bin/utaipan-verify-sOmjnqqW8E/z3 [2024-11-14 02:43:06,457 INFO L229 MonitoredProcess]: Starting monitored process 7 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_da71d4ab-fde8-404d-b8fa-860e6ebdffbf/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-14 02:43:06,459 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_da71d4ab-fde8-404d-b8fa-860e6ebdffbf/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2024-11-14 02:43:06,518 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 02:43:06,523 INFO L255 TraceCheckSpWp]: Trace formula consists of 47 conjuncts, 9 conjuncts are in the unsatisfiable core [2024-11-14 02:43:06,525 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-14 02:43:06,880 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-14 02:43:06,881 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-14 02:43:07,405 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-14 02:43:07,405 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [77600181] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-14 02:43:07,405 INFO L185 FreeRefinementEngine]: Found 0 perfect and 6 imperfect interpolant sequences. [2024-11-14 02:43:07,405 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 4, 4, 4, 5, 5] total 10 [2024-11-14 02:43:07,405 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [235800802] [2024-11-14 02:43:07,405 INFO L85 oduleStraightlineAll]: Using 6 imperfect interpolants to construct interpolant automaton [2024-11-14 02:43:07,406 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2024-11-14 02:43:07,406 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy WALRUS [2024-11-14 02:43:07,406 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2024-11-14 02:43:07,407 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=30, Invalid=60, Unknown=0, NotChecked=0, Total=90 [2024-11-14 02:43:07,407 INFO L87 Difference]: Start difference. First operand 43 states and 51 transitions. Second operand has 10 states, 10 states have (on average 3.5) internal successors, (35), 10 states have internal predecessors, (35), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-14 02:43:08,057 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 02:43:08,057 INFO L93 Difference]: Finished difference Result 63 states and 78 transitions. [2024-11-14 02:43:08,059 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2024-11-14 02:43:08,059 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 10 states have (on average 3.5) internal successors, (35), 10 states have internal predecessors, (35), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 17 [2024-11-14 02:43:08,059 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 02:43:08,060 INFO L225 Difference]: With dead ends: 63 [2024-11-14 02:43:08,060 INFO L226 Difference]: Without dead ends: 50 [2024-11-14 02:43:08,060 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 98 GetRequests, 88 SyntacticMatches, 0 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 6 ImplicationChecksByTransitivity, 0.9s TimeCoverageRelationStatistics Valid=45, Invalid=87, Unknown=0, NotChecked=0, Total=132 [2024-11-14 02:43:08,061 INFO L432 NwaCegarLoop]: 40 mSDtfsCounter, 7 mSDsluCounter, 182 mSDsCounter, 0 mSdLazyCounter, 51 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 7 SdHoareTripleChecker+Valid, 222 SdHoareTripleChecker+Invalid, 53 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 51 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2024-11-14 02:43:08,062 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [7 Valid, 222 Invalid, 53 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 51 Invalid, 0 Unknown, 0 Unchecked, 0.4s Time] [2024-11-14 02:43:08,062 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 50 states. [2024-11-14 02:43:08,069 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 50 to 48. [2024-11-14 02:43:08,070 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 48 states, 34 states have (on average 1.1470588235294117) internal successors, (39), 36 states have internal predecessors, (39), 9 states have call successors, (9), 3 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 02:43:08,070 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 48 states to 48 states and 56 transitions. [2024-11-14 02:43:08,072 INFO L78 Accepts]: Start accepts. Automaton has 48 states and 56 transitions. Word has length 17 [2024-11-14 02:43:08,072 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 02:43:08,072 INFO L471 AbstractCegarLoop]: Abstraction has 48 states and 56 transitions. [2024-11-14 02:43:08,073 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 10 states have (on average 3.5) internal successors, (35), 10 states have internal predecessors, (35), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-14 02:43:08,073 INFO L276 IsEmpty]: Start isEmpty. Operand 48 states and 56 transitions. [2024-11-14 02:43:08,074 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 24 [2024-11-14 02:43:08,074 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 02:43:08,075 INFO L215 NwaCegarLoop]: trace histogram [5, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-14 02:43:08,078 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_da71d4ab-fde8-404d-b8fa-860e6ebdffbf/bin/utaipan-verify-sOmjnqqW8E/cvc4 --incremental --print-success --lang smt (6)] Ended with exit code 0 [2024-11-14 02:43:08,289 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_da71d4ab-fde8-404d-b8fa-860e6ebdffbf/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Ended with exit code 0 [2024-11-14 02:43:08,479 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_da71d4ab-fde8-404d-b8fa-860e6ebdffbf/bin/utaipan-verify-sOmjnqqW8E/mathsat -theory.fp.to_bv_overflow_mode=1 -theory.fp.minmax_zero_mode=4 -theory.bv.div_by_zero_mode=1 -unsat_core_generation=3 (5)] Ended with exit code 0 [2024-11-14 02:43:08,676 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 6 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_da71d4ab-fde8-404d-b8fa-860e6ebdffbf/bin/utaipan-verify-sOmjnqqW8E/cvc4 --incremental --print-success --lang smt,7 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_da71d4ab-fde8-404d-b8fa-860e6ebdffbf/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true,5 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_da71d4ab-fde8-404d-b8fa-860e6ebdffbf/bin/utaipan-verify-sOmjnqqW8E/mathsat -theory.fp.to_bv_overflow_mode=1 -theory.fp.minmax_zero_mode=4 -theory.bv.div_by_zero_mode=1 -unsat_core_generation=3 [2024-11-14 02:43:08,676 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 02:43:08,677 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 02:43:08,677 INFO L85 PathProgramCache]: Analyzing trace with hash -1267107016, now seen corresponding path program 2 times [2024-11-14 02:43:08,677 INFO L118 FreeRefinementEngine]: Executing refinement strategy WALRUS [2024-11-14 02:43:08,677 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleMathsat [694827510] [2024-11-14 02:43:08,677 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-14 02:43:08,677 INFO L173 SolverBuilder]: Constructing external solver with command: mathsat -theory.fp.to_bv_overflow_mode=1 -theory.fp.minmax_zero_mode=4 -theory.bv.div_by_zero_mode=1 -unsat_core_generation=3 [2024-11-14 02:43:08,678 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_da71d4ab-fde8-404d-b8fa-860e6ebdffbf/bin/utaipan-verify-sOmjnqqW8E/mathsat [2024-11-14 02:43:08,681 INFO L229 MonitoredProcess]: Starting monitored process 8 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_da71d4ab-fde8-404d-b8fa-860e6ebdffbf/bin/utaipan-verify-sOmjnqqW8E/mathsat -theory.fp.to_bv_overflow_mode=1 -theory.fp.minmax_zero_mode=4 -theory.bv.div_by_zero_mode=1 -unsat_core_generation=3 (exit command is (exit), workingDir is null) [2024-11-14 02:43:08,682 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_da71d4ab-fde8-404d-b8fa-860e6ebdffbf/bin/utaipan-verify-sOmjnqqW8E/mathsat -theory.fp.to_bv_overflow_mode=1 -theory.fp.minmax_zero_mode=4 -theory.bv.div_by_zero_mode=1 -unsat_core_generation=3 (8)] Waiting until timeout for monitored process [2024-11-14 02:43:08,761 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-14 02:43:08,762 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-14 02:43:08,766 INFO L255 TraceCheckSpWp]: Trace formula consists of 56 conjuncts, 15 conjuncts are in the unsatisfiable core [2024-11-14 02:43:08,768 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-14 02:43:10,797 INFO L134 CoverageAnalysis]: Checked inductivity of 25 backedges. 0 proven. 24 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2024-11-14 02:43:10,798 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-14 02:43:17,954 INFO L134 CoverageAnalysis]: Checked inductivity of 25 backedges. 0 proven. 24 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2024-11-14 02:43:17,954 INFO L136 FreeRefinementEngine]: Strategy WALRUS found an infeasible trace [2024-11-14 02:43:17,954 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleMathsat [694827510] [2024-11-14 02:43:17,954 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleMathsat [694827510] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-14 02:43:17,954 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleCvc4 [335710577] [2024-11-14 02:43:17,955 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-14 02:43:17,955 INFO L173 SolverBuilder]: Constructing external solver with command: cvc4 --incremental --print-success --lang smt [2024-11-14 02:43:17,955 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_da71d4ab-fde8-404d-b8fa-860e6ebdffbf/bin/utaipan-verify-sOmjnqqW8E/cvc4 [2024-11-14 02:43:17,957 INFO L229 MonitoredProcess]: Starting monitored process 9 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_da71d4ab-fde8-404d-b8fa-860e6ebdffbf/bin/utaipan-verify-sOmjnqqW8E/cvc4 --incremental --print-success --lang smt (exit command is (exit), workingDir is null) [2024-11-14 02:43:17,960 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_da71d4ab-fde8-404d-b8fa-860e6ebdffbf/bin/utaipan-verify-sOmjnqqW8E/cvc4 --incremental --print-success --lang smt (9)] Waiting until timeout for monitored process [2024-11-14 02:43:18,155 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-14 02:43:18,155 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-14 02:43:18,156 INFO L255 TraceCheckSpWp]: Trace formula consists of 56 conjuncts, 10 conjuncts are in the unsatisfiable core [2024-11-14 02:43:18,158 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-14 02:43:19,695 INFO L134 CoverageAnalysis]: Checked inductivity of 25 backedges. 12 proven. 12 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2024-11-14 02:43:19,696 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-14 02:43:21,905 INFO L134 CoverageAnalysis]: Checked inductivity of 25 backedges. 12 proven. 12 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2024-11-14 02:43:21,906 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleCvc4 [335710577] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-14 02:43:21,906 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2146315540] [2024-11-14 02:43:21,906 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-14 02:43:21,906 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 02:43:21,906 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_da71d4ab-fde8-404d-b8fa-860e6ebdffbf/bin/utaipan-verify-sOmjnqqW8E/z3 [2024-11-14 02:43:21,908 INFO L229 MonitoredProcess]: Starting monitored process 10 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_da71d4ab-fde8-404d-b8fa-860e6ebdffbf/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-14 02:43:21,910 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_da71d4ab-fde8-404d-b8fa-860e6ebdffbf/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Waiting until timeout for monitored process [2024-11-14 02:43:21,985 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-14 02:43:21,985 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-14 02:43:21,993 INFO L255 TraceCheckSpWp]: Trace formula consists of 56 conjuncts, 12 conjuncts are in the unsatisfiable core [2024-11-14 02:43:21,995 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-14 02:43:23,072 INFO L134 CoverageAnalysis]: Checked inductivity of 25 backedges. 0 proven. 25 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-14 02:43:23,072 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-14 02:43:26,928 INFO L134 CoverageAnalysis]: Checked inductivity of 25 backedges. 0 proven. 25 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-14 02:43:26,929 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2146315540] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-14 02:43:26,930 INFO L185 FreeRefinementEngine]: Found 0 perfect and 6 imperfect interpolant sequences. [2024-11-14 02:43:26,930 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 11, 6, 6, 8, 8] total 36 [2024-11-14 02:43:26,930 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [866749500] [2024-11-14 02:43:26,930 INFO L85 oduleStraightlineAll]: Using 6 imperfect interpolants to construct interpolant automaton [2024-11-14 02:43:26,931 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 36 states [2024-11-14 02:43:26,932 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy WALRUS [2024-11-14 02:43:26,933 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 36 interpolants. [2024-11-14 02:43:26,934 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=169, Invalid=1091, Unknown=0, NotChecked=0, Total=1260 [2024-11-14 02:43:26,936 INFO L87 Difference]: Start difference. First operand 48 states and 56 transitions. Second operand has 36 states, 34 states have (on average 2.676470588235294) internal successors, (91), 34 states have internal predecessors, (91), 3 states have call successors, (3), 3 states have call predecessors, (3), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-14 02:43:40,260 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 02:43:40,260 INFO L93 Difference]: Finished difference Result 75 states and 91 transitions. [2024-11-14 02:43:40,265 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2024-11-14 02:43:40,266 INFO L78 Accepts]: Start accepts. Automaton has has 36 states, 34 states have (on average 2.676470588235294) internal successors, (91), 34 states have internal predecessors, (91), 3 states have call successors, (3), 3 states have call predecessors, (3), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 23 [2024-11-14 02:43:40,266 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 02:43:40,266 INFO L225 Difference]: With dead ends: 75 [2024-11-14 02:43:40,267 INFO L226 Difference]: Without dead ends: 61 [2024-11-14 02:43:40,268 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 135 GetRequests, 98 SyntacticMatches, 0 SemanticMatches, 37 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 195 ImplicationChecksByTransitivity, 20.5s TimeCoverageRelationStatistics Valid=195, Invalid=1287, Unknown=0, NotChecked=0, Total=1482 [2024-11-14 02:43:40,268 INFO L432 NwaCegarLoop]: 35 mSDtfsCounter, 7 mSDsluCounter, 758 mSDsCounter, 0 mSdLazyCounter, 414 mSolverCounterSat, 12 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 6.8s Time, 0 mProtectedPredicate, 0 mProtectedAction, 9 SdHoareTripleChecker+Valid, 793 SdHoareTripleChecker+Invalid, 426 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 12 IncrementalHoareTripleChecker+Valid, 414 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 7.3s IncrementalHoareTripleChecker+Time [2024-11-14 02:43:40,269 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [9 Valid, 793 Invalid, 426 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [12 Valid, 414 Invalid, 0 Unknown, 0 Unchecked, 7.3s Time] [2024-11-14 02:43:40,269 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 61 states. [2024-11-14 02:43:40,278 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 61 to 59. [2024-11-14 02:43:40,278 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 59 states, 43 states have (on average 1.1395348837209303) internal successors, (49), 46 states have internal predecessors, (49), 10 states have call successors, (10), 4 states have call predecessors, (10), 4 states have return successors, (9), 8 states have call predecessors, (9), 9 states have call successors, (9) [2024-11-14 02:43:40,279 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 59 states to 59 states and 68 transitions. [2024-11-14 02:43:40,280 INFO L78 Accepts]: Start accepts. Automaton has 59 states and 68 transitions. Word has length 23 [2024-11-14 02:43:40,280 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 02:43:40,280 INFO L471 AbstractCegarLoop]: Abstraction has 59 states and 68 transitions. [2024-11-14 02:43:40,280 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 36 states, 34 states have (on average 2.676470588235294) internal successors, (91), 34 states have internal predecessors, (91), 3 states have call successors, (3), 3 states have call predecessors, (3), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-14 02:43:40,280 INFO L276 IsEmpty]: Start isEmpty. Operand 59 states and 68 transitions. [2024-11-14 02:43:40,281 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 28 [2024-11-14 02:43:40,281 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 02:43:40,281 INFO L215 NwaCegarLoop]: trace histogram [7, 4, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-14 02:43:40,296 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_da71d4ab-fde8-404d-b8fa-860e6ebdffbf/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Ended with exit code 0 [2024-11-14 02:43:40,485 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_da71d4ab-fde8-404d-b8fa-860e6ebdffbf/bin/utaipan-verify-sOmjnqqW8E/mathsat -theory.fp.to_bv_overflow_mode=1 -theory.fp.minmax_zero_mode=4 -theory.bv.div_by_zero_mode=1 -unsat_core_generation=3 (8)] Ended with exit code 0 [2024-11-14 02:43:40,685 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_da71d4ab-fde8-404d-b8fa-860e6ebdffbf/bin/utaipan-verify-sOmjnqqW8E/cvc4 --incremental --print-success --lang smt (9)] Forceful destruction successful, exit code 0 [2024-11-14 02:43:40,882 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 10 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_da71d4ab-fde8-404d-b8fa-860e6ebdffbf/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true,8 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_da71d4ab-fde8-404d-b8fa-860e6ebdffbf/bin/utaipan-verify-sOmjnqqW8E/mathsat -theory.fp.to_bv_overflow_mode=1 -theory.fp.minmax_zero_mode=4 -theory.bv.div_by_zero_mode=1 -unsat_core_generation=3,9 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_da71d4ab-fde8-404d-b8fa-860e6ebdffbf/bin/utaipan-verify-sOmjnqqW8E/cvc4 --incremental --print-success --lang smt [2024-11-14 02:43:40,882 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 02:43:40,882 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 02:43:40,883 INFO L85 PathProgramCache]: Analyzing trace with hash 1165001134, now seen corresponding path program 3 times [2024-11-14 02:43:40,883 INFO L118 FreeRefinementEngine]: Executing refinement strategy WALRUS [2024-11-14 02:43:40,883 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleMathsat [468842509] [2024-11-14 02:43:40,883 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-14 02:43:40,883 INFO L173 SolverBuilder]: Constructing external solver with command: mathsat -theory.fp.to_bv_overflow_mode=1 -theory.fp.minmax_zero_mode=4 -theory.bv.div_by_zero_mode=1 -unsat_core_generation=3 [2024-11-14 02:43:40,883 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_da71d4ab-fde8-404d-b8fa-860e6ebdffbf/bin/utaipan-verify-sOmjnqqW8E/mathsat [2024-11-14 02:43:40,887 INFO L229 MonitoredProcess]: Starting monitored process 11 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_da71d4ab-fde8-404d-b8fa-860e6ebdffbf/bin/utaipan-verify-sOmjnqqW8E/mathsat -theory.fp.to_bv_overflow_mode=1 -theory.fp.minmax_zero_mode=4 -theory.bv.div_by_zero_mode=1 -unsat_core_generation=3 (exit command is (exit), workingDir is null) [2024-11-14 02:43:40,888 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_da71d4ab-fde8-404d-b8fa-860e6ebdffbf/bin/utaipan-verify-sOmjnqqW8E/mathsat -theory.fp.to_bv_overflow_mode=1 -theory.fp.minmax_zero_mode=4 -theory.bv.div_by_zero_mode=1 -unsat_core_generation=3 (11)] Waiting until timeout for monitored process [2024-11-14 02:43:40,977 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 7 check-sat command(s) [2024-11-14 02:43:40,977 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-14 02:43:40,982 INFO L255 TraceCheckSpWp]: Trace formula consists of 59 conjuncts, 12 conjuncts are in the unsatisfiable core [2024-11-14 02:43:40,984 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-14 02:43:41,877 INFO L134 CoverageAnalysis]: Checked inductivity of 49 backedges. 0 proven. 43 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2024-11-14 02:43:41,877 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-14 02:43:44,133 WARN L851 $PredicateComparison]: unable to prove that (forall ((|ULTIMATE.start_gcd_test_~b#1| (_ BitVec 32))) (not (= (_ bv0 32) (bvadd (bvneg (bvadd |c_ULTIMATE.start_gcd_test_~a#1| (bvneg |ULTIMATE.start_gcd_test_~b#1|))) |ULTIMATE.start_gcd_test_~b#1|)))) is different from false [2024-11-14 02:43:56,305 INFO L134 CoverageAnalysis]: Checked inductivity of 49 backedges. 0 proven. 14 refuted. 2 times theorem prover too weak. 6 trivial. 27 not checked. [2024-11-14 02:43:56,305 INFO L136 FreeRefinementEngine]: Strategy WALRUS found an infeasible trace [2024-11-14 02:43:56,305 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleMathsat [468842509] [2024-11-14 02:43:56,305 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleMathsat [468842509] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-14 02:43:56,305 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleCvc4 [1601473914] [2024-11-14 02:43:56,305 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-14 02:43:56,305 INFO L173 SolverBuilder]: Constructing external solver with command: cvc4 --incremental --print-success --lang smt [2024-11-14 02:43:56,305 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_da71d4ab-fde8-404d-b8fa-860e6ebdffbf/bin/utaipan-verify-sOmjnqqW8E/cvc4 [2024-11-14 02:43:56,311 INFO L229 MonitoredProcess]: Starting monitored process 12 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_da71d4ab-fde8-404d-b8fa-860e6ebdffbf/bin/utaipan-verify-sOmjnqqW8E/cvc4 --incremental --print-success --lang smt (exit command is (exit), workingDir is null) [2024-11-14 02:43:56,312 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_da71d4ab-fde8-404d-b8fa-860e6ebdffbf/bin/utaipan-verify-sOmjnqqW8E/cvc4 --incremental --print-success --lang smt (12)] Waiting until timeout for monitored process [2024-11-14 02:43:56,721 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 7 check-sat command(s) [2024-11-14 02:43:56,721 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-14 02:43:56,722 INFO L255 TraceCheckSpWp]: Trace formula consists of 59 conjuncts, 12 conjuncts are in the unsatisfiable core [2024-11-14 02:43:56,724 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-14 02:43:57,138 INFO L134 CoverageAnalysis]: Checked inductivity of 49 backedges. 0 proven. 43 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2024-11-14 02:43:57,139 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-14 02:43:58,291 INFO L134 CoverageAnalysis]: Checked inductivity of 49 backedges. 0 proven. 14 refuted. 2 times theorem prover too weak. 6 trivial. 27 not checked. [2024-11-14 02:43:58,291 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleCvc4 [1601473914] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-14 02:43:58,291 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1370094182] [2024-11-14 02:43:58,291 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-14 02:43:58,292 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 02:43:58,292 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_da71d4ab-fde8-404d-b8fa-860e6ebdffbf/bin/utaipan-verify-sOmjnqqW8E/z3 [2024-11-14 02:43:58,294 INFO L229 MonitoredProcess]: Starting monitored process 13 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_da71d4ab-fde8-404d-b8fa-860e6ebdffbf/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-14 02:43:58,296 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_da71d4ab-fde8-404d-b8fa-860e6ebdffbf/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Waiting until timeout for monitored process [2024-11-14 02:43:58,389 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 7 check-sat command(s) [2024-11-14 02:43:58,389 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-14 02:43:58,393 INFO L255 TraceCheckSpWp]: Trace formula consists of 59 conjuncts, 14 conjuncts are in the unsatisfiable core [2024-11-14 02:43:58,394 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-14 02:43:58,929 INFO L134 CoverageAnalysis]: Checked inductivity of 49 backedges. 0 proven. 43 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2024-11-14 02:43:58,930 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-14 02:43:59,835 INFO L134 CoverageAnalysis]: Checked inductivity of 49 backedges. 0 proven. 14 refuted. 2 times theorem prover too weak. 6 trivial. 27 not checked. [2024-11-14 02:43:59,835 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1370094182] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-14 02:43:59,835 INFO L185 FreeRefinementEngine]: Found 0 perfect and 6 imperfect interpolant sequences. [2024-11-14 02:43:59,835 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8, 8, 8, 8, 8] total 15 [2024-11-14 02:43:59,836 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [619188123] [2024-11-14 02:43:59,836 INFO L85 oduleStraightlineAll]: Using 6 imperfect interpolants to construct interpolant automaton [2024-11-14 02:43:59,836 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 15 states [2024-11-14 02:43:59,836 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy WALRUS [2024-11-14 02:43:59,837 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2024-11-14 02:43:59,837 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=50, Invalid=131, Unknown=5, NotChecked=24, Total=210 [2024-11-14 02:43:59,837 INFO L87 Difference]: Start difference. First operand 59 states and 68 transitions. Second operand has 15 states, 15 states have (on average 2.7333333333333334) internal successors, (41), 15 states have internal predecessors, (41), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-14 02:44:04,147 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, BitVec], hasArrays=false, hasNonlinArith=false, quantifiers [0, 1] [2024-11-14 02:44:08,672 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, BitVec], hasArrays=false, hasNonlinArith=false, quantifiers [0] [2024-11-14 02:44:10,709 WARN L851 $PredicateComparison]: unable to prove that (and (forall ((|v_ULTIMATE.start_gcd_test_~b#1_43| (_ BitVec 32))) (not (= (bvadd (bvneg (bvadd (bvneg |v_ULTIMATE.start_gcd_test_~b#1_43|) |c_ULTIMATE.start_gcd_test_~a#1| (bvmul (bvneg |c_ULTIMATE.start_gcd_test_~b#1|) (_ bv2 32)))) |v_ULTIMATE.start_gcd_test_~b#1_43|) (_ bv0 32)))) (not (= (_ bv0 32) |c_ULTIMATE.start_gcd_test_~b#1|)) (forall ((|ULTIMATE.start_gcd_test_~b#1| (_ BitVec 32))) (not (= (_ bv0 32) (bvadd (bvneg (bvadd |c_ULTIMATE.start_gcd_test_~a#1| (bvneg |ULTIMATE.start_gcd_test_~b#1|))) |ULTIMATE.start_gcd_test_~b#1|))))) is different from false [2024-11-14 02:44:12,781 WARN L851 $PredicateComparison]: unable to prove that (and (forall ((|v_ULTIMATE.start_gcd_test_~b#1_43| (_ BitVec 32))) (not (= (bvadd (bvneg (bvadd (bvneg |v_ULTIMATE.start_gcd_test_~b#1_43|) |c_ULTIMATE.start_gcd_test_~a#1| (bvmul (bvneg |c_ULTIMATE.start_gcd_test_~b#1|) (_ bv2 32)))) |v_ULTIMATE.start_gcd_test_~b#1_43|) (_ bv0 32)))) (forall ((|ULTIMATE.start_gcd_test_~b#1| (_ BitVec 32))) (not (= (_ bv0 32) (bvadd (bvneg (bvadd |c_ULTIMATE.start_gcd_test_~a#1| (bvneg |ULTIMATE.start_gcd_test_~b#1|))) |ULTIMATE.start_gcd_test_~b#1|))))) is different from false [2024-11-14 02:44:20,536 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.01s for a HTC check with result UNKNOWN. Formula has sorts [Bool, BitVec], hasArrays=false, hasNonlinArith=false, quantifiers [1] [2024-11-14 02:44:30,157 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.27s for a HTC check with result INVALID. Formula has sorts [Bool, BitVec], hasArrays=false, hasNonlinArith=false, quantifiers [1] [2024-11-14 02:44:32,159 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, BitVec], hasArrays=false, hasNonlinArith=false, quantifiers [1] [2024-11-14 02:44:34,277 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, BitVec], hasArrays=false, hasNonlinArith=false, quantifiers [1] [2024-11-14 02:44:36,294 WARN L851 $PredicateComparison]: unable to prove that (and (not (= (_ bv0 32) |c_ULTIMATE.start_gcd_test_~b#1|)) (forall ((|ULTIMATE.start_gcd_test_~b#1| (_ BitVec 32))) (not (= (_ bv0 32) (bvadd (bvneg (bvadd |c_ULTIMATE.start_gcd_test_~a#1| (bvneg |ULTIMATE.start_gcd_test_~b#1|))) |ULTIMATE.start_gcd_test_~b#1|))))) is different from false [2024-11-14 02:44:38,302 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, BitVec], hasArrays=false, hasNonlinArith=false, quantifiers [0, 1] [2024-11-14 02:44:40,335 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, BitVec], hasArrays=false, hasNonlinArith=false, quantifiers [0, 1] [2024-11-14 02:44:40,982 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 02:44:40,982 INFO L93 Difference]: Finished difference Result 88 states and 110 transitions. [2024-11-14 02:44:40,982 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 22 states. [2024-11-14 02:44:40,983 INFO L78 Accepts]: Start accepts. Automaton has has 15 states, 15 states have (on average 2.7333333333333334) internal successors, (41), 15 states have internal predecessors, (41), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 27 [2024-11-14 02:44:40,983 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 02:44:40,985 INFO L225 Difference]: With dead ends: 88 [2024-11-14 02:44:40,985 INFO L226 Difference]: Without dead ends: 77 [2024-11-14 02:44:40,986 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 169 GetRequests, 141 SyntacticMatches, 5 SemanticMatches, 23 ConstructedPredicates, 4 IntricatePredicates, 0 DeprecatedPredicates, 50 ImplicationChecksByTransitivity, 38.8s TimeCoverageRelationStatistics Valid=122, Invalid=300, Unknown=14, NotChecked=164, Total=600 [2024-11-14 02:44:40,987 INFO L432 NwaCegarLoop]: 39 mSDtfsCounter, 15 mSDsluCounter, 254 mSDsCounter, 0 mSdLazyCounter, 137 mSolverCounterSat, 11 mSolverCounterUnsat, 7 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 18.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 15 SdHoareTripleChecker+Valid, 293 SdHoareTripleChecker+Invalid, 287 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 11 IncrementalHoareTripleChecker+Valid, 137 IncrementalHoareTripleChecker+Invalid, 7 IncrementalHoareTripleChecker+Unknown, 132 IncrementalHoareTripleChecker+Unchecked, 18.2s IncrementalHoareTripleChecker+Time [2024-11-14 02:44:40,987 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [15 Valid, 293 Invalid, 287 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [11 Valid, 137 Invalid, 7 Unknown, 132 Unchecked, 18.2s Time] [2024-11-14 02:44:40,988 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 77 states. [2024-11-14 02:44:40,998 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 77 to 74. [2024-11-14 02:44:40,998 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 74 states, 58 states have (on average 1.2586206896551724) internal successors, (73), 61 states have internal predecessors, (73), 10 states have call successors, (10), 4 states have call predecessors, (10), 4 states have return successors, (9), 8 states have call predecessors, (9), 9 states have call successors, (9) [2024-11-14 02:44:40,999 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 74 states to 74 states and 92 transitions. [2024-11-14 02:44:41,000 INFO L78 Accepts]: Start accepts. Automaton has 74 states and 92 transitions. Word has length 27 [2024-11-14 02:44:41,000 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 02:44:41,000 INFO L471 AbstractCegarLoop]: Abstraction has 74 states and 92 transitions. [2024-11-14 02:44:41,000 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 15 states, 15 states have (on average 2.7333333333333334) internal successors, (41), 15 states have internal predecessors, (41), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-14 02:44:41,000 INFO L276 IsEmpty]: Start isEmpty. Operand 74 states and 92 transitions. [2024-11-14 02:44:41,001 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 29 [2024-11-14 02:44:41,001 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 02:44:41,001 INFO L215 NwaCegarLoop]: trace histogram [5, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-14 02:44:41,018 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_da71d4ab-fde8-404d-b8fa-860e6ebdffbf/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Ended with exit code 0 [2024-11-14 02:44:41,206 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_da71d4ab-fde8-404d-b8fa-860e6ebdffbf/bin/utaipan-verify-sOmjnqqW8E/mathsat -theory.fp.to_bv_overflow_mode=1 -theory.fp.minmax_zero_mode=4 -theory.bv.div_by_zero_mode=1 -unsat_core_generation=3 (11)] Ended with exit code 0 [2024-11-14 02:44:41,405 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_da71d4ab-fde8-404d-b8fa-860e6ebdffbf/bin/utaipan-verify-sOmjnqqW8E/cvc4 --incremental --print-success --lang smt (12)] Ended with exit code 0 [2024-11-14 02:44:41,602 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 13 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_da71d4ab-fde8-404d-b8fa-860e6ebdffbf/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true,11 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_da71d4ab-fde8-404d-b8fa-860e6ebdffbf/bin/utaipan-verify-sOmjnqqW8E/mathsat -theory.fp.to_bv_overflow_mode=1 -theory.fp.minmax_zero_mode=4 -theory.bv.div_by_zero_mode=1 -unsat_core_generation=3,12 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_da71d4ab-fde8-404d-b8fa-860e6ebdffbf/bin/utaipan-verify-sOmjnqqW8E/cvc4 --incremental --print-success --lang smt [2024-11-14 02:44:41,603 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 02:44:41,603 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 02:44:41,603 INFO L85 PathProgramCache]: Analyzing trace with hash 1024310784, now seen corresponding path program 1 times [2024-11-14 02:44:41,603 INFO L118 FreeRefinementEngine]: Executing refinement strategy WALRUS [2024-11-14 02:44:41,603 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleMathsat [2077489114] [2024-11-14 02:44:41,603 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 02:44:41,604 INFO L173 SolverBuilder]: Constructing external solver with command: mathsat -theory.fp.to_bv_overflow_mode=1 -theory.fp.minmax_zero_mode=4 -theory.bv.div_by_zero_mode=1 -unsat_core_generation=3 [2024-11-14 02:44:41,604 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_da71d4ab-fde8-404d-b8fa-860e6ebdffbf/bin/utaipan-verify-sOmjnqqW8E/mathsat [2024-11-14 02:44:41,605 INFO L229 MonitoredProcess]: Starting monitored process 14 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_da71d4ab-fde8-404d-b8fa-860e6ebdffbf/bin/utaipan-verify-sOmjnqqW8E/mathsat -theory.fp.to_bv_overflow_mode=1 -theory.fp.minmax_zero_mode=4 -theory.bv.div_by_zero_mode=1 -unsat_core_generation=3 (exit command is (exit), workingDir is null) [2024-11-14 02:44:41,607 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_da71d4ab-fde8-404d-b8fa-860e6ebdffbf/bin/utaipan-verify-sOmjnqqW8E/mathsat -theory.fp.to_bv_overflow_mode=1 -theory.fp.minmax_zero_mode=4 -theory.bv.div_by_zero_mode=1 -unsat_core_generation=3 (14)] Waiting until timeout for monitored process [2024-11-14 02:44:41,725 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 02:44:41,732 INFO L255 TraceCheckSpWp]: Trace formula consists of 63 conjuncts, 14 conjuncts are in the unsatisfiable core [2024-11-14 02:44:41,734 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-14 02:44:43,006 INFO L134 CoverageAnalysis]: Checked inductivity of 27 backedges. 2 proven. 21 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-11-14 02:44:43,006 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-14 02:44:49,449 INFO L134 CoverageAnalysis]: Checked inductivity of 27 backedges. 2 proven. 21 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-11-14 02:44:49,450 INFO L136 FreeRefinementEngine]: Strategy WALRUS found an infeasible trace [2024-11-14 02:44:49,450 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleMathsat [2077489114] [2024-11-14 02:44:49,450 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleMathsat [2077489114] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-14 02:44:49,450 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleCvc4 [86562471] [2024-11-14 02:44:49,450 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 02:44:49,450 INFO L173 SolverBuilder]: Constructing external solver with command: cvc4 --incremental --print-success --lang smt [2024-11-14 02:44:49,450 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_da71d4ab-fde8-404d-b8fa-860e6ebdffbf/bin/utaipan-verify-sOmjnqqW8E/cvc4 [2024-11-14 02:44:49,454 INFO L229 MonitoredProcess]: Starting monitored process 15 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_da71d4ab-fde8-404d-b8fa-860e6ebdffbf/bin/utaipan-verify-sOmjnqqW8E/cvc4 --incremental --print-success --lang smt (exit command is (exit), workingDir is null) [2024-11-14 02:44:49,456 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_da71d4ab-fde8-404d-b8fa-860e6ebdffbf/bin/utaipan-verify-sOmjnqqW8E/cvc4 --incremental --print-success --lang smt (15)] Waiting until timeout for monitored process [2024-11-14 02:44:49,810 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 02:44:49,812 INFO L255 TraceCheckSpWp]: Trace formula consists of 63 conjuncts, 15 conjuncts are in the unsatisfiable core [2024-11-14 02:44:49,813 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-14 02:44:52,339 INFO L134 CoverageAnalysis]: Checked inductivity of 27 backedges. 2 proven. 21 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-11-14 02:44:52,340 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-14 02:44:53,674 INFO L134 CoverageAnalysis]: Checked inductivity of 27 backedges. 2 proven. 21 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-11-14 02:44:53,674 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleCvc4 [86562471] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-14 02:44:53,674 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1157404850] [2024-11-14 02:44:53,674 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 02:44:53,674 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 02:44:53,674 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_da71d4ab-fde8-404d-b8fa-860e6ebdffbf/bin/utaipan-verify-sOmjnqqW8E/z3 [2024-11-14 02:44:53,676 INFO L229 MonitoredProcess]: Starting monitored process 16 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_da71d4ab-fde8-404d-b8fa-860e6ebdffbf/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-14 02:44:53,677 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_da71d4ab-fde8-404d-b8fa-860e6ebdffbf/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Waiting until timeout for monitored process [2024-11-14 02:44:53,772 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 02:44:53,782 INFO L255 TraceCheckSpWp]: Trace formula consists of 63 conjuncts, 21 conjuncts are in the unsatisfiable core [2024-11-14 02:44:53,784 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-14 02:44:55,302 INFO L134 CoverageAnalysis]: Checked inductivity of 27 backedges. 1 proven. 22 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-11-14 02:44:55,302 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-14 02:45:26,826 INFO L134 CoverageAnalysis]: Checked inductivity of 27 backedges. 1 proven. 22 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-11-14 02:45:26,826 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1157404850] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-14 02:45:26,826 INFO L185 FreeRefinementEngine]: Found 0 perfect and 6 imperfect interpolant sequences. [2024-11-14 02:45:26,826 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10, 11, 10, 13, 14] total 34 [2024-11-14 02:45:26,826 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [846886892] [2024-11-14 02:45:26,826 INFO L85 oduleStraightlineAll]: Using 6 imperfect interpolants to construct interpolant automaton [2024-11-14 02:45:26,827 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 34 states [2024-11-14 02:45:26,827 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy WALRUS [2024-11-14 02:45:26,829 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 34 interpolants. [2024-11-14 02:45:26,830 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=142, Invalid=980, Unknown=0, NotChecked=0, Total=1122 [2024-11-14 02:45:26,830 INFO L87 Difference]: Start difference. First operand 74 states and 92 transitions. Second operand has 34 states, 30 states have (on average 2.5) internal successors, (75), 33 states have internal predecessors, (75), 4 states have call successors, (6), 3 states have call predecessors, (6), 2 states have return successors, (5), 2 states have call predecessors, (5), 4 states have call successors, (5) [2024-11-14 02:45:50,379 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 02:45:50,380 INFO L93 Difference]: Finished difference Result 93 states and 117 transitions. [2024-11-14 02:45:50,384 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 20 states. [2024-11-14 02:45:50,384 INFO L78 Accepts]: Start accepts. Automaton has has 34 states, 30 states have (on average 2.5) internal successors, (75), 33 states have internal predecessors, (75), 4 states have call successors, (6), 3 states have call predecessors, (6), 2 states have return successors, (5), 2 states have call predecessors, (5), 4 states have call successors, (5) Word has length 28 [2024-11-14 02:45:50,385 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 02:45:50,386 INFO L225 Difference]: With dead ends: 93 [2024-11-14 02:45:50,386 INFO L226 Difference]: Without dead ends: 82 [2024-11-14 02:45:50,387 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 166 GetRequests, 130 SyntacticMatches, 0 SemanticMatches, 36 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 300 ImplicationChecksByTransitivity, 43.7s TimeCoverageRelationStatistics Valid=183, Invalid=1223, Unknown=0, NotChecked=0, Total=1406 [2024-11-14 02:45:50,387 INFO L432 NwaCegarLoop]: 32 mSDtfsCounter, 5 mSDsluCounter, 618 mSDsCounter, 0 mSdLazyCounter, 408 mSolverCounterSat, 10 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 12.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 7 SdHoareTripleChecker+Valid, 650 SdHoareTripleChecker+Invalid, 418 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 10 IncrementalHoareTripleChecker+Valid, 408 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 13.3s IncrementalHoareTripleChecker+Time [2024-11-14 02:45:50,388 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [7 Valid, 650 Invalid, 418 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [10 Valid, 408 Invalid, 0 Unknown, 0 Unchecked, 13.3s Time] [2024-11-14 02:45:50,389 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 82 states. [2024-11-14 02:45:50,402 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 82 to 82. [2024-11-14 02:45:50,403 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 82 states, 65 states have (on average 1.2769230769230768) internal successors, (83), 68 states have internal predecessors, (83), 11 states have call successors, (11), 4 states have call predecessors, (11), 4 states have return successors, (10), 9 states have call predecessors, (10), 10 states have call successors, (10) [2024-11-14 02:45:50,404 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 82 states to 82 states and 104 transitions. [2024-11-14 02:45:50,404 INFO L78 Accepts]: Start accepts. Automaton has 82 states and 104 transitions. Word has length 28 [2024-11-14 02:45:50,404 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 02:45:50,404 INFO L471 AbstractCegarLoop]: Abstraction has 82 states and 104 transitions. [2024-11-14 02:45:50,404 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 34 states, 30 states have (on average 2.5) internal successors, (75), 33 states have internal predecessors, (75), 4 states have call successors, (6), 3 states have call predecessors, (6), 2 states have return successors, (5), 2 states have call predecessors, (5), 4 states have call successors, (5) [2024-11-14 02:45:50,405 INFO L276 IsEmpty]: Start isEmpty. Operand 82 states and 104 transitions. [2024-11-14 02:45:50,405 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 35 [2024-11-14 02:45:50,406 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 02:45:50,406 INFO L215 NwaCegarLoop]: trace histogram [3, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-14 02:45:50,413 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_da71d4ab-fde8-404d-b8fa-860e6ebdffbf/bin/utaipan-verify-sOmjnqqW8E/mathsat -theory.fp.to_bv_overflow_mode=1 -theory.fp.minmax_zero_mode=4 -theory.bv.div_by_zero_mode=1 -unsat_core_generation=3 (14)] Forceful destruction successful, exit code 0 [2024-11-14 02:45:50,621 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_da71d4ab-fde8-404d-b8fa-860e6ebdffbf/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Ended with exit code 0 [2024-11-14 02:45:50,809 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_da71d4ab-fde8-404d-b8fa-860e6ebdffbf/bin/utaipan-verify-sOmjnqqW8E/cvc4 --incremental --print-success --lang smt (15)] Forceful destruction successful, exit code 0 [2024-11-14 02:45:51,007 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 14 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_da71d4ab-fde8-404d-b8fa-860e6ebdffbf/bin/utaipan-verify-sOmjnqqW8E/mathsat -theory.fp.to_bv_overflow_mode=1 -theory.fp.minmax_zero_mode=4 -theory.bv.div_by_zero_mode=1 -unsat_core_generation=3,16 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_da71d4ab-fde8-404d-b8fa-860e6ebdffbf/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true,15 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_da71d4ab-fde8-404d-b8fa-860e6ebdffbf/bin/utaipan-verify-sOmjnqqW8E/cvc4 --incremental --print-success --lang smt [2024-11-14 02:45:51,007 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 02:45:51,007 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 02:45:51,008 INFO L85 PathProgramCache]: Analyzing trace with hash 1494164943, now seen corresponding path program 1 times [2024-11-14 02:45:51,008 INFO L118 FreeRefinementEngine]: Executing refinement strategy WALRUS [2024-11-14 02:45:51,008 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleMathsat [1392567060] [2024-11-14 02:45:51,008 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 02:45:51,008 INFO L173 SolverBuilder]: Constructing external solver with command: mathsat -theory.fp.to_bv_overflow_mode=1 -theory.fp.minmax_zero_mode=4 -theory.bv.div_by_zero_mode=1 -unsat_core_generation=3 [2024-11-14 02:45:51,008 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_da71d4ab-fde8-404d-b8fa-860e6ebdffbf/bin/utaipan-verify-sOmjnqqW8E/mathsat [2024-11-14 02:45:51,010 INFO L229 MonitoredProcess]: Starting monitored process 17 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_da71d4ab-fde8-404d-b8fa-860e6ebdffbf/bin/utaipan-verify-sOmjnqqW8E/mathsat -theory.fp.to_bv_overflow_mode=1 -theory.fp.minmax_zero_mode=4 -theory.bv.div_by_zero_mode=1 -unsat_core_generation=3 (exit command is (exit), workingDir is null) [2024-11-14 02:45:51,013 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_da71d4ab-fde8-404d-b8fa-860e6ebdffbf/bin/utaipan-verify-sOmjnqqW8E/mathsat -theory.fp.to_bv_overflow_mode=1 -theory.fp.minmax_zero_mode=4 -theory.bv.div_by_zero_mode=1 -unsat_core_generation=3 (17)] Waiting until timeout for monitored process [2024-11-14 02:46:56,122 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-14 02:46:56,123 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-14 02:47:30,654 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-14 02:47:30,843 INFO L130 FreeRefinementEngine]: Strategy WALRUS found a feasible trace [2024-11-14 02:47:30,843 INFO L325 BasicCegarLoop]: Counterexample is feasible [2024-11-14 02:47:30,844 INFO L782 garLoopResultBuilder]: Registering result UNSAFE for location ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION (1 of 2 remaining) [2024-11-14 02:47:30,846 INFO L782 garLoopResultBuilder]: Registering result UNKNOWN for location __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION (0 of 2 remaining) [2024-11-14 02:47:30,929 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_da71d4ab-fde8-404d-b8fa-860e6ebdffbf/bin/utaipan-verify-sOmjnqqW8E/mathsat -theory.fp.to_bv_overflow_mode=1 -theory.fp.minmax_zero_mode=4 -theory.bv.div_by_zero_mode=1 -unsat_core_generation=3 (17)] Forceful destruction successful, exit code 0 [2024-11-14 02:47:31,047 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 17 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_da71d4ab-fde8-404d-b8fa-860e6ebdffbf/bin/utaipan-verify-sOmjnqqW8E/mathsat -theory.fp.to_bv_overflow_mode=1 -theory.fp.minmax_zero_mode=4 -theory.bv.div_by_zero_mode=1 -unsat_core_generation=3 [2024-11-14 02:47:31,049 INFO L407 BasicCegarLoop]: Path program histogram: [3, 1, 1, 1, 1, 1] [2024-11-14 02:47:31,088 INFO L173 ceAbstractionStarter]: Computing trace abstraction results [2024-11-14 02:47:31,092 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 14.11 02:47:31 BoogieIcfgContainer [2024-11-14 02:47:31,092 INFO L131 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2024-11-14 02:47:31,092 INFO L112 PluginConnector]: ------------------------Witness Printer---------------------------- [2024-11-14 02:47:31,092 INFO L270 PluginConnector]: Initializing Witness Printer... [2024-11-14 02:47:31,092 INFO L274 PluginConnector]: Witness Printer initialized [2024-11-14 02:47:31,093 INFO L184 PluginConnector]: Executing the observer RCFGCatcher from plugin Witness Printer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 14.11 02:43:03" (3/4) ... [2024-11-14 02:47:31,094 INFO L136 WitnessPrinter]: Generating witness for reachability counterexample [2024-11-14 02:47:31,142 INFO L149 WitnessManager]: Wrote witness to /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_da71d4ab-fde8-404d-b8fa-860e6ebdffbf/bin/utaipan-verify-sOmjnqqW8E/witness.graphml [2024-11-14 02:47:31,142 INFO L131 PluginConnector]: ------------------------ END Witness Printer---------------------------- [2024-11-14 02:47:31,144 INFO L158 Benchmark]: Toolchain (without parser) took 277669.63ms. Allocated memory is still 83.9MB. Free memory was 60.9MB in the beginning and 41.0MB in the end (delta: 19.9MB). Peak memory consumption was 22.2MB. Max. memory is 16.1GB. [2024-11-14 02:47:31,144 INFO L158 Benchmark]: CDTParser took 1.79ms. Allocated memory is still 83.9MB. Free memory is still 64.5MB. There was no memory consumed. Max. memory is 16.1GB. [2024-11-14 02:47:31,145 INFO L158 Benchmark]: CACSL2BoogieTranslator took 338.49ms. Allocated memory is still 83.9MB. Free memory was 60.6MB in the beginning and 48.2MB in the end (delta: 12.5MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. [2024-11-14 02:47:31,145 INFO L158 Benchmark]: Boogie Procedure Inliner took 57.05ms. Allocated memory is still 83.9MB. Free memory was 48.2MB in the beginning and 46.7MB in the end (delta: 1.5MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. [2024-11-14 02:47:31,145 INFO L158 Benchmark]: Boogie Preprocessor took 40.77ms. Allocated memory is still 83.9MB. Free memory was 46.7MB in the beginning and 45.5MB in the end (delta: 1.2MB). There was no memory consumed. Max. memory is 16.1GB. [2024-11-14 02:47:31,146 INFO L158 Benchmark]: RCFGBuilder took 9138.28ms. Allocated memory is still 83.9MB. Free memory was 45.5MB in the beginning and 32.5MB in the end (delta: 13.0MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. [2024-11-14 02:47:31,146 INFO L158 Benchmark]: TraceAbstraction took 268033.27ms. Allocated memory is still 83.9MB. Free memory was 31.9MB in the beginning and 43.2MB in the end (delta: -11.3MB). There was no memory consumed. Max. memory is 16.1GB. [2024-11-14 02:47:31,146 INFO L158 Benchmark]: Witness Printer took 50.16ms. Allocated memory is still 83.9MB. Free memory was 43.2MB in the beginning and 41.0MB in the end (delta: 2.3MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. [2024-11-14 02:47:31,148 INFO L338 ainManager$Toolchain]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * CDTParser took 1.79ms. Allocated memory is still 83.9MB. Free memory is still 64.5MB. There was no memory consumed. Max. memory is 16.1GB. * CACSL2BoogieTranslator took 338.49ms. Allocated memory is still 83.9MB. Free memory was 60.6MB in the beginning and 48.2MB in the end (delta: 12.5MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. * Boogie Procedure Inliner took 57.05ms. Allocated memory is still 83.9MB. Free memory was 48.2MB in the beginning and 46.7MB in the end (delta: 1.5MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. * Boogie Preprocessor took 40.77ms. Allocated memory is still 83.9MB. Free memory was 46.7MB in the beginning and 45.5MB in the end (delta: 1.2MB). There was no memory consumed. Max. memory is 16.1GB. * RCFGBuilder took 9138.28ms. Allocated memory is still 83.9MB. Free memory was 45.5MB in the beginning and 32.5MB in the end (delta: 13.0MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. * TraceAbstraction took 268033.27ms. Allocated memory is still 83.9MB. Free memory was 31.9MB in the beginning and 43.2MB in the end (delta: -11.3MB). There was no memory consumed. Max. memory is 16.1GB. * Witness Printer took 50.16ms. Allocated memory is still 83.9MB. Free memory was 43.2MB in the beginning and 41.0MB in the end (delta: 2.3MB). Peak memory consumption was 8.4MB. 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 - CounterExampleResult [Line: 109]: a call to reach_error is reachable a call to reach_error is reachable We found a FailurePath: [L115] COND FALSE !(__VERIFIER_nondet_int()) [L118] CALL main2() [L97] float IN = __VERIFIER_nondet_float(); [L98] CALL assume_abort_if_not(IN > -1.4f && IN < 1.4f) [L82] COND FALSE !(!cond) [L98] RET assume_abort_if_not(IN > -1.4f && IN < 1.4f) [L100] CALL, EXPR f(IN) VAL [\old(x)=-1.1720861196517944] [L87] return x - (x*x*x)/6.0f + (x*x*x*x*x)/120.0f + (x*x*x*x*x*x*x)/5040.0f; VAL [\old(x)=-1.1720861196517944, \result=-0.922757089138031] [L100] RET, EXPR f(IN) VAL [IN=-1.1720861196517944] [L100] CALL, EXPR fp(IN) VAL [\old(x)=-1.1720861196517944] [L92] return 1 - (x*x)/2.0f + (x*x*x*x)/24.0f + (x*x*x*x*x*x)/720.0f; VAL [\old(x)=-1.1720861196517944, \result=0.3953450620174408] [L100] RET, EXPR fp(IN) VAL [IN=-1.1720861196517944] [L100] float x = IN - f(IN)/fp(IN); [L102] CALL, EXPR f(x) VAL [\old(x)=1.1619688272476196] [L87] return x - (x*x*x)/6.0f + (x*x*x*x*x)/120.0f + (x*x*x*x*x*x*x)/5040.0f; VAL [\old(x)=1.1619688272476196, \result=0.9187119603157043] [L102] RET, EXPR f(x) VAL [x=1.1619688272476196] [L102] CALL, EXPR fp(x) VAL [\old(x)=1.1619688272476196] [L92] return 1 - (x*x)/2.0f + (x*x*x*x)/24.0f + (x*x*x*x*x*x)/720.0f; VAL [\old(x)=1.1619688272476196, \result=0.40428951382637024] [L102] RET, EXPR fp(x) VAL [x=1.1619688272476196] [L102] x = x - f(x)/fp(x) [L104] CALL, EXPR f(x) VAL [\old(x)=-1.1104422807693481] [L87] return x - (x*x*x)/6.0f + (x*x*x*x*x)/120.0f + (x*x*x*x*x*x*x)/5040.0f; VAL [\old(x)=-1.1104422807693481, \result=-0.8967143893241882] [L104] RET, EXPR f(x) VAL [x=-1.1104422807693481] [L104] CALL, EXPR fp(x) VAL [\old(x)=-1.1104422807693481] [L92] return 1 - (x*x)/2.0f + (x*x*x*x)/24.0f + (x*x*x*x*x*x)/720.0f; VAL [\old(x)=-1.1104422807693481, \result=0.44941678643226624] [L104] RET, EXPR fp(x) VAL [x=-1.1104422807693481] [L104] x = x - f(x)/fp(x) [L108] COND TRUE !(x < 0.1) [L109] reach_error() - UnprovableResult [Line: 27]: Unable to prove that a call to reach_error is unreachable Unable to prove that a call to reach_error is unreachable Reason: Not analyzed. - StatisticsResult: Ultimate Automizer benchmark data CFG has 4 procedures, 46 locations, 2 error locations. Started 1 CEGAR loops. OverallTime: 267.9s, OverallIterations: 8, TraceHistogramMax: 7, PathProgramHistogramMax: 3, EmptinessCheckTime: 0.0s, AutomataDifference: 79.1s, DeadEndRemovalTime: 0.0s, HoareAnnotationTime: 0.0s, InitialAbstractionConstructionTime: 0.0s, HoareTripleCheckerStatistics: 7 mSolverCounterUnknown, 49 SdHoareTripleChecker+Valid, 39.5s IncrementalHoareTripleChecker+Time, 0 mSdLazyCounter, 45 mSDsluCounter, 2210 SdHoareTripleChecker+Invalid, 37.7s Time, 0 mProtectedAction, 0 SdHoareTripleChecker+Unchecked, 132 IncrementalHoareTripleChecker+Unchecked, 1931 mSDsCounter, 37 IncrementalHoareTripleChecker+Valid, 0 mProtectedPredicate, 1039 IncrementalHoareTripleChecker+Invalid, 1215 SdHoareTripleChecker+Unknown, 0 mSolverCounterNotChecked, 37 mSolverCounterUnsat, 279 mSDtfsCounter, 1039 mSolverCounterSat, 0.0s SdHoareTripleChecker+Time, 7 IncrementalHoareTripleChecker+Unknown, PredicateUnifierStatistics: 0 DeclaredPredicates, 604 GetRequests, 490 SyntacticMatches, 5 SemanticMatches, 109 ConstructedPredicates, 4 IntricatePredicates, 0 DeprecatedPredicates, 551 ImplicationChecksByTransitivity, 104.0s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=82occurred in iteration=7, InterpolantAutomatonStates: 72, 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, 7 MinimizatonAttempts, 10 StatesRemovedByMinimization, 4 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TRACE_CHECK: 0.1s SsaConstructionTime, 66.6s SatisfiabilityAnalysisTime, 83.3s InterpolantComputationTime, 358 NumberOfCodeBlocks, 352 NumberOfCodeBlocksAsserted, 37 NumberOfCheckSat, 582 ConstructedInterpolants, 47 QuantifiedInterpolants, 3525 SizeOfPredicates, 42 NumberOfNonLiveVariables, 803 ConjunctsInSsa, 165 ConjunctsInUnsatCore, 27 InterpolantComputations, 3 PerfectInterpolantSequences, 107/631 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 RESULT: Ultimate proved your program to be incorrect! [2024-11-14 02:47:31,269 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_da71d4ab-fde8-404d-b8fa-860e6ebdffbf/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 Writing human readable error path to file UltimateCounterExample.errorpath Result: FALSE