/usr/bin/java -Xmx8000000000 -Xss4m -jar ./plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata ./data -s ../../../trunk/examples/settings/default/taipan/svcomp-Reach-32bit-Taipan_Default.epf -tc ../../../trunk/examples/toolchains/AutomizerC.xml --sifa.abstract.domain IntervalDomain -i ../sv-benchmarks/c/nla-digbench-scaling/egcd3-ll_valuebound100.c -------------------------------------------------------------------------------- This is Ultimate 0.2.3-dev-f954360 [2023-03-31 23:17:25,298 INFO L177 SettingsManager]: Resetting all preferences to default values... [2023-03-31 23:17:25,300 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2023-03-31 23:17:25,333 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2023-03-31 23:17:25,333 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2023-03-31 23:17:25,336 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2023-03-31 23:17:25,339 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2023-03-31 23:17:25,341 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2023-03-31 23:17:25,342 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2023-03-31 23:17:25,346 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2023-03-31 23:17:25,348 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2023-03-31 23:17:25,350 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2023-03-31 23:17:25,350 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2023-03-31 23:17:25,352 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2023-03-31 23:17:25,353 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2023-03-31 23:17:25,354 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2023-03-31 23:17:25,354 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2023-03-31 23:17:25,355 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2023-03-31 23:17:25,357 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2023-03-31 23:17:25,361 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2023-03-31 23:17:25,362 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2023-03-31 23:17:25,363 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2023-03-31 23:17:25,364 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2023-03-31 23:17:25,365 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2023-03-31 23:17:25,372 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2023-03-31 23:17:25,372 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2023-03-31 23:17:25,372 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2023-03-31 23:17:25,373 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2023-03-31 23:17:25,373 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2023-03-31 23:17:25,374 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2023-03-31 23:17:25,374 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2023-03-31 23:17:25,374 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2023-03-31 23:17:25,375 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2023-03-31 23:17:25,376 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2023-03-31 23:17:25,376 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2023-03-31 23:17:25,376 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2023-03-31 23:17:25,377 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2023-03-31 23:17:25,377 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2023-03-31 23:17:25,377 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2023-03-31 23:17:25,377 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2023-03-31 23:17:25,378 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2023-03-31 23:17:25,379 INFO L101 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/default/taipan/svcomp-Reach-32bit-Taipan_Default.epf [2023-03-31 23:17:25,402 INFO L113 SettingsManager]: Loading preferences was successful [2023-03-31 23:17:25,402 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2023-03-31 23:17:25,402 INFO L136 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2023-03-31 23:17:25,402 INFO L138 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2023-03-31 23:17:25,403 INFO L136 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2023-03-31 23:17:25,403 INFO L138 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2023-03-31 23:17:25,403 INFO L138 SettingsManager]: * User list type=DISABLED [2023-03-31 23:17:25,403 INFO L136 SettingsManager]: Preferences of Abstract Interpretation differ from their defaults: [2023-03-31 23:17:25,403 INFO L138 SettingsManager]: * Explicit value domain=true [2023-03-31 23:17:25,403 INFO L138 SettingsManager]: * Abstract domain for RCFG-of-the-future=PoormanAbstractDomain [2023-03-31 23:17:25,404 INFO L138 SettingsManager]: * Octagon Domain=false [2023-03-31 23:17:25,404 INFO L138 SettingsManager]: * Abstract domain=CompoundDomain [2023-03-31 23:17:25,404 INFO L138 SettingsManager]: * Check feasibility of abstract posts with an SMT solver=true [2023-03-31 23:17:25,404 INFO L138 SettingsManager]: * Use the RCFG-of-the-future interface=true [2023-03-31 23:17:25,404 INFO L138 SettingsManager]: * Interval Domain=false [2023-03-31 23:17:25,404 INFO L136 SettingsManager]: Preferences of Sifa differ from their defaults: [2023-03-31 23:17:25,405 INFO L138 SettingsManager]: * Call Summarizer=TopInputCallSummarizer [2023-03-31 23:17:25,405 INFO L138 SettingsManager]: * Simplification Technique=POLY_PAC [2023-03-31 23:17:25,405 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2023-03-31 23:17:25,405 INFO L138 SettingsManager]: * sizeof long=4 [2023-03-31 23:17:25,405 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2023-03-31 23:17:25,405 INFO L138 SettingsManager]: * sizeof POINTER=4 [2023-03-31 23:17:25,405 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2023-03-31 23:17:25,405 INFO L138 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2023-03-31 23:17:25,405 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2023-03-31 23:17:25,406 INFO L138 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2023-03-31 23:17:25,406 INFO L138 SettingsManager]: * sizeof long double=12 [2023-03-31 23:17:25,406 INFO L138 SettingsManager]: * Check if freed pointer was valid=false [2023-03-31 23:17:25,406 INFO L138 SettingsManager]: * Use constant arrays=true [2023-03-31 23:17:25,406 INFO L138 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2023-03-31 23:17:25,406 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2023-03-31 23:17:25,406 INFO L138 SettingsManager]: * SMT solver=External_DefaultMode [2023-03-31 23:17:25,406 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2023-03-31 23:17:25,407 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2023-03-31 23:17:25,407 INFO L138 SettingsManager]: * Abstract interpretation Mode=USE_PREDICATES [2023-03-31 23:17:25,407 INFO L138 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2023-03-31 23:17:25,407 INFO L138 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2023-03-31 23:17:25,407 INFO L138 SettingsManager]: * Trace refinement strategy=SIFA_TAIPAN [2023-03-31 23:17:25,407 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2023-03-31 23:17:25,407 INFO L138 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2023-03-31 23:17:25,407 INFO L138 SettingsManager]: * Trace refinement exception blacklist=NONE [2023-03-31 23:17:25,407 INFO L138 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode WARNING: An illegal reflective access operation has occurred WARNING: Illegal reflective access by com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 (file:/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/com.sun.xml.bind_2.2.0.v201505121915.jar) to method java.lang.ClassLoader.defineClass(java.lang.String,byte[],int,int) WARNING: Please consider reporting this to the maintainers of com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 WARNING: Use --illegal-access=warn to enable warnings of further illegal reflective access operations WARNING: All illegal access operations will be denied in a future release Applying setting for plugin de.uni_freiburg.informatik.ultimate.plugins.sifa: Abstract Domain -> IntervalDomain [2023-03-31 23:17:25,599 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2023-03-31 23:17:25,616 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2023-03-31 23:17:25,618 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2023-03-31 23:17:25,619 INFO L271 PluginConnector]: Initializing CDTParser... [2023-03-31 23:17:25,620 INFO L275 PluginConnector]: CDTParser initialized [2023-03-31 23:17:25,620 INFO L432 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/nla-digbench-scaling/egcd3-ll_valuebound100.c [2023-03-31 23:17:26,608 INFO L500 CDTParser]: Created temporary CDT project at NULL [2023-03-31 23:17:26,768 INFO L351 CDTParser]: Found 1 translation units. [2023-03-31 23:17:26,769 INFO L172 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/egcd3-ll_valuebound100.c [2023-03-31 23:17:26,774 INFO L394 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/6a83d3bb7/5713dce4fd9f43fb83fbf1f151dd365d/FLAG4028f6e3b [2023-03-31 23:17:26,786 INFO L402 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/6a83d3bb7/5713dce4fd9f43fb83fbf1f151dd365d [2023-03-31 23:17:26,788 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2023-03-31 23:17:26,789 INFO L131 ToolchainWalker]: Walking toolchain with 4 elements. [2023-03-31 23:17:26,792 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2023-03-31 23:17:26,793 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2023-03-31 23:17:26,795 INFO L275 PluginConnector]: CACSL2BoogieTranslator initialized [2023-03-31 23:17:26,795 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 31.03 11:17:26" (1/1) ... [2023-03-31 23:17:26,796 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@763dcb6 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 31.03 11:17:26, skipping insertion in model container [2023-03-31 23:17:26,797 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 31.03 11:17:26" (1/1) ... [2023-03-31 23:17:26,801 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2023-03-31 23:17:26,815 INFO L178 MainTranslator]: Built tables and reachable declarations [2023-03-31 23:17:26,904 WARN L247 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/egcd3-ll_valuebound100.c[490,503] [2023-03-31 23:17:26,919 INFO L209 PostProcessor]: Analyzing one entry point: main [2023-03-31 23:17:26,926 INFO L203 MainTranslator]: Completed pre-run [2023-03-31 23:17:26,934 WARN L247 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/egcd3-ll_valuebound100.c[490,503] [2023-03-31 23:17:26,939 INFO L209 PostProcessor]: Analyzing one entry point: main [2023-03-31 23:17:26,950 INFO L208 MainTranslator]: Completed translation [2023-03-31 23:17:26,950 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 31.03 11:17:26 WrapperNode [2023-03-31 23:17:26,950 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2023-03-31 23:17:26,951 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2023-03-31 23:17:26,951 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2023-03-31 23:17:26,951 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2023-03-31 23:17:26,959 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 31.03 11:17:26" (1/1) ... [2023-03-31 23:17:26,959 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 31.03 11:17:26" (1/1) ... [2023-03-31 23:17:26,963 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 31.03 11:17:26" (1/1) ... [2023-03-31 23:17:26,963 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 31.03 11:17:26" (1/1) ... [2023-03-31 23:17:26,966 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 31.03 11:17:26" (1/1) ... [2023-03-31 23:17:26,968 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 31.03 11:17:26" (1/1) ... [2023-03-31 23:17:26,969 INFO L185 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 31.03 11:17:26" (1/1) ... [2023-03-31 23:17:26,970 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 31.03 11:17:26" (1/1) ... [2023-03-31 23:17:26,971 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2023-03-31 23:17:26,972 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2023-03-31 23:17:26,972 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2023-03-31 23:17:26,972 INFO L275 PluginConnector]: RCFGBuilder initialized [2023-03-31 23:17:26,972 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 31.03 11:17:26" (1/1) ... [2023-03-31 23:17:26,976 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2023-03-31 23:17:26,983 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-03-31 23:17:26,993 INFO L229 MonitoredProcess]: Starting monitored process 1 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) [2023-03-31 23:17:26,998 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Waiting until timeout for monitored process [2023-03-31 23:17:27,026 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.init [2023-03-31 23:17:27,026 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2023-03-31 23:17:27,026 INFO L138 BoogieDeclarations]: Found implementation of procedure reach_error [2023-03-31 23:17:27,026 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2023-03-31 23:17:27,026 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2023-03-31 23:17:27,026 INFO L138 BoogieDeclarations]: Found implementation of procedure main [2023-03-31 23:17:27,027 INFO L130 BoogieDeclarations]: Found specification of procedure abort [2023-03-31 23:17:27,027 INFO L130 BoogieDeclarations]: Found specification of procedure __assert_fail [2023-03-31 23:17:27,027 INFO L130 BoogieDeclarations]: Found specification of procedure reach_error [2023-03-31 23:17:27,027 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2023-03-31 23:17:27,027 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_nondet_int [2023-03-31 23:17:27,027 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2023-03-31 23:17:27,027 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2023-03-31 23:17:27,027 INFO L130 BoogieDeclarations]: Found specification of procedure main [2023-03-31 23:17:27,027 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.init [2023-03-31 23:17:27,027 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2023-03-31 23:17:27,027 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2023-03-31 23:17:27,027 INFO L130 BoogieDeclarations]: Found specification of procedure write~int [2023-03-31 23:17:27,028 INFO L130 BoogieDeclarations]: Found specification of procedure read~int [2023-03-31 23:17:27,028 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2023-03-31 23:17:27,070 INFO L236 CfgBuilder]: Building ICFG [2023-03-31 23:17:27,072 INFO L262 CfgBuilder]: Building CFG for each procedure with an implementation [2023-03-31 23:17:27,198 INFO L277 CfgBuilder]: Performing block encoding [2023-03-31 23:17:27,219 INFO L297 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2023-03-31 23:17:27,219 INFO L302 CfgBuilder]: Removed 3 assume(true) statements. [2023-03-31 23:17:27,223 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 31.03 11:17:27 BoogieIcfgContainer [2023-03-31 23:17:27,223 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2023-03-31 23:17:27,224 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2023-03-31 23:17:27,224 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2023-03-31 23:17:27,233 INFO L275 PluginConnector]: TraceAbstraction initialized [2023-03-31 23:17:27,233 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 31.03 11:17:26" (1/3) ... [2023-03-31 23:17:27,233 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@6fb0de82 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 31.03 11:17:27, skipping insertion in model container [2023-03-31 23:17:27,234 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 31.03 11:17:26" (2/3) ... [2023-03-31 23:17:27,234 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@6fb0de82 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 31.03 11:17:27, skipping insertion in model container [2023-03-31 23:17:27,234 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 31.03 11:17:27" (3/3) ... [2023-03-31 23:17:27,235 INFO L112 eAbstractionObserver]: Analyzing ICFG egcd3-ll_valuebound100.c [2023-03-31 23:17:27,247 INFO L203 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2023-03-31 23:17:27,247 INFO L162 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2023-03-31 23:17:27,275 INFO L356 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2023-03-31 23:17:27,280 INFO L357 AbstractCegarLoop]: Settings: SEPARATE_VIOLATION_CHECK=true, mInterprocedural=true, mMaxIterations=1000000, mWatchIteration=1000000, mArtifact=RCFG, mInterpolation=FPandBP, mInterpolantAutomaton=STRAIGHT_LINE, mDumpAutomata=false, mAutomataFormat=ATS_NUMERATE, mDumpPath=., mDeterminiation=PREDICATE_ABSTRACTION, mMinimize=MINIMIZE_SEVPA, mHoare=true, mAutomataTypeConcurrency=FINITE_AUTOMATA, mHoareTripleChecks=INCREMENTAL, mHoareAnnotationPositions=LoopsAndPotentialCycles, 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;@4c23d2a7, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2023-03-31 23:17:27,280 INFO L358 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2023-03-31 23:17:27,292 INFO L276 IsEmpty]: Start isEmpty. Operand has 36 states, 19 states have (on average 1.4210526315789473) internal successors, (27), 20 states have internal predecessors, (27), 11 states have call successors, (11), 4 states have call predecessors, (11), 4 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2023-03-31 23:17:27,297 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 25 [2023-03-31 23:17:27,297 INFO L187 NwaCegarLoop]: Found error trace [2023-03-31 23:17:27,297 INFO L195 NwaCegarLoop]: trace histogram [4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-03-31 23:17:27,299 INFO L420 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-03-31 23:17:27,303 INFO L145 PredicateUnifier]: Initialized classic predicate unifier [2023-03-31 23:17:27,303 INFO L85 PathProgramCache]: Analyzing trace with hash -1897632913, now seen corresponding path program 1 times [2023-03-31 23:17:27,326 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-03-31 23:17:27,327 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1089762959] [2023-03-31 23:17:27,327 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-03-31 23:17:27,327 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-03-31 23:17:27,444 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-03-31 23:17:27,466 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-03-31 23:17:27,467 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1089762959] [2023-03-31 23:17:27,467 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: Unsupported non-linear arithmetic [2023-03-31 23:17:27,467 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1330671316] [2023-03-31 23:17:27,467 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-03-31 23:17:27,468 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-03-31 23:17:27,468 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-03-31 23:17:27,482 INFO L229 MonitoredProcess]: Starting monitored process 2 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-03-31 23:17:27,494 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2023-03-31 23:17:27,536 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-03-31 23:17:27,540 INFO L262 TraceCheckSpWp]: Trace formula consists of 100 conjuncts, 1 conjunts are in the unsatisfiable core [2023-03-31 23:17:27,543 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-03-31 23:17:27,559 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2023-03-31 23:17:27,559 INFO L323 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2023-03-31 23:17:27,560 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1330671316] provided 1 perfect and 0 imperfect interpolant sequences [2023-03-31 23:17:27,560 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-03-31 23:17:27,560 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2023-03-31 23:17:27,561 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [48415335] [2023-03-31 23:17:27,562 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-03-31 23:17:27,564 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2023-03-31 23:17:27,564 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-03-31 23:17:27,595 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2023-03-31 23:17:27,596 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2023-03-31 23:17:27,597 INFO L87 Difference]: Start difference. First operand has 36 states, 19 states have (on average 1.4210526315789473) internal successors, (27), 20 states have internal predecessors, (27), 11 states have call successors, (11), 4 states have call predecessors, (11), 4 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) Second operand has 2 states, 2 states have (on average 4.5) internal successors, (9), 2 states have internal predecessors, (9), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (5), 1 states have call predecessors, (5), 1 states have call successors, (5) [2023-03-31 23:17:27,624 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-03-31 23:17:27,624 INFO L93 Difference]: Finished difference Result 59 states and 87 transitions. [2023-03-31 23:17:27,628 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2023-03-31 23:17:27,629 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 4.5) internal successors, (9), 2 states have internal predecessors, (9), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (5), 1 states have call predecessors, (5), 1 states have call successors, (5) Word has length 24 [2023-03-31 23:17:27,629 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-03-31 23:17:27,633 INFO L225 Difference]: With dead ends: 59 [2023-03-31 23:17:27,633 INFO L226 Difference]: Without dead ends: 32 [2023-03-31 23:17:27,635 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 23 GetRequests, 23 SyntacticMatches, 0 SemanticMatches, 0 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2023-03-31 23:17:27,637 INFO L413 NwaCegarLoop]: 42 mSDtfsCounter, 0 mSDsluCounter, 0 mSDsCounter, 0 mSdLazyCounter, 3 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 42 SdHoareTripleChecker+Invalid, 5 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 3 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-03-31 23:17:27,638 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 42 Invalid, 5 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 3 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-03-31 23:17:27,648 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 32 states. [2023-03-31 23:17:27,658 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 32 to 32. [2023-03-31 23:17:27,659 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 32 states, 17 states have (on average 1.2352941176470589) internal successors, (21), 18 states have internal predecessors, (21), 11 states have call successors, (11), 4 states have call predecessors, (11), 3 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2023-03-31 23:17:27,660 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 32 states to 32 states and 41 transitions. [2023-03-31 23:17:27,661 INFO L78 Accepts]: Start accepts. Automaton has 32 states and 41 transitions. Word has length 24 [2023-03-31 23:17:27,662 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-03-31 23:17:27,662 INFO L495 AbstractCegarLoop]: Abstraction has 32 states and 41 transitions. [2023-03-31 23:17:27,662 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 2 states have (on average 4.5) internal successors, (9), 2 states have internal predecessors, (9), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (5), 1 states have call predecessors, (5), 1 states have call successors, (5) [2023-03-31 23:17:27,662 INFO L276 IsEmpty]: Start isEmpty. Operand 32 states and 41 transitions. [2023-03-31 23:17:27,663 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 26 [2023-03-31 23:17:27,663 INFO L187 NwaCegarLoop]: Found error trace [2023-03-31 23:17:27,663 INFO L195 NwaCegarLoop]: trace histogram [4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-03-31 23:17:27,668 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Ended with exit code 0 [2023-03-31 23:17:27,868 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable0 [2023-03-31 23:17:27,869 INFO L420 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-03-31 23:17:27,869 INFO L145 PredicateUnifier]: Initialized classic predicate unifier [2023-03-31 23:17:27,874 INFO L85 PathProgramCache]: Analyzing trace with hash -1548109508, now seen corresponding path program 1 times [2023-03-31 23:17:27,874 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-03-31 23:17:27,875 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2031745992] [2023-03-31 23:17:27,886 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-03-31 23:17:27,886 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-03-31 23:17:27,917 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-03-31 23:17:27,917 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1592909504] [2023-03-31 23:17:27,917 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-03-31 23:17:27,917 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-03-31 23:17:27,917 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-03-31 23:17:27,922 INFO L229 MonitoredProcess]: Starting monitored process 3 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-03-31 23:17:27,923 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2023-03-31 23:17:27,983 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-03-31 23:17:27,984 INFO L262 TraceCheckSpWp]: Trace formula consists of 102 conjuncts, 7 conjunts are in the unsatisfiable core [2023-03-31 23:17:27,986 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-03-31 23:17:28,028 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 3 proven. 0 refuted. 0 times theorem prover too weak. 9 trivial. 0 not checked. [2023-03-31 23:17:28,028 INFO L323 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2023-03-31 23:17:28,028 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-03-31 23:17:28,029 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2031745992] [2023-03-31 23:17:28,029 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-03-31 23:17:28,029 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1592909504] [2023-03-31 23:17:28,029 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1592909504] provided 1 perfect and 0 imperfect interpolant sequences [2023-03-31 23:17:28,029 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-03-31 23:17:28,029 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2023-03-31 23:17:28,029 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1831861328] [2023-03-31 23:17:28,030 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-03-31 23:17:28,030 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2023-03-31 23:17:28,030 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-03-31 23:17:28,031 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2023-03-31 23:17:28,031 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2023-03-31 23:17:28,031 INFO L87 Difference]: Start difference. First operand 32 states and 41 transitions. Second operand has 5 states, 4 states have (on average 2.75) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (5), 2 states have call predecessors, (5), 1 states have call successors, (5) [2023-03-31 23:17:28,105 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-03-31 23:17:28,105 INFO L93 Difference]: Finished difference Result 51 states and 66 transitions. [2023-03-31 23:17:28,105 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2023-03-31 23:17:28,106 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 4 states have (on average 2.75) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (5), 2 states have call predecessors, (5), 1 states have call successors, (5) Word has length 25 [2023-03-31 23:17:28,106 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-03-31 23:17:28,107 INFO L225 Difference]: With dead ends: 51 [2023-03-31 23:17:28,107 INFO L226 Difference]: Without dead ends: 44 [2023-03-31 23:17:28,107 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 25 GetRequests, 21 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2023-03-31 23:17:28,108 INFO L413 NwaCegarLoop]: 30 mSDtfsCounter, 30 mSDsluCounter, 54 mSDsCounter, 0 mSdLazyCounter, 61 mSolverCounterSat, 8 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 34 SdHoareTripleChecker+Valid, 84 SdHoareTripleChecker+Invalid, 69 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 8 IncrementalHoareTripleChecker+Valid, 61 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-03-31 23:17:28,108 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [34 Valid, 84 Invalid, 69 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [8 Valid, 61 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-03-31 23:17:28,109 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 44 states. [2023-03-31 23:17:28,114 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 44 to 34. [2023-03-31 23:17:28,114 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 34 states, 19 states have (on average 1.2105263157894737) internal successors, (23), 20 states have internal predecessors, (23), 11 states have call successors, (11), 4 states have call predecessors, (11), 3 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2023-03-31 23:17:28,115 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 34 states to 34 states and 43 transitions. [2023-03-31 23:17:28,115 INFO L78 Accepts]: Start accepts. Automaton has 34 states and 43 transitions. Word has length 25 [2023-03-31 23:17:28,115 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-03-31 23:17:28,115 INFO L495 AbstractCegarLoop]: Abstraction has 34 states and 43 transitions. [2023-03-31 23:17:28,116 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 4 states have (on average 2.75) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (5), 2 states have call predecessors, (5), 1 states have call successors, (5) [2023-03-31 23:17:28,116 INFO L276 IsEmpty]: Start isEmpty. Operand 34 states and 43 transitions. [2023-03-31 23:17:28,116 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 29 [2023-03-31 23:17:28,116 INFO L187 NwaCegarLoop]: Found error trace [2023-03-31 23:17:28,116 INFO L195 NwaCegarLoop]: trace histogram [4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-03-31 23:17:28,135 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Ended with exit code 0 [2023-03-31 23:17:28,324 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 3 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable1 [2023-03-31 23:17:28,324 INFO L420 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-03-31 23:17:28,325 INFO L145 PredicateUnifier]: Initialized classic predicate unifier [2023-03-31 23:17:28,325 INFO L85 PathProgramCache]: Analyzing trace with hash 1414952, now seen corresponding path program 1 times [2023-03-31 23:17:28,325 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-03-31 23:17:28,332 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1101367124] [2023-03-31 23:17:28,332 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-03-31 23:17:28,332 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-03-31 23:17:28,354 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-03-31 23:17:28,354 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1949809483] [2023-03-31 23:17:28,354 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-03-31 23:17:28,354 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-03-31 23:17:28,355 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-03-31 23:17:28,365 INFO L229 MonitoredProcess]: Starting monitored process 4 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-03-31 23:17:28,376 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2023-03-31 23:17:28,423 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-03-31 23:17:28,424 INFO L262 TraceCheckSpWp]: Trace formula consists of 112 conjuncts, 20 conjunts are in the unsatisfiable core [2023-03-31 23:17:28,427 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-03-31 23:17:28,633 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 1 proven. 2 refuted. 0 times theorem prover too weak. 9 trivial. 0 not checked. [2023-03-31 23:17:28,633 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-03-31 23:17:28,744 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2023-03-31 23:17:28,744 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-03-31 23:17:28,744 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1101367124] [2023-03-31 23:17:28,744 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-03-31 23:17:28,744 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1949809483] [2023-03-31 23:17:28,745 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1949809483] provided 1 perfect and 1 imperfect interpolant sequences [2023-03-31 23:17:28,745 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2023-03-31 23:17:28,745 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [8] total 12 [2023-03-31 23:17:28,745 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1710702126] [2023-03-31 23:17:28,746 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-03-31 23:17:28,746 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2023-03-31 23:17:28,747 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-03-31 23:17:28,748 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2023-03-31 23:17:28,748 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=30, Invalid=102, Unknown=0, NotChecked=0, Total=132 [2023-03-31 23:17:28,749 INFO L87 Difference]: Start difference. First operand 34 states and 43 transitions. Second operand has 6 states, 6 states have (on average 2.1666666666666665) internal successors, (13), 5 states have internal predecessors, (13), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (5), 1 states have call predecessors, (5), 1 states have call successors, (5) [2023-03-31 23:17:28,821 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-03-31 23:17:28,821 INFO L93 Difference]: Finished difference Result 50 states and 64 transitions. [2023-03-31 23:17:28,821 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2023-03-31 23:17:28,822 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 2.1666666666666665) internal successors, (13), 5 states have internal predecessors, (13), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (5), 1 states have call predecessors, (5), 1 states have call successors, (5) Word has length 28 [2023-03-31 23:17:28,822 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-03-31 23:17:28,826 INFO L225 Difference]: With dead ends: 50 [2023-03-31 23:17:28,826 INFO L226 Difference]: Without dead ends: 48 [2023-03-31 23:17:28,827 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 56 GetRequests, 45 SyntacticMatches, 0 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 19 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=34, Invalid=122, Unknown=0, NotChecked=0, Total=156 [2023-03-31 23:17:28,829 INFO L413 NwaCegarLoop]: 34 mSDtfsCounter, 15 mSDsluCounter, 79 mSDsCounter, 0 mSdLazyCounter, 48 mSolverCounterSat, 7 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 19 SdHoareTripleChecker+Valid, 113 SdHoareTripleChecker+Invalid, 55 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 7 IncrementalHoareTripleChecker+Valid, 48 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-03-31 23:17:28,832 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [19 Valid, 113 Invalid, 55 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [7 Valid, 48 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-03-31 23:17:28,833 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 48 states. [2023-03-31 23:17:28,848 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 48 to 47. [2023-03-31 23:17:28,849 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 47 states, 27 states have (on average 1.2222222222222223) internal successors, (33), 28 states have internal predecessors, (33), 15 states have call successors, (15), 5 states have call predecessors, (15), 4 states have return successors, (13), 13 states have call predecessors, (13), 13 states have call successors, (13) [2023-03-31 23:17:28,849 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 47 states to 47 states and 61 transitions. [2023-03-31 23:17:28,850 INFO L78 Accepts]: Start accepts. Automaton has 47 states and 61 transitions. Word has length 28 [2023-03-31 23:17:28,850 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-03-31 23:17:28,850 INFO L495 AbstractCegarLoop]: Abstraction has 47 states and 61 transitions. [2023-03-31 23:17:28,850 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 2.1666666666666665) internal successors, (13), 5 states have internal predecessors, (13), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (5), 1 states have call predecessors, (5), 1 states have call successors, (5) [2023-03-31 23:17:28,850 INFO L276 IsEmpty]: Start isEmpty. Operand 47 states and 61 transitions. [2023-03-31 23:17:28,851 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 31 [2023-03-31 23:17:28,851 INFO L187 NwaCegarLoop]: Found error trace [2023-03-31 23:17:28,851 INFO L195 NwaCegarLoop]: trace histogram [4, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-03-31 23:17:28,860 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Forceful destruction successful, exit code 0 [2023-03-31 23:17:29,060 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-03-31 23:17:29,060 INFO L420 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-03-31 23:17:29,061 INFO L145 PredicateUnifier]: Initialized classic predicate unifier [2023-03-31 23:17:29,062 INFO L85 PathProgramCache]: Analyzing trace with hash 2146803478, now seen corresponding path program 1 times [2023-03-31 23:17:29,063 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-03-31 23:17:29,064 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [773385931] [2023-03-31 23:17:29,064 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-03-31 23:17:29,064 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-03-31 23:17:29,079 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-03-31 23:17:29,079 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1174617874] [2023-03-31 23:17:29,080 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-03-31 23:17:29,080 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-03-31 23:17:29,080 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-03-31 23:17:29,089 INFO L229 MonitoredProcess]: Starting monitored process 5 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-03-31 23:17:29,090 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2023-03-31 23:17:29,132 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-03-31 23:17:29,133 INFO L262 TraceCheckSpWp]: Trace formula consists of 124 conjuncts, 9 conjunts are in the unsatisfiable core [2023-03-31 23:17:29,136 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-03-31 23:17:29,175 INFO L134 CoverageAnalysis]: Checked inductivity of 14 backedges. 2 proven. 3 refuted. 0 times theorem prover too weak. 9 trivial. 0 not checked. [2023-03-31 23:17:29,175 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-03-31 23:17:29,227 INFO L134 CoverageAnalysis]: Checked inductivity of 14 backedges. 2 proven. 3 refuted. 0 times theorem prover too weak. 9 trivial. 0 not checked. [2023-03-31 23:17:29,227 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-03-31 23:17:29,227 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [773385931] [2023-03-31 23:17:29,227 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-03-31 23:17:29,227 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1174617874] [2023-03-31 23:17:29,227 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1174617874] provided 0 perfect and 2 imperfect interpolant sequences [2023-03-31 23:17:29,228 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1719609239] [2023-03-31 23:17:29,245 INFO L159 IcfgInterpreter]: Started Sifa with 23 locations of interest [2023-03-31 23:17:29,246 INFO L166 IcfgInterpreter]: Building call graph [2023-03-31 23:17:29,248 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-03-31 23:17:29,251 INFO L176 IcfgInterpreter]: Starting interpretation [2023-03-31 23:17:29,251 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-03-31 23:17:29,301 INFO L197 IcfgInterpreter]: Interpreting procedure main with input of size 8 for LOIs [2023-03-31 23:17:29,549 INFO L197 IcfgInterpreter]: Interpreting procedure assume_abort_if_not with input of size 8 for LOIs [2023-03-31 23:17:29,550 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.init with input of size 7 for LOIs [2023-03-31 23:17:29,555 INFO L180 IcfgInterpreter]: Interpretation finished [2023-03-31 23:17:29,920 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSifa [1719609239] provided 1 perfect and 0 imperfect interpolant sequences [2023-03-31 23:17:29,920 INFO L185 FreeRefinementEngine]: Found 1 perfect and 2 imperfect interpolant sequences. [2023-03-31 23:17:29,920 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [15] imperfect sequences [7, 7] total 21 [2023-03-31 23:17:29,921 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1650050391] [2023-03-31 23:17:29,921 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-03-31 23:17:29,921 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2023-03-31 23:17:29,921 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-03-31 23:17:29,921 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2023-03-31 23:17:29,922 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=113, Invalid=307, Unknown=0, NotChecked=0, Total=420 [2023-03-31 23:17:29,922 INFO L87 Difference]: Start difference. First operand 47 states and 61 transitions. Second operand has 16 states, 9 states have (on average 1.5555555555555556) internal successors, (14), 9 states have internal predecessors, (14), 7 states have call successors, (7), 3 states have call predecessors, (7), 2 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) [2023-03-31 23:17:30,895 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-03-31 23:17:30,895 INFO L93 Difference]: Finished difference Result 85 states and 117 transitions. [2023-03-31 23:17:30,895 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2023-03-31 23:17:30,896 INFO L78 Accepts]: Start accepts. Automaton has has 16 states, 9 states have (on average 1.5555555555555556) internal successors, (14), 9 states have internal predecessors, (14), 7 states have call successors, (7), 3 states have call predecessors, (7), 2 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) Word has length 30 [2023-03-31 23:17:30,896 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-03-31 23:17:30,896 INFO L225 Difference]: With dead ends: 85 [2023-03-31 23:17:30,896 INFO L226 Difference]: Without dead ends: 78 [2023-03-31 23:17:30,897 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 101 GetRequests, 66 SyntacticMatches, 4 SemanticMatches, 31 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 107 ImplicationChecksByTransitivity, 1.2s TimeCoverageRelationStatistics Valid=302, Invalid=754, Unknown=0, NotChecked=0, Total=1056 [2023-03-31 23:17:30,897 INFO L413 NwaCegarLoop]: 3 mSDtfsCounter, 118 mSDsluCounter, 4 mSDsCounter, 0 mSdLazyCounter, 197 mSolverCounterSat, 88 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 118 SdHoareTripleChecker+Valid, 7 SdHoareTripleChecker+Invalid, 285 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 88 IncrementalHoareTripleChecker+Valid, 197 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2023-03-31 23:17:30,898 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [118 Valid, 7 Invalid, 285 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [88 Valid, 197 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2023-03-31 23:17:30,898 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 78 states. [2023-03-31 23:17:30,926 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 78 to 54. [2023-03-31 23:17:30,927 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 54 states, 34 states have (on average 1.2352941176470589) internal successors, (42), 35 states have internal predecessors, (42), 15 states have call successors, (15), 5 states have call predecessors, (15), 4 states have return successors, (13), 13 states have call predecessors, (13), 13 states have call successors, (13) [2023-03-31 23:17:30,927 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 54 states to 54 states and 70 transitions. [2023-03-31 23:17:30,927 INFO L78 Accepts]: Start accepts. Automaton has 54 states and 70 transitions. Word has length 30 [2023-03-31 23:17:30,927 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-03-31 23:17:30,928 INFO L495 AbstractCegarLoop]: Abstraction has 54 states and 70 transitions. [2023-03-31 23:17:30,928 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 16 states, 9 states have (on average 1.5555555555555556) internal successors, (14), 9 states have internal predecessors, (14), 7 states have call successors, (7), 3 states have call predecessors, (7), 2 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) [2023-03-31 23:17:30,928 INFO L276 IsEmpty]: Start isEmpty. Operand 54 states and 70 transitions. [2023-03-31 23:17:30,928 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 34 [2023-03-31 23:17:30,928 INFO L187 NwaCegarLoop]: Found error trace [2023-03-31 23:17:30,928 INFO L195 NwaCegarLoop]: trace histogram [4, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-03-31 23:17:30,935 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Forceful destruction successful, exit code 0 [2023-03-31 23:17:31,133 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-03-31 23:17:31,133 INFO L420 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-03-31 23:17:31,134 INFO L145 PredicateUnifier]: Initialized classic predicate unifier [2023-03-31 23:17:31,134 INFO L85 PathProgramCache]: Analyzing trace with hash -874024117, now seen corresponding path program 1 times [2023-03-31 23:17:31,134 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-03-31 23:17:31,134 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [515526235] [2023-03-31 23:17:31,134 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-03-31 23:17:31,134 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-03-31 23:17:31,146 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-03-31 23:17:31,146 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1123176674] [2023-03-31 23:17:31,146 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-03-31 23:17:31,146 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-03-31 23:17:31,146 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-03-31 23:17:31,147 INFO L229 MonitoredProcess]: Starting monitored process 6 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-03-31 23:17:31,149 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2023-03-31 23:17:31,185 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-03-31 23:17:31,186 INFO L262 TraceCheckSpWp]: Trace formula consists of 121 conjuncts, 31 conjunts are in the unsatisfiable core [2023-03-31 23:17:31,187 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-03-31 23:17:31,424 INFO L134 CoverageAnalysis]: Checked inductivity of 14 backedges. 1 proven. 5 refuted. 0 times theorem prover too weak. 8 trivial. 0 not checked. [2023-03-31 23:17:31,425 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-03-31 23:17:31,479 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-03-31 23:17:31,479 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [515526235] [2023-03-31 23:17:31,479 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-03-31 23:17:31,479 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1123176674] [2023-03-31 23:17:31,479 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1123176674] provided 0 perfect and 1 imperfect interpolant sequences [2023-03-31 23:17:31,479 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1186931291] [2023-03-31 23:17:31,481 INFO L159 IcfgInterpreter]: Started Sifa with 26 locations of interest [2023-03-31 23:17:31,481 INFO L166 IcfgInterpreter]: Building call graph [2023-03-31 23:17:31,481 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-03-31 23:17:31,481 INFO L176 IcfgInterpreter]: Starting interpretation [2023-03-31 23:17:31,481 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-03-31 23:17:31,494 INFO L197 IcfgInterpreter]: Interpreting procedure main with input of size 8 for LOIs [2023-03-31 23:17:31,624 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 13 for LOIs [2023-03-31 23:17:31,630 INFO L197 IcfgInterpreter]: Interpreting procedure assume_abort_if_not with input of size 8 for LOIs [2023-03-31 23:17:31,631 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.init with input of size 7 for LOIs [2023-03-31 23:17:31,634 INFO L180 IcfgInterpreter]: Interpretation finished [2023-03-31 23:17:32,237 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '1348#(and (= |__VERIFIER_assert_#in~cond| 0) (= __VERIFIER_assert_~cond 0) (= |#NULL.offset| 0) (<= 0 |#StackHeapBarrier|) (= |#NULL.base| 0))' at error location [2023-03-31 23:17:32,237 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-03-31 23:17:32,237 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2023-03-31 23:17:32,237 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13] total 13 [2023-03-31 23:17:32,237 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [126617061] [2023-03-31 23:17:32,237 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2023-03-31 23:17:32,237 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 13 states [2023-03-31 23:17:32,238 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-03-31 23:17:32,238 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2023-03-31 23:17:32,239 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=181, Invalid=875, Unknown=0, NotChecked=0, Total=1056 [2023-03-31 23:17:32,239 INFO L87 Difference]: Start difference. First operand 54 states and 70 transitions. Second operand has 13 states, 11 states have (on average 1.5454545454545454) internal successors, (17), 10 states have internal predecessors, (17), 5 states have call successors, (8), 2 states have call predecessors, (8), 3 states have return successors, (6), 4 states have call predecessors, (6), 4 states have call successors, (6) [2023-03-31 23:17:32,459 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-03-31 23:17:32,460 INFO L93 Difference]: Finished difference Result 69 states and 89 transitions. [2023-03-31 23:17:32,460 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2023-03-31 23:17:32,460 INFO L78 Accepts]: Start accepts. Automaton has has 13 states, 11 states have (on average 1.5454545454545454) internal successors, (17), 10 states have internal predecessors, (17), 5 states have call successors, (8), 2 states have call predecessors, (8), 3 states have return successors, (6), 4 states have call predecessors, (6), 4 states have call successors, (6) Word has length 33 [2023-03-31 23:17:32,460 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-03-31 23:17:32,461 INFO L225 Difference]: With dead ends: 69 [2023-03-31 23:17:32,461 INFO L226 Difference]: Without dead ends: 67 [2023-03-31 23:17:32,461 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 73 GetRequests, 37 SyntacticMatches, 2 SemanticMatches, 34 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 375 ImplicationChecksByTransitivity, 0.8s TimeCoverageRelationStatistics Valid=206, Invalid=1054, Unknown=0, NotChecked=0, Total=1260 [2023-03-31 23:17:32,462 INFO L413 NwaCegarLoop]: 23 mSDtfsCounter, 48 mSDsluCounter, 117 mSDsCounter, 0 mSdLazyCounter, 299 mSolverCounterSat, 13 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 56 SdHoareTripleChecker+Valid, 140 SdHoareTripleChecker+Invalid, 312 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 13 IncrementalHoareTripleChecker+Valid, 299 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2023-03-31 23:17:32,462 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [56 Valid, 140 Invalid, 312 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [13 Valid, 299 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2023-03-31 23:17:32,462 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 67 states. [2023-03-31 23:17:32,474 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 67 to 58. [2023-03-31 23:17:32,474 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 58 states, 37 states have (on average 1.2162162162162162) internal successors, (45), 38 states have internal predecessors, (45), 15 states have call successors, (15), 6 states have call predecessors, (15), 5 states have return successors, (13), 13 states have call predecessors, (13), 13 states have call successors, (13) [2023-03-31 23:17:32,475 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 58 states to 58 states and 73 transitions. [2023-03-31 23:17:32,475 INFO L78 Accepts]: Start accepts. Automaton has 58 states and 73 transitions. Word has length 33 [2023-03-31 23:17:32,475 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-03-31 23:17:32,475 INFO L495 AbstractCegarLoop]: Abstraction has 58 states and 73 transitions. [2023-03-31 23:17:32,475 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 13 states, 11 states have (on average 1.5454545454545454) internal successors, (17), 10 states have internal predecessors, (17), 5 states have call successors, (8), 2 states have call predecessors, (8), 3 states have return successors, (6), 4 states have call predecessors, (6), 4 states have call successors, (6) [2023-03-31 23:17:32,475 INFO L276 IsEmpty]: Start isEmpty. Operand 58 states and 73 transitions. [2023-03-31 23:17:32,476 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 34 [2023-03-31 23:17:32,476 INFO L187 NwaCegarLoop]: Found error trace [2023-03-31 23:17:32,476 INFO L195 NwaCegarLoop]: trace histogram [4, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-03-31 23:17:32,495 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Forceful destruction successful, exit code 0 [2023-03-31 23:17:32,681 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-03-31 23:17:32,681 INFO L420 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-03-31 23:17:32,681 INFO L145 PredicateUnifier]: Initialized classic predicate unifier [2023-03-31 23:17:32,681 INFO L85 PathProgramCache]: Analyzing trace with hash -562648306, now seen corresponding path program 1 times [2023-03-31 23:17:32,681 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-03-31 23:17:32,682 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1771333938] [2023-03-31 23:17:32,682 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-03-31 23:17:32,682 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-03-31 23:17:32,690 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-03-31 23:17:32,690 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1462677459] [2023-03-31 23:17:32,690 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-03-31 23:17:32,690 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-03-31 23:17:32,690 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-03-31 23:17:32,691 INFO L229 MonitoredProcess]: Starting monitored process 7 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-03-31 23:17:32,693 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2023-03-31 23:17:32,726 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-03-31 23:17:32,727 INFO L262 TraceCheckSpWp]: Trace formula consists of 134 conjuncts, 25 conjunts are in the unsatisfiable core [2023-03-31 23:17:32,728 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-03-31 23:17:32,816 INFO L134 CoverageAnalysis]: Checked inductivity of 16 backedges. 2 proven. 5 refuted. 0 times theorem prover too weak. 9 trivial. 0 not checked. [2023-03-31 23:17:32,817 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-03-31 23:17:32,883 INFO L134 CoverageAnalysis]: Checked inductivity of 16 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2023-03-31 23:17:32,884 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-03-31 23:17:32,884 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1771333938] [2023-03-31 23:17:32,884 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-03-31 23:17:32,884 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1462677459] [2023-03-31 23:17:32,884 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1462677459] provided 0 perfect and 2 imperfect interpolant sequences [2023-03-31 23:17:32,884 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [889144294] [2023-03-31 23:17:32,885 INFO L159 IcfgInterpreter]: Started Sifa with 24 locations of interest [2023-03-31 23:17:32,885 INFO L166 IcfgInterpreter]: Building call graph [2023-03-31 23:17:32,886 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-03-31 23:17:32,886 INFO L176 IcfgInterpreter]: Starting interpretation [2023-03-31 23:17:32,886 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-03-31 23:17:32,896 INFO L197 IcfgInterpreter]: Interpreting procedure main with input of size 8 for LOIs [2023-03-31 23:17:33,011 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 34 for LOIs [2023-03-31 23:17:33,022 INFO L197 IcfgInterpreter]: Interpreting procedure assume_abort_if_not with input of size 8 for LOIs [2023-03-31 23:17:33,022 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.init with input of size 7 for LOIs [2023-03-31 23:17:33,025 INFO L180 IcfgInterpreter]: Interpretation finished [2023-03-31 23:17:33,539 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '1770#(and (= |__VERIFIER_assert_#in~cond| 0) (= __VERIFIER_assert_~cond 0) (= |#NULL.offset| 0) (<= 0 |#StackHeapBarrier|) (= |#NULL.base| 0))' at error location [2023-03-31 23:17:33,539 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-03-31 23:17:33,539 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-03-31 23:17:33,539 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 6] total 12 [2023-03-31 23:17:33,539 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [301044910] [2023-03-31 23:17:33,539 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-03-31 23:17:33,539 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2023-03-31 23:17:33,539 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-03-31 23:17:33,540 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2023-03-31 23:17:33,540 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=144, Invalid=726, Unknown=0, NotChecked=0, Total=870 [2023-03-31 23:17:33,540 INFO L87 Difference]: Start difference. First operand 58 states and 73 transitions. Second operand has 12 states, 11 states have (on average 2.909090909090909) internal successors, (32), 9 states have internal predecessors, (32), 4 states have call successors, (9), 3 states have call predecessors, (9), 2 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2023-03-31 23:17:33,696 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-03-31 23:17:33,697 INFO L93 Difference]: Finished difference Result 84 states and 106 transitions. [2023-03-31 23:17:33,697 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2023-03-31 23:17:33,697 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 11 states have (on average 2.909090909090909) internal successors, (32), 9 states have internal predecessors, (32), 4 states have call successors, (9), 3 states have call predecessors, (9), 2 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) Word has length 33 [2023-03-31 23:17:33,698 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-03-31 23:17:33,698 INFO L225 Difference]: With dead ends: 84 [2023-03-31 23:17:33,698 INFO L226 Difference]: Without dead ends: 82 [2023-03-31 23:17:33,698 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 100 GetRequests, 70 SyntacticMatches, 0 SemanticMatches, 30 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 197 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=156, Invalid=836, Unknown=0, NotChecked=0, Total=992 [2023-03-31 23:17:33,699 INFO L413 NwaCegarLoop]: 41 mSDtfsCounter, 55 mSDsluCounter, 169 mSDsCounter, 0 mSdLazyCounter, 210 mSolverCounterSat, 29 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 63 SdHoareTripleChecker+Valid, 210 SdHoareTripleChecker+Invalid, 239 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 29 IncrementalHoareTripleChecker+Valid, 210 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-03-31 23:17:33,699 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [63 Valid, 210 Invalid, 239 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [29 Valid, 210 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-03-31 23:17:33,699 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 82 states. [2023-03-31 23:17:33,712 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 82 to 79. [2023-03-31 23:17:33,712 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 79 states, 53 states have (on average 1.2264150943396226) internal successors, (65), 54 states have internal predecessors, (65), 19 states have call successors, (19), 7 states have call predecessors, (19), 6 states have return successors, (17), 17 states have call predecessors, (17), 17 states have call successors, (17) [2023-03-31 23:17:33,713 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 79 states to 79 states and 101 transitions. [2023-03-31 23:17:33,713 INFO L78 Accepts]: Start accepts. Automaton has 79 states and 101 transitions. Word has length 33 [2023-03-31 23:17:33,713 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-03-31 23:17:33,713 INFO L495 AbstractCegarLoop]: Abstraction has 79 states and 101 transitions. [2023-03-31 23:17:33,713 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 11 states have (on average 2.909090909090909) internal successors, (32), 9 states have internal predecessors, (32), 4 states have call successors, (9), 3 states have call predecessors, (9), 2 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2023-03-31 23:17:33,713 INFO L276 IsEmpty]: Start isEmpty. Operand 79 states and 101 transitions. [2023-03-31 23:17:33,714 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 39 [2023-03-31 23:17:33,714 INFO L187 NwaCegarLoop]: Found error trace [2023-03-31 23:17:33,714 INFO L195 NwaCegarLoop]: trace histogram [4, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-03-31 23:17:33,731 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Forceful destruction successful, exit code 0 [2023-03-31 23:17:33,919 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-03-31 23:17:33,919 INFO L420 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-03-31 23:17:33,919 INFO L145 PredicateUnifier]: Initialized classic predicate unifier [2023-03-31 23:17:33,919 INFO L85 PathProgramCache]: Analyzing trace with hash 1622527176, now seen corresponding path program 1 times [2023-03-31 23:17:33,920 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-03-31 23:17:33,920 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [620194718] [2023-03-31 23:17:33,920 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-03-31 23:17:33,920 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-03-31 23:17:33,940 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-03-31 23:17:33,941 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1016704360] [2023-03-31 23:17:33,941 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-03-31 23:17:33,941 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-03-31 23:17:33,941 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-03-31 23:17:33,953 INFO L229 MonitoredProcess]: Starting monitored process 8 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-03-31 23:17:33,993 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2023-03-31 23:17:34,003 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-03-31 23:17:34,003 INFO L262 TraceCheckSpWp]: Trace formula consists of 130 conjuncts, 17 conjunts are in the unsatisfiable core [2023-03-31 23:17:34,005 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-03-31 23:17:34,063 INFO L134 CoverageAnalysis]: Checked inductivity of 20 backedges. 5 proven. 2 refuted. 0 times theorem prover too weak. 13 trivial. 0 not checked. [2023-03-31 23:17:34,064 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-03-31 23:17:34,107 INFO L134 CoverageAnalysis]: Checked inductivity of 20 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 16 trivial. 0 not checked. [2023-03-31 23:17:34,107 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-03-31 23:17:34,107 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [620194718] [2023-03-31 23:17:34,107 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-03-31 23:17:34,107 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1016704360] [2023-03-31 23:17:34,107 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1016704360] provided 1 perfect and 1 imperfect interpolant sequences [2023-03-31 23:17:34,107 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2023-03-31 23:17:34,107 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [8] total 11 [2023-03-31 23:17:34,107 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [747273228] [2023-03-31 23:17:34,108 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-03-31 23:17:34,108 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2023-03-31 23:17:34,109 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-03-31 23:17:34,109 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2023-03-31 23:17:34,109 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=23, Invalid=87, Unknown=0, NotChecked=0, Total=110 [2023-03-31 23:17:34,109 INFO L87 Difference]: Start difference. First operand 79 states and 101 transitions. Second operand has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 2 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2023-03-31 23:17:34,161 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-03-31 23:17:34,161 INFO L93 Difference]: Finished difference Result 111 states and 149 transitions. [2023-03-31 23:17:34,162 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2023-03-31 23:17:34,162 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 2 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) Word has length 38 [2023-03-31 23:17:34,162 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-03-31 23:17:34,163 INFO L225 Difference]: With dead ends: 111 [2023-03-31 23:17:34,163 INFO L226 Difference]: Without dead ends: 109 [2023-03-31 23:17:34,163 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 76 GetRequests, 66 SyntacticMatches, 0 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 9 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=27, Invalid=105, Unknown=0, NotChecked=0, Total=132 [2023-03-31 23:17:34,164 INFO L413 NwaCegarLoop]: 33 mSDtfsCounter, 7 mSDsluCounter, 75 mSDsCounter, 0 mSdLazyCounter, 59 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 9 SdHoareTripleChecker+Valid, 108 SdHoareTripleChecker+Invalid, 60 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 59 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-03-31 23:17:34,164 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [9 Valid, 108 Invalid, 60 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 59 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-03-31 23:17:34,164 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 109 states. [2023-03-31 23:17:34,201 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 109 to 105. [2023-03-31 23:17:34,202 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 105 states, 66 states have (on average 1.2575757575757576) internal successors, (83), 67 states have internal predecessors, (83), 31 states have call successors, (31), 8 states have call predecessors, (31), 7 states have return successors, (29), 29 states have call predecessors, (29), 29 states have call successors, (29) [2023-03-31 23:17:34,204 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 105 states to 105 states and 143 transitions. [2023-03-31 23:17:34,205 INFO L78 Accepts]: Start accepts. Automaton has 105 states and 143 transitions. Word has length 38 [2023-03-31 23:17:34,205 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-03-31 23:17:34,205 INFO L495 AbstractCegarLoop]: Abstraction has 105 states and 143 transitions. [2023-03-31 23:17:34,205 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 2 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2023-03-31 23:17:34,205 INFO L276 IsEmpty]: Start isEmpty. Operand 105 states and 143 transitions. [2023-03-31 23:17:34,206 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 39 [2023-03-31 23:17:34,206 INFO L187 NwaCegarLoop]: Found error trace [2023-03-31 23:17:34,207 INFO L195 NwaCegarLoop]: trace histogram [4, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-03-31 23:17:34,211 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Ended with exit code 0 [2023-03-31 23:17:34,412 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-03-31 23:17:34,412 INFO L420 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-03-31 23:17:34,413 INFO L145 PredicateUnifier]: Initialized classic predicate unifier [2023-03-31 23:17:34,413 INFO L85 PathProgramCache]: Analyzing trace with hash -1229660379, now seen corresponding path program 1 times [2023-03-31 23:17:34,413 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-03-31 23:17:34,413 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2115373465] [2023-03-31 23:17:34,413 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-03-31 23:17:34,413 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-03-31 23:17:34,422 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-03-31 23:17:34,422 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [342385820] [2023-03-31 23:17:34,422 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-03-31 23:17:34,422 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-03-31 23:17:34,422 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-03-31 23:17:34,423 INFO L229 MonitoredProcess]: Starting monitored process 9 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-03-31 23:17:34,425 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2023-03-31 23:17:34,469 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-03-31 23:17:34,470 INFO L262 TraceCheckSpWp]: Trace formula consists of 143 conjuncts, 38 conjunts are in the unsatisfiable core [2023-03-31 23:17:34,472 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-03-31 23:17:34,646 INFO L134 CoverageAnalysis]: Checked inductivity of 18 backedges. 3 proven. 6 refuted. 0 times theorem prover too weak. 9 trivial. 0 not checked. [2023-03-31 23:17:34,647 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-03-31 23:17:34,772 INFO L134 CoverageAnalysis]: Checked inductivity of 18 backedges. 2 proven. 4 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2023-03-31 23:17:34,772 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-03-31 23:17:34,772 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2115373465] [2023-03-31 23:17:34,772 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-03-31 23:17:34,772 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [342385820] [2023-03-31 23:17:34,772 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [342385820] provided 0 perfect and 2 imperfect interpolant sequences [2023-03-31 23:17:34,772 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1692475993] [2023-03-31 23:17:34,775 INFO L159 IcfgInterpreter]: Started Sifa with 27 locations of interest [2023-03-31 23:17:34,775 INFO L166 IcfgInterpreter]: Building call graph [2023-03-31 23:17:34,776 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-03-31 23:17:34,776 INFO L176 IcfgInterpreter]: Starting interpretation [2023-03-31 23:17:34,777 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-03-31 23:17:34,786 INFO L197 IcfgInterpreter]: Interpreting procedure main with input of size 8 for LOIs [2023-03-31 23:17:34,975 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 8 for LOIs [2023-03-31 23:17:34,979 INFO L197 IcfgInterpreter]: Interpreting procedure assume_abort_if_not with input of size 8 for LOIs [2023-03-31 23:17:34,980 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.init with input of size 7 for LOIs [2023-03-31 23:17:34,982 INFO L180 IcfgInterpreter]: Interpretation finished [2023-03-31 23:17:35,572 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '2848#(and (= |__VERIFIER_assert_#in~cond| 0) (= __VERIFIER_assert_~cond 0) (= |#NULL.offset| 0) (<= 0 |#StackHeapBarrier|) (= |#NULL.base| 0))' at error location [2023-03-31 23:17:35,572 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-03-31 23:17:35,572 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-03-31 23:17:35,572 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 8] total 17 [2023-03-31 23:17:35,572 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [264221042] [2023-03-31 23:17:35,573 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-03-31 23:17:35,573 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 17 states [2023-03-31 23:17:35,573 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-03-31 23:17:35,573 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2023-03-31 23:17:35,574 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=180, Invalid=1080, Unknown=0, NotChecked=0, Total=1260 [2023-03-31 23:17:35,574 INFO L87 Difference]: Start difference. First operand 105 states and 143 transitions. Second operand has 17 states, 16 states have (on average 2.375) internal successors, (38), 15 states have internal predecessors, (38), 4 states have call successors, (11), 3 states have call predecessors, (11), 3 states have return successors, (9), 4 states have call predecessors, (9), 4 states have call successors, (9) [2023-03-31 23:17:38,625 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-03-31 23:17:38,626 INFO L93 Difference]: Finished difference Result 148 states and 202 transitions. [2023-03-31 23:17:38,626 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 22 states. [2023-03-31 23:17:38,626 INFO L78 Accepts]: Start accepts. Automaton has has 17 states, 16 states have (on average 2.375) internal successors, (38), 15 states have internal predecessors, (38), 4 states have call successors, (11), 3 states have call predecessors, (11), 3 states have return successors, (9), 4 states have call predecessors, (9), 4 states have call successors, (9) Word has length 38 [2023-03-31 23:17:38,626 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-03-31 23:17:38,628 INFO L225 Difference]: With dead ends: 148 [2023-03-31 23:17:38,628 INFO L226 Difference]: Without dead ends: 146 [2023-03-31 23:17:38,629 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 129 GetRequests, 79 SyntacticMatches, 0 SemanticMatches, 50 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 701 ImplicationChecksByTransitivity, 1.8s TimeCoverageRelationStatistics Valid=344, Invalid=2308, Unknown=0, NotChecked=0, Total=2652 [2023-03-31 23:17:38,629 INFO L413 NwaCegarLoop]: 27 mSDtfsCounter, 150 mSDsluCounter, 146 mSDsCounter, 0 mSdLazyCounter, 496 mSolverCounterSat, 89 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.8s Time, 0 mProtectedPredicate, 0 mProtectedAction, 150 SdHoareTripleChecker+Valid, 173 SdHoareTripleChecker+Invalid, 585 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 89 IncrementalHoareTripleChecker+Valid, 496 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.9s IncrementalHoareTripleChecker+Time [2023-03-31 23:17:38,629 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [150 Valid, 173 Invalid, 585 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [89 Valid, 496 Invalid, 0 Unknown, 0 Unchecked, 1.9s Time] [2023-03-31 23:17:38,630 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 146 states. [2023-03-31 23:17:38,663 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 146 to 124. [2023-03-31 23:17:38,663 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 124 states, 79 states have (on average 1.240506329113924) internal successors, (98), 82 states have internal predecessors, (98), 35 states have call successors, (35), 10 states have call predecessors, (35), 9 states have return successors, (33), 31 states have call predecessors, (33), 33 states have call successors, (33) [2023-03-31 23:17:38,664 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 124 states to 124 states and 166 transitions. [2023-03-31 23:17:38,664 INFO L78 Accepts]: Start accepts. Automaton has 124 states and 166 transitions. Word has length 38 [2023-03-31 23:17:38,664 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-03-31 23:17:38,664 INFO L495 AbstractCegarLoop]: Abstraction has 124 states and 166 transitions. [2023-03-31 23:17:38,664 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 17 states, 16 states have (on average 2.375) internal successors, (38), 15 states have internal predecessors, (38), 4 states have call successors, (11), 3 states have call predecessors, (11), 3 states have return successors, (9), 4 states have call predecessors, (9), 4 states have call successors, (9) [2023-03-31 23:17:38,664 INFO L276 IsEmpty]: Start isEmpty. Operand 124 states and 166 transitions. [2023-03-31 23:17:38,665 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 39 [2023-03-31 23:17:38,665 INFO L187 NwaCegarLoop]: Found error trace [2023-03-31 23:17:38,665 INFO L195 NwaCegarLoop]: trace histogram [4, 3, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-03-31 23:17:38,669 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Ended with exit code 0 [2023-03-31 23:17:38,869 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 9 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable7 [2023-03-31 23:17:38,869 INFO L420 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-03-31 23:17:38,870 INFO L145 PredicateUnifier]: Initialized classic predicate unifier [2023-03-31 23:17:38,870 INFO L85 PathProgramCache]: Analyzing trace with hash -918284568, now seen corresponding path program 2 times [2023-03-31 23:17:38,870 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-03-31 23:17:38,870 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [831474185] [2023-03-31 23:17:38,870 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-03-31 23:17:38,870 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-03-31 23:17:38,877 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-03-31 23:17:38,877 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1312547114] [2023-03-31 23:17:38,877 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2023-03-31 23:17:38,877 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-03-31 23:17:38,877 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-03-31 23:17:38,878 INFO L229 MonitoredProcess]: Starting monitored process 10 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-03-31 23:17:38,880 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Waiting until timeout for monitored process [2023-03-31 23:17:38,915 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2023-03-31 23:17:38,915 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-03-31 23:17:38,915 INFO L262 TraceCheckSpWp]: Trace formula consists of 148 conjuncts, 5 conjunts are in the unsatisfiable core [2023-03-31 23:17:38,916 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-03-31 23:17:38,935 INFO L134 CoverageAnalysis]: Checked inductivity of 25 backedges. 13 proven. 0 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2023-03-31 23:17:38,935 INFO L323 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2023-03-31 23:17:38,935 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-03-31 23:17:38,935 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [831474185] [2023-03-31 23:17:38,935 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-03-31 23:17:38,935 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1312547114] [2023-03-31 23:17:38,936 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1312547114] provided 1 perfect and 0 imperfect interpolant sequences [2023-03-31 23:17:38,936 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-03-31 23:17:38,936 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2023-03-31 23:17:38,936 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1951561986] [2023-03-31 23:17:38,936 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-03-31 23:17:38,936 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2023-03-31 23:17:38,936 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-03-31 23:17:38,936 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2023-03-31 23:17:38,937 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2023-03-31 23:17:38,937 INFO L87 Difference]: Start difference. First operand 124 states and 166 transitions. Second operand has 5 states, 5 states have (on average 4.6) internal successors, (23), 5 states have internal predecessors, (23), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (5), 1 states have call predecessors, (5), 1 states have call successors, (5) [2023-03-31 23:17:39,032 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-03-31 23:17:39,032 INFO L93 Difference]: Finished difference Result 164 states and 218 transitions. [2023-03-31 23:17:39,032 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2023-03-31 23:17:39,032 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 4.6) internal successors, (23), 5 states have internal predecessors, (23), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (5), 1 states have call predecessors, (5), 1 states have call successors, (5) Word has length 38 [2023-03-31 23:17:39,032 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-03-31 23:17:39,033 INFO L225 Difference]: With dead ends: 164 [2023-03-31 23:17:39,033 INFO L226 Difference]: Without dead ends: 116 [2023-03-31 23:17:39,033 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 40 GetRequests, 35 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=15, Invalid=27, Unknown=0, NotChecked=0, Total=42 [2023-03-31 23:17:39,034 INFO L413 NwaCegarLoop]: 48 mSDtfsCounter, 19 mSDsluCounter, 83 mSDsCounter, 0 mSdLazyCounter, 86 mSolverCounterSat, 8 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 23 SdHoareTripleChecker+Valid, 131 SdHoareTripleChecker+Invalid, 94 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 8 IncrementalHoareTripleChecker+Valid, 86 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-03-31 23:17:39,034 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [23 Valid, 131 Invalid, 94 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [8 Valid, 86 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-03-31 23:17:39,034 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 116 states. [2023-03-31 23:17:39,066 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 116 to 114. [2023-03-31 23:17:39,066 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 114 states, 69 states have (on average 1.1884057971014492) internal successors, (82), 72 states have internal predecessors, (82), 35 states have call successors, (35), 10 states have call predecessors, (35), 9 states have return successors, (33), 31 states have call predecessors, (33), 33 states have call successors, (33) [2023-03-31 23:17:39,067 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 114 states to 114 states and 150 transitions. [2023-03-31 23:17:39,067 INFO L78 Accepts]: Start accepts. Automaton has 114 states and 150 transitions. Word has length 38 [2023-03-31 23:17:39,067 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-03-31 23:17:39,067 INFO L495 AbstractCegarLoop]: Abstraction has 114 states and 150 transitions. [2023-03-31 23:17:39,067 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 4.6) internal successors, (23), 5 states have internal predecessors, (23), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (5), 1 states have call predecessors, (5), 1 states have call successors, (5) [2023-03-31 23:17:39,067 INFO L276 IsEmpty]: Start isEmpty. Operand 114 states and 150 transitions. [2023-03-31 23:17:39,069 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 44 [2023-03-31 23:17:39,069 INFO L187 NwaCegarLoop]: Found error trace [2023-03-31 23:17:39,069 INFO L195 NwaCegarLoop]: trace histogram [4, 4, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-03-31 23:17:39,078 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Ended with exit code 0 [2023-03-31 23:17:39,273 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,10 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-03-31 23:17:39,273 INFO L420 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-03-31 23:17:39,273 INFO L145 PredicateUnifier]: Initialized classic predicate unifier [2023-03-31 23:17:39,273 INFO L85 PathProgramCache]: Analyzing trace with hash 1365373227, now seen corresponding path program 1 times [2023-03-31 23:17:39,274 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-03-31 23:17:39,274 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1074995970] [2023-03-31 23:17:39,274 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-03-31 23:17:39,274 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-03-31 23:17:39,283 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-03-31 23:17:39,283 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1607224054] [2023-03-31 23:17:39,283 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-03-31 23:17:39,284 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-03-31 23:17:39,284 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-03-31 23:17:39,284 INFO L229 MonitoredProcess]: Starting monitored process 11 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-03-31 23:17:39,292 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Waiting until timeout for monitored process [2023-03-31 23:17:39,326 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-03-31 23:17:39,326 INFO L262 TraceCheckSpWp]: Trace formula consists of 139 conjuncts, 15 conjunts are in the unsatisfiable core [2023-03-31 23:17:39,327 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-03-31 23:17:39,383 INFO L134 CoverageAnalysis]: Checked inductivity of 30 backedges. 8 proven. 1 refuted. 0 times theorem prover too weak. 21 trivial. 0 not checked. [2023-03-31 23:17:39,383 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-03-31 23:17:39,435 INFO L134 CoverageAnalysis]: Checked inductivity of 30 backedges. 6 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2023-03-31 23:17:39,435 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-03-31 23:17:39,435 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1074995970] [2023-03-31 23:17:39,435 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-03-31 23:17:39,435 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1607224054] [2023-03-31 23:17:39,435 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1607224054] provided 1 perfect and 1 imperfect interpolant sequences [2023-03-31 23:17:39,435 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2023-03-31 23:17:39,435 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [6] total 9 [2023-03-31 23:17:39,436 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1671419636] [2023-03-31 23:17:39,436 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-03-31 23:17:39,436 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2023-03-31 23:17:39,436 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-03-31 23:17:39,436 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2023-03-31 23:17:39,436 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=18, Invalid=54, Unknown=0, NotChecked=0, Total=72 [2023-03-31 23:17:39,436 INFO L87 Difference]: Start difference. First operand 114 states and 150 transitions. Second operand has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 2 states have call successors, (10), 2 states have call predecessors, (10), 1 states have return successors, (8), 2 states have call predecessors, (8), 2 states have call successors, (8) [2023-03-31 23:17:39,505 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-03-31 23:17:39,506 INFO L93 Difference]: Finished difference Result 120 states and 155 transitions. [2023-03-31 23:17:39,506 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2023-03-31 23:17:39,506 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 2 states have call successors, (10), 2 states have call predecessors, (10), 1 states have return successors, (8), 2 states have call predecessors, (8), 2 states have call successors, (8) Word has length 43 [2023-03-31 23:17:39,506 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-03-31 23:17:39,507 INFO L225 Difference]: With dead ends: 120 [2023-03-31 23:17:39,507 INFO L226 Difference]: Without dead ends: 118 [2023-03-31 23:17:39,507 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 86 GetRequests, 78 SyntacticMatches, 0 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=22, Invalid=68, Unknown=0, NotChecked=0, Total=90 [2023-03-31 23:17:39,507 INFO L413 NwaCegarLoop]: 37 mSDtfsCounter, 8 mSDsluCounter, 81 mSDsCounter, 0 mSdLazyCounter, 53 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 9 SdHoareTripleChecker+Valid, 118 SdHoareTripleChecker+Invalid, 55 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 53 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-03-31 23:17:39,508 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [9 Valid, 118 Invalid, 55 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 53 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-03-31 23:17:39,508 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 118 states. [2023-03-31 23:17:39,538 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 118 to 118. [2023-03-31 23:17:39,539 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 118 states, 72 states have (on average 1.1805555555555556) internal successors, (85), 75 states have internal predecessors, (85), 35 states have call successors, (35), 11 states have call predecessors, (35), 10 states have return successors, (33), 31 states have call predecessors, (33), 33 states have call successors, (33) [2023-03-31 23:17:39,539 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 118 states to 118 states and 153 transitions. [2023-03-31 23:17:39,539 INFO L78 Accepts]: Start accepts. Automaton has 118 states and 153 transitions. Word has length 43 [2023-03-31 23:17:39,540 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-03-31 23:17:39,540 INFO L495 AbstractCegarLoop]: Abstraction has 118 states and 153 transitions. [2023-03-31 23:17:39,540 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 2 states have call successors, (10), 2 states have call predecessors, (10), 1 states have return successors, (8), 2 states have call predecessors, (8), 2 states have call successors, (8) [2023-03-31 23:17:39,540 INFO L276 IsEmpty]: Start isEmpty. Operand 118 states and 153 transitions. [2023-03-31 23:17:39,540 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 56 [2023-03-31 23:17:39,540 INFO L187 NwaCegarLoop]: Found error trace [2023-03-31 23:17:39,541 INFO L195 NwaCegarLoop]: trace histogram [5, 4, 4, 4, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-03-31 23:17:39,557 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Forceful destruction successful, exit code 0 [2023-03-31 23:17:39,745 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 11 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable9 [2023-03-31 23:17:39,745 INFO L420 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-03-31 23:17:39,745 INFO L145 PredicateUnifier]: Initialized classic predicate unifier [2023-03-31 23:17:39,745 INFO L85 PathProgramCache]: Analyzing trace with hash 656042662, now seen corresponding path program 1 times [2023-03-31 23:17:39,745 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-03-31 23:17:39,745 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1297289848] [2023-03-31 23:17:39,745 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-03-31 23:17:39,746 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-03-31 23:17:39,752 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-03-31 23:17:39,752 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1177612668] [2023-03-31 23:17:39,752 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-03-31 23:17:39,752 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-03-31 23:17:39,752 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-03-31 23:17:39,753 INFO L229 MonitoredProcess]: Starting monitored process 12 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-03-31 23:17:39,773 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Waiting until timeout for monitored process [2023-03-31 23:17:39,803 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-03-31 23:17:39,804 INFO L262 TraceCheckSpWp]: Trace formula consists of 172 conjuncts, 67 conjunts are in the unsatisfiable core [2023-03-31 23:17:39,806 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-03-31 23:17:40,341 INFO L134 CoverageAnalysis]: Checked inductivity of 48 backedges. 12 proven. 13 refuted. 0 times theorem prover too weak. 23 trivial. 0 not checked. [2023-03-31 23:17:40,342 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-03-31 23:17:41,082 INFO L134 CoverageAnalysis]: Checked inductivity of 48 backedges. 10 proven. 11 refuted. 0 times theorem prover too weak. 27 trivial. 0 not checked. [2023-03-31 23:17:41,082 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-03-31 23:17:41,082 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1297289848] [2023-03-31 23:17:41,082 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-03-31 23:17:41,082 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1177612668] [2023-03-31 23:17:41,082 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1177612668] provided 0 perfect and 2 imperfect interpolant sequences [2023-03-31 23:17:41,082 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [843505893] [2023-03-31 23:17:41,083 INFO L159 IcfgInterpreter]: Started Sifa with 32 locations of interest [2023-03-31 23:17:41,083 INFO L166 IcfgInterpreter]: Building call graph [2023-03-31 23:17:41,084 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-03-31 23:17:41,084 INFO L176 IcfgInterpreter]: Starting interpretation [2023-03-31 23:17:41,084 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-03-31 23:17:41,093 INFO L197 IcfgInterpreter]: Interpreting procedure main with input of size 8 for LOIs [2023-03-31 23:17:41,584 WARN L110 ntervalStateProvider]: Interval conversion did not stabilize in 12 iterations. Over-approximation may be very coarse. [2023-03-31 23:17:41,585 WARN L110 ntervalStateProvider]: Interval conversion did not stabilize in 12 iterations. Over-approximation may be very coarse. [2023-03-31 23:17:41,805 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 8 for LOIs [2023-03-31 23:17:41,807 INFO L197 IcfgInterpreter]: Interpreting procedure assume_abort_if_not with input of size 8 for LOIs [2023-03-31 23:17:41,808 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.init with input of size 7 for LOIs [2023-03-31 23:17:41,810 INFO L180 IcfgInterpreter]: Interpretation finished [2023-03-31 23:17:44,092 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '4859#(and (= |__VERIFIER_assert_#in~cond| 0) (= __VERIFIER_assert_~cond 0) (= |#NULL.offset| 0) (<= 0 |#StackHeapBarrier|) (= |#NULL.base| 0))' at error location [2023-03-31 23:17:44,092 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-03-31 23:17:44,093 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-03-31 23:17:44,093 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 13] total 26 [2023-03-31 23:17:44,093 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1405270120] [2023-03-31 23:17:44,093 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-03-31 23:17:44,093 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 26 states [2023-03-31 23:17:44,098 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-03-31 23:17:44,105 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 26 interpolants. [2023-03-31 23:17:44,105 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=272, Invalid=1890, Unknown=0, NotChecked=0, Total=2162 [2023-03-31 23:17:44,106 INFO L87 Difference]: Start difference. First operand 118 states and 153 transitions. Second operand has 26 states, 22 states have (on average 2.0) internal successors, (44), 22 states have internal predecessors, (44), 8 states have call successors, (18), 3 states have call predecessors, (18), 3 states have return successors, (16), 6 states have call predecessors, (16), 6 states have call successors, (16) [2023-03-31 23:17:53,971 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-03-31 23:17:53,971 INFO L93 Difference]: Finished difference Result 338 states and 469 transitions. [2023-03-31 23:17:53,971 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 36 states. [2023-03-31 23:17:53,971 INFO L78 Accepts]: Start accepts. Automaton has has 26 states, 22 states have (on average 2.0) internal successors, (44), 22 states have internal predecessors, (44), 8 states have call successors, (18), 3 states have call predecessors, (18), 3 states have return successors, (16), 6 states have call predecessors, (16), 6 states have call successors, (16) Word has length 55 [2023-03-31 23:17:53,971 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-03-31 23:17:53,973 INFO L225 Difference]: With dead ends: 338 [2023-03-31 23:17:53,973 INFO L226 Difference]: Without dead ends: 250 [2023-03-31 23:17:53,975 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 191 GetRequests, 119 SyntacticMatches, 0 SemanticMatches, 72 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1535 ImplicationChecksByTransitivity, 8.5s TimeCoverageRelationStatistics Valid=701, Invalid=4701, Unknown=0, NotChecked=0, Total=5402 [2023-03-31 23:17:53,975 INFO L413 NwaCegarLoop]: 28 mSDtfsCounter, 176 mSDsluCounter, 169 mSDsCounter, 0 mSdLazyCounter, 666 mSolverCounterSat, 162 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 4.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 182 SdHoareTripleChecker+Valid, 197 SdHoareTripleChecker+Invalid, 828 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 162 IncrementalHoareTripleChecker+Valid, 666 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 4.2s IncrementalHoareTripleChecker+Time [2023-03-31 23:17:53,976 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [182 Valid, 197 Invalid, 828 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [162 Valid, 666 Invalid, 0 Unknown, 0 Unchecked, 4.2s Time] [2023-03-31 23:17:53,976 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 250 states. [2023-03-31 23:17:54,060 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 250 to 207. [2023-03-31 23:17:54,061 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 207 states, 133 states have (on average 1.1879699248120301) internal successors, (158), 136 states have internal predecessors, (158), 59 states have call successors, (59), 15 states have call predecessors, (59), 14 states have return successors, (57), 55 states have call predecessors, (57), 57 states have call successors, (57) [2023-03-31 23:17:54,065 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 207 states to 207 states and 274 transitions. [2023-03-31 23:17:54,065 INFO L78 Accepts]: Start accepts. Automaton has 207 states and 274 transitions. Word has length 55 [2023-03-31 23:17:54,065 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-03-31 23:17:54,065 INFO L495 AbstractCegarLoop]: Abstraction has 207 states and 274 transitions. [2023-03-31 23:17:54,065 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 26 states, 22 states have (on average 2.0) internal successors, (44), 22 states have internal predecessors, (44), 8 states have call successors, (18), 3 states have call predecessors, (18), 3 states have return successors, (16), 6 states have call predecessors, (16), 6 states have call successors, (16) [2023-03-31 23:17:54,065 INFO L276 IsEmpty]: Start isEmpty. Operand 207 states and 274 transitions. [2023-03-31 23:17:54,066 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 64 [2023-03-31 23:17:54,066 INFO L187 NwaCegarLoop]: Found error trace [2023-03-31 23:17:54,066 INFO L195 NwaCegarLoop]: trace histogram [5, 4, 4, 4, 4, 3, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-03-31 23:17:54,073 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Forceful destruction successful, exit code 0 [2023-03-31 23:17:54,271 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 12 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable10 [2023-03-31 23:17:54,271 INFO L420 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-03-31 23:17:54,272 INFO L145 PredicateUnifier]: Initialized classic predicate unifier [2023-03-31 23:17:54,272 INFO L85 PathProgramCache]: Analyzing trace with hash -537054492, now seen corresponding path program 1 times [2023-03-31 23:17:54,272 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-03-31 23:17:54,272 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [604706243] [2023-03-31 23:17:54,272 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-03-31 23:17:54,272 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-03-31 23:17:54,286 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-03-31 23:17:54,286 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1568337624] [2023-03-31 23:17:54,287 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-03-31 23:17:54,287 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-03-31 23:17:54,287 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-03-31 23:17:54,298 INFO L229 MonitoredProcess]: Starting monitored process 13 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-03-31 23:17:54,300 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Waiting until timeout for monitored process [2023-03-31 23:17:54,348 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-03-31 23:17:54,349 INFO L262 TraceCheckSpWp]: Trace formula consists of 204 conjuncts, 60 conjunts are in the unsatisfiable core [2023-03-31 23:17:54,352 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-03-31 23:17:54,753 INFO L134 CoverageAnalysis]: Checked inductivity of 65 backedges. 12 proven. 29 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2023-03-31 23:17:54,753 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-03-31 23:17:55,159 INFO L134 CoverageAnalysis]: Checked inductivity of 65 backedges. 25 proven. 9 refuted. 0 times theorem prover too weak. 31 trivial. 0 not checked. [2023-03-31 23:17:55,159 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-03-31 23:17:55,159 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [604706243] [2023-03-31 23:17:55,160 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-03-31 23:17:55,160 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1568337624] [2023-03-31 23:17:55,160 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1568337624] provided 0 perfect and 2 imperfect interpolant sequences [2023-03-31 23:17:55,160 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1810816591] [2023-03-31 23:17:55,161 INFO L159 IcfgInterpreter]: Started Sifa with 31 locations of interest [2023-03-31 23:17:55,161 INFO L166 IcfgInterpreter]: Building call graph [2023-03-31 23:17:55,161 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-03-31 23:17:55,161 INFO L176 IcfgInterpreter]: Starting interpretation [2023-03-31 23:17:55,161 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-03-31 23:17:55,171 INFO L197 IcfgInterpreter]: Interpreting procedure main with input of size 8 for LOIs [2023-03-31 23:17:55,692 WARN L110 ntervalStateProvider]: Interval conversion did not stabilize in 12 iterations. Over-approximation may be very coarse. [2023-03-31 23:17:55,695 WARN L110 ntervalStateProvider]: Interval conversion did not stabilize in 12 iterations. Over-approximation may be very coarse. [2023-03-31 23:17:55,957 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 8 for LOIs [2023-03-31 23:17:55,960 INFO L197 IcfgInterpreter]: Interpreting procedure assume_abort_if_not with input of size 8 for LOIs [2023-03-31 23:17:55,961 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.init with input of size 7 for LOIs [2023-03-31 23:17:55,963 INFO L180 IcfgInterpreter]: Interpretation finished [2023-03-31 23:17:56,824 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '6184#(and (= |__VERIFIER_assert_#in~cond| 0) (= __VERIFIER_assert_~cond 0) (= |#NULL.offset| 0) (<= 0 |#StackHeapBarrier|) (= |#NULL.base| 0))' at error location [2023-03-31 23:17:56,824 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-03-31 23:17:56,824 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-03-31 23:17:56,824 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [17, 8] total 22 [2023-03-31 23:17:56,824 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [937751727] [2023-03-31 23:17:56,824 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-03-31 23:17:56,824 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 22 states [2023-03-31 23:17:56,824 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-03-31 23:17:56,825 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 22 interpolants. [2023-03-31 23:17:56,825 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=215, Invalid=1507, Unknown=0, NotChecked=0, Total=1722 [2023-03-31 23:17:56,825 INFO L87 Difference]: Start difference. First operand 207 states and 274 transitions. Second operand has 22 states, 21 states have (on average 2.7142857142857144) internal successors, (57), 19 states have internal predecessors, (57), 6 states have call successors, (17), 3 states have call predecessors, (17), 3 states have return successors, (15), 4 states have call predecessors, (15), 4 states have call successors, (15) [2023-03-31 23:18:04,091 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-03-31 23:18:04,091 INFO L93 Difference]: Finished difference Result 313 states and 423 transitions. [2023-03-31 23:18:04,092 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 20 states. [2023-03-31 23:18:04,092 INFO L78 Accepts]: Start accepts. Automaton has has 22 states, 21 states have (on average 2.7142857142857144) internal successors, (57), 19 states have internal predecessors, (57), 6 states have call successors, (17), 3 states have call predecessors, (17), 3 states have return successors, (15), 4 states have call predecessors, (15), 4 states have call successors, (15) Word has length 63 [2023-03-31 23:18:04,092 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-03-31 23:18:04,093 INFO L225 Difference]: With dead ends: 313 [2023-03-31 23:18:04,093 INFO L226 Difference]: Without dead ends: 258 [2023-03-31 23:18:04,094 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 210 GetRequests, 157 SyntacticMatches, 0 SemanticMatches, 53 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 780 ImplicationChecksByTransitivity, 5.5s TimeCoverageRelationStatistics Valid=345, Invalid=2625, Unknown=0, NotChecked=0, Total=2970 [2023-03-31 23:18:04,094 INFO L413 NwaCegarLoop]: 43 mSDtfsCounter, 106 mSDsluCounter, 274 mSDsCounter, 0 mSdLazyCounter, 753 mSolverCounterSat, 76 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 2.8s Time, 0 mProtectedPredicate, 0 mProtectedAction, 108 SdHoareTripleChecker+Valid, 317 SdHoareTripleChecker+Invalid, 829 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 76 IncrementalHoareTripleChecker+Valid, 753 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 2.9s IncrementalHoareTripleChecker+Time [2023-03-31 23:18:04,094 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [108 Valid, 317 Invalid, 829 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [76 Valid, 753 Invalid, 0 Unknown, 0 Unchecked, 2.9s Time] [2023-03-31 23:18:04,095 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 258 states. [2023-03-31 23:18:04,193 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 258 to 217. [2023-03-31 23:18:04,194 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 217 states, 140 states have (on average 1.1857142857142857) internal successors, (166), 142 states have internal predecessors, (166), 61 states have call successors, (61), 16 states have call predecessors, (61), 15 states have return successors, (59), 58 states have call predecessors, (59), 59 states have call successors, (59) [2023-03-31 23:18:04,198 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 217 states to 217 states and 286 transitions. [2023-03-31 23:18:04,198 INFO L78 Accepts]: Start accepts. Automaton has 217 states and 286 transitions. Word has length 63 [2023-03-31 23:18:04,198 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-03-31 23:18:04,198 INFO L495 AbstractCegarLoop]: Abstraction has 217 states and 286 transitions. [2023-03-31 23:18:04,198 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 22 states, 21 states have (on average 2.7142857142857144) internal successors, (57), 19 states have internal predecessors, (57), 6 states have call successors, (17), 3 states have call predecessors, (17), 3 states have return successors, (15), 4 states have call predecessors, (15), 4 states have call successors, (15) [2023-03-31 23:18:04,198 INFO L276 IsEmpty]: Start isEmpty. Operand 217 states and 286 transitions. [2023-03-31 23:18:04,199 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 69 [2023-03-31 23:18:04,199 INFO L187 NwaCegarLoop]: Found error trace [2023-03-31 23:18:04,199 INFO L195 NwaCegarLoop]: trace histogram [6, 5, 5, 4, 4, 3, 3, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-03-31 23:18:04,204 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Ended with exit code 0 [2023-03-31 23:18:04,404 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 13 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable11 [2023-03-31 23:18:04,404 INFO L420 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-03-31 23:18:04,405 INFO L145 PredicateUnifier]: Initialized classic predicate unifier [2023-03-31 23:18:04,405 INFO L85 PathProgramCache]: Analyzing trace with hash -2074620657, now seen corresponding path program 2 times [2023-03-31 23:18:04,405 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-03-31 23:18:04,405 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1296471811] [2023-03-31 23:18:04,405 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-03-31 23:18:04,405 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-03-31 23:18:04,411 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-03-31 23:18:04,411 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [281203248] [2023-03-31 23:18:04,411 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2023-03-31 23:18:04,411 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-03-31 23:18:04,411 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-03-31 23:18:04,412 INFO L229 MonitoredProcess]: Starting monitored process 14 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-03-31 23:18:04,414 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Waiting until timeout for monitored process [2023-03-31 23:18:04,462 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2023-03-31 23:18:04,463 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-03-31 23:18:04,464 INFO L262 TraceCheckSpWp]: Trace formula consists of 178 conjuncts, 68 conjunts are in the unsatisfiable core [2023-03-31 23:18:04,466 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-03-31 23:18:04,977 INFO L134 CoverageAnalysis]: Checked inductivity of 84 backedges. 13 proven. 22 refuted. 0 times theorem prover too weak. 49 trivial. 0 not checked. [2023-03-31 23:18:04,977 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-03-31 23:18:06,330 INFO L134 CoverageAnalysis]: Checked inductivity of 84 backedges. 14 proven. 18 refuted. 0 times theorem prover too weak. 52 trivial. 0 not checked. [2023-03-31 23:18:06,330 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-03-31 23:18:06,330 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1296471811] [2023-03-31 23:18:06,330 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-03-31 23:18:06,330 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [281203248] [2023-03-31 23:18:06,331 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [281203248] provided 0 perfect and 2 imperfect interpolant sequences [2023-03-31 23:18:06,331 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1577902664] [2023-03-31 23:18:06,340 INFO L159 IcfgInterpreter]: Started Sifa with 31 locations of interest [2023-03-31 23:18:06,340 INFO L166 IcfgInterpreter]: Building call graph [2023-03-31 23:18:06,340 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-03-31 23:18:06,341 INFO L176 IcfgInterpreter]: Starting interpretation [2023-03-31 23:18:06,341 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-03-31 23:18:06,350 INFO L197 IcfgInterpreter]: Interpreting procedure main with input of size 8 for LOIs [2023-03-31 23:18:06,873 WARN L110 ntervalStateProvider]: Interval conversion did not stabilize in 12 iterations. Over-approximation may be very coarse. [2023-03-31 23:18:06,874 WARN L110 ntervalStateProvider]: Interval conversion did not stabilize in 12 iterations. Over-approximation may be very coarse. [2023-03-31 23:18:07,111 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 8 for LOIs [2023-03-31 23:18:07,114 INFO L197 IcfgInterpreter]: Interpreting procedure assume_abort_if_not with input of size 8 for LOIs [2023-03-31 23:18:07,115 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.init with input of size 7 for LOIs [2023-03-31 23:18:07,117 INFO L180 IcfgInterpreter]: Interpretation finished [2023-03-31 23:18:12,899 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '7489#(and (= |__VERIFIER_assert_#in~cond| 0) (= __VERIFIER_assert_~cond 0) (= |#NULL.offset| 0) (<= 0 |#StackHeapBarrier|) (= |#NULL.base| 0))' at error location [2023-03-31 23:18:12,900 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-03-31 23:18:12,900 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-03-31 23:18:12,900 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 14] total 28 [2023-03-31 23:18:12,900 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1748418683] [2023-03-31 23:18:12,900 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-03-31 23:18:12,900 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 28 states [2023-03-31 23:18:12,900 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-03-31 23:18:12,901 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 28 interpolants. [2023-03-31 23:18:12,901 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=262, Invalid=1994, Unknown=0, NotChecked=0, Total=2256 [2023-03-31 23:18:12,901 INFO L87 Difference]: Start difference. First operand 217 states and 286 transitions. Second operand has 28 states, 27 states have (on average 2.037037037037037) internal successors, (55), 25 states have internal predecessors, (55), 5 states have call successors, (18), 3 states have call predecessors, (18), 2 states have return successors, (16), 6 states have call predecessors, (16), 5 states have call successors, (16) [2023-03-31 23:18:25,375 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-03-31 23:18:31,303 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-03-31 23:18:31,304 INFO L93 Difference]: Finished difference Result 345 states and 467 transitions. [2023-03-31 23:18:31,304 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 34 states. [2023-03-31 23:18:31,304 INFO L78 Accepts]: Start accepts. Automaton has has 28 states, 27 states have (on average 2.037037037037037) internal successors, (55), 25 states have internal predecessors, (55), 5 states have call successors, (18), 3 states have call predecessors, (18), 2 states have return successors, (16), 6 states have call predecessors, (16), 5 states have call successors, (16) Word has length 68 [2023-03-31 23:18:31,304 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-03-31 23:18:31,311 INFO L225 Difference]: With dead ends: 345 [2023-03-31 23:18:31,311 INFO L226 Difference]: Without dead ends: 343 [2023-03-31 23:18:31,313 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 230 GetRequests, 158 SyntacticMatches, 0 SemanticMatches, 72 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1566 ImplicationChecksByTransitivity, 17.3s TimeCoverageRelationStatistics Valid=717, Invalid=4685, Unknown=0, NotChecked=0, Total=5402 [2023-03-31 23:18:31,319 INFO L413 NwaCegarLoop]: 40 mSDtfsCounter, 224 mSDsluCounter, 305 mSDsCounter, 0 mSdLazyCounter, 1066 mSolverCounterSat, 186 mSolverCounterUnsat, 1 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 7.9s Time, 0 mProtectedPredicate, 0 mProtectedAction, 224 SdHoareTripleChecker+Valid, 345 SdHoareTripleChecker+Invalid, 1253 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 186 IncrementalHoareTripleChecker+Valid, 1066 IncrementalHoareTripleChecker+Invalid, 1 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 8.0s IncrementalHoareTripleChecker+Time [2023-03-31 23:18:31,320 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [224 Valid, 345 Invalid, 1253 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [186 Valid, 1066 Invalid, 1 Unknown, 0 Unchecked, 8.0s Time] [2023-03-31 23:18:31,320 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 343 states. [2023-03-31 23:18:31,480 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 343 to 304. [2023-03-31 23:18:31,481 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 304 states, 194 states have (on average 1.2010309278350515) internal successors, (233), 196 states have internal predecessors, (233), 89 states have call successors, (89), 21 states have call predecessors, (89), 20 states have return successors, (87), 86 states have call predecessors, (87), 87 states have call successors, (87) [2023-03-31 23:18:31,482 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 304 states to 304 states and 409 transitions. [2023-03-31 23:18:31,482 INFO L78 Accepts]: Start accepts. Automaton has 304 states and 409 transitions. Word has length 68 [2023-03-31 23:18:31,482 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-03-31 23:18:31,482 INFO L495 AbstractCegarLoop]: Abstraction has 304 states and 409 transitions. [2023-03-31 23:18:31,482 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 28 states, 27 states have (on average 2.037037037037037) internal successors, (55), 25 states have internal predecessors, (55), 5 states have call successors, (18), 3 states have call predecessors, (18), 2 states have return successors, (16), 6 states have call predecessors, (16), 5 states have call successors, (16) [2023-03-31 23:18:31,482 INFO L276 IsEmpty]: Start isEmpty. Operand 304 states and 409 transitions. [2023-03-31 23:18:31,483 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 83 [2023-03-31 23:18:31,483 INFO L187 NwaCegarLoop]: Found error trace [2023-03-31 23:18:31,483 INFO L195 NwaCegarLoop]: trace histogram [9, 8, 8, 4, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-03-31 23:18:31,488 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Forceful destruction successful, exit code 0 [2023-03-31 23:18:31,688 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 14 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable12 [2023-03-31 23:18:31,688 INFO L420 AbstractCegarLoop]: === Iteration 14 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-03-31 23:18:31,688 INFO L145 PredicateUnifier]: Initialized classic predicate unifier [2023-03-31 23:18:31,689 INFO L85 PathProgramCache]: Analyzing trace with hash -122986527, now seen corresponding path program 1 times [2023-03-31 23:18:31,689 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-03-31 23:18:31,689 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [406318700] [2023-03-31 23:18:31,689 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-03-31 23:18:31,689 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-03-31 23:18:31,695 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-03-31 23:18:31,695 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1714246714] [2023-03-31 23:18:31,695 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-03-31 23:18:31,695 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-03-31 23:18:31,695 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-03-31 23:18:31,696 INFO L229 MonitoredProcess]: Starting monitored process 15 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-03-31 23:18:31,698 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Waiting until timeout for monitored process [2023-03-31 23:18:31,764 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-03-31 23:18:31,766 INFO L262 TraceCheckSpWp]: Trace formula consists of 236 conjuncts, 79 conjunts are in the unsatisfiable core [2023-03-31 23:18:31,767 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-03-31 23:18:32,463 INFO L134 CoverageAnalysis]: Checked inductivity of 159 backedges. 18 proven. 20 refuted. 0 times theorem prover too weak. 121 trivial. 0 not checked. [2023-03-31 23:18:32,463 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-03-31 23:18:34,202 INFO L134 CoverageAnalysis]: Checked inductivity of 159 backedges. 16 proven. 19 refuted. 0 times theorem prover too weak. 124 trivial. 0 not checked. [2023-03-31 23:18:34,202 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-03-31 23:18:34,202 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [406318700] [2023-03-31 23:18:34,202 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-03-31 23:18:34,203 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1714246714] [2023-03-31 23:18:34,203 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1714246714] provided 0 perfect and 2 imperfect interpolant sequences [2023-03-31 23:18:34,203 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1214368446] [2023-03-31 23:18:34,204 INFO L159 IcfgInterpreter]: Started Sifa with 32 locations of interest [2023-03-31 23:18:34,205 INFO L166 IcfgInterpreter]: Building call graph [2023-03-31 23:18:34,205 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-03-31 23:18:34,205 INFO L176 IcfgInterpreter]: Starting interpretation [2023-03-31 23:18:34,205 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-03-31 23:18:34,216 INFO L197 IcfgInterpreter]: Interpreting procedure main with input of size 8 for LOIs [2023-03-31 23:18:34,893 WARN L110 ntervalStateProvider]: Interval conversion did not stabilize in 12 iterations. Over-approximation may be very coarse. [2023-03-31 23:18:34,916 WARN L110 ntervalStateProvider]: Interval conversion did not stabilize in 12 iterations. Over-approximation may be very coarse. [2023-03-31 23:18:35,742 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 8 for LOIs [2023-03-31 23:18:35,744 INFO L197 IcfgInterpreter]: Interpreting procedure assume_abort_if_not with input of size 8 for LOIs [2023-03-31 23:18:35,745 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.init with input of size 7 for LOIs [2023-03-31 23:18:35,756 INFO L180 IcfgInterpreter]: Interpretation finished [2023-03-31 23:18:38,694 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '9079#(and (= |__VERIFIER_assert_#in~cond| 0) (= __VERIFIER_assert_~cond 0) (= |#NULL.offset| 0) (<= 0 |#StackHeapBarrier|) (= |#NULL.base| 0))' at error location [2023-03-31 23:18:38,694 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-03-31 23:18:38,694 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-03-31 23:18:38,694 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [17, 14] total 29 [2023-03-31 23:18:38,694 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [120269938] [2023-03-31 23:18:38,695 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-03-31 23:18:38,695 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 29 states [2023-03-31 23:18:38,695 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-03-31 23:18:38,695 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 29 interpolants. [2023-03-31 23:18:38,696 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=259, Invalid=1997, Unknown=0, NotChecked=0, Total=2256 [2023-03-31 23:18:38,696 INFO L87 Difference]: Start difference. First operand 304 states and 409 transitions. Second operand has 29 states, 26 states have (on average 2.0384615384615383) internal successors, (53), 26 states have internal predecessors, (53), 8 states have call successors, (25), 3 states have call predecessors, (25), 2 states have return successors, (23), 6 states have call predecessors, (23), 6 states have call successors, (23)