/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 OctagonDomain -i ../sv-benchmarks/c/nla-digbench-scaling/cohencu-ll_unwindbound50.c -------------------------------------------------------------------------------- This is Ultimate 0.2.3-dev-f954360 [2023-04-02 22:36:47,763 INFO L177 SettingsManager]: Resetting all preferences to default values... [2023-04-02 22:36:47,765 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2023-04-02 22:36:47,796 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2023-04-02 22:36:47,796 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2023-04-02 22:36:47,798 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2023-04-02 22:36:47,802 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2023-04-02 22:36:47,803 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2023-04-02 22:36:47,804 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2023-04-02 22:36:47,808 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2023-04-02 22:36:47,809 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2023-04-02 22:36:47,810 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2023-04-02 22:36:47,811 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2023-04-02 22:36:47,812 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2023-04-02 22:36:47,813 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2023-04-02 22:36:47,814 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2023-04-02 22:36:47,814 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2023-04-02 22:36:47,815 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2023-04-02 22:36:47,816 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2023-04-02 22:36:47,820 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2023-04-02 22:36:47,821 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2023-04-02 22:36:47,821 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2023-04-02 22:36:47,822 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2023-04-02 22:36:47,823 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2023-04-02 22:36:47,829 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2023-04-02 22:36:47,829 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2023-04-02 22:36:47,829 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2023-04-02 22:36:47,830 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2023-04-02 22:36:47,830 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2023-04-02 22:36:47,831 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2023-04-02 22:36:47,831 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2023-04-02 22:36:47,831 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2023-04-02 22:36:47,832 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2023-04-02 22:36:47,833 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2023-04-02 22:36:47,833 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2023-04-02 22:36:47,834 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2023-04-02 22:36:47,834 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2023-04-02 22:36:47,834 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2023-04-02 22:36:47,834 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2023-04-02 22:36:47,835 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2023-04-02 22:36:47,835 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2023-04-02 22:36:47,836 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-04-02 22:36:47,858 INFO L113 SettingsManager]: Loading preferences was successful [2023-04-02 22:36:47,859 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2023-04-02 22:36:47,859 INFO L136 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2023-04-02 22:36:47,859 INFO L138 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2023-04-02 22:36:47,860 INFO L136 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2023-04-02 22:36:47,860 INFO L138 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2023-04-02 22:36:47,860 INFO L138 SettingsManager]: * User list type=DISABLED [2023-04-02 22:36:47,860 INFO L136 SettingsManager]: Preferences of Abstract Interpretation differ from their defaults: [2023-04-02 22:36:47,860 INFO L138 SettingsManager]: * Explicit value domain=true [2023-04-02 22:36:47,860 INFO L138 SettingsManager]: * Abstract domain for RCFG-of-the-future=PoormanAbstractDomain [2023-04-02 22:36:47,861 INFO L138 SettingsManager]: * Octagon Domain=false [2023-04-02 22:36:47,861 INFO L138 SettingsManager]: * Abstract domain=CompoundDomain [2023-04-02 22:36:47,861 INFO L138 SettingsManager]: * Check feasibility of abstract posts with an SMT solver=true [2023-04-02 22:36:47,861 INFO L138 SettingsManager]: * Use the RCFG-of-the-future interface=true [2023-04-02 22:36:47,861 INFO L138 SettingsManager]: * Interval Domain=false [2023-04-02 22:36:47,861 INFO L136 SettingsManager]: Preferences of Sifa differ from their defaults: [2023-04-02 22:36:47,861 INFO L138 SettingsManager]: * Call Summarizer=TopInputCallSummarizer [2023-04-02 22:36:47,861 INFO L138 SettingsManager]: * Simplification Technique=POLY_PAC [2023-04-02 22:36:47,862 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2023-04-02 22:36:47,862 INFO L138 SettingsManager]: * sizeof long=4 [2023-04-02 22:36:47,862 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2023-04-02 22:36:47,862 INFO L138 SettingsManager]: * sizeof POINTER=4 [2023-04-02 22:36:47,862 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2023-04-02 22:36:47,862 INFO L138 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2023-04-02 22:36:47,862 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2023-04-02 22:36:47,862 INFO L138 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2023-04-02 22:36:47,863 INFO L138 SettingsManager]: * sizeof long double=12 [2023-04-02 22:36:47,863 INFO L138 SettingsManager]: * Check if freed pointer was valid=false [2023-04-02 22:36:47,863 INFO L138 SettingsManager]: * Use constant arrays=true [2023-04-02 22:36:47,863 INFO L138 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2023-04-02 22:36:47,863 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2023-04-02 22:36:47,863 INFO L138 SettingsManager]: * SMT solver=External_DefaultMode [2023-04-02 22:36:47,863 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2023-04-02 22:36:47,863 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2023-04-02 22:36:47,863 INFO L138 SettingsManager]: * Abstract interpretation Mode=USE_PREDICATES [2023-04-02 22:36:47,863 INFO L138 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2023-04-02 22:36:47,864 INFO L138 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2023-04-02 22:36:47,864 INFO L138 SettingsManager]: * Trace refinement strategy=SIFA_TAIPAN [2023-04-02 22:36:47,864 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2023-04-02 22:36:47,864 INFO L138 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2023-04-02 22:36:47,864 INFO L138 SettingsManager]: * Trace refinement exception blacklist=NONE [2023-04-02 22:36:47,864 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 -> OctagonDomain [2023-04-02 22:36:48,063 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2023-04-02 22:36:48,087 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2023-04-02 22:36:48,089 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2023-04-02 22:36:48,091 INFO L271 PluginConnector]: Initializing CDTParser... [2023-04-02 22:36:48,091 INFO L275 PluginConnector]: CDTParser initialized [2023-04-02 22:36:48,092 INFO L432 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/nla-digbench-scaling/cohencu-ll_unwindbound50.c [2023-04-02 22:36:49,060 INFO L500 CDTParser]: Created temporary CDT project at NULL [2023-04-02 22:36:49,213 INFO L351 CDTParser]: Found 1 translation units. [2023-04-02 22:36:49,213 INFO L172 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/cohencu-ll_unwindbound50.c [2023-04-02 22:36:49,217 INFO L394 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/fe877a548/d1365f08c16d4c129bbc6583184db251/FLAG88ec85ad2 [2023-04-02 22:36:49,227 INFO L402 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/fe877a548/d1365f08c16d4c129bbc6583184db251 [2023-04-02 22:36:49,228 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2023-04-02 22:36:49,229 INFO L131 ToolchainWalker]: Walking toolchain with 4 elements. [2023-04-02 22:36:49,230 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2023-04-02 22:36:49,230 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2023-04-02 22:36:49,232 INFO L275 PluginConnector]: CACSL2BoogieTranslator initialized [2023-04-02 22:36:49,233 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 02.04 10:36:49" (1/1) ... [2023-04-02 22:36:49,234 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@2ef26c47 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.04 10:36:49, skipping insertion in model container [2023-04-02 22:36:49,234 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 02.04 10:36:49" (1/1) ... [2023-04-02 22:36:49,238 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2023-04-02 22:36:49,253 INFO L178 MainTranslator]: Built tables and reachable declarations [2023-04-02 22:36:49,368 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/cohencu-ll_unwindbound50.c[588,601] [2023-04-02 22:36:49,403 INFO L209 PostProcessor]: Analyzing one entry point: main [2023-04-02 22:36:49,409 INFO L203 MainTranslator]: Completed pre-run [2023-04-02 22:36:49,420 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/cohencu-ll_unwindbound50.c[588,601] [2023-04-02 22:36:49,438 INFO L209 PostProcessor]: Analyzing one entry point: main [2023-04-02 22:36:49,447 INFO L208 MainTranslator]: Completed translation [2023-04-02 22:36:49,447 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.04 10:36:49 WrapperNode [2023-04-02 22:36:49,447 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2023-04-02 22:36:49,448 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2023-04-02 22:36:49,448 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2023-04-02 22:36:49,448 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2023-04-02 22:36:49,459 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.04 10:36:49" (1/1) ... [2023-04-02 22:36:49,459 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.04 10:36:49" (1/1) ... [2023-04-02 22:36:49,471 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.04 10:36:49" (1/1) ... [2023-04-02 22:36:49,472 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.04 10:36:49" (1/1) ... [2023-04-02 22:36:49,480 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.04 10:36:49" (1/1) ... [2023-04-02 22:36:49,482 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.04 10:36:49" (1/1) ... [2023-04-02 22:36:49,483 INFO L185 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.04 10:36:49" (1/1) ... [2023-04-02 22:36:49,483 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.04 10:36:49" (1/1) ... [2023-04-02 22:36:49,484 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2023-04-02 22:36:49,485 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2023-04-02 22:36:49,485 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2023-04-02 22:36:49,485 INFO L275 PluginConnector]: RCFGBuilder initialized [2023-04-02 22:36:49,485 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.04 10:36:49" (1/1) ... [2023-04-02 22:36:49,489 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2023-04-02 22:36:49,498 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-04-02 22:36:49,516 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-04-02 22:36:49,550 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-04-02 22:36:49,581 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.init [2023-04-02 22:36:49,582 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2023-04-02 22:36:49,582 INFO L138 BoogieDeclarations]: Found implementation of procedure reach_error [2023-04-02 22:36:49,586 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2023-04-02 22:36:49,586 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2023-04-02 22:36:49,586 INFO L138 BoogieDeclarations]: Found implementation of procedure main [2023-04-02 22:36:49,586 INFO L130 BoogieDeclarations]: Found specification of procedure abort [2023-04-02 22:36:49,586 INFO L130 BoogieDeclarations]: Found specification of procedure __assert_fail [2023-04-02 22:36:49,586 INFO L130 BoogieDeclarations]: Found specification of procedure reach_error [2023-04-02 22:36:49,586 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2023-04-02 22:36:49,586 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_nondet_ushort [2023-04-02 22:36:49,587 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2023-04-02 22:36:49,587 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2023-04-02 22:36:49,587 INFO L130 BoogieDeclarations]: Found specification of procedure main [2023-04-02 22:36:49,587 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.init [2023-04-02 22:36:49,587 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2023-04-02 22:36:49,587 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2023-04-02 22:36:49,587 INFO L130 BoogieDeclarations]: Found specification of procedure write~int [2023-04-02 22:36:49,587 INFO L130 BoogieDeclarations]: Found specification of procedure read~int [2023-04-02 22:36:49,587 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2023-04-02 22:36:49,639 INFO L236 CfgBuilder]: Building ICFG [2023-04-02 22:36:49,641 INFO L262 CfgBuilder]: Building CFG for each procedure with an implementation [2023-04-02 22:36:49,757 INFO L277 CfgBuilder]: Performing block encoding [2023-04-02 22:36:49,775 INFO L297 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2023-04-02 22:36:49,775 INFO L302 CfgBuilder]: Removed 1 assume(true) statements. [2023-04-02 22:36:49,777 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 02.04 10:36:49 BoogieIcfgContainer [2023-04-02 22:36:49,777 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2023-04-02 22:36:49,778 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2023-04-02 22:36:49,778 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2023-04-02 22:36:49,780 INFO L275 PluginConnector]: TraceAbstraction initialized [2023-04-02 22:36:49,780 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 02.04 10:36:49" (1/3) ... [2023-04-02 22:36:49,781 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@62ccf190 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 02.04 10:36:49, skipping insertion in model container [2023-04-02 22:36:49,781 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.04 10:36:49" (2/3) ... [2023-04-02 22:36:49,781 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@62ccf190 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 02.04 10:36:49, skipping insertion in model container [2023-04-02 22:36:49,781 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 02.04 10:36:49" (3/3) ... [2023-04-02 22:36:49,782 INFO L112 eAbstractionObserver]: Analyzing ICFG cohencu-ll_unwindbound50.c [2023-04-02 22:36:49,795 INFO L203 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2023-04-02 22:36:49,795 INFO L162 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2023-04-02 22:36:49,840 INFO L356 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2023-04-02 22:36:49,845 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;@452ed75f, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2023-04-02 22:36:49,845 INFO L358 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2023-04-02 22:36:49,848 INFO L276 IsEmpty]: Start isEmpty. Operand has 29 states, 11 states have (on average 1.4545454545454546) internal successors, (16), 12 states have internal predecessors, (16), 13 states have call successors, (13), 3 states have call predecessors, (13), 3 states have return successors, (13), 13 states have call predecessors, (13), 13 states have call successors, (13) [2023-04-02 22:36:49,852 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 11 [2023-04-02 22:36:49,852 INFO L187 NwaCegarLoop]: Found error trace [2023-04-02 22:36:49,852 INFO L195 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-04-02 22:36:49,853 INFO L420 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-04-02 22:36:49,856 INFO L145 PredicateUnifier]: Initialized classic predicate unifier [2023-04-02 22:36:49,856 INFO L85 PathProgramCache]: Analyzing trace with hash -1647932821, now seen corresponding path program 1 times [2023-04-02 22:36:49,862 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-04-02 22:36:49,863 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1895677181] [2023-04-02 22:36:49,863 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-04-02 22:36:49,863 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-04-02 22:36:49,925 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-04-02 22:36:49,959 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-04-02 22:36:49,960 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-04-02 22:36:49,960 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1895677181] [2023-04-02 22:36:49,960 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1895677181] provided 1 perfect and 0 imperfect interpolant sequences [2023-04-02 22:36:49,960 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-04-02 22:36:49,961 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2023-04-02 22:36:49,962 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [807945900] [2023-04-02 22:36:49,962 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-04-02 22:36:49,965 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2023-04-02 22:36:49,965 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-04-02 22:36:49,982 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2023-04-02 22:36:49,983 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2023-04-02 22:36:49,984 INFO L87 Difference]: Start difference. First operand has 29 states, 11 states have (on average 1.4545454545454546) internal successors, (16), 12 states have internal predecessors, (16), 13 states have call successors, (13), 3 states have call predecessors, (13), 3 states have return successors, (13), 13 states have call predecessors, (13), 13 states have call successors, (13) Second operand has 2 states, 2 states have (on average 3.0) internal successors, (6), 2 states have internal predecessors, (6), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2023-04-02 22:36:50,004 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-04-02 22:36:50,004 INFO L93 Difference]: Finished difference Result 53 states and 90 transitions. [2023-04-02 22:36:50,005 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2023-04-02 22:36:50,006 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 3.0) internal successors, (6), 2 states have internal predecessors, (6), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 10 [2023-04-02 22:36:50,007 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-04-02 22:36:50,011 INFO L225 Difference]: With dead ends: 53 [2023-04-02 22:36:50,011 INFO L226 Difference]: Without dead ends: 25 [2023-04-02 22:36:50,013 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 2 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 0 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2023-04-02 22:36:50,017 INFO L413 NwaCegarLoop]: 38 mSDtfsCounter, 0 mSDsluCounter, 0 mSDsCounter, 0 mSdLazyCounter, 2 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 38 SdHoareTripleChecker+Invalid, 2 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 2 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-04-02 22:36:50,018 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 38 Invalid, 2 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 2 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-04-02 22:36:50,029 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 25 states. [2023-04-02 22:36:50,056 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 25 to 25. [2023-04-02 22:36:50,057 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 25 states, 9 states have (on average 1.3333333333333333) internal successors, (12), 10 states have internal predecessors, (12), 13 states have call successors, (13), 3 states have call predecessors, (13), 2 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2023-04-02 22:36:50,058 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 25 states to 25 states and 36 transitions. [2023-04-02 22:36:50,059 INFO L78 Accepts]: Start accepts. Automaton has 25 states and 36 transitions. Word has length 10 [2023-04-02 22:36:50,059 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-04-02 22:36:50,059 INFO L495 AbstractCegarLoop]: Abstraction has 25 states and 36 transitions. [2023-04-02 22:36:50,060 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 2 states have (on average 3.0) internal successors, (6), 2 states have internal predecessors, (6), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2023-04-02 22:36:50,060 INFO L276 IsEmpty]: Start isEmpty. Operand 25 states and 36 transitions. [2023-04-02 22:36:50,060 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 12 [2023-04-02 22:36:50,060 INFO L187 NwaCegarLoop]: Found error trace [2023-04-02 22:36:50,060 INFO L195 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-04-02 22:36:50,060 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2023-04-02 22:36:50,061 INFO L420 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-04-02 22:36:50,061 INFO L145 PredicateUnifier]: Initialized classic predicate unifier [2023-04-02 22:36:50,061 INFO L85 PathProgramCache]: Analyzing trace with hash -78558798, now seen corresponding path program 1 times [2023-04-02 22:36:50,061 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-04-02 22:36:50,061 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1906813849] [2023-04-02 22:36:50,061 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-04-02 22:36:50,062 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-04-02 22:36:50,089 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-04-02 22:36:50,243 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-04-02 22:36:50,243 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-04-02 22:36:50,244 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1906813849] [2023-04-02 22:36:50,244 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1906813849] provided 1 perfect and 0 imperfect interpolant sequences [2023-04-02 22:36:50,244 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-04-02 22:36:50,244 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2023-04-02 22:36:50,244 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1398204583] [2023-04-02 22:36:50,244 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-04-02 22:36:50,245 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2023-04-02 22:36:50,245 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-04-02 22:36:50,246 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2023-04-02 22:36:50,246 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2023-04-02 22:36:50,246 INFO L87 Difference]: Start difference. First operand 25 states and 36 transitions. Second operand has 4 states, 4 states have (on average 1.75) internal successors, (7), 3 states have internal predecessors, (7), 3 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2023-04-02 22:36:50,272 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-04-02 22:36:50,272 INFO L93 Difference]: Finished difference Result 39 states and 55 transitions. [2023-04-02 22:36:50,272 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2023-04-02 22:36:50,273 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 1.75) internal successors, (7), 3 states have internal predecessors, (7), 3 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 11 [2023-04-02 22:36:50,273 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-04-02 22:36:50,273 INFO L225 Difference]: With dead ends: 39 [2023-04-02 22:36:50,273 INFO L226 Difference]: Without dead ends: 27 [2023-04-02 22:36:50,274 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 5 GetRequests, 3 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2023-04-02 22:36:50,275 INFO L413 NwaCegarLoop]: 33 mSDtfsCounter, 0 mSDsluCounter, 62 mSDsCounter, 0 mSdLazyCounter, 9 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 95 SdHoareTripleChecker+Invalid, 9 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 9 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-04-02 22:36:50,275 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 95 Invalid, 9 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 9 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-04-02 22:36:50,276 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 27 states. [2023-04-02 22:36:50,280 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 27 to 27. [2023-04-02 22:36:50,280 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 27 states, 11 states have (on average 1.2727272727272727) internal successors, (14), 12 states have internal predecessors, (14), 13 states have call successors, (13), 3 states have call predecessors, (13), 2 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2023-04-02 22:36:50,281 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 27 states to 27 states and 38 transitions. [2023-04-02 22:36:50,281 INFO L78 Accepts]: Start accepts. Automaton has 27 states and 38 transitions. Word has length 11 [2023-04-02 22:36:50,281 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-04-02 22:36:50,282 INFO L495 AbstractCegarLoop]: Abstraction has 27 states and 38 transitions. [2023-04-02 22:36:50,282 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 1.75) internal successors, (7), 3 states have internal predecessors, (7), 3 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2023-04-02 22:36:50,282 INFO L276 IsEmpty]: Start isEmpty. Operand 27 states and 38 transitions. [2023-04-02 22:36:50,282 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 12 [2023-04-02 22:36:50,282 INFO L187 NwaCegarLoop]: Found error trace [2023-04-02 22:36:50,282 INFO L195 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-04-02 22:36:50,282 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2023-04-02 22:36:50,282 INFO L420 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-04-02 22:36:50,283 INFO L145 PredicateUnifier]: Initialized classic predicate unifier [2023-04-02 22:36:50,283 INFO L85 PathProgramCache]: Analyzing trace with hash -77009666, now seen corresponding path program 1 times [2023-04-02 22:36:50,283 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-04-02 22:36:50,283 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [628074873] [2023-04-02 22:36:50,283 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-04-02 22:36:50,284 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-04-02 22:36:50,300 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-04-02 22:36:50,465 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-04-02 22:36:50,465 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-04-02 22:36:50,466 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [628074873] [2023-04-02 22:36:50,466 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [628074873] provided 1 perfect and 0 imperfect interpolant sequences [2023-04-02 22:36:50,466 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-04-02 22:36:50,466 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2023-04-02 22:36:50,466 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1723604368] [2023-04-02 22:36:50,466 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-04-02 22:36:50,467 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2023-04-02 22:36:50,467 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-04-02 22:36:50,467 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2023-04-02 22:36:50,467 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2023-04-02 22:36:50,468 INFO L87 Difference]: Start difference. First operand 27 states and 38 transitions. Second operand has 5 states, 5 states have (on average 1.4) internal successors, (7), 4 states have internal predecessors, (7), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2023-04-02 22:36:50,547 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-04-02 22:36:50,547 INFO L93 Difference]: Finished difference Result 33 states and 43 transitions. [2023-04-02 22:36:50,547 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2023-04-02 22:36:50,547 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 1.4) internal successors, (7), 4 states have internal predecessors, (7), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 11 [2023-04-02 22:36:50,548 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-04-02 22:36:50,548 INFO L225 Difference]: With dead ends: 33 [2023-04-02 22:36:50,548 INFO L226 Difference]: Without dead ends: 31 [2023-04-02 22:36:50,549 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 6 GetRequests, 2 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-04-02 22:36:50,550 INFO L413 NwaCegarLoop]: 29 mSDtfsCounter, 8 mSDsluCounter, 41 mSDsCounter, 0 mSdLazyCounter, 54 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 18 SdHoareTripleChecker+Valid, 70 SdHoareTripleChecker+Invalid, 57 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 54 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-04-02 22:36:50,550 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [18 Valid, 70 Invalid, 57 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 54 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-04-02 22:36:50,551 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 31 states. [2023-04-02 22:36:50,558 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 31 to 31. [2023-04-02 22:36:50,558 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 31 states, 14 states have (on average 1.2142857142857142) internal successors, (17), 15 states have internal predecessors, (17), 13 states have call successors, (13), 4 states have call predecessors, (13), 3 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2023-04-02 22:36:50,559 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 31 states to 31 states and 41 transitions. [2023-04-02 22:36:50,559 INFO L78 Accepts]: Start accepts. Automaton has 31 states and 41 transitions. Word has length 11 [2023-04-02 22:36:50,559 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-04-02 22:36:50,559 INFO L495 AbstractCegarLoop]: Abstraction has 31 states and 41 transitions. [2023-04-02 22:36:50,560 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 1.4) internal successors, (7), 4 states have internal predecessors, (7), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2023-04-02 22:36:50,560 INFO L276 IsEmpty]: Start isEmpty. Operand 31 states and 41 transitions. [2023-04-02 22:36:50,560 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 17 [2023-04-02 22:36:50,560 INFO L187 NwaCegarLoop]: Found error trace [2023-04-02 22:36:50,560 INFO L195 NwaCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-04-02 22:36:50,560 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2 [2023-04-02 22:36:50,561 INFO L420 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-04-02 22:36:50,561 INFO L145 PredicateUnifier]: Initialized classic predicate unifier [2023-04-02 22:36:50,561 INFO L85 PathProgramCache]: Analyzing trace with hash 1662799058, now seen corresponding path program 1 times [2023-04-02 22:36:50,561 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-04-02 22:36:50,561 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [543345234] [2023-04-02 22:36:50,562 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-04-02 22:36:50,562 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-04-02 22:36:50,577 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-04-02 22:36:50,577 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2125318887] [2023-04-02 22:36:50,577 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-04-02 22:36:50,578 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-04-02 22:36:50,578 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-04-02 22:36:50,582 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-04-02 22:36:50,590 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-04-02 22:36:50,630 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-04-02 22:36:50,631 INFO L262 TraceCheckSpWp]: Trace formula consists of 79 conjuncts, 17 conjunts are in the unsatisfiable core [2023-04-02 22:36:50,635 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-04-02 22:36:50,723 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 1 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-04-02 22:36:50,724 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-04-02 22:36:50,822 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 1 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-04-02 22:36:50,823 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-04-02 22:36:50,823 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [543345234] [2023-04-02 22:36:50,823 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-04-02 22:36:50,823 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2125318887] [2023-04-02 22:36:50,824 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2125318887] provided 0 perfect and 2 imperfect interpolant sequences [2023-04-02 22:36:50,826 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1595769886] [2023-04-02 22:36:50,845 INFO L159 IcfgInterpreter]: Started Sifa with 15 locations of interest [2023-04-02 22:36:50,845 INFO L166 IcfgInterpreter]: Building call graph [2023-04-02 22:36:50,848 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-04-02 22:36:50,851 INFO L176 IcfgInterpreter]: Starting interpretation [2023-04-02 22:36:50,851 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-04-02 22:36:50,901 INFO L197 IcfgInterpreter]: Interpreting procedure main with input of size 13 for LOIs [2023-04-02 22:36:51,101 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 13 for LOIs [2023-04-02 22:36:51,108 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.init with input of size 10 for LOIs [2023-04-02 22:36:51,115 INFO L180 IcfgInterpreter]: Interpretation finished [2023-04-02 22:36:51,354 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSifa [1595769886] provided 1 perfect and 0 imperfect interpolant sequences [2023-04-02 22:36:51,354 INFO L185 FreeRefinementEngine]: Found 1 perfect and 2 imperfect interpolant sequences. [2023-04-02 22:36:51,355 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [11] imperfect sequences [8, 7] total 22 [2023-04-02 22:36:51,355 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [192196810] [2023-04-02 22:36:51,355 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-04-02 22:36:51,356 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2023-04-02 22:36:51,356 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-04-02 22:36:51,356 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2023-04-02 22:36:51,357 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=85, Invalid=377, Unknown=0, NotChecked=0, Total=462 [2023-04-02 22:36:51,357 INFO L87 Difference]: Start difference. First operand 31 states and 41 transitions. Second operand has 12 states, 7 states have (on average 1.2857142857142858) internal successors, (9), 6 states have internal predecessors, (9), 4 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2023-04-02 22:36:51,745 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-04-02 22:36:51,746 INFO L93 Difference]: Finished difference Result 53 states and 72 transitions. [2023-04-02 22:36:51,746 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2023-04-02 22:36:51,746 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 7 states have (on average 1.2857142857142858) internal successors, (9), 6 states have internal predecessors, (9), 4 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) Word has length 16 [2023-04-02 22:36:51,746 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-04-02 22:36:51,747 INFO L225 Difference]: With dead ends: 53 [2023-04-02 22:36:51,747 INFO L226 Difference]: Without dead ends: 45 [2023-04-02 22:36:51,748 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 51 GetRequests, 27 SyntacticMatches, 0 SemanticMatches, 24 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 138 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=122, Invalid=528, Unknown=0, NotChecked=0, Total=650 [2023-04-02 22:36:51,748 INFO L413 NwaCegarLoop]: 25 mSDtfsCounter, 14 mSDsluCounter, 11 mSDsCounter, 0 mSdLazyCounter, 182 mSolverCounterSat, 36 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 24 SdHoareTripleChecker+Valid, 36 SdHoareTripleChecker+Invalid, 218 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 36 IncrementalHoareTripleChecker+Valid, 182 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2023-04-02 22:36:51,749 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [24 Valid, 36 Invalid, 218 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [36 Valid, 182 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2023-04-02 22:36:51,749 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 45 states. [2023-04-02 22:36:51,757 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 45 to 45. [2023-04-02 22:36:51,757 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 45 states, 21 states have (on average 1.1428571428571428) internal successors, (24), 22 states have internal predecessors, (24), 18 states have call successors, (18), 6 states have call predecessors, (18), 5 states have return successors, (16), 16 states have call predecessors, (16), 16 states have call successors, (16) [2023-04-02 22:36:51,758 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 45 states to 45 states and 58 transitions. [2023-04-02 22:36:51,758 INFO L78 Accepts]: Start accepts. Automaton has 45 states and 58 transitions. Word has length 16 [2023-04-02 22:36:51,758 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-04-02 22:36:51,758 INFO L495 AbstractCegarLoop]: Abstraction has 45 states and 58 transitions. [2023-04-02 22:36:51,758 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 7 states have (on average 1.2857142857142858) internal successors, (9), 6 states have internal predecessors, (9), 4 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2023-04-02 22:36:51,759 INFO L276 IsEmpty]: Start isEmpty. Operand 45 states and 58 transitions. [2023-04-02 22:36:51,759 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 45 [2023-04-02 22:36:51,759 INFO L187 NwaCegarLoop]: Found error trace [2023-04-02 22:36:51,759 INFO L195 NwaCegarLoop]: trace histogram [7, 6, 6, 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-04-02 22:36:51,777 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Forceful destruction successful, exit code 0 [2023-04-02 22:36:51,964 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-04-02 22:36:51,965 INFO L420 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-04-02 22:36:51,965 INFO L145 PredicateUnifier]: Initialized classic predicate unifier [2023-04-02 22:36:51,965 INFO L85 PathProgramCache]: Analyzing trace with hash 1441032967, now seen corresponding path program 1 times [2023-04-02 22:36:51,965 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-04-02 22:36:51,965 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1353985246] [2023-04-02 22:36:51,966 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-04-02 22:36:51,966 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-04-02 22:36:51,990 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-04-02 22:36:51,990 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1540092930] [2023-04-02 22:36:51,991 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-04-02 22:36:51,991 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-04-02 22:36:51,991 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-04-02 22:36:51,995 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-04-02 22:36:51,996 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-04-02 22:36:52,055 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-04-02 22:36:52,056 INFO L262 TraceCheckSpWp]: Trace formula consists of 138 conjuncts, 7 conjunts are in the unsatisfiable core [2023-04-02 22:36:52,058 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-04-02 22:36:52,106 INFO L134 CoverageAnalysis]: Checked inductivity of 74 backedges. 30 proven. 2 refuted. 0 times theorem prover too weak. 42 trivial. 0 not checked. [2023-04-02 22:36:52,106 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-04-02 22:36:52,155 INFO L134 CoverageAnalysis]: Checked inductivity of 74 backedges. 12 proven. 2 refuted. 0 times theorem prover too weak. 60 trivial. 0 not checked. [2023-04-02 22:36:52,155 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-04-02 22:36:52,155 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1353985246] [2023-04-02 22:36:52,155 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-04-02 22:36:52,156 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1540092930] [2023-04-02 22:36:52,156 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1540092930] provided 0 perfect and 2 imperfect interpolant sequences [2023-04-02 22:36:52,156 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [900439599] [2023-04-02 22:36:52,158 INFO L159 IcfgInterpreter]: Started Sifa with 21 locations of interest [2023-04-02 22:36:52,158 INFO L166 IcfgInterpreter]: Building call graph [2023-04-02 22:36:52,159 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-04-02 22:36:52,159 INFO L176 IcfgInterpreter]: Starting interpretation [2023-04-02 22:36:52,159 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-04-02 22:36:52,183 INFO L197 IcfgInterpreter]: Interpreting procedure main with input of size 13 for LOIs [2023-04-02 22:36:53,404 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 23 for LOIs [2023-04-02 22:36:53,410 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.init with input of size 10 for LOIs [2023-04-02 22:36:53,413 INFO L180 IcfgInterpreter]: Interpretation finished [2023-04-02 22:36:53,751 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '929#(and (<= 1 |#StackHeapBarrier|) (<= 1 ~counter~0) (= |__VERIFIER_assert_#in~cond| 0) (= __VERIFIER_assert_~cond 0) (= |#NULL.offset| 0) (= |#NULL.base| 0))' at error location [2023-04-02 22:36:53,751 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-04-02 22:36:53,751 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-04-02 22:36:53,752 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 5] total 8 [2023-04-02 22:36:53,752 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [577738319] [2023-04-02 22:36:53,752 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-04-02 22:36:53,752 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2023-04-02 22:36:53,752 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-04-02 22:36:53,753 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2023-04-02 22:36:53,753 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=68, Invalid=352, Unknown=0, NotChecked=0, Total=420 [2023-04-02 22:36:53,753 INFO L87 Difference]: Start difference. First operand 45 states and 58 transitions. Second operand has 8 states, 8 states have (on average 3.125) internal successors, (25), 8 states have internal predecessors, (25), 6 states have call successors, (16), 5 states have call predecessors, (16), 5 states have return successors, (14), 5 states have call predecessors, (14), 4 states have call successors, (14) [2023-04-02 22:36:53,873 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-04-02 22:36:53,873 INFO L93 Difference]: Finished difference Result 111 states and 148 transitions. [2023-04-02 22:36:53,874 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2023-04-02 22:36:53,874 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 8 states have (on average 3.125) internal successors, (25), 8 states have internal predecessors, (25), 6 states have call successors, (16), 5 states have call predecessors, (16), 5 states have return successors, (14), 5 states have call predecessors, (14), 4 states have call successors, (14) Word has length 44 [2023-04-02 22:36:53,874 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-04-02 22:36:53,875 INFO L225 Difference]: With dead ends: 111 [2023-04-02 22:36:53,875 INFO L226 Difference]: Without dead ends: 95 [2023-04-02 22:36:53,876 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 134 GetRequests, 110 SyntacticMatches, 2 SemanticMatches, 22 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 162 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=88, Invalid=464, Unknown=0, NotChecked=0, Total=552 [2023-04-02 22:36:53,876 INFO L413 NwaCegarLoop]: 33 mSDtfsCounter, 51 mSDsluCounter, 114 mSDsCounter, 0 mSdLazyCounter, 71 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 51 SdHoareTripleChecker+Valid, 147 SdHoareTripleChecker+Invalid, 72 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 71 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-04-02 22:36:53,876 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [51 Valid, 147 Invalid, 72 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 71 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-04-02 22:36:53,877 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 95 states. [2023-04-02 22:36:53,889 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 95 to 91. [2023-04-02 22:36:53,889 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 91 states, 41 states have (on average 1.170731707317073) internal successors, (48), 44 states have internal predecessors, (48), 40 states have call successors, (40), 10 states have call predecessors, (40), 9 states have return successors, (36), 36 states have call predecessors, (36), 36 states have call successors, (36) [2023-04-02 22:36:53,890 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 91 states to 91 states and 124 transitions. [2023-04-02 22:36:53,890 INFO L78 Accepts]: Start accepts. Automaton has 91 states and 124 transitions. Word has length 44 [2023-04-02 22:36:53,890 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-04-02 22:36:53,890 INFO L495 AbstractCegarLoop]: Abstraction has 91 states and 124 transitions. [2023-04-02 22:36:53,890 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 8 states have (on average 3.125) internal successors, (25), 8 states have internal predecessors, (25), 6 states have call successors, (16), 5 states have call predecessors, (16), 5 states have return successors, (14), 5 states have call predecessors, (14), 4 states have call successors, (14) [2023-04-02 22:36:53,890 INFO L276 IsEmpty]: Start isEmpty. Operand 91 states and 124 transitions. [2023-04-02 22:36:53,891 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 45 [2023-04-02 22:36:53,891 INFO L187 NwaCegarLoop]: Found error trace [2023-04-02 22:36:53,891 INFO L195 NwaCegarLoop]: trace histogram [7, 6, 6, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-04-02 22:36:53,897 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Ended with exit code 0 [2023-04-02 22:36:54,096 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,3 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-04-02 22:36:54,097 INFO L420 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-04-02 22:36:54,097 INFO L145 PredicateUnifier]: Initialized classic predicate unifier [2023-04-02 22:36:54,097 INFO L85 PathProgramCache]: Analyzing trace with hash 1933148283, now seen corresponding path program 1 times [2023-04-02 22:36:54,097 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-04-02 22:36:54,097 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1920300206] [2023-04-02 22:36:54,097 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-04-02 22:36:54,097 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-04-02 22:36:54,108 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-04-02 22:36:54,108 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1571018225] [2023-04-02 22:36:54,108 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-04-02 22:36:54,108 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-04-02 22:36:54,109 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-04-02 22:36:54,121 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-04-02 22:36:54,122 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-04-02 22:36:54,169 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-04-02 22:36:54,169 INFO L262 TraceCheckSpWp]: Trace formula consists of 138 conjuncts, 21 conjunts are in the unsatisfiable core [2023-04-02 22:36:54,171 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-04-02 22:36:54,240 INFO L134 CoverageAnalysis]: Checked inductivity of 76 backedges. 11 proven. 20 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2023-04-02 22:36:54,240 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-04-02 22:36:54,343 INFO L134 CoverageAnalysis]: Checked inductivity of 76 backedges. 14 proven. 17 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2023-04-02 22:36:54,343 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-04-02 22:36:54,343 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1920300206] [2023-04-02 22:36:54,343 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-04-02 22:36:54,343 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1571018225] [2023-04-02 22:36:54,343 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1571018225] provided 0 perfect and 2 imperfect interpolant sequences [2023-04-02 22:36:54,343 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [2012893077] [2023-04-02 22:36:54,345 INFO L159 IcfgInterpreter]: Started Sifa with 19 locations of interest [2023-04-02 22:36:54,345 INFO L166 IcfgInterpreter]: Building call graph [2023-04-02 22:36:54,345 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-04-02 22:36:54,345 INFO L176 IcfgInterpreter]: Starting interpretation [2023-04-02 22:36:54,345 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-04-02 22:36:54,358 INFO L197 IcfgInterpreter]: Interpreting procedure main with input of size 13 for LOIs [2023-04-02 22:36:55,095 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 23 for LOIs [2023-04-02 22:36:55,100 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.init with input of size 10 for LOIs [2023-04-02 22:36:55,102 INFO L180 IcfgInterpreter]: Interpretation finished [2023-04-02 22:36:55,480 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '1542#(and (<= 1 |#StackHeapBarrier|) (<= 1 ~counter~0) (= |__VERIFIER_assert_#in~cond| 0) (= __VERIFIER_assert_~cond 0) (= |#NULL.offset| 0) (= |#NULL.base| 0))' at error location [2023-04-02 22:36:55,481 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-04-02 22:36:55,481 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-04-02 22:36:55,481 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 13 [2023-04-02 22:36:55,481 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [48453394] [2023-04-02 22:36:55,481 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-04-02 22:36:55,481 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 13 states [2023-04-02 22:36:55,481 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-04-02 22:36:55,482 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2023-04-02 22:36:55,482 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=78, Invalid=522, Unknown=0, NotChecked=0, Total=600 [2023-04-02 22:36:55,482 INFO L87 Difference]: Start difference. First operand 91 states and 124 transitions. Second operand has 13 states, 13 states have (on average 2.0) internal successors, (26), 11 states have internal predecessors, (26), 6 states have call successors, (16), 3 states have call predecessors, (16), 2 states have return successors, (13), 5 states have call predecessors, (13), 6 states have call successors, (13) [2023-04-02 22:36:55,787 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-04-02 22:36:55,787 INFO L93 Difference]: Finished difference Result 109 states and 140 transitions. [2023-04-02 22:36:55,801 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2023-04-02 22:36:55,801 INFO L78 Accepts]: Start accepts. Automaton has has 13 states, 13 states have (on average 2.0) internal successors, (26), 11 states have internal predecessors, (26), 6 states have call successors, (16), 3 states have call predecessors, (16), 2 states have return successors, (13), 5 states have call predecessors, (13), 6 states have call successors, (13) Word has length 44 [2023-04-02 22:36:55,801 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-04-02 22:36:55,802 INFO L225 Difference]: With dead ends: 109 [2023-04-02 22:36:55,802 INFO L226 Difference]: Without dead ends: 107 [2023-04-02 22:36:55,802 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 135 GetRequests, 105 SyntacticMatches, 3 SemanticMatches, 27 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 183 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=108, Invalid=704, Unknown=0, NotChecked=0, Total=812 [2023-04-02 22:36:55,803 INFO L413 NwaCegarLoop]: 27 mSDtfsCounter, 23 mSDsluCounter, 71 mSDsCounter, 0 mSdLazyCounter, 275 mSolverCounterSat, 54 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 23 SdHoareTripleChecker+Valid, 98 SdHoareTripleChecker+Invalid, 329 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 54 IncrementalHoareTripleChecker+Valid, 275 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2023-04-02 22:36:55,803 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [23 Valid, 98 Invalid, 329 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [54 Valid, 275 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2023-04-02 22:36:55,803 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 107 states. [2023-04-02 22:36:55,832 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 107 to 107. [2023-04-02 22:36:55,834 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 107 states, 53 states have (on average 1.1320754716981132) internal successors, (60), 56 states have internal predecessors, (60), 40 states have call successors, (40), 14 states have call predecessors, (40), 13 states have return successors, (36), 36 states have call predecessors, (36), 36 states have call successors, (36) [2023-04-02 22:36:55,837 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 107 states to 107 states and 136 transitions. [2023-04-02 22:36:55,837 INFO L78 Accepts]: Start accepts. Automaton has 107 states and 136 transitions. Word has length 44 [2023-04-02 22:36:55,852 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-04-02 22:36:55,854 INFO L495 AbstractCegarLoop]: Abstraction has 107 states and 136 transitions. [2023-04-02 22:36:55,854 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 13 states, 13 states have (on average 2.0) internal successors, (26), 11 states have internal predecessors, (26), 6 states have call successors, (16), 3 states have call predecessors, (16), 2 states have return successors, (13), 5 states have call predecessors, (13), 6 states have call successors, (13) [2023-04-02 22:36:55,858 INFO L276 IsEmpty]: Start isEmpty. Operand 107 states and 136 transitions. [2023-04-02 22:36:55,860 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 50 [2023-04-02 22:36:55,860 INFO L187 NwaCegarLoop]: Found error trace [2023-04-02 22:36:55,860 INFO L195 NwaCegarLoop]: trace histogram [8, 7, 7, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-04-02 22:36:55,874 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-04-02 22:36:56,065 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-04-02 22:36:56,065 INFO L420 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-04-02 22:36:56,065 INFO L145 PredicateUnifier]: Initialized classic predicate unifier [2023-04-02 22:36:56,066 INFO L85 PathProgramCache]: Analyzing trace with hash -82151627, now seen corresponding path program 2 times [2023-04-02 22:36:56,066 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-04-02 22:36:56,066 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1117292443] [2023-04-02 22:36:56,066 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-04-02 22:36:56,066 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-04-02 22:36:56,074 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-04-02 22:36:56,074 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1769692380] [2023-04-02 22:36:56,074 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2023-04-02 22:36:56,074 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-04-02 22:36:56,074 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-04-02 22:36:56,080 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-04-02 22:36:56,104 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-04-02 22:36:56,162 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 2 check-sat command(s) [2023-04-02 22:36:56,162 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-04-02 22:36:56,163 INFO L262 TraceCheckSpWp]: Trace formula consists of 102 conjuncts, 16 conjunts are in the unsatisfiable core [2023-04-02 22:36:56,164 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-04-02 22:36:56,224 INFO L134 CoverageAnalysis]: Checked inductivity of 103 backedges. 14 proven. 5 refuted. 0 times theorem prover too weak. 84 trivial. 0 not checked. [2023-04-02 22:36:56,224 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-04-02 22:36:56,283 INFO L134 CoverageAnalysis]: Checked inductivity of 103 backedges. 14 proven. 5 refuted. 0 times theorem prover too weak. 84 trivial. 0 not checked. [2023-04-02 22:36:56,284 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-04-02 22:36:56,284 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1117292443] [2023-04-02 22:36:56,284 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-04-02 22:36:56,284 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1769692380] [2023-04-02 22:36:56,284 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1769692380] provided 0 perfect and 2 imperfect interpolant sequences [2023-04-02 22:36:56,284 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1343665648] [2023-04-02 22:36:56,285 INFO L159 IcfgInterpreter]: Started Sifa with 19 locations of interest [2023-04-02 22:36:56,285 INFO L166 IcfgInterpreter]: Building call graph [2023-04-02 22:36:56,286 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-04-02 22:36:56,286 INFO L176 IcfgInterpreter]: Starting interpretation [2023-04-02 22:36:56,286 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-04-02 22:36:56,302 INFO L197 IcfgInterpreter]: Interpreting procedure main with input of size 13 for LOIs [2023-04-02 22:36:56,948 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 23 for LOIs [2023-04-02 22:36:56,953 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.init with input of size 10 for LOIs [2023-04-02 22:36:56,955 INFO L180 IcfgInterpreter]: Interpretation finished [2023-04-02 22:36:57,322 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '2197#(and (<= 1 |#StackHeapBarrier|) (<= 1 ~counter~0) (= |__VERIFIER_assert_#in~cond| 0) (= __VERIFIER_assert_~cond 0) (= |#NULL.offset| 0) (= |#NULL.base| 0))' at error location [2023-04-02 22:36:57,322 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-04-02 22:36:57,322 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-04-02 22:36:57,323 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 10 [2023-04-02 22:36:57,323 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [850864336] [2023-04-02 22:36:57,323 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-04-02 22:36:57,323 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2023-04-02 22:36:57,324 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-04-02 22:36:57,324 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2023-04-02 22:36:57,325 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=59, Invalid=403, Unknown=0, NotChecked=0, Total=462 [2023-04-02 22:36:57,325 INFO L87 Difference]: Start difference. First operand 107 states and 136 transitions. Second operand has 10 states, 10 states have (on average 2.1) internal successors, (21), 8 states have internal predecessors, (21), 5 states have call successors, (18), 3 states have call predecessors, (18), 1 states have return successors, (15), 5 states have call predecessors, (15), 5 states have call successors, (15) [2023-04-02 22:36:57,430 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-04-02 22:36:57,430 INFO L93 Difference]: Finished difference Result 121 states and 147 transitions. [2023-04-02 22:36:57,431 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2023-04-02 22:36:57,431 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 10 states have (on average 2.1) internal successors, (21), 8 states have internal predecessors, (21), 5 states have call successors, (18), 3 states have call predecessors, (18), 1 states have return successors, (15), 5 states have call predecessors, (15), 5 states have call successors, (15) Word has length 49 [2023-04-02 22:36:57,431 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-04-02 22:36:57,432 INFO L225 Difference]: With dead ends: 121 [2023-04-02 22:36:57,432 INFO L226 Difference]: Without dead ends: 119 [2023-04-02 22:36:57,432 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 147 GetRequests, 122 SyntacticMatches, 4 SemanticMatches, 21 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 120 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=66, Invalid=440, Unknown=0, NotChecked=0, Total=506 [2023-04-02 22:36:57,433 INFO L413 NwaCegarLoop]: 43 mSDtfsCounter, 7 mSDsluCounter, 133 mSDsCounter, 0 mSdLazyCounter, 150 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 15 SdHoareTripleChecker+Valid, 176 SdHoareTripleChecker+Invalid, 153 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 150 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-04-02 22:36:57,433 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [15 Valid, 176 Invalid, 153 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 150 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-04-02 22:36:57,433 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 119 states. [2023-04-02 22:36:57,447 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 119 to 119. [2023-04-02 22:36:57,448 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 119 states, 62 states have (on average 1.1129032258064515) internal successors, (69), 65 states have internal predecessors, (69), 40 states have call successors, (40), 17 states have call predecessors, (40), 16 states have return successors, (36), 36 states have call predecessors, (36), 36 states have call successors, (36) [2023-04-02 22:36:57,448 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 119 states to 119 states and 145 transitions. [2023-04-02 22:36:57,448 INFO L78 Accepts]: Start accepts. Automaton has 119 states and 145 transitions. Word has length 49 [2023-04-02 22:36:57,449 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-04-02 22:36:57,449 INFO L495 AbstractCegarLoop]: Abstraction has 119 states and 145 transitions. [2023-04-02 22:36:57,449 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 10 states have (on average 2.1) internal successors, (21), 8 states have internal predecessors, (21), 5 states have call successors, (18), 3 states have call predecessors, (18), 1 states have return successors, (15), 5 states have call predecessors, (15), 5 states have call successors, (15) [2023-04-02 22:36:57,449 INFO L276 IsEmpty]: Start isEmpty. Operand 119 states and 145 transitions. [2023-04-02 22:36:57,449 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 55 [2023-04-02 22:36:57,449 INFO L187 NwaCegarLoop]: Found error trace [2023-04-02 22:36:57,449 INFO L195 NwaCegarLoop]: trace histogram [9, 8, 8, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-04-02 22:36:57,456 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Ended with exit code 0 [2023-04-02 22:36:57,656 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-04-02 22:36:57,657 INFO L420 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-04-02 22:36:57,657 INFO L145 PredicateUnifier]: Initialized classic predicate unifier [2023-04-02 22:36:57,657 INFO L85 PathProgramCache]: Analyzing trace with hash 1692777595, now seen corresponding path program 3 times [2023-04-02 22:36:57,657 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-04-02 22:36:57,657 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1516301046] [2023-04-02 22:36:57,657 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-04-02 22:36:57,658 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-04-02 22:36:57,668 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-04-02 22:36:57,668 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1702267899] [2023-04-02 22:36:57,668 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2023-04-02 22:36:57,668 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-04-02 22:36:57,668 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-04-02 22:36:57,682 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-04-02 22:36:57,721 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-04-02 22:36:57,757 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2023-04-02 22:36:57,757 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-04-02 22:36:57,758 INFO L262 TraceCheckSpWp]: Trace formula consists of 156 conjuncts, 26 conjunts are in the unsatisfiable core [2023-04-02 22:36:57,759 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-04-02 22:36:57,858 INFO L134 CoverageAnalysis]: Checked inductivity of 134 backedges. 15 proven. 28 refuted. 0 times theorem prover too weak. 91 trivial. 0 not checked. [2023-04-02 22:36:57,859 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-04-02 22:37:00,352 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-04-02 22:37:00,352 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1516301046] [2023-04-02 22:37:00,352 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-04-02 22:37:00,352 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1702267899] [2023-04-02 22:37:00,352 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1702267899] provided 0 perfect and 1 imperfect interpolant sequences [2023-04-02 22:37:00,352 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [501890213] [2023-04-02 22:37:00,354 INFO L159 IcfgInterpreter]: Started Sifa with 19 locations of interest [2023-04-02 22:37:00,354 INFO L166 IcfgInterpreter]: Building call graph [2023-04-02 22:37:00,354 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-04-02 22:37:00,354 INFO L176 IcfgInterpreter]: Starting interpretation [2023-04-02 22:37:00,354 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-04-02 22:37:00,372 INFO L197 IcfgInterpreter]: Interpreting procedure main with input of size 13 for LOIs [2023-04-02 22:37:01,170 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 9 for LOIs [2023-04-02 22:37:01,173 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.init with input of size 10 for LOIs [2023-04-02 22:37:01,175 INFO L180 IcfgInterpreter]: Interpretation finished [2023-04-02 22:37:01,481 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '2814#(and (<= 1 |#StackHeapBarrier|) (= |__VERIFIER_assert_#in~cond| 0) (= __VERIFIER_assert_~cond 0) (= |#NULL.offset| 0) (= |#NULL.base| 0))' at error location [2023-04-02 22:37:01,481 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-04-02 22:37:01,481 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2023-04-02 22:37:01,481 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8] total 8 [2023-04-02 22:37:01,481 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [131601979] [2023-04-02 22:37:01,481 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2023-04-02 22:37:01,482 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2023-04-02 22:37:01,482 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-04-02 22:37:01,482 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2023-04-02 22:37:01,482 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=66, Invalid=396, Unknown=0, NotChecked=0, Total=462 [2023-04-02 22:37:01,482 INFO L87 Difference]: Start difference. First operand 119 states and 145 transitions. Second operand has 8 states, 8 states have (on average 2.0) internal successors, (16), 7 states have internal predecessors, (16), 3 states have call successors, (11), 2 states have call predecessors, (11), 2 states have return successors, (9), 3 states have call predecessors, (9), 3 states have call successors, (9) [2023-04-02 22:37:01,623 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-04-02 22:37:01,624 INFO L93 Difference]: Finished difference Result 125 states and 150 transitions. [2023-04-02 22:37:01,624 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2023-04-02 22:37:01,624 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 8 states have (on average 2.0) internal successors, (16), 7 states have internal predecessors, (16), 3 states have call successors, (11), 2 states have call predecessors, (11), 2 states have return successors, (9), 3 states have call predecessors, (9), 3 states have call successors, (9) Word has length 54 [2023-04-02 22:37:01,624 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-04-02 22:37:01,625 INFO L225 Difference]: With dead ends: 125 [2023-04-02 22:37:01,625 INFO L226 Difference]: Without dead ends: 121 [2023-04-02 22:37:01,625 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 132 GetRequests, 106 SyntacticMatches, 4 SemanticMatches, 22 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 141 ImplicationChecksByTransitivity, 2.7s TimeCoverageRelationStatistics Valid=80, Invalid=472, Unknown=0, NotChecked=0, Total=552 [2023-04-02 22:37:01,626 INFO L413 NwaCegarLoop]: 28 mSDtfsCounter, 13 mSDsluCounter, 51 mSDsCounter, 0 mSdLazyCounter, 189 mSolverCounterSat, 12 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 20 SdHoareTripleChecker+Valid, 79 SdHoareTripleChecker+Invalid, 201 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 12 IncrementalHoareTripleChecker+Valid, 189 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-04-02 22:37:01,626 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [20 Valid, 79 Invalid, 201 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [12 Valid, 189 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-04-02 22:37:01,626 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 121 states. [2023-04-02 22:37:01,655 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 121 to 121. [2023-04-02 22:37:01,656 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 121 states, 65 states have (on average 1.1076923076923078) internal successors, (72), 68 states have internal predecessors, (72), 38 states have call successors, (38), 18 states have call predecessors, (38), 17 states have return successors, (34), 34 states have call predecessors, (34), 34 states have call successors, (34) [2023-04-02 22:37:01,656 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 121 states to 121 states and 144 transitions. [2023-04-02 22:37:01,657 INFO L78 Accepts]: Start accepts. Automaton has 121 states and 144 transitions. Word has length 54 [2023-04-02 22:37:01,657 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-04-02 22:37:01,657 INFO L495 AbstractCegarLoop]: Abstraction has 121 states and 144 transitions. [2023-04-02 22:37:01,657 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 8 states have (on average 2.0) internal successors, (16), 7 states have internal predecessors, (16), 3 states have call successors, (11), 2 states have call predecessors, (11), 2 states have return successors, (9), 3 states have call predecessors, (9), 3 states have call successors, (9) [2023-04-02 22:37:01,657 INFO L276 IsEmpty]: Start isEmpty. Operand 121 states and 144 transitions. [2023-04-02 22:37:01,658 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 71 [2023-04-02 22:37:01,658 INFO L187 NwaCegarLoop]: Found error trace [2023-04-02 22:37:01,658 INFO L195 NwaCegarLoop]: trace histogram [12, 11, 11, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-04-02 22:37:01,669 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-04-02 22:37:01,858 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-04-02 22:37:01,858 INFO L420 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-04-02 22:37:01,859 INFO L145 PredicateUnifier]: Initialized classic predicate unifier [2023-04-02 22:37:01,859 INFO L85 PathProgramCache]: Analyzing trace with hash -1446194315, now seen corresponding path program 1 times [2023-04-02 22:37:01,859 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-04-02 22:37:01,859 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1233935873] [2023-04-02 22:37:01,859 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-04-02 22:37:01,859 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-04-02 22:37:01,865 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-04-02 22:37:01,865 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1903927935] [2023-04-02 22:37:01,865 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-04-02 22:37:01,865 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-04-02 22:37:01,865 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-04-02 22:37:01,866 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-04-02 22:37:01,868 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-04-02 22:37:01,907 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-04-02 22:37:01,908 INFO L262 TraceCheckSpWp]: Trace formula consists of 184 conjuncts, 26 conjunts are in the unsatisfiable core [2023-04-02 22:37:01,910 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-04-02 22:37:02,058 INFO L134 CoverageAnalysis]: Checked inductivity of 250 backedges. 21 proven. 39 refuted. 0 times theorem prover too weak. 190 trivial. 0 not checked. [2023-04-02 22:37:02,058 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-04-02 22:37:02,256 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-04-02 22:37:02,257 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1233935873] [2023-04-02 22:37:02,257 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-04-02 22:37:02,257 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1903927935] [2023-04-02 22:37:02,257 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1903927935] provided 0 perfect and 1 imperfect interpolant sequences [2023-04-02 22:37:02,257 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1043775532] [2023-04-02 22:37:02,258 INFO L159 IcfgInterpreter]: Started Sifa with 21 locations of interest [2023-04-02 22:37:02,258 INFO L166 IcfgInterpreter]: Building call graph [2023-04-02 22:37:02,258 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-04-02 22:37:02,258 INFO L176 IcfgInterpreter]: Starting interpretation [2023-04-02 22:37:02,259 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-04-02 22:37:02,271 INFO L197 IcfgInterpreter]: Interpreting procedure main with input of size 13 for LOIs [2023-04-02 22:37:03,063 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 14 for LOIs [2023-04-02 22:37:03,066 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.init with input of size 10 for LOIs [2023-04-02 22:37:03,068 INFO L180 IcfgInterpreter]: Interpretation finished [2023-04-02 22:37:03,577 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '3536#(and (<= 1 |#StackHeapBarrier|) (<= 1 ~counter~0) (= |__VERIFIER_assert_#in~cond| 0) (= __VERIFIER_assert_~cond 0) (= |#NULL.offset| 0) (= |#NULL.base| 0))' at error location [2023-04-02 22:37:03,577 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-04-02 22:37:03,577 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2023-04-02 22:37:03,577 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9] total 9 [2023-04-02 22:37:03,577 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [730623437] [2023-04-02 22:37:03,577 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2023-04-02 22:37:03,578 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2023-04-02 22:37:03,578 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-04-02 22:37:03,578 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2023-04-02 22:37:03,579 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=77, Invalid=573, Unknown=0, NotChecked=0, Total=650 [2023-04-02 22:37:03,579 INFO L87 Difference]: Start difference. First operand 121 states and 144 transitions. Second operand has 9 states, 8 states have (on average 2.125) internal successors, (17), 8 states have internal predecessors, (17), 4 states have call successors, (14), 2 states have call predecessors, (14), 2 states have return successors, (12), 4 states have call predecessors, (12), 4 states have call successors, (12) [2023-04-02 22:37:03,761 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-04-02 22:37:03,761 INFO L93 Difference]: Finished difference Result 127 states and 149 transitions. [2023-04-02 22:37:03,762 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2023-04-02 22:37:03,762 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 8 states have (on average 2.125) internal successors, (17), 8 states have internal predecessors, (17), 4 states have call successors, (14), 2 states have call predecessors, (14), 2 states have return successors, (12), 4 states have call predecessors, (12), 4 states have call successors, (12) Word has length 70 [2023-04-02 22:37:03,762 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-04-02 22:37:03,763 INFO L225 Difference]: With dead ends: 127 [2023-04-02 22:37:03,763 INFO L226 Difference]: Without dead ends: 125 [2023-04-02 22:37:03,763 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 181 GetRequests, 149 SyntacticMatches, 5 SemanticMatches, 27 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 202 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=97, Invalid=715, Unknown=0, NotChecked=0, Total=812 [2023-04-02 22:37:03,764 INFO L413 NwaCegarLoop]: 27 mSDtfsCounter, 13 mSDsluCounter, 59 mSDsCounter, 0 mSdLazyCounter, 231 mSolverCounterSat, 17 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 13 SdHoareTripleChecker+Valid, 86 SdHoareTripleChecker+Invalid, 248 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 17 IncrementalHoareTripleChecker+Valid, 231 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-04-02 22:37:03,764 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [13 Valid, 86 Invalid, 248 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [17 Valid, 231 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-04-02 22:37:03,764 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 125 states. [2023-04-02 22:37:03,783 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 125 to 125. [2023-04-02 22:37:03,783 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 125 states, 68 states have (on average 1.1029411764705883) internal successors, (75), 71 states have internal predecessors, (75), 38 states have call successors, (38), 19 states have call predecessors, (38), 18 states have return successors, (34), 34 states have call predecessors, (34), 34 states have call successors, (34) [2023-04-02 22:37:03,784 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 125 states to 125 states and 147 transitions. [2023-04-02 22:37:03,784 INFO L78 Accepts]: Start accepts. Automaton has 125 states and 147 transitions. Word has length 70 [2023-04-02 22:37:03,784 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-04-02 22:37:03,784 INFO L495 AbstractCegarLoop]: Abstraction has 125 states and 147 transitions. [2023-04-02 22:37:03,784 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 8 states have (on average 2.125) internal successors, (17), 8 states have internal predecessors, (17), 4 states have call successors, (14), 2 states have call predecessors, (14), 2 states have return successors, (12), 4 states have call predecessors, (12), 4 states have call successors, (12) [2023-04-02 22:37:03,784 INFO L276 IsEmpty]: Start isEmpty. Operand 125 states and 147 transitions. [2023-04-02 22:37:03,787 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 76 [2023-04-02 22:37:03,787 INFO L187 NwaCegarLoop]: Found error trace [2023-04-02 22:37:03,787 INFO L195 NwaCegarLoop]: trace histogram [13, 12, 12, 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] [2023-04-02 22:37:03,792 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-04-02 22:37:03,992 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-04-02 22:37:03,992 INFO L420 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-04-02 22:37:03,992 INFO L145 PredicateUnifier]: Initialized classic predicate unifier [2023-04-02 22:37:03,992 INFO L85 PathProgramCache]: Analyzing trace with hash -2131269829, now seen corresponding path program 1 times [2023-04-02 22:37:03,993 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-04-02 22:37:03,993 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1309715127] [2023-04-02 22:37:03,993 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-04-02 22:37:03,993 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-04-02 22:37:03,998 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-04-02 22:37:03,998 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1688548685] [2023-04-02 22:37:03,998 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-04-02 22:37:03,998 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-04-02 22:37:03,998 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-04-02 22:37:03,999 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-04-02 22:37:04,001 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-04-02 22:37:04,043 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-04-02 22:37:04,044 INFO L262 TraceCheckSpWp]: Trace formula consists of 193 conjuncts, 24 conjunts are in the unsatisfiable core [2023-04-02 22:37:04,045 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-04-02 22:37:04,186 INFO L134 CoverageAnalysis]: Checked inductivity of 296 backedges. 23 proven. 42 refuted. 0 times theorem prover too weak. 231 trivial. 0 not checked. [2023-04-02 22:37:04,186 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-04-02 22:37:04,334 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-04-02 22:37:04,334 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1309715127] [2023-04-02 22:37:04,334 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-04-02 22:37:04,334 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1688548685] [2023-04-02 22:37:04,334 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1688548685] provided 0 perfect and 1 imperfect interpolant sequences [2023-04-02 22:37:04,334 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1134367310] [2023-04-02 22:37:04,336 INFO L159 IcfgInterpreter]: Started Sifa with 22 locations of interest [2023-04-02 22:37:04,336 INFO L166 IcfgInterpreter]: Building call graph [2023-04-02 22:37:04,336 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-04-02 22:37:04,336 INFO L176 IcfgInterpreter]: Starting interpretation [2023-04-02 22:37:04,336 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-04-02 22:37:04,351 INFO L197 IcfgInterpreter]: Interpreting procedure main with input of size 13 for LOIs [2023-04-02 22:37:05,148 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 9 for LOIs [2023-04-02 22:37:05,151 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.init with input of size 10 for LOIs [2023-04-02 22:37:05,153 INFO L180 IcfgInterpreter]: Interpretation finished [2023-04-02 22:37:05,645 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '4298#(and (<= 1 |#StackHeapBarrier|) (= |__VERIFIER_assert_#in~cond| 0) (= __VERIFIER_assert_~cond 0) (= |#NULL.offset| 0) (= |#NULL.base| 0))' at error location [2023-04-02 22:37:05,645 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-04-02 22:37:05,645 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2023-04-02 22:37:05,646 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9] total 9 [2023-04-02 22:37:05,646 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1796757249] [2023-04-02 22:37:05,646 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2023-04-02 22:37:05,646 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2023-04-02 22:37:05,646 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-04-02 22:37:05,646 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2023-04-02 22:37:05,647 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=78, Invalid=522, Unknown=0, NotChecked=0, Total=600 [2023-04-02 22:37:05,647 INFO L87 Difference]: Start difference. First operand 125 states and 147 transitions. Second operand has 9 states, 8 states have (on average 2.125) internal successors, (17), 8 states have internal predecessors, (17), 4 states have call successors, (15), 2 states have call predecessors, (15), 2 states have return successors, (13), 4 states have call predecessors, (13), 4 states have call successors, (13) [2023-04-02 22:37:05,829 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-04-02 22:37:05,829 INFO L93 Difference]: Finished difference Result 135 states and 155 transitions. [2023-04-02 22:37:05,831 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2023-04-02 22:37:05,831 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 8 states have (on average 2.125) internal successors, (17), 8 states have internal predecessors, (17), 4 states have call successors, (15), 2 states have call predecessors, (15), 2 states have return successors, (13), 4 states have call predecessors, (13), 4 states have call successors, (13) Word has length 75 [2023-04-02 22:37:05,832 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-04-02 22:37:05,832 INFO L225 Difference]: With dead ends: 135 [2023-04-02 22:37:05,832 INFO L226 Difference]: Without dead ends: 131 [2023-04-02 22:37:05,833 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 196 GetRequests, 164 SyntacticMatches, 6 SemanticMatches, 26 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 210 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=98, Invalid=658, Unknown=0, NotChecked=0, Total=756 [2023-04-02 22:37:05,833 INFO L413 NwaCegarLoop]: 27 mSDtfsCounter, 13 mSDsluCounter, 59 mSDsCounter, 0 mSdLazyCounter, 233 mSolverCounterSat, 14 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 13 SdHoareTripleChecker+Valid, 86 SdHoareTripleChecker+Invalid, 247 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 14 IncrementalHoareTripleChecker+Valid, 233 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-04-02 22:37:05,833 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [13 Valid, 86 Invalid, 247 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [14 Valid, 233 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-04-02 22:37:05,834 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 131 states. [2023-04-02 22:37:05,853 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 131 to 131. [2023-04-02 22:37:05,857 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 131 states, 73 states have (on average 1.082191780821918) internal successors, (79), 75 states have internal predecessors, (79), 38 states have call successors, (38), 21 states have call predecessors, (38), 19 states have return successors, (34), 34 states have call predecessors, (34), 34 states have call successors, (34) [2023-04-02 22:37:05,857 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 131 states to 131 states and 151 transitions. [2023-04-02 22:37:05,858 INFO L78 Accepts]: Start accepts. Automaton has 131 states and 151 transitions. Word has length 75 [2023-04-02 22:37:05,858 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-04-02 22:37:05,858 INFO L495 AbstractCegarLoop]: Abstraction has 131 states and 151 transitions. [2023-04-02 22:37:05,858 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 8 states have (on average 2.125) internal successors, (17), 8 states have internal predecessors, (17), 4 states have call successors, (15), 2 states have call predecessors, (15), 2 states have return successors, (13), 4 states have call predecessors, (13), 4 states have call successors, (13) [2023-04-02 22:37:05,858 INFO L276 IsEmpty]: Start isEmpty. Operand 131 states and 151 transitions. [2023-04-02 22:37:05,861 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 78 [2023-04-02 22:37:05,861 INFO L187 NwaCegarLoop]: Found error trace [2023-04-02 22:37:05,861 INFO L195 NwaCegarLoop]: trace histogram [13, 12, 12, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1] [2023-04-02 22:37:05,870 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Forceful destruction successful, exit code 0 [2023-04-02 22:37:06,066 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable9,8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-04-02 22:37:06,066 INFO L420 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-04-02 22:37:06,067 INFO L145 PredicateUnifier]: Initialized classic predicate unifier [2023-04-02 22:37:06,067 INFO L85 PathProgramCache]: Analyzing trace with hash -794288980, now seen corresponding path program 4 times [2023-04-02 22:37:06,067 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-04-02 22:37:06,067 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [337895630] [2023-04-02 22:37:06,067 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-04-02 22:37:06,067 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-04-02 22:37:06,079 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-04-02 22:37:06,079 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1504440781] [2023-04-02 22:37:06,079 INFO L93 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2023-04-02 22:37:06,079 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-04-02 22:37:06,080 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-04-02 22:37:06,082 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-04-02 22:37:06,088 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-04-02 22:37:06,130 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-04-02 22:37:06,131 INFO L262 TraceCheckSpWp]: Trace formula consists of 206 conjuncts, 36 conjunts are in the unsatisfiable core [2023-04-02 22:37:06,132 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-04-02 22:37:06,280 INFO L134 CoverageAnalysis]: Checked inductivity of 306 backedges. 52 proven. 50 refuted. 0 times theorem prover too weak. 204 trivial. 0 not checked. [2023-04-02 22:37:06,280 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-04-02 22:37:06,508 INFO L134 CoverageAnalysis]: Checked inductivity of 306 backedges. 52 proven. 50 refuted. 0 times theorem prover too weak. 204 trivial. 0 not checked. [2023-04-02 22:37:06,508 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-04-02 22:37:06,508 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [337895630] [2023-04-02 22:37:06,508 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-04-02 22:37:06,508 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1504440781] [2023-04-02 22:37:06,508 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1504440781] provided 0 perfect and 2 imperfect interpolant sequences [2023-04-02 22:37:06,508 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1882954468] [2023-04-02 22:37:06,509 INFO L159 IcfgInterpreter]: Started Sifa with 19 locations of interest [2023-04-02 22:37:06,509 INFO L166 IcfgInterpreter]: Building call graph [2023-04-02 22:37:06,510 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-04-02 22:37:06,510 INFO L176 IcfgInterpreter]: Starting interpretation [2023-04-02 22:37:06,510 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-04-02 22:37:06,521 INFO L197 IcfgInterpreter]: Interpreting procedure main with input of size 13 for LOIs [2023-04-02 22:37:07,144 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 23 for LOIs [2023-04-02 22:37:07,149 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.init with input of size 10 for LOIs [2023-04-02 22:37:07,152 INFO L180 IcfgInterpreter]: Interpretation finished [2023-04-02 22:37:07,643 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '5186#(and (<= 1 |#StackHeapBarrier|) (<= 1 ~counter~0) (= |__VERIFIER_assert_#in~cond| 0) (= __VERIFIER_assert_~cond 0) (= |#NULL.offset| 0) (= |#NULL.base| 0))' at error location [2023-04-02 22:37:07,643 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-04-02 22:37:07,643 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-04-02 22:37:07,643 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10] total 17 [2023-04-02 22:37:07,643 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1027323580] [2023-04-02 22:37:07,643 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-04-02 22:37:07,644 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 17 states [2023-04-02 22:37:07,644 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-04-02 22:37:07,644 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2023-04-02 22:37:07,644 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=97, Invalid=715, Unknown=0, NotChecked=0, Total=812 [2023-04-02 22:37:07,645 INFO L87 Difference]: Start difference. First operand 131 states and 151 transitions. Second operand has 17 states, 15 states have (on average 2.1333333333333333) internal successors, (32), 13 states have internal predecessors, (32), 10 states have call successors, (28), 3 states have call predecessors, (28), 2 states have return successors, (25), 9 states have call predecessors, (25), 8 states have call successors, (25) [2023-04-02 22:37:10,165 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-04-02 22:37:12,427 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-04-02 22:37:12,488 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-04-02 22:37:12,489 INFO L93 Difference]: Finished difference Result 164 states and 203 transitions. [2023-04-02 22:37:12,489 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2023-04-02 22:37:12,489 INFO L78 Accepts]: Start accepts. Automaton has has 17 states, 15 states have (on average 2.1333333333333333) internal successors, (32), 13 states have internal predecessors, (32), 10 states have call successors, (28), 3 states have call predecessors, (28), 2 states have return successors, (25), 9 states have call predecessors, (25), 8 states have call successors, (25) Word has length 77 [2023-04-02 22:37:12,489 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-04-02 22:37:12,491 INFO L225 Difference]: With dead ends: 164 [2023-04-02 22:37:12,491 INFO L226 Difference]: Without dead ends: 148 [2023-04-02 22:37:12,492 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 239 GetRequests, 197 SyntacticMatches, 6 SemanticMatches, 36 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 356 ImplicationChecksByTransitivity, 0.8s TimeCoverageRelationStatistics Valid=187, Invalid=1219, Unknown=0, NotChecked=0, Total=1406 [2023-04-02 22:37:12,492 INFO L413 NwaCegarLoop]: 38 mSDtfsCounter, 32 mSDsluCounter, 117 mSDsCounter, 0 mSdLazyCounter, 560 mSolverCounterSat, 87 mSolverCounterUnsat, 2 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 4.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 40 SdHoareTripleChecker+Valid, 155 SdHoareTripleChecker+Invalid, 649 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 87 IncrementalHoareTripleChecker+Valid, 560 IncrementalHoareTripleChecker+Invalid, 2 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 4.6s IncrementalHoareTripleChecker+Time [2023-04-02 22:37:12,493 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [40 Valid, 155 Invalid, 649 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [87 Valid, 560 Invalid, 2 Unknown, 0 Unchecked, 4.6s Time] [2023-04-02 22:37:12,493 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 148 states. [2023-04-02 22:37:12,520 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 148 to 125. [2023-04-02 22:37:12,520 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 125 states, 71 states have (on average 1.0704225352112675) internal successors, (76), 73 states have internal predecessors, (76), 34 states have call successors, (34), 20 states have call predecessors, (34), 19 states have return successors, (31), 31 states have call predecessors, (31), 31 states have call successors, (31) [2023-04-02 22:37:12,523 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 125 states to 125 states and 141 transitions. [2023-04-02 22:37:12,523 INFO L78 Accepts]: Start accepts. Automaton has 125 states and 141 transitions. Word has length 77 [2023-04-02 22:37:12,524 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-04-02 22:37:12,524 INFO L495 AbstractCegarLoop]: Abstraction has 125 states and 141 transitions. [2023-04-02 22:37:12,524 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 17 states, 15 states have (on average 2.1333333333333333) internal successors, (32), 13 states have internal predecessors, (32), 10 states have call successors, (28), 3 states have call predecessors, (28), 2 states have return successors, (25), 9 states have call predecessors, (25), 8 states have call successors, (25) [2023-04-02 22:37:12,525 INFO L276 IsEmpty]: Start isEmpty. Operand 125 states and 141 transitions. [2023-04-02 22:37:12,527 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 83 [2023-04-02 22:37:12,527 INFO L187 NwaCegarLoop]: Found error trace [2023-04-02 22:37:12,527 INFO L195 NwaCegarLoop]: trace histogram [14, 13, 13, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1] [2023-04-02 22:37:12,534 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Ended with exit code 0 [2023-04-02 22:37:12,734 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,SelfDestructingSolverStorable10 [2023-04-02 22:37:12,734 INFO L420 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-04-02 22:37:12,734 INFO L145 PredicateUnifier]: Initialized classic predicate unifier [2023-04-02 22:37:12,735 INFO L85 PathProgramCache]: Analyzing trace with hash 1512565092, now seen corresponding path program 5 times [2023-04-02 22:37:12,735 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-04-02 22:37:12,735 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1586215323] [2023-04-02 22:37:12,735 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-04-02 22:37:12,735 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-04-02 22:37:12,744 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-04-02 22:37:12,744 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [289885596] [2023-04-02 22:37:12,744 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2023-04-02 22:37:12,745 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-04-02 22:37:12,745 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-04-02 22:37:12,745 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-04-02 22:37:12,749 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-04-02 22:37:12,792 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2023-04-02 22:37:12,792 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-04-02 22:37:12,793 INFO L262 TraceCheckSpWp]: Trace formula consists of 143 conjuncts, 38 conjunts are in the unsatisfiable core [2023-04-02 22:37:12,794 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-04-02 22:37:13,025 INFO L134 CoverageAnalysis]: Checked inductivity of 358 backedges. 55 proven. 27 refuted. 0 times theorem prover too weak. 276 trivial. 0 not checked. [2023-04-02 22:37:13,025 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-04-02 22:37:13,526 INFO L134 CoverageAnalysis]: Checked inductivity of 358 backedges. 55 proven. 27 refuted. 0 times theorem prover too weak. 276 trivial. 0 not checked. [2023-04-02 22:37:13,527 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-04-02 22:37:13,527 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1586215323] [2023-04-02 22:37:13,527 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-04-02 22:37:13,527 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [289885596] [2023-04-02 22:37:13,527 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [289885596] provided 0 perfect and 2 imperfect interpolant sequences [2023-04-02 22:37:13,527 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [29074571] [2023-04-02 22:37:13,529 INFO L159 IcfgInterpreter]: Started Sifa with 19 locations of interest [2023-04-02 22:37:13,529 INFO L166 IcfgInterpreter]: Building call graph [2023-04-02 22:37:13,530 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-04-02 22:37:13,530 INFO L176 IcfgInterpreter]: Starting interpretation [2023-04-02 22:37:13,530 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-04-02 22:37:13,544 INFO L197 IcfgInterpreter]: Interpreting procedure main with input of size 13 for LOIs [2023-04-02 22:37:14,268 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 23 for LOIs [2023-04-02 22:37:14,273 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.init with input of size 10 for LOIs [2023-04-02 22:37:14,275 INFO L180 IcfgInterpreter]: Interpretation finished [2023-04-02 22:37:14,953 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '6156#(and (<= 1 |#StackHeapBarrier|) (<= 1 ~counter~0) (= |__VERIFIER_assert_#in~cond| 0) (= __VERIFIER_assert_~cond 0) (= |#NULL.offset| 0) (= |#NULL.base| 0))' at error location [2023-04-02 22:37:14,953 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-04-02 22:37:14,953 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-04-02 22:37:14,953 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 9] total 16 [2023-04-02 22:37:14,954 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [775357470] [2023-04-02 22:37:14,954 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-04-02 22:37:14,954 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2023-04-02 22:37:14,954 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-04-02 22:37:14,954 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2023-04-02 22:37:14,955 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=95, Invalid=661, Unknown=0, NotChecked=0, Total=756 [2023-04-02 22:37:14,955 INFO L87 Difference]: Start difference. First operand 125 states and 141 transitions. Second operand has 16 states, 14 states have (on average 2.2857142857142856) internal successors, (32), 13 states have internal predecessors, (32), 9 states have call successors, (30), 3 states have call predecessors, (30), 2 states have return successors, (27), 7 states have call predecessors, (27), 9 states have call successors, (27) [2023-04-02 22:37:17,863 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.04s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-04-02 22:37:18,505 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-04-02 22:37:18,505 INFO L93 Difference]: Finished difference Result 137 states and 154 transitions. [2023-04-02 22:37:18,505 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2023-04-02 22:37:18,505 INFO L78 Accepts]: Start accepts. Automaton has has 16 states, 14 states have (on average 2.2857142857142856) internal successors, (32), 13 states have internal predecessors, (32), 9 states have call successors, (30), 3 states have call predecessors, (30), 2 states have return successors, (27), 7 states have call predecessors, (27), 9 states have call successors, (27) Word has length 82 [2023-04-02 22:37:18,505 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-04-02 22:37:18,506 INFO L225 Difference]: With dead ends: 137 [2023-04-02 22:37:18,506 INFO L226 Difference]: Without dead ends: 130 [2023-04-02 22:37:18,508 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 250 GetRequests, 213 SyntacticMatches, 7 SemanticMatches, 30 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 280 ImplicationChecksByTransitivity, 1.7s TimeCoverageRelationStatistics Valid=132, Invalid=860, Unknown=0, NotChecked=0, Total=992 [2023-04-02 22:37:18,508 INFO L413 NwaCegarLoop]: 34 mSDtfsCounter, 24 mSDsluCounter, 113 mSDsCounter, 0 mSdLazyCounter, 461 mSolverCounterSat, 62 mSolverCounterUnsat, 1 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 2.8s Time, 0 mProtectedPredicate, 0 mProtectedAction, 34 SdHoareTripleChecker+Valid, 147 SdHoareTripleChecker+Invalid, 524 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 62 IncrementalHoareTripleChecker+Valid, 461 IncrementalHoareTripleChecker+Invalid, 1 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 2.9s IncrementalHoareTripleChecker+Time [2023-04-02 22:37:18,508 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [34 Valid, 147 Invalid, 524 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [62 Valid, 461 Invalid, 1 Unknown, 0 Unchecked, 2.9s Time] [2023-04-02 22:37:18,509 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 130 states. [2023-04-02 22:37:18,526 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 130 to 128. [2023-04-02 22:37:18,526 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 128 states, 77 states have (on average 1.0649350649350648) internal successors, (82), 79 states have internal predecessors, (82), 29 states have call successors, (29), 22 states have call predecessors, (29), 21 states have return successors, (26), 26 states have call predecessors, (26), 26 states have call successors, (26) [2023-04-02 22:37:18,527 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 128 states to 128 states and 137 transitions. [2023-04-02 22:37:18,527 INFO L78 Accepts]: Start accepts. Automaton has 128 states and 137 transitions. Word has length 82 [2023-04-02 22:37:18,527 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-04-02 22:37:18,527 INFO L495 AbstractCegarLoop]: Abstraction has 128 states and 137 transitions. [2023-04-02 22:37:18,527 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 16 states, 14 states have (on average 2.2857142857142856) internal successors, (32), 13 states have internal predecessors, (32), 9 states have call successors, (30), 3 states have call predecessors, (30), 2 states have return successors, (27), 7 states have call predecessors, (27), 9 states have call successors, (27) [2023-04-02 22:37:18,527 INFO L276 IsEmpty]: Start isEmpty. Operand 128 states and 137 transitions. [2023-04-02 22:37:18,528 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 99 [2023-04-02 22:37:18,528 INFO L187 NwaCegarLoop]: Found error trace [2023-04-02 22:37:18,528 INFO L195 NwaCegarLoop]: trace histogram [17, 16, 16, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-04-02 22:37:18,535 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Forceful destruction successful, exit code 0 [2023-04-02 22:37:18,733 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable11,10 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-04-02 22:37:18,733 INFO L420 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-04-02 22:37:18,733 INFO L145 PredicateUnifier]: Initialized classic predicate unifier [2023-04-02 22:37:18,733 INFO L85 PathProgramCache]: Analyzing trace with hash 2010254942, now seen corresponding path program 2 times [2023-04-02 22:37:18,733 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-04-02 22:37:18,733 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [940866904] [2023-04-02 22:37:18,733 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-04-02 22:37:18,733 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-04-02 22:37:18,739 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-04-02 22:37:18,739 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [763263163] [2023-04-02 22:37:18,739 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2023-04-02 22:37:18,739 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-04-02 22:37:18,740 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-04-02 22:37:18,740 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-04-02 22:37:18,746 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-04-02 22:37:18,812 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2023-04-02 22:37:18,812 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-04-02 22:37:18,813 INFO L262 TraceCheckSpWp]: Trace formula consists of 144 conjuncts, 39 conjunts are in the unsatisfiable core [2023-04-02 22:37:18,817 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-04-02 22:37:19,031 INFO L134 CoverageAnalysis]: Checked inductivity of 536 backedges. 76 proven. 25 refuted. 0 times theorem prover too weak. 435 trivial. 0 not checked. [2023-04-02 22:37:19,031 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-04-02 22:37:19,989 INFO L134 CoverageAnalysis]: Checked inductivity of 536 backedges. 92 proven. 1 refuted. 0 times theorem prover too weak. 443 trivial. 0 not checked. [2023-04-02 22:37:19,989 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-04-02 22:37:19,989 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [940866904] [2023-04-02 22:37:19,989 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-04-02 22:37:19,989 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [763263163] [2023-04-02 22:37:19,989 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [763263163] provided 0 perfect and 2 imperfect interpolant sequences [2023-04-02 22:37:19,989 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [981468273] [2023-04-02 22:37:19,992 INFO L159 IcfgInterpreter]: Started Sifa with 21 locations of interest [2023-04-02 22:37:19,992 INFO L166 IcfgInterpreter]: Building call graph [2023-04-02 22:37:19,992 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-04-02 22:37:19,992 INFO L176 IcfgInterpreter]: Starting interpretation [2023-04-02 22:37:19,992 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-04-02 22:37:20,006 INFO L197 IcfgInterpreter]: Interpreting procedure main with input of size 13 for LOIs [2023-04-02 22:37:20,722 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 14 for LOIs [2023-04-02 22:37:20,725 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.init with input of size 10 for LOIs [2023-04-02 22:37:20,727 INFO L180 IcfgInterpreter]: Interpretation finished [2023-04-02 22:37:21,230 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '7162#(and (<= 1 |#StackHeapBarrier|) (<= 1 ~counter~0) (= |__VERIFIER_assert_#in~cond| 0) (= __VERIFIER_assert_~cond 0) (= |#NULL.offset| 0) (= |#NULL.base| 0))' at error location [2023-04-02 22:37:21,230 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-04-02 22:37:21,231 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-04-02 22:37:21,231 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 8] total 16 [2023-04-02 22:37:21,231 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1235077872] [2023-04-02 22:37:21,231 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-04-02 22:37:21,231 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2023-04-02 22:37:21,231 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-04-02 22:37:21,231 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2023-04-02 22:37:21,232 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=97, Invalid=715, Unknown=0, NotChecked=0, Total=812 [2023-04-02 22:37:21,232 INFO L87 Difference]: Start difference. First operand 128 states and 137 transitions. Second operand has 16 states, 12 states have (on average 2.6666666666666665) internal successors, (32), 13 states have internal predecessors, (32), 9 states have call successors, (31), 3 states have call predecessors, (31), 2 states have return successors, (28), 7 states have call predecessors, (28), 7 states have call successors, (28) [2023-04-02 22:37:21,780 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-04-02 22:37:21,780 INFO L93 Difference]: Finished difference Result 140 states and 150 transitions. [2023-04-02 22:37:21,781 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2023-04-02 22:37:21,781 INFO L78 Accepts]: Start accepts. Automaton has has 16 states, 12 states have (on average 2.6666666666666665) internal successors, (32), 13 states have internal predecessors, (32), 9 states have call successors, (31), 3 states have call predecessors, (31), 2 states have return successors, (28), 7 states have call predecessors, (28), 7 states have call successors, (28) Word has length 98 [2023-04-02 22:37:21,781 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-04-02 22:37:21,782 INFO L225 Difference]: With dead ends: 140 [2023-04-02 22:37:21,782 INFO L226 Difference]: Without dead ends: 136 [2023-04-02 22:37:21,785 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 296 GetRequests, 259 SyntacticMatches, 7 SemanticMatches, 30 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 317 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=117, Invalid=875, Unknown=0, NotChecked=0, Total=992 [2023-04-02 22:37:21,787 INFO L413 NwaCegarLoop]: 32 mSDtfsCounter, 16 mSDsluCounter, 90 mSDsCounter, 0 mSdLazyCounter, 348 mSolverCounterSat, 37 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 22 SdHoareTripleChecker+Valid, 122 SdHoareTripleChecker+Invalid, 385 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 37 IncrementalHoareTripleChecker+Valid, 348 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.5s IncrementalHoareTripleChecker+Time [2023-04-02 22:37:21,787 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [22 Valid, 122 Invalid, 385 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [37 Valid, 348 Invalid, 0 Unknown, 0 Unchecked, 0.5s Time] [2023-04-02 22:37:21,788 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 136 states. [2023-04-02 22:37:21,810 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 136 to 136. [2023-04-02 22:37:21,810 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 136 states, 82 states have (on average 1.048780487804878) internal successors, (86), 84 states have internal predecessors, (86), 31 states have call successors, (31), 24 states have call predecessors, (31), 22 states have return successors, (28), 27 states have call predecessors, (28), 28 states have call successors, (28) [2023-04-02 22:37:21,811 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 136 states to 136 states and 145 transitions. [2023-04-02 22:37:21,811 INFO L78 Accepts]: Start accepts. Automaton has 136 states and 145 transitions. Word has length 98 [2023-04-02 22:37:21,811 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-04-02 22:37:21,811 INFO L495 AbstractCegarLoop]: Abstraction has 136 states and 145 transitions. [2023-04-02 22:37:21,811 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 16 states, 12 states have (on average 2.6666666666666665) internal successors, (32), 13 states have internal predecessors, (32), 9 states have call successors, (31), 3 states have call predecessors, (31), 2 states have return successors, (28), 7 states have call predecessors, (28), 7 states have call successors, (28) [2023-04-02 22:37:21,811 INFO L276 IsEmpty]: Start isEmpty. Operand 136 states and 145 transitions. [2023-04-02 22:37:21,812 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 104 [2023-04-02 22:37:21,812 INFO L187 NwaCegarLoop]: Found error trace [2023-04-02 22:37:21,812 INFO L195 NwaCegarLoop]: trace histogram [18, 17, 17, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-04-02 22:37:21,816 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-04-02 22:37:22,017 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,SelfDestructingSolverStorable12 [2023-04-02 22:37:22,017 INFO L420 AbstractCegarLoop]: === Iteration 14 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-04-02 22:37:22,017 INFO L145 PredicateUnifier]: Initialized classic predicate unifier [2023-04-02 22:37:22,017 INFO L85 PathProgramCache]: Analyzing trace with hash 884970994, now seen corresponding path program 2 times [2023-04-02 22:37:22,017 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-04-02 22:37:22,017 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [648671716] [2023-04-02 22:37:22,017 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-04-02 22:37:22,018 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-04-02 22:37:22,024 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-04-02 22:37:22,024 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1491705276] [2023-04-02 22:37:22,024 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2023-04-02 22:37:22,024 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-04-02 22:37:22,024 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-04-02 22:37:22,025 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-04-02 22:37:22,070 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-04-02 22:37:22,108 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2023-04-02 22:37:22,108 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-04-02 22:37:22,110 INFO L262 TraceCheckSpWp]: Trace formula consists of 143 conjuncts, 41 conjunts are in the unsatisfiable core [2023-04-02 22:37:22,111 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-04-02 22:37:22,353 INFO L134 CoverageAnalysis]: Checked inductivity of 602 backedges. 107 proven. 41 refuted. 0 times theorem prover too weak. 454 trivial. 0 not checked. [2023-04-02 22:37:22,353 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-04-02 22:37:23,044 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-04-02 22:37:23,045 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [648671716] [2023-04-02 22:37:23,045 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-04-02 22:37:23,045 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1491705276] [2023-04-02 22:37:23,045 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1491705276] provided 0 perfect and 1 imperfect interpolant sequences [2023-04-02 22:37:23,045 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1832002823] [2023-04-02 22:37:23,054 INFO L159 IcfgInterpreter]: Started Sifa with 22 locations of interest [2023-04-02 22:37:23,054 INFO L166 IcfgInterpreter]: Building call graph [2023-04-02 22:37:23,055 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-04-02 22:37:23,055 INFO L176 IcfgInterpreter]: Starting interpretation [2023-04-02 22:37:23,055 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-04-02 22:37:23,067 INFO L197 IcfgInterpreter]: Interpreting procedure main with input of size 13 for LOIs [2023-04-02 22:37:23,743 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 14 for LOIs [2023-04-02 22:37:23,746 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.init with input of size 10 for LOIs [2023-04-02 22:37:23,748 INFO L180 IcfgInterpreter]: Interpretation finished [2023-04-02 22:37:24,271 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '8032#(and (<= 1 |#StackHeapBarrier|) (<= 1 ~counter~0) (= |__VERIFIER_assert_#in~cond| 0) (= __VERIFIER_assert_~cond 0) (= |#NULL.offset| 0) (= |#NULL.base| 0))' at error location [2023-04-02 22:37:24,271 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-04-02 22:37:24,271 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2023-04-02 22:37:24,271 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11] total 11 [2023-04-02 22:37:24,271 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1185143796] [2023-04-02 22:37:24,271 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2023-04-02 22:37:24,272 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 11 states [2023-04-02 22:37:24,272 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-04-02 22:37:24,272 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2023-04-02 22:37:24,272 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=104, Invalid=766, Unknown=0, NotChecked=0, Total=870 [2023-04-02 22:37:24,273 INFO L87 Difference]: Start difference. First operand 136 states and 145 transitions. Second operand has 11 states, 10 states have (on average 2.0) internal successors, (20), 9 states have internal predecessors, (20), 6 states have call successors, (20), 2 states have call predecessors, (20), 2 states have return successors, (18), 5 states have call predecessors, (18), 5 states have call successors, (18) [2023-04-02 22:37:24,577 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-04-02 22:37:24,577 INFO L93 Difference]: Finished difference Result 138 states and 146 transitions. [2023-04-02 22:37:24,577 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2023-04-02 22:37:24,578 INFO L78 Accepts]: Start accepts. Automaton has has 11 states, 10 states have (on average 2.0) internal successors, (20), 9 states have internal predecessors, (20), 6 states have call successors, (20), 2 states have call predecessors, (20), 2 states have return successors, (18), 5 states have call predecessors, (18), 5 states have call successors, (18) Word has length 103 [2023-04-02 22:37:24,578 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-04-02 22:37:24,579 INFO L225 Difference]: With dead ends: 138 [2023-04-02 22:37:24,579 INFO L226 Difference]: Without dead ends: 127 [2023-04-02 22:37:24,580 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 252 GetRequests, 213 SyntacticMatches, 8 SemanticMatches, 31 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 327 ImplicationChecksByTransitivity, 1.0s TimeCoverageRelationStatistics Valid=129, Invalid=927, Unknown=0, NotChecked=0, Total=1056 [2023-04-02 22:37:24,580 INFO L413 NwaCegarLoop]: 32 mSDtfsCounter, 12 mSDsluCounter, 92 mSDsCounter, 0 mSdLazyCounter, 347 mSolverCounterSat, 22 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 17 SdHoareTripleChecker+Valid, 124 SdHoareTripleChecker+Invalid, 369 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 22 IncrementalHoareTripleChecker+Valid, 347 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2023-04-02 22:37:24,580 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [17 Valid, 124 Invalid, 369 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [22 Valid, 347 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2023-04-02 22:37:24,581 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 127 states. [2023-04-02 22:37:24,600 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 127 to 127. [2023-04-02 22:37:24,601 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 127 states, 77 states have (on average 1.0389610389610389) internal successors, (80), 79 states have internal predecessors, (80), 28 states have call successors, (28), 22 states have call predecessors, (28), 21 states have return successors, (26), 25 states have call predecessors, (26), 26 states have call successors, (26) [2023-04-02 22:37:24,601 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 127 states to 127 states and 134 transitions. [2023-04-02 22:37:24,602 INFO L78 Accepts]: Start accepts. Automaton has 127 states and 134 transitions. Word has length 103 [2023-04-02 22:37:24,602 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-04-02 22:37:24,602 INFO L495 AbstractCegarLoop]: Abstraction has 127 states and 134 transitions. [2023-04-02 22:37:24,602 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 11 states, 10 states have (on average 2.0) internal successors, (20), 9 states have internal predecessors, (20), 6 states have call successors, (20), 2 states have call predecessors, (20), 2 states have return successors, (18), 5 states have call predecessors, (18), 5 states have call successors, (18) [2023-04-02 22:37:24,602 INFO L276 IsEmpty]: Start isEmpty. Operand 127 states and 134 transitions. [2023-04-02 22:37:24,603 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 129 [2023-04-02 22:37:24,603 INFO L187 NwaCegarLoop]: Found error trace [2023-04-02 22:37:24,603 INFO L195 NwaCegarLoop]: trace histogram [22, 21, 21, 5, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-04-02 22:37:24,609 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-04-02 22:37:24,808 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,SelfDestructingSolverStorable13 [2023-04-02 22:37:24,808 INFO L420 AbstractCegarLoop]: === Iteration 15 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-04-02 22:37:24,808 INFO L145 PredicateUnifier]: Initialized classic predicate unifier [2023-04-02 22:37:24,808 INFO L85 PathProgramCache]: Analyzing trace with hash -689366782, now seen corresponding path program 2 times [2023-04-02 22:37:24,809 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-04-02 22:37:24,809 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [922365826] [2023-04-02 22:37:24,809 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-04-02 22:37:24,809 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-04-02 22:37:24,814 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-04-02 22:37:24,815 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1953416881] [2023-04-02 22:37:24,815 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2023-04-02 22:37:24,815 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-04-02 22:37:24,815 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-04-02 22:37:24,816 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-04-02 22:37:24,816 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-04-02 22:37:24,930 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 10 check-sat command(s) [2023-04-02 22:37:24,931 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-04-02 22:37:24,932 INFO L262 TraceCheckSpWp]: Trace formula consists of 288 conjuncts, 13 conjunts are in the unsatisfiable core [2023-04-02 22:37:24,934 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-04-02 22:37:25,050 INFO L134 CoverageAnalysis]: Checked inductivity of 938 backedges. 120 proven. 656 refuted. 0 times theorem prover too weak. 162 trivial. 0 not checked. [2023-04-02 22:37:25,051 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-04-02 22:37:25,184 INFO L134 CoverageAnalysis]: Checked inductivity of 938 backedges. 42 proven. 56 refuted. 0 times theorem prover too weak. 840 trivial. 0 not checked. [2023-04-02 22:37:25,184 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-04-02 22:37:25,184 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [922365826] [2023-04-02 22:37:25,184 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-04-02 22:37:25,184 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1953416881] [2023-04-02 22:37:25,184 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1953416881] provided 0 perfect and 2 imperfect interpolant sequences [2023-04-02 22:37:25,184 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1659144537] [2023-04-02 22:37:25,185 INFO L159 IcfgInterpreter]: Started Sifa with 21 locations of interest [2023-04-02 22:37:25,185 INFO L166 IcfgInterpreter]: Building call graph [2023-04-02 22:37:25,185 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-04-02 22:37:25,185 INFO L176 IcfgInterpreter]: Starting interpretation [2023-04-02 22:37:25,185 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-04-02 22:37:25,196 INFO L197 IcfgInterpreter]: Interpreting procedure main with input of size 13 for LOIs [2023-04-02 22:37:25,754 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 23 for LOIs [2023-04-02 22:37:25,759 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.init with input of size 10 for LOIs [2023-04-02 22:37:25,761 INFO L180 IcfgInterpreter]: Interpretation finished [2023-04-02 22:37:26,182 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '9210#(and (<= 1 |#StackHeapBarrier|) (<= 1 ~counter~0) (= |__VERIFIER_assert_#in~cond| 0) (= __VERIFIER_assert_~cond 0) (= |#NULL.offset| 0) (= |#NULL.base| 0))' at error location [2023-04-02 22:37:26,182 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-04-02 22:37:26,182 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-04-02 22:37:26,182 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 14 [2023-04-02 22:37:26,182 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1990225196] [2023-04-02 22:37:26,182 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-04-02 22:37:26,182 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2023-04-02 22:37:26,183 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-04-02 22:37:26,183 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2023-04-02 22:37:26,183 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=137, Invalid=565, Unknown=0, NotChecked=0, Total=702 [2023-04-02 22:37:26,183 INFO L87 Difference]: Start difference. First operand 127 states and 134 transitions. Second operand has 14 states, 14 states have (on average 3.7142857142857144) internal successors, (52), 14 states have internal predecessors, (52), 12 states have call successors, (46), 8 states have call predecessors, (46), 8 states have return successors, (44), 11 states have call predecessors, (44), 10 states have call successors, (44) [2023-04-02 22:37:26,516 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-04-02 22:37:26,516 INFO L93 Difference]: Finished difference Result 369 states and 401 transitions. [2023-04-02 22:37:26,516 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 22 states. [2023-04-02 22:37:26,517 INFO L78 Accepts]: Start accepts. Automaton has has 14 states, 14 states have (on average 3.7142857142857144) internal successors, (52), 14 states have internal predecessors, (52), 12 states have call successors, (46), 8 states have call predecessors, (46), 8 states have return successors, (44), 11 states have call predecessors, (44), 10 states have call successors, (44) Word has length 128 [2023-04-02 22:37:26,517 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-04-02 22:37:26,518 INFO L225 Difference]: With dead ends: 369 [2023-04-02 22:37:26,518 INFO L226 Difference]: Without dead ends: 355 [2023-04-02 22:37:26,520 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 392 GetRequests, 350 SyntacticMatches, 8 SemanticMatches, 34 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 522 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=250, Invalid=1010, Unknown=0, NotChecked=0, Total=1260 [2023-04-02 22:37:26,520 INFO L413 NwaCegarLoop]: 29 mSDtfsCounter, 122 mSDsluCounter, 148 mSDsCounter, 0 mSdLazyCounter, 177 mSolverCounterSat, 32 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 122 SdHoareTripleChecker+Valid, 177 SdHoareTripleChecker+Invalid, 209 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 32 IncrementalHoareTripleChecker+Valid, 177 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2023-04-02 22:37:26,521 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [122 Valid, 177 Invalid, 209 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [32 Valid, 177 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2023-04-02 22:37:26,521 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 355 states. [2023-04-02 22:37:26,599 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 355 to 288. [2023-04-02 22:37:26,600 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 288 states, 173 states have (on average 1.0578034682080926) internal successors, (183), 181 states have internal predecessors, (183), 67 states have call successors, (67), 48 states have call predecessors, (67), 47 states have return successors, (64), 58 states have call predecessors, (64), 64 states have call successors, (64) [2023-04-02 22:37:26,601 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 288 states to 288 states and 314 transitions. [2023-04-02 22:37:26,601 INFO L78 Accepts]: Start accepts. Automaton has 288 states and 314 transitions. Word has length 128 [2023-04-02 22:37:26,601 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-04-02 22:37:26,601 INFO L495 AbstractCegarLoop]: Abstraction has 288 states and 314 transitions. [2023-04-02 22:37:26,601 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 14 states, 14 states have (on average 3.7142857142857144) internal successors, (52), 14 states have internal predecessors, (52), 12 states have call successors, (46), 8 states have call predecessors, (46), 8 states have return successors, (44), 11 states have call predecessors, (44), 10 states have call successors, (44) [2023-04-02 22:37:26,601 INFO L276 IsEmpty]: Start isEmpty. Operand 288 states and 314 transitions. [2023-04-02 22:37:26,602 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 132 [2023-04-02 22:37:26,602 INFO L187 NwaCegarLoop]: Found error trace [2023-04-02 22:37:26,602 INFO L195 NwaCegarLoop]: trace histogram [23, 22, 22, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-04-02 22:37:26,621 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Forceful destruction successful, exit code 0 [2023-04-02 22:37:26,802 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,SelfDestructingSolverStorable14 [2023-04-02 22:37:26,802 INFO L420 AbstractCegarLoop]: === Iteration 16 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-04-02 22:37:26,803 INFO L145 PredicateUnifier]: Initialized classic predicate unifier [2023-04-02 22:37:26,803 INFO L85 PathProgramCache]: Analyzing trace with hash -810345431, now seen corresponding path program 3 times [2023-04-02 22:37:26,803 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-04-02 22:37:26,803 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [997985342] [2023-04-02 22:37:26,803 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-04-02 22:37:26,803 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-04-02 22:37:26,810 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-04-02 22:37:26,810 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1852007475] [2023-04-02 22:37:26,810 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2023-04-02 22:37:26,810 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-04-02 22:37:26,810 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-04-02 22:37:26,813 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-04-02 22:37:26,817 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-04-02 22:37:29,722 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2023-04-02 22:37:29,722 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-04-02 22:37:29,724 INFO L262 TraceCheckSpWp]: Trace formula consists of 236 conjuncts, 51 conjunts are in the unsatisfiable core [2023-04-02 22:37:29,726 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-04-02 22:37:29,934 INFO L134 CoverageAnalysis]: Checked inductivity of 1016 backedges. 143 proven. 188 refuted. 0 times theorem prover too weak. 685 trivial. 0 not checked. [2023-04-02 22:37:29,934 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-04-02 22:37:30,167 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-04-02 22:37:30,167 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [997985342] [2023-04-02 22:37:30,167 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-04-02 22:37:30,167 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1852007475] [2023-04-02 22:37:30,167 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1852007475] provided 0 perfect and 1 imperfect interpolant sequences [2023-04-02 22:37:30,167 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1578334093] [2023-04-02 22:37:30,168 INFO L159 IcfgInterpreter]: Started Sifa with 22 locations of interest [2023-04-02 22:37:30,168 INFO L166 IcfgInterpreter]: Building call graph [2023-04-02 22:37:30,168 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-04-02 22:37:30,169 INFO L176 IcfgInterpreter]: Starting interpretation [2023-04-02 22:37:30,169 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-04-02 22:37:30,180 INFO L197 IcfgInterpreter]: Interpreting procedure main with input of size 13 for LOIs [2023-04-02 22:37:31,162 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 14 for LOIs [2023-04-02 22:37:31,166 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.init with input of size 10 for LOIs [2023-04-02 22:37:31,168 INFO L180 IcfgInterpreter]: Interpretation finished [2023-04-02 22:37:32,083 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '10719#(and (<= 1 |#StackHeapBarrier|) (<= 1 ~counter~0) (= |__VERIFIER_assert_#in~cond| 0) (= __VERIFIER_assert_~cond 0) (= |#NULL.offset| 0) (= |#NULL.base| 0))' at error location [2023-04-02 22:37:32,084 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-04-02 22:37:32,084 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2023-04-02 22:37:32,093 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10] total 10 [2023-04-02 22:37:32,094 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1415193043] [2023-04-02 22:37:32,094 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2023-04-02 22:37:32,095 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2023-04-02 22:37:32,095 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-04-02 22:37:32,095 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2023-04-02 22:37:32,095 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=96, Invalid=716, Unknown=0, NotChecked=0, Total=812 [2023-04-02 22:37:32,096 INFO L87 Difference]: Start difference. First operand 288 states and 314 transitions. Second operand has 10 states, 8 states have (on average 2.5) internal successors, (20), 8 states have internal predecessors, (20), 5 states have call successors, (17), 2 states have call predecessors, (17), 2 states have return successors, (15), 5 states have call predecessors, (15), 5 states have call successors, (15) [2023-04-02 22:37:33,693 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.36s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-04-02 22:37:34,815 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.12s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-04-02 22:37:36,817 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-04-02 22:37:38,768 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-04-02 22:37:38,768 INFO L93 Difference]: Finished difference Result 300 states and 326 transitions. [2023-04-02 22:37:38,769 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2023-04-02 22:37:38,769 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 8 states have (on average 2.5) internal successors, (20), 8 states have internal predecessors, (20), 5 states have call successors, (17), 2 states have call predecessors, (17), 2 states have return successors, (15), 5 states have call predecessors, (15), 5 states have call successors, (15) Word has length 131 [2023-04-02 22:37:38,769 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-04-02 22:37:38,770 INFO L225 Difference]: With dead ends: 300 [2023-04-02 22:37:38,770 INFO L226 Difference]: Without dead ends: 296 [2023-04-02 22:37:38,770 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 308 GetRequests, 266 SyntacticMatches, 12 SemanticMatches, 30 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 404 ImplicationChecksByTransitivity, 1.1s TimeCoverageRelationStatistics Valid=122, Invalid=870, Unknown=0, NotChecked=0, Total=992 [2023-04-02 22:37:38,771 INFO L413 NwaCegarLoop]: 25 mSDtfsCounter, 14 mSDsluCounter, 68 mSDsCounter, 0 mSdLazyCounter, 236 mSolverCounterSat, 11 mSolverCounterUnsat, 1 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 6.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 17 SdHoareTripleChecker+Valid, 93 SdHoareTripleChecker+Invalid, 248 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 11 IncrementalHoareTripleChecker+Valid, 236 IncrementalHoareTripleChecker+Invalid, 1 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 6.5s IncrementalHoareTripleChecker+Time [2023-04-02 22:37:38,771 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [17 Valid, 93 Invalid, 248 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [11 Valid, 236 Invalid, 1 Unknown, 0 Unchecked, 6.5s Time] [2023-04-02 22:37:38,771 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 296 states. [2023-04-02 22:37:38,828 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 296 to 295. [2023-04-02 22:37:38,828 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 295 states, 178 states have (on average 1.050561797752809) internal successors, (187), 185 states have internal predecessors, (187), 68 states have call successors, (68), 50 states have call predecessors, (68), 48 states have return successors, (65), 59 states have call predecessors, (65), 65 states have call successors, (65) [2023-04-02 22:37:38,829 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 295 states to 295 states and 320 transitions. [2023-04-02 22:37:38,830 INFO L78 Accepts]: Start accepts. Automaton has 295 states and 320 transitions. Word has length 131 [2023-04-02 22:37:38,830 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-04-02 22:37:38,830 INFO L495 AbstractCegarLoop]: Abstraction has 295 states and 320 transitions. [2023-04-02 22:37:38,830 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 8 states have (on average 2.5) internal successors, (20), 8 states have internal predecessors, (20), 5 states have call successors, (17), 2 states have call predecessors, (17), 2 states have return successors, (15), 5 states have call predecessors, (15), 5 states have call successors, (15) [2023-04-02 22:37:38,830 INFO L276 IsEmpty]: Start isEmpty. Operand 295 states and 320 transitions. [2023-04-02 22:37:38,831 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 137 [2023-04-02 22:37:38,831 INFO L187 NwaCegarLoop]: Found error trace [2023-04-02 22:37:38,831 INFO L195 NwaCegarLoop]: trace histogram [24, 23, 23, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-04-02 22:37:38,838 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-04-02 22:37:39,038 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,SelfDestructingSolverStorable15 [2023-04-02 22:37:39,038 INFO L420 AbstractCegarLoop]: === Iteration 17 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-04-02 22:37:39,038 INFO L145 PredicateUnifier]: Initialized classic predicate unifier [2023-04-02 22:37:39,038 INFO L85 PathProgramCache]: Analyzing trace with hash 721651399, now seen corresponding path program 1 times [2023-04-02 22:37:39,038 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-04-02 22:37:39,038 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2134985706] [2023-04-02 22:37:39,038 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-04-02 22:37:39,038 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-04-02 22:37:39,044 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-04-02 22:37:39,044 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [734047969] [2023-04-02 22:37:39,044 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-04-02 22:37:39,044 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-04-02 22:37:39,044 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-04-02 22:37:39,050 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-04-02 22:37:39,050 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-04-02 22:37:39,113 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-04-02 22:37:39,115 INFO L262 TraceCheckSpWp]: Trace formula consists of 320 conjuncts, 49 conjunts are in the unsatisfiable core [2023-04-02 22:37:39,118 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-04-02 22:37:39,562 INFO L134 CoverageAnalysis]: Checked inductivity of 1106 backedges. 104 proven. 116 refuted. 0 times theorem prover too weak. 886 trivial. 0 not checked. [2023-04-02 22:37:39,562 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-04-02 22:37:51,889 INFO L134 CoverageAnalysis]: Checked inductivity of 1106 backedges. 104 proven. 116 refuted. 0 times theorem prover too weak. 886 trivial. 0 not checked. [2023-04-02 22:37:51,890 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-04-02 22:37:51,890 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2134985706] [2023-04-02 22:37:51,890 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-04-02 22:37:51,890 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [734047969] [2023-04-02 22:37:51,890 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [734047969] provided 0 perfect and 2 imperfect interpolant sequences [2023-04-02 22:37:51,890 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1316345493] [2023-04-02 22:37:51,891 INFO L159 IcfgInterpreter]: Started Sifa with 23 locations of interest [2023-04-02 22:37:51,891 INFO L166 IcfgInterpreter]: Building call graph [2023-04-02 22:37:51,891 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-04-02 22:37:51,891 INFO L176 IcfgInterpreter]: Starting interpretation [2023-04-02 22:37:51,891 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-04-02 22:37:51,901 INFO L197 IcfgInterpreter]: Interpreting procedure main with input of size 13 for LOIs [2023-04-02 22:37:52,746 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 14 for LOIs [2023-04-02 22:37:52,749 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.init with input of size 10 for LOIs [2023-04-02 22:37:52,752 INFO L180 IcfgInterpreter]: Interpretation finished [2023-04-02 22:37:57,058 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '12424#(and (<= 1 |#StackHeapBarrier|) (<= 1 ~counter~0) (= |__VERIFIER_assert_#in~cond| 0) (= __VERIFIER_assert_~cond 0) (= |#NULL.offset| 0) (= |#NULL.base| 0))' at error location [2023-04-02 22:37:57,059 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-04-02 22:37:57,059 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-04-02 22:37:57,059 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 11] total 19 [2023-04-02 22:37:57,059 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [58570627] [2023-04-02 22:37:57,059 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-04-02 22:37:57,060 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 19 states [2023-04-02 22:37:57,060 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-04-02 22:37:57,062 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 19 interpolants. [2023-04-02 22:37:57,062 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=125, Invalid=864, Unknown=3, NotChecked=0, Total=992 [2023-04-02 22:37:57,062 INFO L87 Difference]: Start difference. First operand 295 states and 320 transitions. Second operand has 19 states, 17 states have (on average 2.3529411764705883) internal successors, (40), 15 states have internal predecessors, (40), 12 states have call successors, (50), 3 states have call predecessors, (50), 2 states have return successors, (47), 11 states have call predecessors, (47), 12 states have call successors, (47) [2023-04-02 22:38:28,047 WARN L223 SmtUtils]: Spent 27.24s on a formula simplification that was a NOOP. DAG size: 98 (called from [L 376] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2023-04-02 22:38:30,458 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-04-02 22:38:34,080 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.01s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-04-02 22:38:42,901 WARN L223 SmtUtils]: Spent 8.12s on a formula simplification that was a NOOP. DAG size: 103 (called from [L 376] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2023-04-02 22:38:45,158 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.10s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-04-02 22:38:46,975 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.69s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-04-02 22:38:53,017 WARN L223 SmtUtils]: Spent 5.69s on a formula simplification that was a NOOP. DAG size: 91 (called from [L 376] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2023-04-02 22:38:53,221 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-04-02 22:38:53,221 INFO L93 Difference]: Finished difference Result 311 states and 339 transitions. [2023-04-02 22:38:53,221 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2023-04-02 22:38:53,221 INFO L78 Accepts]: Start accepts. Automaton has has 19 states, 17 states have (on average 2.3529411764705883) internal successors, (40), 15 states have internal predecessors, (40), 12 states have call successors, (50), 3 states have call predecessors, (50), 2 states have return successors, (47), 11 states have call predecessors, (47), 12 states have call successors, (47) Word has length 136 [2023-04-02 22:38:53,222 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-04-02 22:38:53,222 INFO L225 Difference]: With dead ends: 311 [2023-04-02 22:38:53,223 INFO L226 Difference]: Without dead ends: 295 [2023-04-02 22:38:53,223 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 414 GetRequests, 366 SyntacticMatches, 11 SemanticMatches, 37 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 480 ImplicationChecksByTransitivity, 58.7s TimeCoverageRelationStatistics Valid=205, Invalid=1274, Unknown=3, NotChecked=0, Total=1482 [2023-04-02 22:38:53,223 INFO L413 NwaCegarLoop]: 39 mSDtfsCounter, 28 mSDsluCounter, 126 mSDsCounter, 0 mSdLazyCounter, 544 mSolverCounterSat, 73 mSolverCounterUnsat, 3 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 9.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 30 SdHoareTripleChecker+Valid, 165 SdHoareTripleChecker+Invalid, 620 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 73 IncrementalHoareTripleChecker+Valid, 544 IncrementalHoareTripleChecker+Invalid, 3 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 9.4s IncrementalHoareTripleChecker+Time [2023-04-02 22:38:53,224 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [30 Valid, 165 Invalid, 620 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [73 Valid, 544 Invalid, 3 Unknown, 0 Unchecked, 9.4s Time] [2023-04-02 22:38:53,224 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 295 states. [2023-04-02 22:38:53,299 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 295 to 294. [2023-04-02 22:38:53,299 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 294 states, 181 states have (on average 1.022099447513812) internal successors, (185), 183 states have internal predecessors, (185), 63 states have call successors, (63), 51 states have call predecessors, (63), 49 states have return successors, (60), 59 states have call predecessors, (60), 60 states have call successors, (60) [2023-04-02 22:38:53,300 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 294 states to 294 states and 308 transitions. [2023-04-02 22:38:53,300 INFO L78 Accepts]: Start accepts. Automaton has 294 states and 308 transitions. Word has length 136 [2023-04-02 22:38:53,300 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-04-02 22:38:53,300 INFO L495 AbstractCegarLoop]: Abstraction has 294 states and 308 transitions. [2023-04-02 22:38:53,300 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 19 states, 17 states have (on average 2.3529411764705883) internal successors, (40), 15 states have internal predecessors, (40), 12 states have call successors, (50), 3 states have call predecessors, (50), 2 states have return successors, (47), 11 states have call predecessors, (47), 12 states have call successors, (47) [2023-04-02 22:38:53,300 INFO L276 IsEmpty]: Start isEmpty. Operand 294 states and 308 transitions. [2023-04-02 22:38:53,302 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 277 [2023-04-02 22:38:53,302 INFO L187 NwaCegarLoop]: Found error trace [2023-04-02 22:38:53,302 INFO L195 NwaCegarLoop]: trace histogram [49, 48, 48, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 8, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-04-02 22:38:53,309 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Ended with exit code 0 [2023-04-02 22:38:53,509 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable16,15 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-04-02 22:38:53,509 INFO L420 AbstractCegarLoop]: === Iteration 18 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-04-02 22:38:53,509 INFO L145 PredicateUnifier]: Initialized classic predicate unifier [2023-04-02 22:38:53,510 INFO L85 PathProgramCache]: Analyzing trace with hash 707939092, now seen corresponding path program 2 times [2023-04-02 22:38:53,510 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-04-02 22:38:53,510 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2066466704] [2023-04-02 22:38:53,510 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-04-02 22:38:53,510 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-04-02 22:38:53,518 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-04-02 22:38:53,519 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [622439806] [2023-04-02 22:38:53,519 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2023-04-02 22:38:53,519 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-04-02 22:38:53,519 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-04-02 22:38:53,520 INFO L229 MonitoredProcess]: Starting monitored process 16 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-04-02 22:38:53,522 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Waiting until timeout for monitored process [2023-04-02 22:38:53,732 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2023-04-02 22:38:53,732 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-04-02 22:38:53,734 INFO L262 TraceCheckSpWp]: Trace formula consists of 193 conjuncts, 53 conjunts are in the unsatisfiable core [2023-04-02 22:38:53,737 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-04-02 22:39:35,664 WARN L223 SmtUtils]: Spent 6.15s on a formula simplification that was a NOOP. DAG size: 46 (called from [L 376] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2023-04-02 22:39:35,873 INFO L134 CoverageAnalysis]: Checked inductivity of 4896 backedges. 903 proven. 75 refuted. 0 times theorem prover too weak. 3918 trivial. 0 not checked. [2023-04-02 22:39:35,874 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-04-02 22:39:50,370 WARN L223 SmtUtils]: Spent 8.25s on a formula simplification. DAG size of input: 53 DAG size of output: 52 (called from [L 376] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2023-04-02 22:40:12,710 WARN L861 $PredicateComparison]: unable to prove that (let ((.cse2 (* 2 c_main_~z~0)) (.cse3 (* c_main_~y~0 c_main_~z~0))) (let ((.cse4 (div (+ .cse2 (- 6) (* (- 12) c_main_~y~0) .cse3) 18))) (let ((.cse1 (* 6 c_main_~y~0)) (.cse0 (* c_main_~z~0 c_main_~z~0)) (.cse5 (* .cse4 c_main_~z~0))) (or (not (= (+ 6 (* 6 c_main_~n~0)) c_main_~z~0)) (not (= (+ (* 6 c_main_~z~0) (* 12 c_main_~y~0)) (+ 12 .cse0))) (not (= (* 2 c_main_~y~0) (+ (* c_main_~a~0 c_main_~z~0) 2))) (not (= 0 (mod (+ .cse1 .cse2 12 .cse3) 18))) (not (= (+ .cse1 (* 6 (* .cse4 c_main_~a~0)) (* 6 (* c_main_~y~0 c_main_~a~0)) (* .cse4 6)) (+ .cse5 .cse3))) (= (+ (* 2 .cse0) (* 2 (* c_main_~y~0 c_main_~y~0)) 8 .cse3) (+ (* .cse4 36) (* .cse5 3) (* 46 c_main_~y~0) (* 7 c_main_~z~0))))))) is different from true