./Ultimate.py --spec ../../sv-benchmarks/c/properties/unreach-call.prp --file ../../sv-benchmarks/c/nla-digbench-scaling/fermat2-ll_unwindbound100.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version 826ab2ba Calling Ultimate with: /usr/bin/java -Dosgi.configuration.area=/tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_25b0f514-5f57-40ae-9922-9007e959137d/bin/utaipan-verify-sOmjnqqW8E/data/config -Xmx15G -Xms4m -jar /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_25b0f514-5f57-40ae-9922-9007e959137d/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_25b0f514-5f57-40ae-9922-9007e959137d/bin/utaipan-verify-sOmjnqqW8E/data -tc /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_25b0f514-5f57-40ae-9922-9007e959137d/bin/utaipan-verify-sOmjnqqW8E/config/TaipanReach.xml -i ../../sv-benchmarks/c/nla-digbench-scaling/fermat2-ll_unwindbound100.c -s /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_25b0f514-5f57-40ae-9922-9007e959137d/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_25b0f514-5f57-40ae-9922-9007e959137d/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 36da946a83103a61b88f0f1db9af94484aad5eefbde5313f974f53b267bd14bf --- Real Ultimate output --- This is Ultimate 0.3.0-dev-826ab2b [2024-11-14 03:03:36,894 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-11-14 03:03:36,971 INFO L114 SettingsManager]: Loading settings from /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_25b0f514-5f57-40ae-9922-9007e959137d/bin/utaipan-verify-sOmjnqqW8E/config/svcomp-Reach-32bit-Taipan_Default.epf [2024-11-14 03:03:36,975 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-11-14 03:03:36,976 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-11-14 03:03:37,016 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-11-14 03:03:37,017 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-11-14 03:03:37,017 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-11-14 03:03:37,018 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2024-11-14 03:03:37,019 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2024-11-14 03:03:37,020 INFO L153 SettingsManager]: * User list type=DISABLED [2024-11-14 03:03:37,020 INFO L151 SettingsManager]: Preferences of Abstract Interpretation differ from their defaults: [2024-11-14 03:03:37,020 INFO L153 SettingsManager]: * Explicit value domain=true [2024-11-14 03:03:37,020 INFO L153 SettingsManager]: * Abstract domain for RCFG-of-the-future=PoormanAbstractDomain [2024-11-14 03:03:37,020 INFO L153 SettingsManager]: * Octagon Domain=false [2024-11-14 03:03:37,020 INFO L153 SettingsManager]: * Abstract domain=CompoundDomain [2024-11-14 03:03:37,020 INFO L153 SettingsManager]: * Check feasibility of abstract posts with an SMT solver=true [2024-11-14 03:03:37,020 INFO L153 SettingsManager]: * Use the RCFG-of-the-future interface=true [2024-11-14 03:03:37,020 INFO L153 SettingsManager]: * Interval Domain=false [2024-11-14 03:03:37,021 INFO L151 SettingsManager]: Preferences of Sifa differ from their defaults: [2024-11-14 03:03:37,021 INFO L153 SettingsManager]: * Call Summarizer=TopInputCallSummarizer [2024-11-14 03:03:37,021 INFO L153 SettingsManager]: * Simplification Technique=POLY_PAC [2024-11-14 03:03:37,021 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-11-14 03:03:37,021 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2024-11-14 03:03:37,021 INFO L153 SettingsManager]: * sizeof long=4 [2024-11-14 03:03:37,021 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2024-11-14 03:03:37,021 INFO L153 SettingsManager]: * sizeof POINTER=4 [2024-11-14 03:03:37,021 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-11-14 03:03:37,022 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2024-11-14 03:03:37,022 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2024-11-14 03:03:37,022 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2024-11-14 03:03:37,022 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-11-14 03:03:37,022 INFO L153 SettingsManager]: * sizeof long double=12 [2024-11-14 03:03:37,022 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-11-14 03:03:37,022 INFO L153 SettingsManager]: * Use constant arrays=true [2024-11-14 03:03:37,022 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2024-11-14 03:03:37,022 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2024-11-14 03:03:37,022 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2024-11-14 03:03:37,023 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2024-11-14 03:03:37,023 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-11-14 03:03:37,023 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2024-11-14 03:03:37,023 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2024-11-14 03:03:37,023 INFO L153 SettingsManager]: * Trace refinement strategy=SIFA_TAIPAN [2024-11-14 03:03:37,023 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2024-11-14 03:03:37,023 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2024-11-14 03:03:37,024 INFO L153 SettingsManager]: * Trace refinement exception blacklist=NONE [2024-11-14 03:03:37,024 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2024-11-14 03:03:37,024 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_25b0f514-5f57-40ae-9922-9007e959137d/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 -> 36da946a83103a61b88f0f1db9af94484aad5eefbde5313f974f53b267bd14bf [2024-11-14 03:03:37,359 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-11-14 03:03:37,367 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-11-14 03:03:37,369 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-11-14 03:03:37,370 INFO L270 PluginConnector]: Initializing CDTParser... [2024-11-14 03:03:37,371 INFO L274 PluginConnector]: CDTParser initialized [2024-11-14 03:03:37,372 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_25b0f514-5f57-40ae-9922-9007e959137d/bin/utaipan-verify-sOmjnqqW8E/../../sv-benchmarks/c/nla-digbench-scaling/fermat2-ll_unwindbound100.c Unable to find full path for "g++" [2024-11-14 03:03:39,365 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-11-14 03:03:39,731 INFO L384 CDTParser]: Found 1 translation units. [2024-11-14 03:03:39,732 INFO L180 CDTParser]: Scanning /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_25b0f514-5f57-40ae-9922-9007e959137d/sv-benchmarks/c/nla-digbench-scaling/fermat2-ll_unwindbound100.c [2024-11-14 03:03:39,744 INFO L427 CDTParser]: About to delete temporary CDT project at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_25b0f514-5f57-40ae-9922-9007e959137d/bin/utaipan-verify-sOmjnqqW8E/data/db7430644/925d25b6d7af4bdfad9be0196891c291/FLAG17c42efa4 [2024-11-14 03:03:39,801 INFO L435 CDTParser]: Successfully deleted /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_25b0f514-5f57-40ae-9922-9007e959137d/bin/utaipan-verify-sOmjnqqW8E/data/db7430644/925d25b6d7af4bdfad9be0196891c291 [2024-11-14 03:03:39,811 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-11-14 03:03:39,813 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2024-11-14 03:03:39,819 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-11-14 03:03:39,819 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-11-14 03:03:39,828 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-11-14 03:03:39,829 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 14.11 03:03:39" (1/1) ... [2024-11-14 03:03:39,835 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@52d59fa6 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 03:03:39, skipping insertion in model container [2024-11-14 03:03:39,835 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 14.11 03:03:39" (1/1) ... [2024-11-14 03:03:39,865 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-11-14 03:03:40,076 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_25b0f514-5f57-40ae-9922-9007e959137d/sv-benchmarks/c/nla-digbench-scaling/fermat2-ll_unwindbound100.c[524,537] [2024-11-14 03:03:40,101 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-14 03:03:40,112 INFO L200 MainTranslator]: Completed pre-run [2024-11-14 03:03:40,123 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_25b0f514-5f57-40ae-9922-9007e959137d/sv-benchmarks/c/nla-digbench-scaling/fermat2-ll_unwindbound100.c[524,537] [2024-11-14 03:03:40,134 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-14 03:03:40,149 INFO L204 MainTranslator]: Completed translation [2024-11-14 03:03:40,150 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 03:03:40 WrapperNode [2024-11-14 03:03:40,150 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-11-14 03:03:40,151 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-11-14 03:03:40,151 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-11-14 03:03:40,152 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-11-14 03:03:40,160 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 03:03:40" (1/1) ... [2024-11-14 03:03:40,167 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 03:03:40" (1/1) ... [2024-11-14 03:03:40,183 INFO L138 Inliner]: procedures = 14, calls = 11, calls flagged for inlining = 2, calls inlined = 2, statements flattened = 46 [2024-11-14 03:03:40,183 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-11-14 03:03:40,184 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-11-14 03:03:40,184 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-11-14 03:03:40,184 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-11-14 03:03:40,191 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 03:03:40" (1/1) ... [2024-11-14 03:03:40,191 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 03:03:40" (1/1) ... [2024-11-14 03:03:40,192 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 03:03:40" (1/1) ... [2024-11-14 03:03:40,193 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 03:03:40" (1/1) ... [2024-11-14 03:03:40,195 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 03:03:40" (1/1) ... [2024-11-14 03:03:40,199 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 03:03:40" (1/1) ... [2024-11-14 03:03:40,200 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 03:03:40" (1/1) ... [2024-11-14 03:03:40,200 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 03:03:40" (1/1) ... [2024-11-14 03:03:40,202 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-11-14 03:03:40,202 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2024-11-14 03:03:40,203 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2024-11-14 03:03:40,203 INFO L274 PluginConnector]: RCFGBuilder initialized [2024-11-14 03:03:40,204 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 03:03:40" (1/1) ... [2024-11-14 03:03:40,210 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2024-11-14 03:03:40,223 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_25b0f514-5f57-40ae-9922-9007e959137d/bin/utaipan-verify-sOmjnqqW8E/z3 [2024-11-14 03:03:40,235 INFO L229 MonitoredProcess]: Starting monitored process 1 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_25b0f514-5f57-40ae-9922-9007e959137d/bin/utaipan-verify-sOmjnqqW8E/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) [2024-11-14 03:03:40,239 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_25b0f514-5f57-40ae-9922-9007e959137d/bin/utaipan-verify-sOmjnqqW8E/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Waiting until timeout for monitored process [2024-11-14 03:03:40,261 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2024-11-14 03:03:40,262 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2024-11-14 03:03:40,262 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2024-11-14 03:03:40,262 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2024-11-14 03:03:40,262 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-11-14 03:03:40,262 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-11-14 03:03:40,262 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2024-11-14 03:03:40,262 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2024-11-14 03:03:40,395 INFO L238 CfgBuilder]: Building ICFG [2024-11-14 03:03:40,400 INFO L264 CfgBuilder]: Building CFG for each procedure with an implementation [2024-11-14 03:03:40,615 INFO L? ?]: Removed 7 outVars from TransFormulas that were not future-live. [2024-11-14 03:03:40,615 INFO L287 CfgBuilder]: Performing block encoding [2024-11-14 03:03:40,674 INFO L311 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-11-14 03:03:40,674 INFO L316 CfgBuilder]: Removed 1 assume(true) statements. [2024-11-14 03:03:40,675 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 14.11 03:03:40 BoogieIcfgContainer [2024-11-14 03:03:40,675 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2024-11-14 03:03:40,677 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2024-11-14 03:03:40,678 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2024-11-14 03:03:40,684 INFO L274 PluginConnector]: TraceAbstraction initialized [2024-11-14 03:03:40,684 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 14.11 03:03:39" (1/3) ... [2024-11-14 03:03:40,685 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@75ccca07 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 14.11 03:03:40, skipping insertion in model container [2024-11-14 03:03:40,685 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 03:03:40" (2/3) ... [2024-11-14 03:03:40,685 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@75ccca07 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 14.11 03:03:40, skipping insertion in model container [2024-11-14 03:03:40,685 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 14.11 03:03:40" (3/3) ... [2024-11-14 03:03:40,687 INFO L112 eAbstractionObserver]: Analyzing ICFG fermat2-ll_unwindbound100.c [2024-11-14 03:03:40,705 INFO L217 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2024-11-14 03:03:40,707 INFO L154 ceAbstractionStarter]: Applying trace abstraction to ICFG fermat2-ll_unwindbound100.c that has 3 procedures, 19 locations, 1 initial locations, 1 loop locations, and 1 error locations. [2024-11-14 03:03:40,780 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2024-11-14 03:03:40,799 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;@6bf1f482, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2024-11-14 03:03:40,799 INFO L334 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2024-11-14 03:03:40,808 INFO L276 IsEmpty]: Start isEmpty. Operand has 19 states, 11 states have (on average 1.4545454545454546) internal successors, (16), 12 states have internal predecessors, (16), 4 states have call successors, (4), 2 states have call predecessors, (4), 2 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) [2024-11-14 03:03:40,814 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 14 [2024-11-14 03:03:40,814 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 03:03:40,815 INFO L215 NwaCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-14 03:03:40,816 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 03:03:40,823 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 03:03:40,823 INFO L85 PathProgramCache]: Analyzing trace with hash 287051146, now seen corresponding path program 1 times [2024-11-14 03:03:40,831 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 03:03:40,832 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1617697440] [2024-11-14 03:03:40,833 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 03:03:40,833 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 03:03:40,949 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 03:03:41,034 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2024-11-14 03:03:41,035 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 03:03:41,037 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1617697440] [2024-11-14 03:03:41,038 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1617697440] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-14 03:03:41,038 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-14 03:03:41,038 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2024-11-14 03:03:41,040 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1868052116] [2024-11-14 03:03:41,043 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-14 03:03:41,047 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2024-11-14 03:03:41,048 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 03:03:41,070 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2024-11-14 03:03:41,071 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2024-11-14 03:03:41,073 INFO L87 Difference]: Start difference. First operand has 19 states, 11 states have (on average 1.4545454545454546) internal successors, (16), 12 states have internal predecessors, (16), 4 states have call successors, (4), 2 states have call predecessors, (4), 2 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) Second operand has 2 states, 2 states have (on average 3.5) internal successors, (7), 2 states have internal predecessors, (7), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2024-11-14 03:03:41,115 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 03:03:41,115 INFO L93 Difference]: Finished difference Result 32 states and 43 transitions. [2024-11-14 03:03:41,119 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2024-11-14 03:03:41,120 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 3.5) internal successors, (7), 2 states have internal predecessors, (7), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) Word has length 13 [2024-11-14 03:03:41,120 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 03:03:41,127 INFO L225 Difference]: With dead ends: 32 [2024-11-14 03:03:41,128 INFO L226 Difference]: Without dead ends: 17 [2024-11-14 03:03:41,133 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 2 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 0 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2024-11-14 03:03:41,135 INFO L432 NwaCegarLoop]: 18 mSDtfsCounter, 0 mSDsluCounter, 0 mSDsCounter, 0 mSdLazyCounter, 4 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 18 SdHoareTripleChecker+Invalid, 4 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 4 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-14 03:03:41,138 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 18 Invalid, 4 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 4 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-14 03:03:41,153 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 17 states. [2024-11-14 03:03:41,169 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 17 to 17. [2024-11-14 03:03:41,171 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 17 states, 10 states have (on average 1.3) internal successors, (13), 11 states have internal predecessors, (13), 4 states have call successors, (4), 2 states have call predecessors, (4), 2 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2024-11-14 03:03:41,178 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 17 states to 17 states and 20 transitions. [2024-11-14 03:03:41,181 INFO L78 Accepts]: Start accepts. Automaton has 17 states and 20 transitions. Word has length 13 [2024-11-14 03:03:41,182 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 03:03:41,182 INFO L471 AbstractCegarLoop]: Abstraction has 17 states and 20 transitions. [2024-11-14 03:03:41,182 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 2 states have (on average 3.5) internal successors, (7), 2 states have internal predecessors, (7), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2024-11-14 03:03:41,183 INFO L276 IsEmpty]: Start isEmpty. Operand 17 states and 20 transitions. [2024-11-14 03:03:41,184 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 15 [2024-11-14 03:03:41,184 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 03:03:41,187 INFO L215 NwaCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-14 03:03:41,187 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2024-11-14 03:03:41,188 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 03:03:41,188 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 03:03:41,188 INFO L85 PathProgramCache]: Analyzing trace with hash -279128393, now seen corresponding path program 1 times [2024-11-14 03:03:41,189 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 03:03:41,189 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1052687223] [2024-11-14 03:03:41,189 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 03:03:41,189 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 03:03:41,231 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 03:03:41,415 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2024-11-14 03:03:41,416 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 03:03:41,416 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1052687223] [2024-11-14 03:03:41,416 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1052687223] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-14 03:03:41,416 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-14 03:03:41,416 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2024-11-14 03:03:41,416 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1127843973] [2024-11-14 03:03:41,416 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-14 03:03:41,417 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2024-11-14 03:03:41,418 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 03:03:41,419 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2024-11-14 03:03:41,419 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2024-11-14 03:03:41,419 INFO L87 Difference]: Start difference. First operand 17 states and 20 transitions. Second operand has 4 states, 4 states have (on average 2.0) internal successors, (8), 4 states have internal predecessors, (8), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2024-11-14 03:03:41,469 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 03:03:41,470 INFO L93 Difference]: Finished difference Result 26 states and 29 transitions. [2024-11-14 03:03:41,471 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2024-11-14 03:03:41,471 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 2.0) internal successors, (8), 4 states have internal predecessors, (8), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) Word has length 14 [2024-11-14 03:03:41,471 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 03:03:41,472 INFO L225 Difference]: With dead ends: 26 [2024-11-14 03:03:41,473 INFO L226 Difference]: Without dead ends: 19 [2024-11-14 03:03:41,473 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 4 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2024-11-14 03:03:41,474 INFO L432 NwaCegarLoop]: 15 mSDtfsCounter, 3 mSDsluCounter, 24 mSDsCounter, 0 mSdLazyCounter, 14 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 3 SdHoareTripleChecker+Valid, 39 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 03:03:41,474 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [3 Valid, 39 Invalid, 14 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 14 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-14 03:03:41,477 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 19 states. [2024-11-14 03:03:41,481 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 19 to 19. [2024-11-14 03:03:41,482 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 19 states, 12 states have (on average 1.25) internal successors, (15), 13 states have internal predecessors, (15), 4 states have call successors, (4), 2 states have call predecessors, (4), 2 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2024-11-14 03:03:41,483 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 19 states to 19 states and 22 transitions. [2024-11-14 03:03:41,483 INFO L78 Accepts]: Start accepts. Automaton has 19 states and 22 transitions. Word has length 14 [2024-11-14 03:03:41,484 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 03:03:41,484 INFO L471 AbstractCegarLoop]: Abstraction has 19 states and 22 transitions. [2024-11-14 03:03:41,484 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 2.0) internal successors, (8), 4 states have internal predecessors, (8), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2024-11-14 03:03:41,484 INFO L276 IsEmpty]: Start isEmpty. Operand 19 states and 22 transitions. [2024-11-14 03:03:41,485 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 15 [2024-11-14 03:03:41,485 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 03:03:41,485 INFO L215 NwaCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-14 03:03:41,485 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2024-11-14 03:03:41,485 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 03:03:41,486 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 03:03:41,486 INFO L85 PathProgramCache]: Analyzing trace with hash -277340933, now seen corresponding path program 1 times [2024-11-14 03:03:41,486 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 03:03:41,486 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1506177483] [2024-11-14 03:03:41,486 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 03:03:41,487 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 03:03:41,515 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-14 03:03:41,518 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1109401488] [2024-11-14 03:03:41,518 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 03:03:41,519 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 03:03:41,519 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_25b0f514-5f57-40ae-9922-9007e959137d/bin/utaipan-verify-sOmjnqqW8E/z3 [2024-11-14 03:03:41,523 INFO L229 MonitoredProcess]: Starting monitored process 2 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_25b0f514-5f57-40ae-9922-9007e959137d/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-14 03:03:41,525 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_25b0f514-5f57-40ae-9922-9007e959137d/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2024-11-14 03:03:41,606 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 03:03:41,608 INFO L255 TraceCheckSpWp]: Trace formula consists of 59 conjuncts, 9 conjuncts are in the unsatisfiable core [2024-11-14 03:03:41,613 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-14 03:03:41,956 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2024-11-14 03:03:41,957 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-14 03:03:41,957 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 03:03:41,957 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1506177483] [2024-11-14 03:03:41,958 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-14 03:03:41,959 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1109401488] [2024-11-14 03:03:41,960 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1109401488] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-14 03:03:41,960 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-14 03:03:41,960 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-14 03:03:41,961 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [822832149] [2024-11-14 03:03:41,961 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-14 03:03:41,961 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-14 03:03:41,961 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 03:03:41,962 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-14 03:03:41,963 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-14 03:03:41,964 INFO L87 Difference]: Start difference. First operand 19 states and 22 transitions. Second operand has 5 states, 5 states have (on average 1.6) internal successors, (8), 4 states have internal predecessors, (8), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2024-11-14 03:03:43,980 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.95s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-14 03:03:44,000 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 03:03:44,000 INFO L93 Difference]: Finished difference Result 27 states and 31 transitions. [2024-11-14 03:03:44,002 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-14 03:03:44,003 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 1.6) internal successors, (8), 4 states have internal predecessors, (8), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) Word has length 14 [2024-11-14 03:03:44,003 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 03:03:44,003 INFO L225 Difference]: With dead ends: 27 [2024-11-14 03:03:44,003 INFO L226 Difference]: Without dead ends: 25 [2024-11-14 03:03:44,004 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 14 GetRequests, 10 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2024-11-14 03:03:44,005 INFO L432 NwaCegarLoop]: 13 mSDtfsCounter, 3 mSDsluCounter, 37 mSDsCounter, 0 mSdLazyCounter, 29 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 2.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 4 SdHoareTripleChecker+Valid, 50 SdHoareTripleChecker+Invalid, 29 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 29 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 2.0s IncrementalHoareTripleChecker+Time [2024-11-14 03:03:44,005 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [4 Valid, 50 Invalid, 29 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 29 Invalid, 0 Unknown, 0 Unchecked, 2.0s Time] [2024-11-14 03:03:44,006 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 25 states. [2024-11-14 03:03:44,011 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 25 to 24. [2024-11-14 03:03:44,011 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 24 states, 15 states have (on average 1.2) internal successors, (18), 17 states have internal predecessors, (18), 5 states have call successors, (5), 3 states have call predecessors, (5), 3 states have return successors, (4), 3 states have call predecessors, (4), 4 states have call successors, (4) [2024-11-14 03:03:44,012 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 24 states to 24 states and 27 transitions. [2024-11-14 03:03:44,012 INFO L78 Accepts]: Start accepts. Automaton has 24 states and 27 transitions. Word has length 14 [2024-11-14 03:03:44,012 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 03:03:44,012 INFO L471 AbstractCegarLoop]: Abstraction has 24 states and 27 transitions. [2024-11-14 03:03:44,013 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 1.6) internal successors, (8), 4 states have internal predecessors, (8), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2024-11-14 03:03:44,013 INFO L276 IsEmpty]: Start isEmpty. Operand 24 states and 27 transitions. [2024-11-14 03:03:44,013 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 21 [2024-11-14 03:03:44,013 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 03:03:44,013 INFO L215 NwaCegarLoop]: trace histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-14 03:03:44,044 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_25b0f514-5f57-40ae-9922-9007e959137d/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Ended with exit code 0 [2024-11-14 03:03:44,217 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2,2 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_25b0f514-5f57-40ae-9922-9007e959137d/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 03:03:44,217 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 03:03:44,218 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 03:03:44,218 INFO L85 PathProgramCache]: Analyzing trace with hash -144982397, now seen corresponding path program 1 times [2024-11-14 03:03:44,218 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 03:03:44,218 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1639359279] [2024-11-14 03:03:44,218 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 03:03:44,218 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 03:03:44,255 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 03:03:44,638 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 1 proven. 1 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2024-11-14 03:03:44,638 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 03:03:44,638 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1639359279] [2024-11-14 03:03:44,638 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1639359279] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-14 03:03:44,638 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2038864074] [2024-11-14 03:03:44,638 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 03:03:44,638 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 03:03:44,639 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_25b0f514-5f57-40ae-9922-9007e959137d/bin/utaipan-verify-sOmjnqqW8E/z3 [2024-11-14 03:03:44,641 INFO L229 MonitoredProcess]: Starting monitored process 3 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_25b0f514-5f57-40ae-9922-9007e959137d/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-14 03:03:44,644 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_25b0f514-5f57-40ae-9922-9007e959137d/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2024-11-14 03:03:44,707 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 03:03:44,708 INFO L255 TraceCheckSpWp]: Trace formula consists of 70 conjuncts, 10 conjuncts are in the unsatisfiable core [2024-11-14 03:03:44,709 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-14 03:03:44,782 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 1 proven. 1 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2024-11-14 03:03:44,782 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-14 03:03:44,933 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 1 proven. 1 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2024-11-14 03:03:44,933 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2038864074] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-14 03:03:44,933 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1856341582] [2024-11-14 03:03:44,950 INFO L159 IcfgInterpreter]: Started Sifa with 17 locations of interest [2024-11-14 03:03:44,950 INFO L166 IcfgInterpreter]: Building call graph [2024-11-14 03:03:44,953 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2024-11-14 03:03:44,958 INFO L176 IcfgInterpreter]: Starting interpretation [2024-11-14 03:03:44,958 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2024-11-14 03:03:45,991 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 103 for LOIs [2024-11-14 03:03:47,667 INFO L197 IcfgInterpreter]: Interpreting procedure assume_abort_if_not with input of size 92 for LOIs [2024-11-14 03:03:47,714 INFO L180 IcfgInterpreter]: Interpretation finished [2024-11-14 03:04:13,893 WARN L286 SmtUtils]: Spent 5.37s on a formula simplification. DAG size of input: 103 DAG size of output: 73 (called from [L 388] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2024-11-14 03:04:44,271 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSifa [1856341582] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-14 03:04:44,271 INFO L185 FreeRefinementEngine]: Found 1 perfect and 3 imperfect interpolant sequences. [2024-11-14 03:04:44,271 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [15] imperfect sequences [7, 8, 8] total 25 [2024-11-14 03:04:44,272 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [188564976] [2024-11-14 03:04:44,272 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-14 03:04:44,273 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2024-11-14 03:04:44,273 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 03:04:44,275 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2024-11-14 03:04:44,276 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=84, Invalid=504, Unknown=12, NotChecked=0, Total=600 [2024-11-14 03:04:44,277 INFO L87 Difference]: Start difference. First operand 24 states and 27 transitions. Second operand has 16 states, 10 states have (on average 1.1) internal successors, (11), 10 states have internal predecessors, (11), 4 states have call successors, (4), 2 states have call predecessors, (4), 2 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2024-11-14 03:04:46,535 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [] [2024-11-14 03:04:48,646 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2024-11-14 03:04:50,668 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2024-11-14 03:04:52,687 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2024-11-14 03:04:54,714 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2024-11-14 03:04:56,753 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2024-11-14 03:04:58,928 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2024-11-14 03:05:01,070 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.05s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2024-11-14 03:05:01,122 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 03:05:01,122 INFO L93 Difference]: Finished difference Result 32 states and 35 transitions. [2024-11-14 03:05:01,123 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2024-11-14 03:05:01,123 INFO L78 Accepts]: Start accepts. Automaton has has 16 states, 10 states have (on average 1.1) internal successors, (11), 10 states have internal predecessors, (11), 4 states have call successors, (4), 2 states have call predecessors, (4), 2 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) Word has length 20 [2024-11-14 03:05:01,123 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 03:05:01,123 INFO L225 Difference]: With dead ends: 32 [2024-11-14 03:05:01,124 INFO L226 Difference]: Without dead ends: 25 [2024-11-14 03:05:01,124 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 68 GetRequests, 43 SyntacticMatches, 2 SemanticMatches, 23 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 123 ImplicationChecksByTransitivity, 56.7s TimeCoverageRelationStatistics Valid=84, Invalid=504, Unknown=12, NotChecked=0, Total=600 [2024-11-14 03:05:01,125 INFO L432 NwaCegarLoop]: 8 mSDtfsCounter, 2 mSDsluCounter, 39 mSDsCounter, 0 mSdLazyCounter, 150 mSolverCounterSat, 0 mSolverCounterUnsat, 8 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 16.7s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 47 SdHoareTripleChecker+Invalid, 158 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 150 IncrementalHoareTripleChecker+Invalid, 8 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 16.8s IncrementalHoareTripleChecker+Time [2024-11-14 03:05:01,125 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [2 Valid, 47 Invalid, 158 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 150 Invalid, 8 Unknown, 0 Unchecked, 16.8s Time] [2024-11-14 03:05:01,125 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 25 states. [2024-11-14 03:05:01,133 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 25 to 25. [2024-11-14 03:05:01,133 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 25 states, 16 states have (on average 1.1875) internal successors, (19), 17 states have internal predecessors, (19), 5 states have call successors, (5), 3 states have call predecessors, (5), 3 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) [2024-11-14 03:05:01,134 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 25 states to 25 states and 28 transitions. [2024-11-14 03:05:01,134 INFO L78 Accepts]: Start accepts. Automaton has 25 states and 28 transitions. Word has length 20 [2024-11-14 03:05:01,134 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 03:05:01,134 INFO L471 AbstractCegarLoop]: Abstraction has 25 states and 28 transitions. [2024-11-14 03:05:01,134 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 16 states, 10 states have (on average 1.1) internal successors, (11), 10 states have internal predecessors, (11), 4 states have call successors, (4), 2 states have call predecessors, (4), 2 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2024-11-14 03:05:01,135 INFO L276 IsEmpty]: Start isEmpty. Operand 25 states and 28 transitions. [2024-11-14 03:05:01,135 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 23 [2024-11-14 03:05:01,135 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 03:05:01,135 INFO L215 NwaCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-14 03:05:01,155 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_25b0f514-5f57-40ae-9922-9007e959137d/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Ended with exit code 0 [2024-11-14 03:05:01,339 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,3 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_25b0f514-5f57-40ae-9922-9007e959137d/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 03:05:01,340 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 03:05:01,340 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 03:05:01,340 INFO L85 PathProgramCache]: Analyzing trace with hash 568038870, now seen corresponding path program 1 times [2024-11-14 03:05:01,341 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 03:05:01,341 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [621790459] [2024-11-14 03:05:01,341 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 03:05:01,341 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 03:05:01,365 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 03:05:01,506 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 2 proven. 2 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2024-11-14 03:05:01,506 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 03:05:01,506 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [621790459] [2024-11-14 03:05:01,506 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [621790459] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-14 03:05:01,506 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [941753093] [2024-11-14 03:05:01,506 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 03:05:01,507 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 03:05:01,507 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_25b0f514-5f57-40ae-9922-9007e959137d/bin/utaipan-verify-sOmjnqqW8E/z3 [2024-11-14 03:05:01,513 INFO L229 MonitoredProcess]: Starting monitored process 4 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_25b0f514-5f57-40ae-9922-9007e959137d/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-14 03:05:01,514 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_25b0f514-5f57-40ae-9922-9007e959137d/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2024-11-14 03:05:01,566 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 03:05:01,567 INFO L255 TraceCheckSpWp]: Trace formula consists of 75 conjuncts, 5 conjuncts are in the unsatisfiable core [2024-11-14 03:05:01,569 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-14 03:05:01,626 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 2 proven. 2 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2024-11-14 03:05:01,627 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-14 03:05:01,700 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 2 proven. 2 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2024-11-14 03:05:01,701 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [941753093] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-14 03:05:01,701 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1095047191] [2024-11-14 03:05:01,703 INFO L159 IcfgInterpreter]: Started Sifa with 17 locations of interest [2024-11-14 03:05:01,703 INFO L166 IcfgInterpreter]: Building call graph [2024-11-14 03:05:01,703 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2024-11-14 03:05:01,703 INFO L176 IcfgInterpreter]: Starting interpretation [2024-11-14 03:05:01,704 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2024-11-14 03:05:03,256 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 58 for LOIs [2024-11-14 03:05:03,360 INFO L197 IcfgInterpreter]: Interpreting procedure assume_abort_if_not with input of size 96 for LOIs [2024-11-14 03:05:03,425 INFO L180 IcfgInterpreter]: Interpretation finished [2024-11-14 03:05:11,128 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '655#(and (= |__VERIFIER_assert_#in~cond| 0) (or (exists ((|v_ULTIMATE.start_main_~v~0#1_BEFORE_CALL_17| Int) (|v_ULTIMATE.start_main_~u~0#1_BEFORE_CALL_17| Int) (|v_ULTIMATE.start_main_~r~0#1_BEFORE_CALL_14| Int) (|v_ULTIMATE.start_main_~A~0#1_BEFORE_CALL_27| Int)) (and (<= |v_ULTIMATE.start_main_~A~0#1_BEFORE_CALL_27| 2147483647) (<= 1 |#StackHeapBarrier|) (<= 1 ~counter~0) (<= 0 |v_ULTIMATE.start_main_~A~0#1_BEFORE_CALL_27|) (not (= (+ (* 2 |v_ULTIMATE.start_main_~u~0#1_BEFORE_CALL_17|) (* |v_ULTIMATE.start_main_~v~0#1_BEFORE_CALL_17| |v_ULTIMATE.start_main_~v~0#1_BEFORE_CALL_17|) (* |v_ULTIMATE.start_main_~r~0#1_BEFORE_CALL_14| 4) (* |v_ULTIMATE.start_main_~A~0#1_BEFORE_CALL_27| 4)) (+ (* |v_ULTIMATE.start_main_~v~0#1_BEFORE_CALL_17| 2) (* |v_ULTIMATE.start_main_~u~0#1_BEFORE_CALL_17| |v_ULTIMATE.start_main_~u~0#1_BEFORE_CALL_17|)))))) (and (<= 1 |#StackHeapBarrier|) (<= 1 ~counter~0) (exists ((|v_ULTIMATE.start_main_~v~0#1_BEFORE_CALL_16| Int) (|v_ULTIMATE.start_main_~u~0#1_BEFORE_CALL_16| Int) (|v_ULTIMATE.start_main_~A~0#1_BEFORE_CALL_26| Int)) (and (<= 0 |v_ULTIMATE.start_main_~A~0#1_BEFORE_CALL_26|) (not (= (+ (* |v_ULTIMATE.start_main_~u~0#1_BEFORE_CALL_16| |v_ULTIMATE.start_main_~u~0#1_BEFORE_CALL_16|) (* |v_ULTIMATE.start_main_~v~0#1_BEFORE_CALL_16| 2)) (+ (* |v_ULTIMATE.start_main_~A~0#1_BEFORE_CALL_26| 4) (* |v_ULTIMATE.start_main_~v~0#1_BEFORE_CALL_16| |v_ULTIMATE.start_main_~v~0#1_BEFORE_CALL_16|) (* 2 |v_ULTIMATE.start_main_~u~0#1_BEFORE_CALL_16|)))) (<= |v_ULTIMATE.start_main_~A~0#1_BEFORE_CALL_26| 2147483647))))))' at error location [2024-11-14 03:05:11,128 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2024-11-14 03:05:11,128 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-14 03:05:11,128 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 4, 5] total 10 [2024-11-14 03:05:11,129 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [473118418] [2024-11-14 03:05:11,129 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-14 03:05:11,129 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2024-11-14 03:05:11,129 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 03:05:11,130 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2024-11-14 03:05:11,130 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=93, Invalid=411, Unknown=2, NotChecked=0, Total=506 [2024-11-14 03:05:11,131 INFO L87 Difference]: Start difference. First operand 25 states and 28 transitions. Second operand has 10 states, 10 states have (on average 2.9) internal successors, (29), 10 states have internal predecessors, (29), 6 states have call successors, (10), 4 states have call predecessors, (10), 3 states have return successors, (9), 5 states have call predecessors, (9), 5 states have call successors, (9) [2024-11-14 03:05:11,318 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 03:05:11,318 INFO L93 Difference]: Finished difference Result 56 states and 63 transitions. [2024-11-14 03:05:11,319 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2024-11-14 03:05:11,319 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 10 states have (on average 2.9) internal successors, (29), 10 states have internal predecessors, (29), 6 states have call successors, (10), 4 states have call predecessors, (10), 3 states have return successors, (9), 5 states have call predecessors, (9), 5 states have call successors, (9) Word has length 22 [2024-11-14 03:05:11,319 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 03:05:11,320 INFO L225 Difference]: With dead ends: 56 [2024-11-14 03:05:11,320 INFO L226 Difference]: Without dead ends: 49 [2024-11-14 03:05:11,321 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 72 GetRequests, 48 SyntacticMatches, 1 SemanticMatches, 23 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 205 ImplicationChecksByTransitivity, 7.8s TimeCoverageRelationStatistics Valid=106, Invalid=492, Unknown=2, NotChecked=0, Total=600 [2024-11-14 03:05:11,322 INFO L432 NwaCegarLoop]: 15 mSDtfsCounter, 28 mSDsluCounter, 44 mSDsCounter, 0 mSdLazyCounter, 42 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 28 SdHoareTripleChecker+Valid, 59 SdHoareTripleChecker+Invalid, 45 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 42 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-14 03:05:11,322 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [28 Valid, 59 Invalid, 45 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 42 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-14 03:05:11,327 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 49 states. [2024-11-14 03:05:11,344 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 49 to 45. [2024-11-14 03:05:11,345 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 45 states, 30 states have (on average 1.2333333333333334) internal successors, (37), 33 states have internal predecessors, (37), 9 states have call successors, (9), 5 states have call predecessors, (9), 5 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2024-11-14 03:05:11,346 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 45 states to 45 states and 52 transitions. [2024-11-14 03:05:11,348 INFO L78 Accepts]: Start accepts. Automaton has 45 states and 52 transitions. Word has length 22 [2024-11-14 03:05:11,349 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 03:05:11,349 INFO L471 AbstractCegarLoop]: Abstraction has 45 states and 52 transitions. [2024-11-14 03:05:11,349 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 10 states have (on average 2.9) internal successors, (29), 10 states have internal predecessors, (29), 6 states have call successors, (10), 4 states have call predecessors, (10), 3 states have return successors, (9), 5 states have call predecessors, (9), 5 states have call successors, (9) [2024-11-14 03:05:11,349 INFO L276 IsEmpty]: Start isEmpty. Operand 45 states and 52 transitions. [2024-11-14 03:05:11,350 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 23 [2024-11-14 03:05:11,351 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 03:05:11,351 INFO L215 NwaCegarLoop]: trace histogram [2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-14 03:05:11,375 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_25b0f514-5f57-40ae-9922-9007e959137d/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Ended with exit code 0 [2024-11-14 03:05:11,552 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,4 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_25b0f514-5f57-40ae-9922-9007e959137d/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 03:05:11,552 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 03:05:11,552 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 03:05:11,552 INFO L85 PathProgramCache]: Analyzing trace with hash 569826330, now seen corresponding path program 1 times [2024-11-14 03:05:11,552 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 03:05:11,553 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [380343635] [2024-11-14 03:05:11,553 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 03:05:11,553 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 03:05:11,589 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-14 03:05:11,590 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1910216736] [2024-11-14 03:05:11,590 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 03:05:11,590 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 03:05:11,590 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_25b0f514-5f57-40ae-9922-9007e959137d/bin/utaipan-verify-sOmjnqqW8E/z3 [2024-11-14 03:05:11,596 INFO L229 MonitoredProcess]: Starting monitored process 5 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_25b0f514-5f57-40ae-9922-9007e959137d/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-14 03:05:11,598 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_25b0f514-5f57-40ae-9922-9007e959137d/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2024-11-14 03:05:11,657 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 03:05:11,658 INFO L255 TraceCheckSpWp]: Trace formula consists of 75 conjuncts, 18 conjuncts are in the unsatisfiable core [2024-11-14 03:05:11,661 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-14 03:05:18,665 INFO L134 CoverageAnalysis]: Checked inductivity of 7 backedges. 1 proven. 5 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2024-11-14 03:05:18,665 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-14 03:05:22,609 INFO L134 CoverageAnalysis]: Checked inductivity of 7 backedges. 4 proven. 1 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2024-11-14 03:05:22,609 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 03:05:22,609 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [380343635] [2024-11-14 03:05:22,609 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-14 03:05:22,610 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1910216736] [2024-11-14 03:05:22,610 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1910216736] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-14 03:05:22,610 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [202970425] [2024-11-14 03:05:22,612 INFO L159 IcfgInterpreter]: Started Sifa with 16 locations of interest [2024-11-14 03:05:22,612 INFO L166 IcfgInterpreter]: Building call graph [2024-11-14 03:05:22,612 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2024-11-14 03:05:22,612 INFO L176 IcfgInterpreter]: Starting interpretation [2024-11-14 03:05:22,613 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2024-11-14 03:05:23,802 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 37 for LOIs [2024-11-14 03:05:23,833 INFO L197 IcfgInterpreter]: Interpreting procedure assume_abort_if_not with input of size 96 for LOIs [2024-11-14 03:05:23,854 INFO L180 IcfgInterpreter]: Interpretation finished [2024-11-14 03:05:41,152 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '962#(and (= |__VERIFIER_assert_#in~cond| 0) (exists ((|v_ULTIMATE.start_main_~u~0#1_BEFORE_CALL_29| Int) (|v_ULTIMATE.start_main_~v~0#1_BEFORE_CALL_29| Int) (|v_ULTIMATE.start_main_~A~0#1_BEFORE_CALL_47| Int) (|v_ULTIMATE.start_main_~r~0#1_BEFORE_CALL_26| Int)) (and (<= 1 |#StackHeapBarrier|) (<= |v_ULTIMATE.start_main_~A~0#1_BEFORE_CALL_47| 2147483647) (<= 0 |v_ULTIMATE.start_main_~A~0#1_BEFORE_CALL_47|) (not (= (+ (* |v_ULTIMATE.start_main_~r~0#1_BEFORE_CALL_26| 4) (* |v_ULTIMATE.start_main_~v~0#1_BEFORE_CALL_29| |v_ULTIMATE.start_main_~v~0#1_BEFORE_CALL_29|) (* 2 |v_ULTIMATE.start_main_~u~0#1_BEFORE_CALL_29|) (* |v_ULTIMATE.start_main_~A~0#1_BEFORE_CALL_47| 4)) (+ (* |v_ULTIMATE.start_main_~v~0#1_BEFORE_CALL_29| 2) (* |v_ULTIMATE.start_main_~u~0#1_BEFORE_CALL_29| |v_ULTIMATE.start_main_~u~0#1_BEFORE_CALL_29|)))) (<= 1 ~counter~0))))' at error location [2024-11-14 03:05:41,153 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2024-11-14 03:05:41,153 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-14 03:05:41,153 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 7] total 12 [2024-11-14 03:05:41,153 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [253714750] [2024-11-14 03:05:41,153 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-14 03:05:41,153 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2024-11-14 03:05:41,153 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 03:05:41,154 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2024-11-14 03:05:41,154 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=71, Invalid=524, Unknown=5, NotChecked=0, Total=600 [2024-11-14 03:05:41,155 INFO L87 Difference]: Start difference. First operand 45 states and 52 transitions. Second operand has 12 states, 11 states have (on average 2.090909090909091) internal successors, (23), 10 states have internal predecessors, (23), 5 states have call successors, (7), 2 states have call predecessors, (7), 3 states have return successors, (6), 4 states have call predecessors, (6), 3 states have call successors, (6) [2024-11-14 03:05:42,360 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.13s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-14 03:05:44,562 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-14 03:05:52,091 WARN L286 SmtUtils]: Spent 7.43s on a formula simplification. DAG size of input: 49 DAG size of output: 40 (called from [L 388] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2024-11-14 03:05:53,846 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.74s for a HTC check with result VALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-14 03:05:55,864 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-14 03:05:55,936 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 03:05:55,936 INFO L93 Difference]: Finished difference Result 60 states and 66 transitions. [2024-11-14 03:05:55,936 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2024-11-14 03:05:55,937 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 11 states have (on average 2.090909090909091) internal successors, (23), 10 states have internal predecessors, (23), 5 states have call successors, (7), 2 states have call predecessors, (7), 3 states have return successors, (6), 4 states have call predecessors, (6), 3 states have call successors, (6) Word has length 22 [2024-11-14 03:05:55,937 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 03:05:55,938 INFO L225 Difference]: With dead ends: 60 [2024-11-14 03:05:55,938 INFO L226 Difference]: Without dead ends: 52 [2024-11-14 03:05:55,939 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 67 GetRequests, 39 SyntacticMatches, 3 SemanticMatches, 25 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 97 ImplicationChecksByTransitivity, 30.1s TimeCoverageRelationStatistics Valid=82, Invalid=615, Unknown=5, NotChecked=0, Total=702 [2024-11-14 03:05:55,940 INFO L432 NwaCegarLoop]: 13 mSDtfsCounter, 4 mSDsluCounter, 69 mSDsCounter, 0 mSdLazyCounter, 91 mSolverCounterSat, 1 mSolverCounterUnsat, 2 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 7.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 4 SdHoareTripleChecker+Valid, 82 SdHoareTripleChecker+Invalid, 94 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 91 IncrementalHoareTripleChecker+Invalid, 2 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 7.2s IncrementalHoareTripleChecker+Time [2024-11-14 03:05:55,940 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [4 Valid, 82 Invalid, 94 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 91 Invalid, 2 Unknown, 0 Unchecked, 7.2s Time] [2024-11-14 03:05:55,941 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 52 states. [2024-11-14 03:05:55,955 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 52 to 45. [2024-11-14 03:05:55,955 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 45 states, 32 states have (on average 1.125) internal successors, (36), 32 states have internal predecessors, (36), 7 states have call successors, (7), 6 states have call predecessors, (7), 5 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2024-11-14 03:05:55,956 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 45 states to 45 states and 49 transitions. [2024-11-14 03:05:55,957 INFO L78 Accepts]: Start accepts. Automaton has 45 states and 49 transitions. Word has length 22 [2024-11-14 03:05:55,957 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 03:05:55,957 INFO L471 AbstractCegarLoop]: Abstraction has 45 states and 49 transitions. [2024-11-14 03:05:55,957 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 11 states have (on average 2.090909090909091) internal successors, (23), 10 states have internal predecessors, (23), 5 states have call successors, (7), 2 states have call predecessors, (7), 3 states have return successors, (6), 4 states have call predecessors, (6), 3 states have call successors, (6) [2024-11-14 03:05:55,957 INFO L276 IsEmpty]: Start isEmpty. Operand 45 states and 49 transitions. [2024-11-14 03:05:55,958 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 29 [2024-11-14 03:05:55,958 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 03:05:55,958 INFO L215 NwaCegarLoop]: trace histogram [3, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-14 03:05:55,984 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_25b0f514-5f57-40ae-9922-9007e959137d/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Ended with exit code 0 [2024-11-14 03:05:56,158 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 5 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_25b0f514-5f57-40ae-9922-9007e959137d/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable5 [2024-11-14 03:05:56,159 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 03:05:56,159 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 03:05:56,159 INFO L85 PathProgramCache]: Analyzing trace with hash 24144482, now seen corresponding path program 1 times [2024-11-14 03:05:56,159 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 03:05:56,159 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [327693804] [2024-11-14 03:05:56,159 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 03:05:56,160 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 03:05:56,184 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 03:05:56,438 INFO L134 CoverageAnalysis]: Checked inductivity of 14 backedges. 7 proven. 1 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2024-11-14 03:05:56,438 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 03:05:56,438 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [327693804] [2024-11-14 03:05:56,438 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [327693804] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-14 03:05:56,438 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1623002031] [2024-11-14 03:05:56,438 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 03:05:56,439 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 03:05:56,439 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_25b0f514-5f57-40ae-9922-9007e959137d/bin/utaipan-verify-sOmjnqqW8E/z3 [2024-11-14 03:05:56,441 INFO L229 MonitoredProcess]: Starting monitored process 6 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_25b0f514-5f57-40ae-9922-9007e959137d/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-14 03:05:56,444 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_25b0f514-5f57-40ae-9922-9007e959137d/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2024-11-14 03:05:56,506 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 03:05:56,507 INFO L255 TraceCheckSpWp]: Trace formula consists of 86 conjuncts, 10 conjuncts are in the unsatisfiable core [2024-11-14 03:05:56,509 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-14 03:05:56,606 INFO L134 CoverageAnalysis]: Checked inductivity of 14 backedges. 7 proven. 1 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2024-11-14 03:05:56,606 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-14 03:05:56,841 INFO L134 CoverageAnalysis]: Checked inductivity of 14 backedges. 7 proven. 1 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2024-11-14 03:05:56,842 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1623002031] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-14 03:05:56,842 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [118174213] [2024-11-14 03:05:56,845 INFO L159 IcfgInterpreter]: Started Sifa with 17 locations of interest [2024-11-14 03:05:56,846 INFO L166 IcfgInterpreter]: Building call graph [2024-11-14 03:05:56,847 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2024-11-14 03:05:56,847 INFO L176 IcfgInterpreter]: Starting interpretation [2024-11-14 03:05:56,847 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2024-11-14 03:05:57,742 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 54 for LOIs [2024-11-14 03:05:57,786 INFO L197 IcfgInterpreter]: Interpreting procedure assume_abort_if_not with input of size 92 for LOIs [2024-11-14 03:05:57,808 INFO L180 IcfgInterpreter]: Interpretation finished [2024-11-14 03:06:12,188 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '1312#(and (= |__VERIFIER_assert_#in~cond| 0) (exists ((|v_ULTIMATE.start_main_~r~0#1_BEFORE_CALL_36| Int) (|v_ULTIMATE.start_main_~v~0#1_BEFORE_CALL_41| Int) (|v_ULTIMATE.start_main_~u~0#1_BEFORE_CALL_41| Int) (|v_ULTIMATE.start_main_~A~0#1_BEFORE_CALL_65| Int)) (and (<= 1 |#StackHeapBarrier|) (<= 0 |v_ULTIMATE.start_main_~A~0#1_BEFORE_CALL_65|) (<= 1 ~counter~0) (<= |v_ULTIMATE.start_main_~A~0#1_BEFORE_CALL_65| 2147483647) (not (= (+ (* |v_ULTIMATE.start_main_~v~0#1_BEFORE_CALL_41| 2) (* |v_ULTIMATE.start_main_~u~0#1_BEFORE_CALL_41| |v_ULTIMATE.start_main_~u~0#1_BEFORE_CALL_41|)) (+ (* |v_ULTIMATE.start_main_~v~0#1_BEFORE_CALL_41| |v_ULTIMATE.start_main_~v~0#1_BEFORE_CALL_41|) (* |v_ULTIMATE.start_main_~r~0#1_BEFORE_CALL_36| 4) (* 2 |v_ULTIMATE.start_main_~u~0#1_BEFORE_CALL_41|) (* |v_ULTIMATE.start_main_~A~0#1_BEFORE_CALL_65| 4)))))))' at error location [2024-11-14 03:06:12,188 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2024-11-14 03:06:12,188 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-14 03:06:12,188 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 8, 8] total 11 [2024-11-14 03:06:12,189 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1974064033] [2024-11-14 03:06:12,189 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-14 03:06:12,189 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 11 states [2024-11-14 03:06:12,189 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 03:06:12,190 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2024-11-14 03:06:12,191 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=75, Invalid=521, Unknown=4, NotChecked=0, Total=600 [2024-11-14 03:06:12,191 INFO L87 Difference]: Start difference. First operand 45 states and 49 transitions. Second operand has 11 states, 10 states have (on average 2.1) internal successors, (21), 8 states have internal predecessors, (21), 2 states have call successors, (5), 3 states have call predecessors, (5), 2 states have return successors, (5), 3 states have call predecessors, (5), 1 states have call successors, (5) [2024-11-14 03:06:12,393 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 03:06:12,394 INFO L93 Difference]: Finished difference Result 50 states and 53 transitions. [2024-11-14 03:06:12,397 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2024-11-14 03:06:12,398 INFO L78 Accepts]: Start accepts. Automaton has has 11 states, 10 states have (on average 2.1) internal successors, (21), 8 states have internal predecessors, (21), 2 states have call successors, (5), 3 states have call predecessors, (5), 2 states have return successors, (5), 3 states have call predecessors, (5), 1 states have call successors, (5) Word has length 28 [2024-11-14 03:06:12,398 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 03:06:12,398 INFO L225 Difference]: With dead ends: 50 [2024-11-14 03:06:12,399 INFO L226 Difference]: Without dead ends: 45 [2024-11-14 03:06:12,399 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 92 GetRequests, 66 SyntacticMatches, 2 SemanticMatches, 24 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 125 ImplicationChecksByTransitivity, 14.6s TimeCoverageRelationStatistics Valid=83, Invalid=563, Unknown=4, NotChecked=0, Total=650 [2024-11-14 03:06:12,400 INFO L432 NwaCegarLoop]: 13 mSDtfsCounter, 10 mSDsluCounter, 53 mSDsCounter, 0 mSdLazyCounter, 48 mSolverCounterSat, 6 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 10 SdHoareTripleChecker+Valid, 66 SdHoareTripleChecker+Invalid, 54 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 6 IncrementalHoareTripleChecker+Valid, 48 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-11-14 03:06:12,400 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [10 Valid, 66 Invalid, 54 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [6 Valid, 48 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-11-14 03:06:12,401 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 45 states. [2024-11-14 03:06:12,419 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 45 to 45. [2024-11-14 03:06:12,419 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 45 states, 32 states have (on average 1.03125) internal successors, (33), 32 states have internal predecessors, (33), 7 states have call successors, (7), 6 states have call predecessors, (7), 5 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2024-11-14 03:06:12,420 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 45 states to 45 states and 46 transitions. [2024-11-14 03:06:12,420 INFO L78 Accepts]: Start accepts. Automaton has 45 states and 46 transitions. Word has length 28 [2024-11-14 03:06:12,420 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 03:06:12,421 INFO L471 AbstractCegarLoop]: Abstraction has 45 states and 46 transitions. [2024-11-14 03:06:12,421 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 11 states, 10 states have (on average 2.1) internal successors, (21), 8 states have internal predecessors, (21), 2 states have call successors, (5), 3 states have call predecessors, (5), 2 states have return successors, (5), 3 states have call predecessors, (5), 1 states have call successors, (5) [2024-11-14 03:06:12,421 INFO L276 IsEmpty]: Start isEmpty. Operand 45 states and 46 transitions. [2024-11-14 03:06:12,422 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 47 [2024-11-14 03:06:12,422 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 03:06:12,422 INFO L215 NwaCegarLoop]: trace histogram [5, 5, 4, 4, 4, 4, 4, 4, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-14 03:06:12,443 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_25b0f514-5f57-40ae-9922-9007e959137d/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Ended with exit code 0 [2024-11-14 03:06:12,623 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,6 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_25b0f514-5f57-40ae-9922-9007e959137d/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 03:06:12,623 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 03:06:12,623 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 03:06:12,624 INFO L85 PathProgramCache]: Analyzing trace with hash 351435059, now seen corresponding path program 2 times [2024-11-14 03:06:12,624 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 03:06:12,624 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [776461828] [2024-11-14 03:06:12,624 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 03:06:12,624 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 03:06:12,643 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 03:06:12,961 INFO L134 CoverageAnalysis]: Checked inductivity of 66 backedges. 8 proven. 32 refuted. 0 times theorem prover too weak. 26 trivial. 0 not checked. [2024-11-14 03:06:12,961 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 03:06:12,961 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [776461828] [2024-11-14 03:06:12,961 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [776461828] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-14 03:06:12,961 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1065589449] [2024-11-14 03:06:12,962 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-14 03:06:12,962 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 03:06:12,962 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_25b0f514-5f57-40ae-9922-9007e959137d/bin/utaipan-verify-sOmjnqqW8E/z3 [2024-11-14 03:06:12,964 INFO L229 MonitoredProcess]: Starting monitored process 7 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_25b0f514-5f57-40ae-9922-9007e959137d/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-14 03:06:12,965 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_25b0f514-5f57-40ae-9922-9007e959137d/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2024-11-14 03:06:13,046 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 5 check-sat command(s) [2024-11-14 03:06:13,046 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-14 03:06:13,047 INFO L255 TraceCheckSpWp]: Trace formula consists of 123 conjuncts, 11 conjuncts are in the unsatisfiable core [2024-11-14 03:06:13,049 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-14 03:06:13,190 INFO L134 CoverageAnalysis]: Checked inductivity of 66 backedges. 8 proven. 56 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2024-11-14 03:06:13,190 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-14 03:06:13,349 INFO L134 CoverageAnalysis]: Checked inductivity of 66 backedges. 8 proven. 32 refuted. 0 times theorem prover too weak. 26 trivial. 0 not checked. [2024-11-14 03:06:13,349 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1065589449] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-14 03:06:13,349 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1934359065] [2024-11-14 03:06:13,351 INFO L159 IcfgInterpreter]: Started Sifa with 17 locations of interest [2024-11-14 03:06:13,351 INFO L166 IcfgInterpreter]: Building call graph [2024-11-14 03:06:13,351 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2024-11-14 03:06:13,351 INFO L176 IcfgInterpreter]: Starting interpretation [2024-11-14 03:06:13,351 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2024-11-14 03:06:14,282 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 58 for LOIs [2024-11-14 03:06:14,345 INFO L197 IcfgInterpreter]: Interpreting procedure assume_abort_if_not with input of size 92 for LOIs [2024-11-14 03:06:14,361 INFO L180 IcfgInterpreter]: Interpretation finished [2024-11-14 03:06:23,650 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '1757#(and (or (and (<= 1 |#StackHeapBarrier|) (<= 1 ~counter~0) (exists ((|v_ULTIMATE.start_main_~u~0#1_BEFORE_CALL_50| Int) (|v_ULTIMATE.start_main_~v~0#1_BEFORE_CALL_50| Int) (|v_ULTIMATE.start_main_~A~0#1_BEFORE_CALL_80| Int)) (and (<= |v_ULTIMATE.start_main_~A~0#1_BEFORE_CALL_80| 2147483647) (<= 0 |v_ULTIMATE.start_main_~A~0#1_BEFORE_CALL_80|) (not (= (+ (* |v_ULTIMATE.start_main_~u~0#1_BEFORE_CALL_50| |v_ULTIMATE.start_main_~u~0#1_BEFORE_CALL_50|) (* |v_ULTIMATE.start_main_~v~0#1_BEFORE_CALL_50| 2)) (+ (* 2 |v_ULTIMATE.start_main_~u~0#1_BEFORE_CALL_50|) (* |v_ULTIMATE.start_main_~v~0#1_BEFORE_CALL_50| |v_ULTIMATE.start_main_~v~0#1_BEFORE_CALL_50|) (* |v_ULTIMATE.start_main_~A~0#1_BEFORE_CALL_80| 4))))))) (exists ((|v_ULTIMATE.start_main_~r~0#1_BEFORE_CALL_45| Int) (|v_ULTIMATE.start_main_~v~0#1_BEFORE_CALL_51| Int) (|v_ULTIMATE.start_main_~A~0#1_BEFORE_CALL_81| Int) (|v_ULTIMATE.start_main_~u~0#1_BEFORE_CALL_51| Int)) (and (<= 1 |#StackHeapBarrier|) (<= 0 |v_ULTIMATE.start_main_~A~0#1_BEFORE_CALL_81|) (<= 1 ~counter~0) (not (= (+ (* |v_ULTIMATE.start_main_~v~0#1_BEFORE_CALL_51| 2) (* |v_ULTIMATE.start_main_~u~0#1_BEFORE_CALL_51| |v_ULTIMATE.start_main_~u~0#1_BEFORE_CALL_51|)) (+ (* |v_ULTIMATE.start_main_~A~0#1_BEFORE_CALL_81| 4) (* |v_ULTIMATE.start_main_~v~0#1_BEFORE_CALL_51| |v_ULTIMATE.start_main_~v~0#1_BEFORE_CALL_51|) (* |v_ULTIMATE.start_main_~r~0#1_BEFORE_CALL_45| 4) (* 2 |v_ULTIMATE.start_main_~u~0#1_BEFORE_CALL_51|)))) (<= |v_ULTIMATE.start_main_~A~0#1_BEFORE_CALL_81| 2147483647)))) (= |__VERIFIER_assert_#in~cond| 0))' at error location [2024-11-14 03:06:23,651 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2024-11-14 03:06:23,651 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-14 03:06:23,651 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 7, 8] total 16 [2024-11-14 03:06:23,651 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1779126792] [2024-11-14 03:06:23,651 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-14 03:06:23,651 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2024-11-14 03:06:23,652 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 03:06:23,652 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2024-11-14 03:06:23,653 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=187, Invalid=623, Unknown=2, NotChecked=0, Total=812 [2024-11-14 03:06:23,653 INFO L87 Difference]: Start difference. First operand 45 states and 46 transitions. Second operand has 16 states, 16 states have (on average 3.5) internal successors, (56), 16 states have internal predecessors, (56), 12 states have call successors, (19), 7 states have call predecessors, (19), 6 states have return successors, (18), 11 states have call predecessors, (18), 11 states have call successors, (18) [2024-11-14 03:06:24,229 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 03:06:24,229 INFO L93 Difference]: Finished difference Result 98 states and 104 transitions. [2024-11-14 03:06:24,230 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 22 states. [2024-11-14 03:06:24,230 INFO L78 Accepts]: Start accepts. Automaton has has 16 states, 16 states have (on average 3.5) internal successors, (56), 16 states have internal predecessors, (56), 12 states have call successors, (19), 7 states have call predecessors, (19), 6 states have return successors, (18), 11 states have call predecessors, (18), 11 states have call successors, (18) Word has length 46 [2024-11-14 03:06:24,231 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 03:06:24,232 INFO L225 Difference]: With dead ends: 98 [2024-11-14 03:06:24,232 INFO L226 Difference]: Without dead ends: 93 [2024-11-14 03:06:24,233 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 153 GetRequests, 114 SyntacticMatches, 4 SemanticMatches, 35 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 532 ImplicationChecksByTransitivity, 9.8s TimeCoverageRelationStatistics Valid=287, Invalid=1043, Unknown=2, NotChecked=0, Total=1332 [2024-11-14 03:06:24,234 INFO L432 NwaCegarLoop]: 14 mSDtfsCounter, 50 mSDsluCounter, 57 mSDsCounter, 0 mSdLazyCounter, 60 mSolverCounterSat, 9 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 50 SdHoareTripleChecker+Valid, 71 SdHoareTripleChecker+Invalid, 69 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 9 IncrementalHoareTripleChecker+Valid, 60 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-11-14 03:06:24,234 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [50 Valid, 71 Invalid, 69 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [9 Valid, 60 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-11-14 03:06:24,235 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 93 states. [2024-11-14 03:06:24,259 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 93 to 93. [2024-11-14 03:06:24,260 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 93 states, 68 states have (on average 1.0147058823529411) internal successors, (69), 68 states have internal predecessors, (69), 13 states have call successors, (13), 12 states have call predecessors, (13), 11 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) [2024-11-14 03:06:24,261 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 93 states to 93 states and 94 transitions. [2024-11-14 03:06:24,262 INFO L78 Accepts]: Start accepts. Automaton has 93 states and 94 transitions. Word has length 46 [2024-11-14 03:06:24,262 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 03:06:24,262 INFO L471 AbstractCegarLoop]: Abstraction has 93 states and 94 transitions. [2024-11-14 03:06:24,263 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 16 states, 16 states have (on average 3.5) internal successors, (56), 16 states have internal predecessors, (56), 12 states have call successors, (19), 7 states have call predecessors, (19), 6 states have return successors, (18), 11 states have call predecessors, (18), 11 states have call successors, (18) [2024-11-14 03:06:24,263 INFO L276 IsEmpty]: Start isEmpty. Operand 93 states and 94 transitions. [2024-11-14 03:06:24,265 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 95 [2024-11-14 03:06:24,265 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 03:06:24,266 INFO L215 NwaCegarLoop]: trace histogram [11, 11, 10, 10, 10, 10, 10, 10, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-14 03:06:24,284 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_25b0f514-5f57-40ae-9922-9007e959137d/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Ended with exit code 0 [2024-11-14 03:06:24,470 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,7 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_25b0f514-5f57-40ae-9922-9007e959137d/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 03:06:24,470 INFO L396 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 03:06:24,471 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 03:06:24,471 INFO L85 PathProgramCache]: Analyzing trace with hash -2021774611, now seen corresponding path program 3 times [2024-11-14 03:06:24,471 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 03:06:24,471 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [433186870] [2024-11-14 03:06:24,471 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 03:06:24,471 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 03:06:24,506 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 03:06:25,236 INFO L134 CoverageAnalysis]: Checked inductivity of 402 backedges. 20 proven. 200 refuted. 0 times theorem prover too weak. 182 trivial. 0 not checked. [2024-11-14 03:06:25,236 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 03:06:25,236 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [433186870] [2024-11-14 03:06:25,236 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [433186870] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-14 03:06:25,237 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1946600924] [2024-11-14 03:06:25,237 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2024-11-14 03:06:25,237 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 03:06:25,237 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_25b0f514-5f57-40ae-9922-9007e959137d/bin/utaipan-verify-sOmjnqqW8E/z3 [2024-11-14 03:06:25,239 INFO L229 MonitoredProcess]: Starting monitored process 8 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_25b0f514-5f57-40ae-9922-9007e959137d/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-14 03:06:25,241 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_25b0f514-5f57-40ae-9922-9007e959137d/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2024-11-14 03:06:25,345 INFO L227 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2024-11-14 03:06:25,345 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-14 03:06:25,347 INFO L255 TraceCheckSpWp]: Trace formula consists of 219 conjuncts, 23 conjuncts are in the unsatisfiable core [2024-11-14 03:06:25,350 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-14 03:06:25,617 INFO L134 CoverageAnalysis]: Checked inductivity of 402 backedges. 20 proven. 380 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2024-11-14 03:06:25,617 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-14 03:06:26,152 INFO L134 CoverageAnalysis]: Checked inductivity of 402 backedges. 20 proven. 200 refuted. 0 times theorem prover too weak. 182 trivial. 0 not checked. [2024-11-14 03:06:26,152 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1946600924] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-14 03:06:26,153 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [2032656683] [2024-11-14 03:06:26,155 INFO L159 IcfgInterpreter]: Started Sifa with 17 locations of interest [2024-11-14 03:06:26,155 INFO L166 IcfgInterpreter]: Building call graph [2024-11-14 03:06:26,155 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2024-11-14 03:06:26,155 INFO L176 IcfgInterpreter]: Starting interpretation [2024-11-14 03:06:26,156 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2024-11-14 03:06:27,110 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 58 for LOIs [2024-11-14 03:06:27,165 INFO L197 IcfgInterpreter]: Interpreting procedure assume_abort_if_not with input of size 96 for LOIs [2024-11-14 03:06:27,189 INFO L180 IcfgInterpreter]: Interpretation finished [2024-11-14 03:06:36,594 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '2659#(and (or (and (<= 1 |#StackHeapBarrier|) (exists ((|v_ULTIMATE.start_main_~v~0#1_BEFORE_CALL_60| Int) (|v_ULTIMATE.start_main_~u~0#1_BEFORE_CALL_60| Int) (|v_ULTIMATE.start_main_~A~0#1_BEFORE_CALL_96| Int)) (and (<= |v_ULTIMATE.start_main_~A~0#1_BEFORE_CALL_96| 2147483647) (not (= (+ (* |v_ULTIMATE.start_main_~v~0#1_BEFORE_CALL_60| 2) (* |v_ULTIMATE.start_main_~u~0#1_BEFORE_CALL_60| |v_ULTIMATE.start_main_~u~0#1_BEFORE_CALL_60|)) (+ (* |v_ULTIMATE.start_main_~v~0#1_BEFORE_CALL_60| |v_ULTIMATE.start_main_~v~0#1_BEFORE_CALL_60|) (* 2 |v_ULTIMATE.start_main_~u~0#1_BEFORE_CALL_60|) (* |v_ULTIMATE.start_main_~A~0#1_BEFORE_CALL_96| 4)))) (<= 0 |v_ULTIMATE.start_main_~A~0#1_BEFORE_CALL_96|))) (<= 1 ~counter~0)) (exists ((|v_ULTIMATE.start_main_~u~0#1_BEFORE_CALL_61| Int) (|v_ULTIMATE.start_main_~v~0#1_BEFORE_CALL_61| Int) (|v_ULTIMATE.start_main_~r~0#1_BEFORE_CALL_54| Int) (|v_ULTIMATE.start_main_~A~0#1_BEFORE_CALL_97| Int)) (and (<= 1 |#StackHeapBarrier|) (<= |v_ULTIMATE.start_main_~A~0#1_BEFORE_CALL_97| 2147483647) (<= 1 ~counter~0) (not (= (+ (* |v_ULTIMATE.start_main_~v~0#1_BEFORE_CALL_61| 2) (* |v_ULTIMATE.start_main_~u~0#1_BEFORE_CALL_61| |v_ULTIMATE.start_main_~u~0#1_BEFORE_CALL_61|)) (+ (* |v_ULTIMATE.start_main_~v~0#1_BEFORE_CALL_61| |v_ULTIMATE.start_main_~v~0#1_BEFORE_CALL_61|) (* |v_ULTIMATE.start_main_~r~0#1_BEFORE_CALL_54| 4) (* |v_ULTIMATE.start_main_~A~0#1_BEFORE_CALL_97| 4) (* 2 |v_ULTIMATE.start_main_~u~0#1_BEFORE_CALL_61|)))) (<= 0 |v_ULTIMATE.start_main_~A~0#1_BEFORE_CALL_97|)))) (= |__VERIFIER_assert_#in~cond| 0))' at error location [2024-11-14 03:06:36,594 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2024-11-14 03:06:36,594 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-14 03:06:36,594 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [15, 13, 14] total 28 [2024-11-14 03:06:36,594 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1352567277] [2024-11-14 03:06:36,594 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-14 03:06:36,595 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 28 states [2024-11-14 03:06:36,595 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 03:06:36,596 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 28 interpolants. [2024-11-14 03:06:36,597 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=480, Invalid=1158, Unknown=2, NotChecked=0, Total=1640 [2024-11-14 03:06:36,597 INFO L87 Difference]: Start difference. First operand 93 states and 94 transitions. Second operand has 28 states, 28 states have (on average 3.9285714285714284) internal successors, (110), 28 states have internal predecessors, (110), 24 states have call successors, (37), 13 states have call predecessors, (37), 12 states have return successors, (36), 23 states have call predecessors, (36), 23 states have call successors, (36) [2024-11-14 03:06:38,367 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 03:06:38,367 INFO L93 Difference]: Finished difference Result 194 states and 206 transitions. [2024-11-14 03:06:38,368 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 46 states. [2024-11-14 03:06:38,368 INFO L78 Accepts]: Start accepts. Automaton has has 28 states, 28 states have (on average 3.9285714285714284) internal successors, (110), 28 states have internal predecessors, (110), 24 states have call successors, (37), 13 states have call predecessors, (37), 12 states have return successors, (36), 23 states have call predecessors, (36), 23 states have call successors, (36) Word has length 94 [2024-11-14 03:06:38,369 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 03:06:38,370 INFO L225 Difference]: With dead ends: 194 [2024-11-14 03:06:38,370 INFO L226 Difference]: Without dead ends: 189 [2024-11-14 03:06:38,372 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 315 GetRequests, 256 SyntacticMatches, 0 SemanticMatches, 59 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1045 ImplicationChecksByTransitivity, 11.2s TimeCoverageRelationStatistics Valid=970, Invalid=2688, Unknown=2, NotChecked=0, Total=3660 [2024-11-14 03:06:38,373 INFO L432 NwaCegarLoop]: 14 mSDtfsCounter, 83 mSDsluCounter, 109 mSDsCounter, 0 mSdLazyCounter, 131 mSolverCounterSat, 12 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 83 SdHoareTripleChecker+Valid, 123 SdHoareTripleChecker+Invalid, 143 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 12 IncrementalHoareTripleChecker+Valid, 131 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2024-11-14 03:06:38,373 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [83 Valid, 123 Invalid, 143 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [12 Valid, 131 Invalid, 0 Unknown, 0 Unchecked, 0.4s Time] [2024-11-14 03:06:38,374 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 189 states. [2024-11-14 03:06:38,411 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 189 to 189. [2024-11-14 03:06:38,411 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 189 states, 140 states have (on average 1.0071428571428571) internal successors, (141), 140 states have internal predecessors, (141), 25 states have call successors, (25), 24 states have call predecessors, (25), 23 states have return successors, (24), 24 states have call predecessors, (24), 24 states have call successors, (24) [2024-11-14 03:06:38,414 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 189 states to 189 states and 190 transitions. [2024-11-14 03:06:38,416 INFO L78 Accepts]: Start accepts. Automaton has 189 states and 190 transitions. Word has length 94 [2024-11-14 03:06:38,417 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 03:06:38,417 INFO L471 AbstractCegarLoop]: Abstraction has 189 states and 190 transitions. [2024-11-14 03:06:38,417 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 28 states, 28 states have (on average 3.9285714285714284) internal successors, (110), 28 states have internal predecessors, (110), 24 states have call successors, (37), 13 states have call predecessors, (37), 12 states have return successors, (36), 23 states have call predecessors, (36), 23 states have call successors, (36) [2024-11-14 03:06:38,418 INFO L276 IsEmpty]: Start isEmpty. Operand 189 states and 190 transitions. [2024-11-14 03:06:38,421 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 191 [2024-11-14 03:06:38,421 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 03:06:38,421 INFO L215 NwaCegarLoop]: trace histogram [23, 23, 22, 22, 22, 22, 22, 22, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-14 03:06:38,439 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_25b0f514-5f57-40ae-9922-9007e959137d/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Ended with exit code 0 [2024-11-14 03:06:38,625 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 8 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_25b0f514-5f57-40ae-9922-9007e959137d/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable8 [2024-11-14 03:06:38,625 INFO L396 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 03:06:38,626 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 03:06:38,626 INFO L85 PathProgramCache]: Analyzing trace with hash 1780038241, now seen corresponding path program 4 times [2024-11-14 03:06:38,626 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 03:06:38,626 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [557701749] [2024-11-14 03:06:38,626 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 03:06:38,626 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 03:06:38,695 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 03:06:41,364 INFO L134 CoverageAnalysis]: Checked inductivity of 1938 backedges. 44 proven. 968 refuted. 0 times theorem prover too weak. 926 trivial. 0 not checked. [2024-11-14 03:06:41,364 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 03:06:41,364 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [557701749] [2024-11-14 03:06:41,364 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [557701749] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-14 03:06:41,365 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [778765513] [2024-11-14 03:06:41,365 INFO L93 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2024-11-14 03:06:41,365 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 03:06:41,365 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_25b0f514-5f57-40ae-9922-9007e959137d/bin/utaipan-verify-sOmjnqqW8E/z3 [2024-11-14 03:06:41,367 INFO L229 MonitoredProcess]: Starting monitored process 9 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_25b0f514-5f57-40ae-9922-9007e959137d/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-14 03:06:41,370 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_25b0f514-5f57-40ae-9922-9007e959137d/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2024-11-14 03:06:41,518 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 03:06:41,521 INFO L255 TraceCheckSpWp]: Trace formula consists of 411 conjuncts, 47 conjuncts are in the unsatisfiable core [2024-11-14 03:06:41,527 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-14 03:06:42,143 INFO L134 CoverageAnalysis]: Checked inductivity of 1938 backedges. 44 proven. 1892 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2024-11-14 03:06:42,143 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-14 03:06:44,875 INFO L134 CoverageAnalysis]: Checked inductivity of 1938 backedges. 44 proven. 968 refuted. 0 times theorem prover too weak. 926 trivial. 0 not checked. [2024-11-14 03:06:44,876 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [778765513] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-14 03:06:44,876 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [148166478] [2024-11-14 03:06:44,878 INFO L159 IcfgInterpreter]: Started Sifa with 17 locations of interest [2024-11-14 03:06:44,878 INFO L166 IcfgInterpreter]: Building call graph [2024-11-14 03:06:44,878 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2024-11-14 03:06:44,879 INFO L176 IcfgInterpreter]: Starting interpretation [2024-11-14 03:06:44,879 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2024-11-14 03:06:45,967 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 58 for LOIs [2024-11-14 03:06:46,049 INFO L197 IcfgInterpreter]: Interpreting procedure assume_abort_if_not with input of size 92 for LOIs [2024-11-14 03:06:46,079 INFO L180 IcfgInterpreter]: Interpretation finished [2024-11-14 03:06:56,501 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '4473#(and (or (exists ((|v_ULTIMATE.start_main_~v~0#1_BEFORE_CALL_71| Int) (|v_ULTIMATE.start_main_~u~0#1_BEFORE_CALL_71| Int) (|v_ULTIMATE.start_main_~A~0#1_BEFORE_CALL_113| Int) (|v_ULTIMATE.start_main_~r~0#1_BEFORE_CALL_63| Int)) (and (<= 1 |#StackHeapBarrier|) (<= 0 |v_ULTIMATE.start_main_~A~0#1_BEFORE_CALL_113|) (not (= (+ (* |v_ULTIMATE.start_main_~v~0#1_BEFORE_CALL_71| 2) (* |v_ULTIMATE.start_main_~u~0#1_BEFORE_CALL_71| |v_ULTIMATE.start_main_~u~0#1_BEFORE_CALL_71|)) (+ (* |v_ULTIMATE.start_main_~r~0#1_BEFORE_CALL_63| 4) (* 2 |v_ULTIMATE.start_main_~u~0#1_BEFORE_CALL_71|) (* |v_ULTIMATE.start_main_~A~0#1_BEFORE_CALL_113| 4) (* |v_ULTIMATE.start_main_~v~0#1_BEFORE_CALL_71| |v_ULTIMATE.start_main_~v~0#1_BEFORE_CALL_71|)))) (<= 1 ~counter~0) (<= |v_ULTIMATE.start_main_~A~0#1_BEFORE_CALL_113| 2147483647))) (and (<= 1 |#StackHeapBarrier|) (exists ((|v_ULTIMATE.start_main_~v~0#1_BEFORE_CALL_70| Int) (|v_ULTIMATE.start_main_~A~0#1_BEFORE_CALL_112| Int) (|v_ULTIMATE.start_main_~u~0#1_BEFORE_CALL_70| Int)) (and (not (= (+ (* 2 |v_ULTIMATE.start_main_~u~0#1_BEFORE_CALL_70|) (* |v_ULTIMATE.start_main_~A~0#1_BEFORE_CALL_112| 4) (* |v_ULTIMATE.start_main_~v~0#1_BEFORE_CALL_70| |v_ULTIMATE.start_main_~v~0#1_BEFORE_CALL_70|)) (+ (* |v_ULTIMATE.start_main_~v~0#1_BEFORE_CALL_70| 2) (* |v_ULTIMATE.start_main_~u~0#1_BEFORE_CALL_70| |v_ULTIMATE.start_main_~u~0#1_BEFORE_CALL_70|)))) (<= |v_ULTIMATE.start_main_~A~0#1_BEFORE_CALL_112| 2147483647) (<= 0 |v_ULTIMATE.start_main_~A~0#1_BEFORE_CALL_112|))) (<= 1 ~counter~0))) (= |__VERIFIER_assert_#in~cond| 0))' at error location [2024-11-14 03:06:56,501 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2024-11-14 03:06:56,501 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-14 03:06:56,501 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [27, 25, 26] total 52 [2024-11-14 03:06:56,501 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1866579090] [2024-11-14 03:06:56,501 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-14 03:06:56,503 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 52 states [2024-11-14 03:06:56,503 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 03:06:56,505 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 52 interpolants. [2024-11-14 03:06:56,506 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1500, Invalid=2658, Unknown=2, NotChecked=0, Total=4160 [2024-11-14 03:06:56,507 INFO L87 Difference]: Start difference. First operand 189 states and 190 transitions. Second operand has 52 states, 52 states have (on average 4.1923076923076925) internal successors, (218), 52 states have internal predecessors, (218), 48 states have call successors, (73), 25 states have call predecessors, (73), 24 states have return successors, (72), 47 states have call predecessors, (72), 47 states have call successors, (72) [2024-11-14 03:07:01,541 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 03:07:01,541 INFO L93 Difference]: Finished difference Result 386 states and 410 transitions. [2024-11-14 03:07:01,542 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 94 states. [2024-11-14 03:07:01,542 INFO L78 Accepts]: Start accepts. Automaton has has 52 states, 52 states have (on average 4.1923076923076925) internal successors, (218), 52 states have internal predecessors, (218), 48 states have call successors, (73), 25 states have call predecessors, (73), 24 states have return successors, (72), 47 states have call predecessors, (72), 47 states have call successors, (72) Word has length 190 [2024-11-14 03:07:01,543 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 03:07:01,550 INFO L225 Difference]: With dead ends: 386 [2024-11-14 03:07:01,550 INFO L226 Difference]: Without dead ends: 381 [2024-11-14 03:07:01,553 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 639 GetRequests, 532 SyntacticMatches, 0 SemanticMatches, 107 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2815 ImplicationChecksByTransitivity, 17.5s TimeCoverageRelationStatistics Valid=3634, Invalid=8136, Unknown=2, NotChecked=0, Total=11772 [2024-11-14 03:07:01,555 INFO L432 NwaCegarLoop]: 14 mSDtfsCounter, 221 mSDsluCounter, 180 mSDsCounter, 0 mSdLazyCounter, 256 mSolverCounterSat, 42 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.8s Time, 0 mProtectedPredicate, 0 mProtectedAction, 221 SdHoareTripleChecker+Valid, 194 SdHoareTripleChecker+Invalid, 298 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 42 IncrementalHoareTripleChecker+Valid, 256 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.9s IncrementalHoareTripleChecker+Time [2024-11-14 03:07:01,555 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [221 Valid, 194 Invalid, 298 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [42 Valid, 256 Invalid, 0 Unknown, 0 Unchecked, 0.9s Time] [2024-11-14 03:07:01,558 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 381 states. [2024-11-14 03:07:01,621 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 381 to 381. [2024-11-14 03:07:01,622 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 381 states, 284 states have (on average 1.0035211267605635) internal successors, (285), 284 states have internal predecessors, (285), 49 states have call successors, (49), 48 states have call predecessors, (49), 47 states have return successors, (48), 48 states have call predecessors, (48), 48 states have call successors, (48) [2024-11-14 03:07:01,625 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 381 states to 381 states and 382 transitions. [2024-11-14 03:07:01,625 INFO L78 Accepts]: Start accepts. Automaton has 381 states and 382 transitions. Word has length 190 [2024-11-14 03:07:01,627 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 03:07:01,629 INFO L471 AbstractCegarLoop]: Abstraction has 381 states and 382 transitions. [2024-11-14 03:07:01,629 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 52 states, 52 states have (on average 4.1923076923076925) internal successors, (218), 52 states have internal predecessors, (218), 48 states have call successors, (73), 25 states have call predecessors, (73), 24 states have return successors, (72), 47 states have call predecessors, (72), 47 states have call successors, (72) [2024-11-14 03:07:01,629 INFO L276 IsEmpty]: Start isEmpty. Operand 381 states and 382 transitions. [2024-11-14 03:07:01,641 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 383 [2024-11-14 03:07:01,642 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 03:07:01,642 INFO L215 NwaCegarLoop]: trace histogram [47, 47, 46, 46, 46, 46, 46, 46, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-14 03:07:01,665 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_25b0f514-5f57-40ae-9922-9007e959137d/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Ended with exit code 0 [2024-11-14 03:07:01,842 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 9 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_25b0f514-5f57-40ae-9922-9007e959137d/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable9 [2024-11-14 03:07:01,843 INFO L396 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 03:07:01,843 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 03:07:01,843 INFO L85 PathProgramCache]: Analyzing trace with hash -843183799, now seen corresponding path program 5 times [2024-11-14 03:07:01,843 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 03:07:01,843 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [452241072] [2024-11-14 03:07:01,844 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 03:07:01,844 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 03:07:01,956 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 03:07:10,803 INFO L134 CoverageAnalysis]: Checked inductivity of 8466 backedges. 92 proven. 4232 refuted. 0 times theorem prover too weak. 4142 trivial. 0 not checked. [2024-11-14 03:07:10,803 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 03:07:10,803 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [452241072] [2024-11-14 03:07:10,803 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [452241072] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-14 03:07:10,803 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [524482414] [2024-11-14 03:07:10,804 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-14 03:07:10,804 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 03:07:10,804 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_25b0f514-5f57-40ae-9922-9007e959137d/bin/utaipan-verify-sOmjnqqW8E/z3 [2024-11-14 03:07:10,806 INFO L229 MonitoredProcess]: Starting monitored process 10 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_25b0f514-5f57-40ae-9922-9007e959137d/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-14 03:07:10,807 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_25b0f514-5f57-40ae-9922-9007e959137d/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Waiting until timeout for monitored process