./Ultimate.py --spec ../sv-benchmarks/c/properties/unreach-call.prp --file ../sv-benchmarks/c/nla-digbench-scaling/egcd3-ll_valuebound50.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version eb692b52 Calling Ultimate with: /usr/bin/java -Dosgi.configuration.area=/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/config -Xmx15G -Xms4m -jar /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data -tc /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/AutomizerReach.xml -i ../sv-benchmarks/c/nla-digbench-scaling/egcd3-ll_valuebound50.c -s /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf --cacsl2boogietranslator.entry.function main --witnessprinter.witness.directory /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux --witnessprinter.witness.filename witness.graphml --witnessprinter.write.witness.besides.input.file false --witnessprinter.graph.data.specification CHECK( init(main()), LTL(G ! call(reach_error())) ) --witnessprinter.graph.data.producer Automizer --witnessprinter.graph.data.architecture 32bit --witnessprinter.graph.data.programhash 05dbf98a57cbdf117305bcdd9c3dde8d1b2284b890adec5d1f5924f0e5e4bbbb --- Real Ultimate output --- This is Ultimate 0.2.2-?-eb692b5 [2022-07-19 15:52:05,530 INFO L177 SettingsManager]: Resetting all preferences to default values... [2022-07-19 15:52:05,532 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2022-07-19 15:52:05,566 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2022-07-19 15:52:05,566 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2022-07-19 15:52:05,567 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2022-07-19 15:52:05,568 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2022-07-19 15:52:05,570 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2022-07-19 15:52:05,571 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2022-07-19 15:52:05,574 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2022-07-19 15:52:05,575 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2022-07-19 15:52:05,577 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2022-07-19 15:52:05,577 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2022-07-19 15:52:05,578 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2022-07-19 15:52:05,579 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2022-07-19 15:52:05,582 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2022-07-19 15:52:05,582 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2022-07-19 15:52:05,583 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2022-07-19 15:52:05,584 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2022-07-19 15:52:05,588 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2022-07-19 15:52:05,589 INFO L181 SettingsManager]: Resetting HornVerifier preferences to default values [2022-07-19 15:52:05,590 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2022-07-19 15:52:05,590 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2022-07-19 15:52:05,591 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2022-07-19 15:52:05,592 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2022-07-19 15:52:05,597 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2022-07-19 15:52:05,597 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2022-07-19 15:52:05,597 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2022-07-19 15:52:05,598 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2022-07-19 15:52:05,598 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2022-07-19 15:52:05,599 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2022-07-19 15:52:05,599 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2022-07-19 15:52:05,600 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2022-07-19 15:52:05,601 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2022-07-19 15:52:05,601 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2022-07-19 15:52:05,602 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2022-07-19 15:52:05,602 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2022-07-19 15:52:05,602 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2022-07-19 15:52:05,603 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2022-07-19 15:52:05,603 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2022-07-19 15:52:05,603 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2022-07-19 15:52:05,605 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2022-07-19 15:52:05,605 INFO L101 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf [2022-07-19 15:52:05,626 INFO L113 SettingsManager]: Loading preferences was successful [2022-07-19 15:52:05,627 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2022-07-19 15:52:05,627 INFO L136 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2022-07-19 15:52:05,627 INFO L138 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2022-07-19 15:52:05,628 INFO L136 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2022-07-19 15:52:05,628 INFO L138 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2022-07-19 15:52:05,628 INFO L136 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2022-07-19 15:52:05,628 INFO L138 SettingsManager]: * Create parallel compositions if possible=false [2022-07-19 15:52:05,628 INFO L138 SettingsManager]: * Use SBE=true [2022-07-19 15:52:05,629 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2022-07-19 15:52:05,629 INFO L138 SettingsManager]: * sizeof long=4 [2022-07-19 15:52:05,630 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2022-07-19 15:52:05,630 INFO L138 SettingsManager]: * sizeof POINTER=4 [2022-07-19 15:52:05,630 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2022-07-19 15:52:05,630 INFO L138 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2022-07-19 15:52:05,630 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2022-07-19 15:52:05,630 INFO L138 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2022-07-19 15:52:05,630 INFO L138 SettingsManager]: * sizeof long double=12 [2022-07-19 15:52:05,631 INFO L138 SettingsManager]: * Check if freed pointer was valid=false [2022-07-19 15:52:05,631 INFO L138 SettingsManager]: * Use constant arrays=true [2022-07-19 15:52:05,632 INFO L138 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2022-07-19 15:52:05,632 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2022-07-19 15:52:05,632 INFO L138 SettingsManager]: * Size of a code block=SequenceOfStatements [2022-07-19 15:52:05,632 INFO L138 SettingsManager]: * SMT solver=External_DefaultMode [2022-07-19 15:52:05,632 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-07-19 15:52:05,632 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2022-07-19 15:52:05,632 INFO L138 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2022-07-19 15:52:05,633 INFO L138 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2022-07-19 15:52:05,633 INFO L138 SettingsManager]: * Trace refinement strategy=CAMEL [2022-07-19 15:52:05,633 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2022-07-19 15:52:05,633 INFO L138 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2022-07-19 15:52:05,633 INFO L138 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2022-07-19 15:52:05,633 INFO L138 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2022-07-19 15:52:05,634 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.generator.cacsl2boogietranslator: Entry function -> main Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Witness directory -> /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Witness filename -> witness.graphml Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Write witness besides input file -> false Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data specification -> CHECK( init(main()), LTL(G ! call(reach_error())) ) Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data producer -> Automizer Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data architecture -> 32bit Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data programhash -> 05dbf98a57cbdf117305bcdd9c3dde8d1b2284b890adec5d1f5924f0e5e4bbbb [2022-07-19 15:52:05,806 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2022-07-19 15:52:05,818 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2022-07-19 15:52:05,820 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2022-07-19 15:52:05,821 INFO L271 PluginConnector]: Initializing CDTParser... [2022-07-19 15:52:05,821 INFO L275 PluginConnector]: CDTParser initialized [2022-07-19 15:52:05,822 INFO L432 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/nla-digbench-scaling/egcd3-ll_valuebound50.c [2022-07-19 15:52:05,904 INFO L220 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/40ea70531/cf08c5f152fb4861a7851b7d370547d7/FLAG554bc3782 [2022-07-19 15:52:06,228 INFO L306 CDTParser]: Found 1 translation units. [2022-07-19 15:52:06,229 INFO L160 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/egcd3-ll_valuebound50.c [2022-07-19 15:52:06,234 INFO L349 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/40ea70531/cf08c5f152fb4861a7851b7d370547d7/FLAG554bc3782 [2022-07-19 15:52:06,248 INFO L357 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/40ea70531/cf08c5f152fb4861a7851b7d370547d7 [2022-07-19 15:52:06,250 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2022-07-19 15:52:06,251 INFO L131 ToolchainWalker]: Walking toolchain with 6 elements. [2022-07-19 15:52:06,252 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2022-07-19 15:52:06,252 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2022-07-19 15:52:06,254 INFO L275 PluginConnector]: CACSL2BoogieTranslator initialized [2022-07-19 15:52:06,255 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 19.07 03:52:06" (1/1) ... [2022-07-19 15:52:06,255 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@3bf05c05 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.07 03:52:06, skipping insertion in model container [2022-07-19 15:52:06,256 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 19.07 03:52:06" (1/1) ... [2022-07-19 15:52:06,262 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2022-07-19 15:52:06,273 INFO L178 MainTranslator]: Built tables and reachable declarations [2022-07-19 15:52:06,409 WARN L230 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/egcd3-ll_valuebound50.c[490,503] [2022-07-19 15:52:06,435 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-07-19 15:52:06,440 INFO L203 MainTranslator]: Completed pre-run [2022-07-19 15:52:06,448 WARN L230 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/egcd3-ll_valuebound50.c[490,503] [2022-07-19 15:52:06,455 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-07-19 15:52:06,463 INFO L208 MainTranslator]: Completed translation [2022-07-19 15:52:06,464 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.07 03:52:06 WrapperNode [2022-07-19 15:52:06,464 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2022-07-19 15:52:06,465 INFO L113 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2022-07-19 15:52:06,465 INFO L271 PluginConnector]: Initializing Boogie Procedure Inliner... [2022-07-19 15:52:06,465 INFO L275 PluginConnector]: Boogie Procedure Inliner initialized [2022-07-19 15:52:06,470 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.07 03:52:06" (1/1) ... [2022-07-19 15:52:06,474 INFO L185 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.07 03:52:06" (1/1) ... [2022-07-19 15:52:06,486 INFO L137 Inliner]: procedures = 14, calls = 16, calls flagged for inlining = 2, calls inlined = 2, statements flattened = 80 [2022-07-19 15:52:06,486 INFO L132 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2022-07-19 15:52:06,487 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2022-07-19 15:52:06,487 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2022-07-19 15:52:06,487 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2022-07-19 15:52:06,492 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.07 03:52:06" (1/1) ... [2022-07-19 15:52:06,492 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.07 03:52:06" (1/1) ... [2022-07-19 15:52:06,493 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.07 03:52:06" (1/1) ... [2022-07-19 15:52:06,493 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.07 03:52:06" (1/1) ... [2022-07-19 15:52:06,495 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.07 03:52:06" (1/1) ... [2022-07-19 15:52:06,498 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.07 03:52:06" (1/1) ... [2022-07-19 15:52:06,499 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.07 03:52:06" (1/1) ... [2022-07-19 15:52:06,504 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2022-07-19 15:52:06,505 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2022-07-19 15:52:06,505 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2022-07-19 15:52:06,505 INFO L275 PluginConnector]: RCFGBuilder initialized [2022-07-19 15:52:06,506 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.07 03:52:06" (1/1) ... [2022-07-19 15:52:06,511 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-07-19 15:52:06,520 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-19 15:52:06,530 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) [2022-07-19 15:52:06,533 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 [2022-07-19 15:52:06,558 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2022-07-19 15:52:06,558 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2022-07-19 15:52:06,558 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2022-07-19 15:52:06,563 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2022-07-19 15:52:06,564 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2022-07-19 15:52:06,564 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2022-07-19 15:52:06,564 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2022-07-19 15:52:06,564 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2022-07-19 15:52:06,607 INFO L234 CfgBuilder]: Building ICFG [2022-07-19 15:52:06,608 INFO L260 CfgBuilder]: Building CFG for each procedure with an implementation [2022-07-19 15:52:06,705 INFO L275 CfgBuilder]: Performing block encoding [2022-07-19 15:52:06,710 INFO L294 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2022-07-19 15:52:06,710 INFO L299 CfgBuilder]: Removed 3 assume(true) statements. [2022-07-19 15:52:06,711 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 19.07 03:52:06 BoogieIcfgContainer [2022-07-19 15:52:06,711 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2022-07-19 15:52:06,713 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2022-07-19 15:52:06,713 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2022-07-19 15:52:06,716 INFO L275 PluginConnector]: TraceAbstraction initialized [2022-07-19 15:52:06,716 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 19.07 03:52:06" (1/3) ... [2022-07-19 15:52:06,717 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@6ac88714 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 19.07 03:52:06, skipping insertion in model container [2022-07-19 15:52:06,717 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.07 03:52:06" (2/3) ... [2022-07-19 15:52:06,718 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@6ac88714 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 19.07 03:52:06, skipping insertion in model container [2022-07-19 15:52:06,718 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 19.07 03:52:06" (3/3) ... [2022-07-19 15:52:06,732 INFO L111 eAbstractionObserver]: Analyzing ICFG egcd3-ll_valuebound50.c [2022-07-19 15:52:06,741 INFO L201 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2022-07-19 15:52:06,741 INFO L160 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2022-07-19 15:52:06,771 INFO L356 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2022-07-19 15:52:06,776 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=PETRI_NET, 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=de.uni_freiburg.informatik.ultimate.lib.tracecheckerutils.partialorder.independence.IndependenceSettings@2423528b, mLbeIndependenceSettings=de.uni_freiburg.informatik.ultimate.lib.tracecheckerutils.partialorder.independence.IndependenceSettings@7398992f [2022-07-19 15:52:06,776 INFO L358 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2022-07-19 15:52:06,779 INFO L276 IsEmpty]: Start isEmpty. Operand has 35 states, 22 states have (on average 1.5454545454545454) internal successors, (34), 23 states have internal predecessors, (34), 9 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2022-07-19 15:52:06,783 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 30 [2022-07-19 15:52:06,783 INFO L187 NwaCegarLoop]: Found error trace [2022-07-19 15:52:06,784 INFO L195 NwaCegarLoop]: trace histogram [4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-19 15:52:06,784 INFO L420 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-19 15:52:06,787 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-19 15:52:06,787 INFO L85 PathProgramCache]: Analyzing trace with hash 872320404, now seen corresponding path program 1 times [2022-07-19 15:52:06,793 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-19 15:52:06,793 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [943269722] [2022-07-19 15:52:06,793 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-19 15:52:06,794 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-19 15:52:06,853 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-19 15:52:06,878 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2022-07-19 15:52:06,880 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-19 15:52:06,882 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 8 [2022-07-19 15:52:06,884 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-19 15:52:06,885 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 13 [2022-07-19 15:52:06,886 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-19 15:52:06,888 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 18 [2022-07-19 15:52:06,889 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-19 15:52:06,891 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2022-07-19 15:52:06,891 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-19 15:52:06,891 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [943269722] [2022-07-19 15:52:06,892 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [943269722] provided 1 perfect and 0 imperfect interpolant sequences [2022-07-19 15:52:06,892 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-07-19 15:52:06,892 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2022-07-19 15:52:06,893 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1787086824] [2022-07-19 15:52:06,894 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-07-19 15:52:06,896 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2022-07-19 15:52:06,896 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-19 15:52:06,912 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2022-07-19 15:52:06,912 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2022-07-19 15:52:06,914 INFO L87 Difference]: Start difference. First operand has 35 states, 22 states have (on average 1.5454545454545454) internal successors, (34), 23 states have internal predecessors, (34), 9 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) Second operand has 2 states, 2 states have (on average 5.5) internal successors, (11), 2 states have internal predecessors, (11), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 2 states have call successors, (4) [2022-07-19 15:52:06,927 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-19 15:52:06,927 INFO L93 Difference]: Finished difference Result 67 states and 109 transitions. [2022-07-19 15:52:06,927 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2022-07-19 15:52:06,928 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 5.5) internal successors, (11), 2 states have internal predecessors, (11), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 2 states have call successors, (4) Word has length 29 [2022-07-19 15:52:06,928 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-19 15:52:06,932 INFO L225 Difference]: With dead ends: 67 [2022-07-19 15:52:06,933 INFO L226 Difference]: Without dead ends: 31 [2022-07-19 15:52:06,935 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 14 GetRequests, 14 SyntacticMatches, 0 SemanticMatches, 0 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2022-07-19 15:52:06,937 INFO L413 NwaCegarLoop]: 44 mSDtfsCounter, 0 mSDsluCounter, 0 mSDsCounter, 0 mSdLazyCounter, 0 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 44 SdHoareTripleChecker+Invalid, 0 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 0 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-07-19 15:52:06,938 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 44 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 0 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-07-19 15:52:06,948 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 31 states. [2022-07-19 15:52:06,959 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 31 to 31. [2022-07-19 15:52:06,960 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 31 states, 19 states have (on average 1.2105263157894737) internal successors, (23), 20 states have internal predecessors, (23), 9 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2022-07-19 15:52:06,961 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 31 states to 31 states and 40 transitions. [2022-07-19 15:52:06,962 INFO L78 Accepts]: Start accepts. Automaton has 31 states and 40 transitions. Word has length 29 [2022-07-19 15:52:06,962 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-19 15:52:06,962 INFO L495 AbstractCegarLoop]: Abstraction has 31 states and 40 transitions. [2022-07-19 15:52:06,963 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 2 states have (on average 5.5) internal successors, (11), 2 states have internal predecessors, (11), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 2 states have call successors, (4) [2022-07-19 15:52:06,963 INFO L276 IsEmpty]: Start isEmpty. Operand 31 states and 40 transitions. [2022-07-19 15:52:06,966 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 31 [2022-07-19 15:52:06,966 INFO L187 NwaCegarLoop]: Found error trace [2022-07-19 15:52:06,966 INFO L195 NwaCegarLoop]: trace histogram [4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-19 15:52:06,967 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2022-07-19 15:52:06,967 INFO L420 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-19 15:52:06,968 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-19 15:52:06,968 INFO L85 PathProgramCache]: Analyzing trace with hash 1714405113, now seen corresponding path program 1 times [2022-07-19 15:52:06,969 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-19 15:52:06,969 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1151256143] [2022-07-19 15:52:06,969 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-19 15:52:06,969 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-19 15:52:06,986 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-07-19 15:52:06,986 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1231076940] [2022-07-19 15:52:06,987 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-19 15:52:06,987 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-19 15:52:06,987 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-19 15:52:07,006 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) [2022-07-19 15:52:07,015 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2022-07-19 15:52:07,057 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-19 15:52:07,059 INFO L263 TraceCheckSpWp]: Trace formula consists of 91 conjuncts, 7 conjunts are in the unsatisfiable core [2022-07-19 15:52:07,062 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-19 15:52:07,164 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 9 proven. 0 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2022-07-19 15:52:07,164 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-07-19 15:52:07,164 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-19 15:52:07,164 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1151256143] [2022-07-19 15:52:07,165 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-07-19 15:52:07,165 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1231076940] [2022-07-19 15:52:07,165 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1231076940] provided 1 perfect and 0 imperfect interpolant sequences [2022-07-19 15:52:07,165 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-07-19 15:52:07,165 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2022-07-19 15:52:07,166 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1101880476] [2022-07-19 15:52:07,166 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-07-19 15:52:07,167 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2022-07-19 15:52:07,167 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-19 15:52:07,168 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2022-07-19 15:52:07,168 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2022-07-19 15:52:07,169 INFO L87 Difference]: Start difference. First operand 31 states and 40 transitions. Second operand has 6 states, 6 states have (on average 2.5) internal successors, (15), 5 states have internal predecessors, (15), 2 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (4), 2 states have call predecessors, (4), 1 states have call successors, (4) [2022-07-19 15:52:07,285 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-19 15:52:07,286 INFO L93 Difference]: Finished difference Result 50 states and 65 transitions. [2022-07-19 15:52:07,286 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2022-07-19 15:52:07,286 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 2.5) internal successors, (15), 5 states have internal predecessors, (15), 2 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (4), 2 states have call predecessors, (4), 1 states have call successors, (4) Word has length 30 [2022-07-19 15:52:07,287 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-19 15:52:07,287 INFO L225 Difference]: With dead ends: 50 [2022-07-19 15:52:07,287 INFO L226 Difference]: Without dead ends: 43 [2022-07-19 15:52:07,288 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 31 GetRequests, 25 SyntacticMatches, 0 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=17, Invalid=39, Unknown=0, NotChecked=0, Total=56 [2022-07-19 15:52:07,289 INFO L413 NwaCegarLoop]: 34 mSDtfsCounter, 31 mSDsluCounter, 79 mSDsCounter, 0 mSdLazyCounter, 76 mSolverCounterSat, 9 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 35 SdHoareTripleChecker+Valid, 113 SdHoareTripleChecker+Invalid, 85 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 9 IncrementalHoareTripleChecker+Valid, 76 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-07-19 15:52:07,289 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [35 Valid, 113 Invalid, 85 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [9 Valid, 76 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-07-19 15:52:07,290 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 43 states. [2022-07-19 15:52:07,296 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 43 to 33. [2022-07-19 15:52:07,296 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 33 states, 21 states have (on average 1.1904761904761905) internal successors, (25), 22 states have internal predecessors, (25), 9 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2022-07-19 15:52:07,297 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 33 states to 33 states and 42 transitions. [2022-07-19 15:52:07,297 INFO L78 Accepts]: Start accepts. Automaton has 33 states and 42 transitions. Word has length 30 [2022-07-19 15:52:07,297 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-19 15:52:07,298 INFO L495 AbstractCegarLoop]: Abstraction has 33 states and 42 transitions. [2022-07-19 15:52:07,298 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 2.5) internal successors, (15), 5 states have internal predecessors, (15), 2 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (4), 2 states have call predecessors, (4), 1 states have call successors, (4) [2022-07-19 15:52:07,298 INFO L276 IsEmpty]: Start isEmpty. Operand 33 states and 42 transitions. [2022-07-19 15:52:07,299 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 34 [2022-07-19 15:52:07,299 INFO L187 NwaCegarLoop]: Found error trace [2022-07-19 15:52:07,299 INFO L195 NwaCegarLoop]: trace histogram [4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-19 15:52:07,317 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Ended with exit code 0 [2022-07-19 15:52:07,511 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1,2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-19 15:52:07,512 INFO L420 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-19 15:52:07,512 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-19 15:52:07,512 INFO L85 PathProgramCache]: Analyzing trace with hash -1825736765, now seen corresponding path program 1 times [2022-07-19 15:52:07,512 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-19 15:52:07,512 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1265944290] [2022-07-19 15:52:07,513 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-19 15:52:07,513 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-19 15:52:07,526 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-07-19 15:52:07,526 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [92515170] [2022-07-19 15:52:07,526 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-19 15:52:07,527 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-19 15:52:07,527 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-19 15:52:07,528 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) [2022-07-19 15:52:07,529 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2022-07-19 15:52:07,564 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-19 15:52:07,565 INFO L263 TraceCheckSpWp]: Trace formula consists of 101 conjuncts, 9 conjunts are in the unsatisfiable core [2022-07-19 15:52:07,566 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-19 15:52:07,623 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2022-07-19 15:52:07,623 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-07-19 15:52:07,624 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-19 15:52:07,624 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1265944290] [2022-07-19 15:52:07,624 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-07-19 15:52:07,624 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [92515170] [2022-07-19 15:52:07,624 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [92515170] provided 1 perfect and 0 imperfect interpolant sequences [2022-07-19 15:52:07,624 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-07-19 15:52:07,625 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-07-19 15:52:07,625 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1393274122] [2022-07-19 15:52:07,625 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-07-19 15:52:07,625 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-07-19 15:52:07,625 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-19 15:52:07,626 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-07-19 15:52:07,626 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-07-19 15:52:07,626 INFO L87 Difference]: Start difference. First operand 33 states and 42 transitions. Second operand has 5 states, 5 states have (on average 3.0) internal successors, (15), 4 states have internal predecessors, (15), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2022-07-19 15:52:07,659 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-19 15:52:07,660 INFO L93 Difference]: Finished difference Result 49 states and 63 transitions. [2022-07-19 15:52:07,660 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-07-19 15:52:07,660 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.0) internal successors, (15), 4 states have internal predecessors, (15), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) Word has length 33 [2022-07-19 15:52:07,661 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-19 15:52:07,661 INFO L225 Difference]: With dead ends: 49 [2022-07-19 15:52:07,661 INFO L226 Difference]: Without dead ends: 47 [2022-07-19 15:52:07,662 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 33 GetRequests, 29 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2022-07-19 15:52:07,662 INFO L413 NwaCegarLoop]: 39 mSDtfsCounter, 9 mSDsluCounter, 98 mSDsCounter, 0 mSdLazyCounter, 34 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 13 SdHoareTripleChecker+Valid, 137 SdHoareTripleChecker+Invalid, 34 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 34 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-07-19 15:52:07,663 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [13 Valid, 137 Invalid, 34 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 34 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-07-19 15:52:07,663 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 47 states. [2022-07-19 15:52:07,668 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 47 to 46. [2022-07-19 15:52:07,669 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 46 states, 29 states have (on average 1.206896551724138) internal successors, (35), 30 states have internal predecessors, (35), 13 states have call successors, (13), 3 states have call predecessors, (13), 3 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) [2022-07-19 15:52:07,670 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 46 states to 46 states and 60 transitions. [2022-07-19 15:52:07,670 INFO L78 Accepts]: Start accepts. Automaton has 46 states and 60 transitions. Word has length 33 [2022-07-19 15:52:07,670 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-19 15:52:07,670 INFO L495 AbstractCegarLoop]: Abstraction has 46 states and 60 transitions. [2022-07-19 15:52:07,670 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.0) internal successors, (15), 4 states have internal predecessors, (15), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2022-07-19 15:52:07,670 INFO L276 IsEmpty]: Start isEmpty. Operand 46 states and 60 transitions. [2022-07-19 15:52:07,671 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 36 [2022-07-19 15:52:07,671 INFO L187 NwaCegarLoop]: Found error trace [2022-07-19 15:52:07,671 INFO L195 NwaCegarLoop]: trace histogram [4, 4, 4, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-19 15:52:07,689 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Ended with exit code 0 [2022-07-19 15:52:07,875 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 3 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable2 [2022-07-19 15:52:07,876 INFO L420 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-19 15:52:07,876 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-19 15:52:07,876 INFO L85 PathProgramCache]: Analyzing trace with hash -1547103247, now seen corresponding path program 1 times [2022-07-19 15:52:07,877 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-19 15:52:07,877 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1380360597] [2022-07-19 15:52:07,877 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-19 15:52:07,877 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-19 15:52:07,894 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-07-19 15:52:07,895 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [242481495] [2022-07-19 15:52:07,895 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-19 15:52:07,895 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-19 15:52:07,896 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-19 15:52:07,897 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) [2022-07-19 15:52:07,900 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2022-07-19 15:52:07,950 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-19 15:52:07,951 INFO L263 TraceCheckSpWp]: Trace formula consists of 113 conjuncts, 9 conjunts are in the unsatisfiable core [2022-07-19 15:52:07,953 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-19 15:52:08,016 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 6 proven. 5 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2022-07-19 15:52:08,018 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-19 15:52:08,094 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 6 proven. 5 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2022-07-19 15:52:08,095 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-19 15:52:08,095 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1380360597] [2022-07-19 15:52:08,095 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-07-19 15:52:08,095 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [242481495] [2022-07-19 15:52:08,095 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [242481495] provided 0 perfect and 2 imperfect interpolant sequences [2022-07-19 15:52:08,095 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-07-19 15:52:08,096 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 9 [2022-07-19 15:52:08,096 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1879598222] [2022-07-19 15:52:08,096 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-07-19 15:52:08,097 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2022-07-19 15:52:08,097 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-19 15:52:08,097 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2022-07-19 15:52:08,098 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=17, Invalid=55, Unknown=0, NotChecked=0, Total=72 [2022-07-19 15:52:08,098 INFO L87 Difference]: Start difference. First operand 46 states and 60 transitions. Second operand has 9 states, 9 states have (on average 2.4444444444444446) internal successors, (22), 8 states have internal predecessors, (22), 3 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2022-07-19 15:52:08,259 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-19 15:52:08,260 INFO L93 Difference]: Finished difference Result 99 states and 139 transitions. [2022-07-19 15:52:08,260 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2022-07-19 15:52:08,260 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 9 states have (on average 2.4444444444444446) internal successors, (22), 8 states have internal predecessors, (22), 3 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) Word has length 35 [2022-07-19 15:52:08,261 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-19 15:52:08,265 INFO L225 Difference]: With dead ends: 99 [2022-07-19 15:52:08,265 INFO L226 Difference]: Without dead ends: 92 [2022-07-19 15:52:08,266 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 73 GetRequests, 60 SyntacticMatches, 1 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 6 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=47, Invalid=135, Unknown=0, NotChecked=0, Total=182 [2022-07-19 15:52:08,268 INFO L413 NwaCegarLoop]: 48 mSDtfsCounter, 60 mSDsluCounter, 128 mSDsCounter, 0 mSdLazyCounter, 136 mSolverCounterSat, 46 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 64 SdHoareTripleChecker+Valid, 176 SdHoareTripleChecker+Invalid, 182 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 46 IncrementalHoareTripleChecker+Valid, 136 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-07-19 15:52:08,269 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [64 Valid, 176 Invalid, 182 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [46 Valid, 136 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-07-19 15:52:08,269 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 92 states. [2022-07-19 15:52:08,277 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 92 to 67. [2022-07-19 15:52:08,279 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 67 states, 46 states have (on average 1.2608695652173914) internal successors, (58), 47 states have internal predecessors, (58), 17 states have call successors, (17), 3 states have call predecessors, (17), 3 states have return successors, (16), 16 states have call predecessors, (16), 16 states have call successors, (16) [2022-07-19 15:52:08,283 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 67 states to 67 states and 91 transitions. [2022-07-19 15:52:08,285 INFO L78 Accepts]: Start accepts. Automaton has 67 states and 91 transitions. Word has length 35 [2022-07-19 15:52:08,286 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-19 15:52:08,286 INFO L495 AbstractCegarLoop]: Abstraction has 67 states and 91 transitions. [2022-07-19 15:52:08,286 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 9 states have (on average 2.4444444444444446) internal successors, (22), 8 states have internal predecessors, (22), 3 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2022-07-19 15:52:08,286 INFO L276 IsEmpty]: Start isEmpty. Operand 67 states and 91 transitions. [2022-07-19 15:52:08,287 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 39 [2022-07-19 15:52:08,287 INFO L187 NwaCegarLoop]: Found error trace [2022-07-19 15:52:08,287 INFO L195 NwaCegarLoop]: trace histogram [4, 4, 4, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-19 15:52:08,304 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Forceful destruction successful, exit code 0 [2022-07-19 15:52:08,490 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-19 15:52:08,491 INFO L420 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-19 15:52:08,491 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-19 15:52:08,491 INFO L85 PathProgramCache]: Analyzing trace with hash -720434099, now seen corresponding path program 1 times [2022-07-19 15:52:08,491 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-19 15:52:08,492 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [680517598] [2022-07-19 15:52:08,492 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-19 15:52:08,492 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-19 15:52:08,526 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-07-19 15:52:08,531 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [760518619] [2022-07-19 15:52:08,531 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-19 15:52:08,531 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-19 15:52:08,531 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-19 15:52:08,532 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) [2022-07-19 15:52:08,539 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2022-07-19 15:52:08,580 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-19 15:52:08,581 INFO L263 TraceCheckSpWp]: Trace formula consists of 110 conjuncts, 9 conjunts are in the unsatisfiable core [2022-07-19 15:52:08,582 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-19 15:52:08,625 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2022-07-19 15:52:08,625 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-07-19 15:52:08,625 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-19 15:52:08,625 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [680517598] [2022-07-19 15:52:08,625 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-07-19 15:52:08,626 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [760518619] [2022-07-19 15:52:08,626 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [760518619] provided 1 perfect and 0 imperfect interpolant sequences [2022-07-19 15:52:08,626 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-07-19 15:52:08,626 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-07-19 15:52:08,626 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1998433460] [2022-07-19 15:52:08,626 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-07-19 15:52:08,627 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-07-19 15:52:08,627 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-19 15:52:08,627 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-07-19 15:52:08,627 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-07-19 15:52:08,627 INFO L87 Difference]: Start difference. First operand 67 states and 91 transitions. Second operand has 5 states, 5 states have (on average 3.6) internal successors, (18), 4 states have internal predecessors, (18), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2022-07-19 15:52:08,660 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-19 15:52:08,661 INFO L93 Difference]: Finished difference Result 75 states and 98 transitions. [2022-07-19 15:52:08,661 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-07-19 15:52:08,661 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.6) internal successors, (18), 4 states have internal predecessors, (18), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) Word has length 38 [2022-07-19 15:52:08,663 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-19 15:52:08,663 INFO L225 Difference]: With dead ends: 75 [2022-07-19 15:52:08,664 INFO L226 Difference]: Without dead ends: 73 [2022-07-19 15:52:08,664 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 38 GetRequests, 34 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2022-07-19 15:52:08,664 INFO L413 NwaCegarLoop]: 40 mSDtfsCounter, 9 mSDsluCounter, 91 mSDsCounter, 0 mSdLazyCounter, 46 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 12 SdHoareTripleChecker+Valid, 131 SdHoareTripleChecker+Invalid, 46 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 46 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-07-19 15:52:08,665 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [12 Valid, 131 Invalid, 46 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 46 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-07-19 15:52:08,668 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 73 states. [2022-07-19 15:52:08,680 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 73 to 71. [2022-07-19 15:52:08,683 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 71 states, 49 states have (on average 1.2448979591836735) internal successors, (61), 50 states have internal predecessors, (61), 17 states have call successors, (17), 4 states have call predecessors, (17), 4 states have return successors, (16), 16 states have call predecessors, (16), 16 states have call successors, (16) [2022-07-19 15:52:08,686 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 71 states to 71 states and 94 transitions. [2022-07-19 15:52:08,686 INFO L78 Accepts]: Start accepts. Automaton has 71 states and 94 transitions. Word has length 38 [2022-07-19 15:52:08,687 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-19 15:52:08,687 INFO L495 AbstractCegarLoop]: Abstraction has 71 states and 94 transitions. [2022-07-19 15:52:08,687 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.6) internal successors, (18), 4 states have internal predecessors, (18), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2022-07-19 15:52:08,687 INFO L276 IsEmpty]: Start isEmpty. Operand 71 states and 94 transitions. [2022-07-19 15:52:08,690 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 39 [2022-07-19 15:52:08,692 INFO L187 NwaCegarLoop]: Found error trace [2022-07-19 15:52:08,692 INFO L195 NwaCegarLoop]: trace histogram [4, 4, 4, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-19 15:52:08,710 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Forceful destruction successful, exit code 0 [2022-07-19 15:52:08,899 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-19 15:52:08,900 INFO L420 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-19 15:52:08,900 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-19 15:52:08,900 INFO L85 PathProgramCache]: Analyzing trace with hash -376152117, now seen corresponding path program 1 times [2022-07-19 15:52:08,900 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-19 15:52:08,900 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1529624399] [2022-07-19 15:52:08,900 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-19 15:52:08,900 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-19 15:52:08,913 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-07-19 15:52:08,913 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1558309675] [2022-07-19 15:52:08,914 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-19 15:52:08,914 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-19 15:52:08,914 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-19 15:52:08,915 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) [2022-07-19 15:52:08,916 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2022-07-19 15:52:08,946 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-19 15:52:08,947 INFO L263 TraceCheckSpWp]: Trace formula consists of 123 conjuncts, 19 conjunts are in the unsatisfiable core [2022-07-19 15:52:08,948 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-19 15:52:09,035 INFO L134 CoverageAnalysis]: Checked inductivity of 28 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2022-07-19 15:52:09,036 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-19 15:52:09,213 INFO L134 CoverageAnalysis]: Checked inductivity of 28 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2022-07-19 15:52:09,214 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-19 15:52:09,214 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1529624399] [2022-07-19 15:52:09,214 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-07-19 15:52:09,214 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1558309675] [2022-07-19 15:52:09,214 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1558309675] provided 0 perfect and 2 imperfect interpolant sequences [2022-07-19 15:52:09,214 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-07-19 15:52:09,214 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 8 [2022-07-19 15:52:09,215 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1428213777] [2022-07-19 15:52:09,215 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-07-19 15:52:09,215 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2022-07-19 15:52:09,215 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-19 15:52:09,216 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2022-07-19 15:52:09,216 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=15, Invalid=41, Unknown=0, NotChecked=0, Total=56 [2022-07-19 15:52:09,216 INFO L87 Difference]: Start difference. First operand 71 states and 94 transitions. Second operand has 8 states, 8 states have (on average 3.875) internal successors, (31), 7 states have internal predecessors, (31), 3 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2022-07-19 15:52:09,263 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-19 15:52:09,263 INFO L93 Difference]: Finished difference Result 95 states and 125 transitions. [2022-07-19 15:52:09,263 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2022-07-19 15:52:09,264 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 8 states have (on average 3.875) internal successors, (31), 7 states have internal predecessors, (31), 3 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) Word has length 38 [2022-07-19 15:52:09,264 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-19 15:52:09,265 INFO L225 Difference]: With dead ends: 95 [2022-07-19 15:52:09,265 INFO L226 Difference]: Without dead ends: 93 [2022-07-19 15:52:09,266 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 75 GetRequests, 67 SyntacticMatches, 1 SemanticMatches, 7 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=19, Invalid=53, Unknown=0, NotChecked=0, Total=72 [2022-07-19 15:52:09,266 INFO L413 NwaCegarLoop]: 53 mSDtfsCounter, 13 mSDsluCounter, 176 mSDsCounter, 0 mSdLazyCounter, 58 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 17 SdHoareTripleChecker+Valid, 229 SdHoareTripleChecker+Invalid, 111 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 58 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 53 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-07-19 15:52:09,266 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [17 Valid, 229 Invalid, 111 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 58 Invalid, 0 Unknown, 53 Unchecked, 0.0s Time] [2022-07-19 15:52:09,267 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 93 states. [2022-07-19 15:52:09,278 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 93 to 89. [2022-07-19 15:52:09,278 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 89 states, 62 states have (on average 1.2419354838709677) internal successors, (77), 63 states have internal predecessors, (77), 21 states have call successors, (21), 5 states have call predecessors, (21), 5 states have return successors, (20), 20 states have call predecessors, (20), 20 states have call successors, (20) [2022-07-19 15:52:09,279 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 89 states to 89 states and 118 transitions. [2022-07-19 15:52:09,279 INFO L78 Accepts]: Start accepts. Automaton has 89 states and 118 transitions. Word has length 38 [2022-07-19 15:52:09,279 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-19 15:52:09,279 INFO L495 AbstractCegarLoop]: Abstraction has 89 states and 118 transitions. [2022-07-19 15:52:09,279 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 8 states have (on average 3.875) internal successors, (31), 7 states have internal predecessors, (31), 3 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2022-07-19 15:52:09,279 INFO L276 IsEmpty]: Start isEmpty. Operand 89 states and 118 transitions. [2022-07-19 15:52:09,280 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 44 [2022-07-19 15:52:09,280 INFO L187 NwaCegarLoop]: Found error trace [2022-07-19 15:52:09,280 INFO L195 NwaCegarLoop]: trace histogram [4, 4, 4, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-19 15:52:09,298 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Ended with exit code 0 [2022-07-19 15:52:09,495 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-19 15:52:09,496 INFO L420 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-19 15:52:09,499 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-19 15:52:09,499 INFO L85 PathProgramCache]: Analyzing trace with hash 279172547, now seen corresponding path program 1 times [2022-07-19 15:52:09,499 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-19 15:52:09,500 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [652256562] [2022-07-19 15:52:09,500 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-19 15:52:09,500 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-19 15:52:09,509 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-07-19 15:52:09,509 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [303382656] [2022-07-19 15:52:09,509 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-19 15:52:09,509 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-19 15:52:09,510 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-19 15:52:09,511 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) [2022-07-19 15:52:09,512 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2022-07-19 15:52:09,547 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-19 15:52:09,547 INFO L263 TraceCheckSpWp]: Trace formula consists of 119 conjuncts, 7 conjunts are in the unsatisfiable core [2022-07-19 15:52:09,549 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-19 15:52:09,578 INFO L134 CoverageAnalysis]: Checked inductivity of 32 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2022-07-19 15:52:09,578 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-07-19 15:52:09,578 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-19 15:52:09,579 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [652256562] [2022-07-19 15:52:09,579 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-07-19 15:52:09,579 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [303382656] [2022-07-19 15:52:09,579 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [303382656] provided 1 perfect and 0 imperfect interpolant sequences [2022-07-19 15:52:09,579 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-07-19 15:52:09,579 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-07-19 15:52:09,580 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [980014323] [2022-07-19 15:52:09,580 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-07-19 15:52:09,580 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-07-19 15:52:09,580 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-19 15:52:09,581 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-07-19 15:52:09,581 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-07-19 15:52:09,581 INFO L87 Difference]: Start difference. First operand 89 states and 118 transitions. Second operand has 5 states, 5 states have (on average 3.6) internal successors, (18), 4 states have internal predecessors, (18), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) [2022-07-19 15:52:09,623 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-19 15:52:09,623 INFO L93 Difference]: Finished difference Result 126 states and 175 transitions. [2022-07-19 15:52:09,623 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-07-19 15:52:09,624 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.6) internal successors, (18), 4 states have internal predecessors, (18), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) Word has length 43 [2022-07-19 15:52:09,624 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-19 15:52:09,625 INFO L225 Difference]: With dead ends: 126 [2022-07-19 15:52:09,625 INFO L226 Difference]: Without dead ends: 124 [2022-07-19 15:52:09,626 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 43 GetRequests, 39 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2022-07-19 15:52:09,626 INFO L413 NwaCegarLoop]: 38 mSDtfsCounter, 8 mSDsluCounter, 92 mSDsCounter, 0 mSdLazyCounter, 47 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 10 SdHoareTripleChecker+Valid, 130 SdHoareTripleChecker+Invalid, 47 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 47 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-07-19 15:52:09,627 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [10 Valid, 130 Invalid, 47 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 47 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-07-19 15:52:09,628 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 124 states. [2022-07-19 15:52:09,649 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 124 to 119. [2022-07-19 15:52:09,649 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 119 states, 75 states have (on average 1.2666666666666666) internal successors, (95), 76 states have internal predecessors, (95), 37 states have call successors, (37), 6 states have call predecessors, (37), 6 states have return successors, (36), 36 states have call predecessors, (36), 36 states have call successors, (36) [2022-07-19 15:52:09,652 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 119 states to 119 states and 168 transitions. [2022-07-19 15:52:09,652 INFO L78 Accepts]: Start accepts. Automaton has 119 states and 168 transitions. Word has length 43 [2022-07-19 15:52:09,653 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-19 15:52:09,653 INFO L495 AbstractCegarLoop]: Abstraction has 119 states and 168 transitions. [2022-07-19 15:52:09,653 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.6) internal successors, (18), 4 states have internal predecessors, (18), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) [2022-07-19 15:52:09,653 INFO L276 IsEmpty]: Start isEmpty. Operand 119 states and 168 transitions. [2022-07-19 15:52:09,655 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 44 [2022-07-19 15:52:09,655 INFO L187 NwaCegarLoop]: Found error trace [2022-07-19 15:52:09,655 INFO L195 NwaCegarLoop]: trace histogram [4, 4, 4, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-19 15:52:09,689 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Forceful destruction successful, exit code 0 [2022-07-19 15:52:09,867 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-19 15:52:09,868 INFO L420 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-19 15:52:09,868 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-19 15:52:09,868 INFO L85 PathProgramCache]: Analyzing trace with hash -2141198011, now seen corresponding path program 1 times [2022-07-19 15:52:09,868 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-19 15:52:09,868 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [292882864] [2022-07-19 15:52:09,869 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-19 15:52:09,869 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-19 15:52:09,876 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-07-19 15:52:09,876 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1686688947] [2022-07-19 15:52:09,876 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-19 15:52:09,876 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-19 15:52:09,877 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-19 15:52:09,884 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) [2022-07-19 15:52:09,885 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2022-07-19 15:52:09,917 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-19 15:52:09,918 INFO L263 TraceCheckSpWp]: Trace formula consists of 132 conjuncts, 25 conjunts are in the unsatisfiable core [2022-07-19 15:52:09,919 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-19 15:52:10,025 INFO L134 CoverageAnalysis]: Checked inductivity of 30 backedges. 2 proven. 4 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2022-07-19 15:52:10,026 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-19 15:52:10,050 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-19 15:52:10,050 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [292882864] [2022-07-19 15:52:10,050 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-07-19 15:52:10,050 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1686688947] [2022-07-19 15:52:10,050 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1686688947] provided 0 perfect and 1 imperfect interpolant sequences [2022-07-19 15:52:10,051 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-07-19 15:52:10,051 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7] total 7 [2022-07-19 15:52:10,051 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1067463009] [2022-07-19 15:52:10,051 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2022-07-19 15:52:10,051 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2022-07-19 15:52:10,051 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-19 15:52:10,052 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2022-07-19 15:52:10,052 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=14, Invalid=42, Unknown=0, NotChecked=0, Total=56 [2022-07-19 15:52:10,052 INFO L87 Difference]: Start difference. First operand 119 states and 168 transitions. Second operand has 7 states, 7 states have (on average 3.2857142857142856) internal successors, (23), 6 states have internal predecessors, (23), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2022-07-19 15:52:10,165 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-19 15:52:10,166 INFO L93 Difference]: Finished difference Result 133 states and 180 transitions. [2022-07-19 15:52:10,166 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2022-07-19 15:52:10,166 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 7 states have (on average 3.2857142857142856) internal successors, (23), 6 states have internal predecessors, (23), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) Word has length 43 [2022-07-19 15:52:10,166 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-19 15:52:10,167 INFO L225 Difference]: With dead ends: 133 [2022-07-19 15:52:10,167 INFO L226 Difference]: Without dead ends: 131 [2022-07-19 15:52:10,168 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 49 GetRequests, 40 SyntacticMatches, 1 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=22, Invalid=68, Unknown=0, NotChecked=0, Total=90 [2022-07-19 15:52:10,168 INFO L413 NwaCegarLoop]: 49 mSDtfsCounter, 27 mSDsluCounter, 155 mSDsCounter, 0 mSdLazyCounter, 154 mSolverCounterSat, 12 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 34 SdHoareTripleChecker+Valid, 204 SdHoareTripleChecker+Invalid, 166 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 12 IncrementalHoareTripleChecker+Valid, 154 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-07-19 15:52:10,168 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [34 Valid, 204 Invalid, 166 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [12 Valid, 154 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-07-19 15:52:10,169 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 131 states. [2022-07-19 15:52:10,177 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 131 to 127. [2022-07-19 15:52:10,177 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 127 states, 81 states have (on average 1.2469135802469136) internal successors, (101), 82 states have internal predecessors, (101), 37 states have call successors, (37), 8 states have call predecessors, (37), 8 states have return successors, (36), 36 states have call predecessors, (36), 36 states have call successors, (36) [2022-07-19 15:52:10,184 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 127 states to 127 states and 174 transitions. [2022-07-19 15:52:10,184 INFO L78 Accepts]: Start accepts. Automaton has 127 states and 174 transitions. Word has length 43 [2022-07-19 15:52:10,184 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-19 15:52:10,184 INFO L495 AbstractCegarLoop]: Abstraction has 127 states and 174 transitions. [2022-07-19 15:52:10,184 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 7 states have (on average 3.2857142857142856) internal successors, (23), 6 states have internal predecessors, (23), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2022-07-19 15:52:10,185 INFO L276 IsEmpty]: Start isEmpty. Operand 127 states and 174 transitions. [2022-07-19 15:52:10,185 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 44 [2022-07-19 15:52:10,185 INFO L187 NwaCegarLoop]: Found error trace [2022-07-19 15:52:10,185 INFO L195 NwaCegarLoop]: trace histogram [4, 4, 4, 3, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-19 15:52:10,213 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Forceful destruction successful, exit code 0 [2022-07-19 15:52:10,402 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-19 15:52:10,402 INFO L420 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-19 15:52:10,402 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-19 15:52:10,403 INFO L85 PathProgramCache]: Analyzing trace with hash -1796916029, now seen corresponding path program 2 times [2022-07-19 15:52:10,403 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-19 15:52:10,403 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [784134774] [2022-07-19 15:52:10,403 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-19 15:52:10,403 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-19 15:52:10,411 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-07-19 15:52:10,411 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1200278028] [2022-07-19 15:52:10,411 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-07-19 15:52:10,411 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-19 15:52:10,411 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-19 15:52:10,412 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) [2022-07-19 15:52:10,413 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2022-07-19 15:52:10,452 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-07-19 15:52:10,453 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-07-19 15:52:10,453 INFO L263 TraceCheckSpWp]: Trace formula consists of 145 conjuncts, 5 conjunts are in the unsatisfiable core [2022-07-19 15:52:10,454 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-19 15:52:10,477 INFO L134 CoverageAnalysis]: Checked inductivity of 37 backedges. 13 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2022-07-19 15:52:10,477 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-07-19 15:52:10,477 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-19 15:52:10,477 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [784134774] [2022-07-19 15:52:10,477 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-07-19 15:52:10,477 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1200278028] [2022-07-19 15:52:10,477 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1200278028] provided 1 perfect and 0 imperfect interpolant sequences [2022-07-19 15:52:10,478 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-07-19 15:52:10,478 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-07-19 15:52:10,478 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1061561935] [2022-07-19 15:52:10,478 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-07-19 15:52:10,478 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-07-19 15:52:10,478 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-19 15:52:10,478 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-07-19 15:52:10,478 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-07-19 15:52:10,478 INFO L87 Difference]: Start difference. First operand 127 states and 174 transitions. Second operand has 5 states, 5 states have (on average 5.0) internal successors, (25), 5 states have internal predecessors, (25), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2022-07-19 15:52:10,548 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-19 15:52:10,548 INFO L93 Difference]: Finished difference Result 166 states and 226 transitions. [2022-07-19 15:52:10,548 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2022-07-19 15:52:10,549 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 5.0) internal successors, (25), 5 states have internal predecessors, (25), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) Word has length 43 [2022-07-19 15:52:10,550 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-19 15:52:10,551 INFO L225 Difference]: With dead ends: 166 [2022-07-19 15:52:10,551 INFO L226 Difference]: Without dead ends: 110 [2022-07-19 15:52:10,553 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 45 GetRequests, 40 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=15, Invalid=27, Unknown=0, NotChecked=0, Total=42 [2022-07-19 15:52:10,554 INFO L413 NwaCegarLoop]: 53 mSDtfsCounter, 18 mSDsluCounter, 86 mSDsCounter, 0 mSdLazyCounter, 82 mSolverCounterSat, 9 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 22 SdHoareTripleChecker+Valid, 139 SdHoareTripleChecker+Invalid, 91 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 9 IncrementalHoareTripleChecker+Valid, 82 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-07-19 15:52:10,554 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [22 Valid, 139 Invalid, 91 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [9 Valid, 82 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-07-19 15:52:10,555 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 110 states. [2022-07-19 15:52:10,563 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 110 to 102. [2022-07-19 15:52:10,564 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 102 states, 64 states have (on average 1.1875) internal successors, (76), 65 states have internal predecessors, (76), 29 states have call successors, (29), 8 states have call predecessors, (29), 8 states have return successors, (28), 28 states have call predecessors, (28), 28 states have call successors, (28) [2022-07-19 15:52:10,564 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 102 states to 102 states and 133 transitions. [2022-07-19 15:52:10,565 INFO L78 Accepts]: Start accepts. Automaton has 102 states and 133 transitions. Word has length 43 [2022-07-19 15:52:10,565 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-19 15:52:10,565 INFO L495 AbstractCegarLoop]: Abstraction has 102 states and 133 transitions. [2022-07-19 15:52:10,565 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 5.0) internal successors, (25), 5 states have internal predecessors, (25), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2022-07-19 15:52:10,565 INFO L276 IsEmpty]: Start isEmpty. Operand 102 states and 133 transitions. [2022-07-19 15:52:10,565 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 49 [2022-07-19 15:52:10,565 INFO L187 NwaCegarLoop]: Found error trace [2022-07-19 15:52:10,566 INFO L195 NwaCegarLoop]: trace histogram [4, 4, 4, 4, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-19 15:52:10,581 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Ended with exit code 0 [2022-07-19 15:52:10,781 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,SelfDestructingSolverStorable8 [2022-07-19 15:52:10,782 INFO L420 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-19 15:52:10,782 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-19 15:52:10,782 INFO L85 PathProgramCache]: Analyzing trace with hash -1189241395, now seen corresponding path program 1 times [2022-07-19 15:52:10,782 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-19 15:52:10,782 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [477448663] [2022-07-19 15:52:10,782 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-19 15:52:10,782 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-19 15:52:10,789 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-07-19 15:52:10,789 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [609189784] [2022-07-19 15:52:10,790 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-19 15:52:10,790 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-19 15:52:10,790 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-19 15:52:10,804 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) [2022-07-19 15:52:10,805 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Waiting until timeout for monitored process [2022-07-19 15:52:10,834 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-19 15:52:10,835 INFO L263 TraceCheckSpWp]: Trace formula consists of 128 conjuncts, 7 conjunts are in the unsatisfiable core [2022-07-19 15:52:10,838 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-19 15:52:10,862 INFO L134 CoverageAnalysis]: Checked inductivity of 42 backedges. 6 proven. 0 refuted. 0 times theorem prover too weak. 36 trivial. 0 not checked. [2022-07-19 15:52:10,863 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-07-19 15:52:10,863 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-19 15:52:10,863 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [477448663] [2022-07-19 15:52:10,863 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-07-19 15:52:10,863 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [609189784] [2022-07-19 15:52:10,863 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [609189784] provided 1 perfect and 0 imperfect interpolant sequences [2022-07-19 15:52:10,863 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-07-19 15:52:10,863 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-07-19 15:52:10,863 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [995267809] [2022-07-19 15:52:10,863 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-07-19 15:52:10,864 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-07-19 15:52:10,864 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-19 15:52:10,865 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-07-19 15:52:10,865 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-07-19 15:52:10,865 INFO L87 Difference]: Start difference. First operand 102 states and 133 transitions. Second operand has 5 states, 5 states have (on average 3.6) internal successors, (18), 4 states have internal predecessors, (18), 2 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2022-07-19 15:52:10,913 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-19 15:52:10,913 INFO L93 Difference]: Finished difference Result 154 states and 217 transitions. [2022-07-19 15:52:10,913 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-07-19 15:52:10,914 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.6) internal successors, (18), 4 states have internal predecessors, (18), 2 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) Word has length 48 [2022-07-19 15:52:10,914 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-19 15:52:10,915 INFO L225 Difference]: With dead ends: 154 [2022-07-19 15:52:10,915 INFO L226 Difference]: Without dead ends: 152 [2022-07-19 15:52:10,915 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 48 GetRequests, 44 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2022-07-19 15:52:10,915 INFO L413 NwaCegarLoop]: 42 mSDtfsCounter, 9 mSDsluCounter, 98 mSDsCounter, 0 mSdLazyCounter, 50 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 10 SdHoareTripleChecker+Valid, 140 SdHoareTripleChecker+Invalid, 50 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 50 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-07-19 15:52:10,916 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [10 Valid, 140 Invalid, 50 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 50 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-07-19 15:52:10,916 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 152 states. [2022-07-19 15:52:10,926 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 152 to 136. [2022-07-19 15:52:10,926 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 136 states, 73 states have (on average 1.1643835616438356) internal successors, (85), 80 states have internal predecessors, (85), 53 states have call successors, (53), 9 states have call predecessors, (53), 9 states have return successors, (52), 46 states have call predecessors, (52), 52 states have call successors, (52) [2022-07-19 15:52:10,927 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 136 states to 136 states and 190 transitions. [2022-07-19 15:52:10,927 INFO L78 Accepts]: Start accepts. Automaton has 136 states and 190 transitions. Word has length 48 [2022-07-19 15:52:10,927 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-19 15:52:10,927 INFO L495 AbstractCegarLoop]: Abstraction has 136 states and 190 transitions. [2022-07-19 15:52:10,928 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.6) internal successors, (18), 4 states have internal predecessors, (18), 2 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2022-07-19 15:52:10,928 INFO L276 IsEmpty]: Start isEmpty. Operand 136 states and 190 transitions. [2022-07-19 15:52:10,928 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 61 [2022-07-19 15:52:10,928 INFO L187 NwaCegarLoop]: Found error trace [2022-07-19 15:52:10,928 INFO L195 NwaCegarLoop]: trace histogram [5, 4, 4, 4, 4, 4, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-19 15:52:10,945 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Ended with exit code 0 [2022-07-19 15:52:11,139 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 10 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable9 [2022-07-19 15:52:11,141 INFO L420 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-19 15:52:11,141 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-19 15:52:11,142 INFO L85 PathProgramCache]: Analyzing trace with hash -828341661, now seen corresponding path program 1 times [2022-07-19 15:52:11,142 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-19 15:52:11,142 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1465133465] [2022-07-19 15:52:11,142 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-19 15:52:11,143 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-19 15:52:11,169 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-07-19 15:52:11,169 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1025309643] [2022-07-19 15:52:11,169 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-19 15:52:11,169 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-19 15:52:11,169 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-19 15:52:11,170 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) [2022-07-19 15:52:11,171 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Waiting until timeout for monitored process [2022-07-19 15:52:11,201 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-19 15:52:11,216 INFO L263 TraceCheckSpWp]: Trace formula consists of 161 conjuncts, 53 conjunts are in the unsatisfiable core [2022-07-19 15:52:11,218 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-19 15:52:11,575 INFO L134 CoverageAnalysis]: Checked inductivity of 60 backedges. 6 proven. 18 refuted. 0 times theorem prover too weak. 36 trivial. 0 not checked. [2022-07-19 15:52:11,575 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-19 15:52:14,208 WARN L855 $PredicateComparison]: unable to prove that (or (not (= (+ |c_ULTIMATE.start_main_~c~0#1| (* (- 1) |c_ULTIMATE.start_main_~v~0#1|)) 0)) (let ((.cse11 (+ |c_ULTIMATE.start_main_~d~0#1| |c_ULTIMATE.start_main_~k~0#1|))) (let ((.cse8 (= |c_ULTIMATE.start_main_~p~0#1| 0)) (.cse4 (+ (* (- 1) .cse11 |c_ULTIMATE.start_main_~q~0#1|) |c_ULTIMATE.start_main_~p~0#1|)) (.cse6 (* |c_ULTIMATE.start_main_~y~0#1| (+ |c_ULTIMATE.start_main_~r~0#1| (* (* |c_ULTIMATE.start_main_~s~0#1| .cse11) (- 1))))) (.cse7 (* |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~s~0#1|)) (.cse0 (+ |c_ULTIMATE.start_main_~a~0#1| (* (- 1) |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~r~0#1|)))) (and (or (not (= .cse0 0)) (let ((.cse3 (= 0 |c_ULTIMATE.start_main_~q~0#1|)) (.cse1 (+ |c_ULTIMATE.start_main_~b~0#1| (* (- 1) |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~s~0#1|)))) (and (or (not (= .cse1 0)) (forall ((|ULTIMATE.start_main_~x~0#1| Int)) (= (+ (* |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~s~0#1|) (* |ULTIMATE.start_main_~x~0#1| |c_ULTIMATE.start_main_~q~0#1|)) (let ((.cse2 (+ |c_ULTIMATE.start_main_~d~0#1| |c_ULTIMATE.start_main_~k~0#1|))) (+ (* (+ (* (- 1) .cse2 |c_ULTIMATE.start_main_~q~0#1|) |c_ULTIMATE.start_main_~p~0#1|) |ULTIMATE.start_main_~x~0#1|) |c_ULTIMATE.start_main_~b~0#1| (* |c_ULTIMATE.start_main_~y~0#1| (+ |c_ULTIMATE.start_main_~r~0#1| (* (* |c_ULTIMATE.start_main_~s~0#1| .cse2) (- 1)))))))) (not .cse3)) (or .cse3 (not (= (mod .cse1 |c_ULTIMATE.start_main_~q~0#1|) 0)) (let ((.cse5 (div .cse1 |c_ULTIMATE.start_main_~q~0#1|))) (= (+ (* .cse4 .cse5) |c_ULTIMATE.start_main_~b~0#1| .cse6) (+ .cse7 (* .cse5 |c_ULTIMATE.start_main_~q~0#1|))))))) (not .cse8)) (let ((.cse10 (div .cse0 |c_ULTIMATE.start_main_~p~0#1|))) (let ((.cse9 (+ .cse7 (* .cse10 |c_ULTIMATE.start_main_~q~0#1|)))) (or (not (= .cse9 |c_ULTIMATE.start_main_~b~0#1|)) .cse8 (not (= (mod .cse0 |c_ULTIMATE.start_main_~p~0#1|) 0)) (= .cse9 (+ (* .cse4 .cse10) |c_ULTIMATE.start_main_~b~0#1| .cse6))))))))) is different from true [2022-07-19 15:52:14,209 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-19 15:52:14,210 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1465133465] [2022-07-19 15:52:14,210 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-07-19 15:52:14,210 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1025309643] [2022-07-19 15:52:14,210 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1025309643] provided 0 perfect and 1 imperfect interpolant sequences [2022-07-19 15:52:14,210 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-07-19 15:52:14,210 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13] total 13 [2022-07-19 15:52:14,210 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1442865553] [2022-07-19 15:52:14,210 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2022-07-19 15:52:14,210 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 13 states [2022-07-19 15:52:14,210 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-19 15:52:14,211 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2022-07-19 15:52:14,211 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=55, Invalid=290, Unknown=1, NotChecked=34, Total=380 [2022-07-19 15:52:14,211 INFO L87 Difference]: Start difference. First operand 136 states and 190 transitions. Second operand has 13 states, 12 states have (on average 2.3333333333333335) internal successors, (28), 12 states have internal predecessors, (28), 4 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (8), 2 states have call predecessors, (8), 3 states have call successors, (8) [2022-07-19 15:52:14,684 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-19 15:52:14,684 INFO L93 Difference]: Finished difference Result 196 states and 279 transitions. [2022-07-19 15:52:14,685 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2022-07-19 15:52:14,685 INFO L78 Accepts]: Start accepts. Automaton has has 13 states, 12 states have (on average 2.3333333333333335) internal successors, (28), 12 states have internal predecessors, (28), 4 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (8), 2 states have call predecessors, (8), 3 states have call successors, (8) Word has length 60 [2022-07-19 15:52:14,686 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-19 15:52:14,687 INFO L225 Difference]: With dead ends: 196 [2022-07-19 15:52:14,687 INFO L226 Difference]: Without dead ends: 193 [2022-07-19 15:52:14,688 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 90 GetRequests, 66 SyntacticMatches, 2 SemanticMatches, 22 ConstructedPredicates, 1 IntricatePredicates, 0 DeprecatedPredicates, 92 ImplicationChecksByTransitivity, 2.3s TimeCoverageRelationStatistics Valid=84, Invalid=425, Unknown=1, NotChecked=42, Total=552 [2022-07-19 15:52:14,688 INFO L413 NwaCegarLoop]: 43 mSDtfsCounter, 46 mSDsluCounter, 181 mSDsCounter, 0 mSdLazyCounter, 487 mSolverCounterSat, 34 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 63 SdHoareTripleChecker+Valid, 224 SdHoareTripleChecker+Invalid, 521 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 34 IncrementalHoareTripleChecker+Valid, 487 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2022-07-19 15:52:14,688 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [63 Valid, 224 Invalid, 521 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [34 Valid, 487 Invalid, 0 Unknown, 0 Unchecked, 0.4s Time] [2022-07-19 15:52:14,689 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 193 states. [2022-07-19 15:52:14,705 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 193 to 178. [2022-07-19 15:52:14,706 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 178 states, 97 states have (on average 1.175257731958763) internal successors, (114), 105 states have internal predecessors, (114), 69 states have call successors, (69), 11 states have call predecessors, (69), 11 states have return successors, (68), 61 states have call predecessors, (68), 68 states have call successors, (68) [2022-07-19 15:52:14,707 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 178 states to 178 states and 251 transitions. [2022-07-19 15:52:14,707 INFO L78 Accepts]: Start accepts. Automaton has 178 states and 251 transitions. Word has length 60 [2022-07-19 15:52:14,708 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-19 15:52:14,708 INFO L495 AbstractCegarLoop]: Abstraction has 178 states and 251 transitions. [2022-07-19 15:52:14,708 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 13 states, 12 states have (on average 2.3333333333333335) internal successors, (28), 12 states have internal predecessors, (28), 4 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (8), 2 states have call predecessors, (8), 3 states have call successors, (8) [2022-07-19 15:52:14,708 INFO L276 IsEmpty]: Start isEmpty. Operand 178 states and 251 transitions. [2022-07-19 15:52:14,708 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 66 [2022-07-19 15:52:14,709 INFO L187 NwaCegarLoop]: Found error trace [2022-07-19 15:52:14,709 INFO L195 NwaCegarLoop]: trace histogram [5, 4, 4, 4, 4, 4, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-19 15:52:14,727 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Ended with exit code 0 [2022-07-19 15:52:14,925 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,SelfDestructingSolverStorable10 [2022-07-19 15:52:14,925 INFO L420 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-19 15:52:14,925 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-19 15:52:14,925 INFO L85 PathProgramCache]: Analyzing trace with hash -1649355429, now seen corresponding path program 2 times [2022-07-19 15:52:14,926 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-19 15:52:14,926 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1527465168] [2022-07-19 15:52:14,926 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-19 15:52:14,926 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-19 15:52:14,934 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-07-19 15:52:14,935 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [453896340] [2022-07-19 15:52:14,935 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-07-19 15:52:14,935 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-19 15:52:14,935 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-19 15:52:14,936 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) [2022-07-19 15:52:14,937 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Waiting until timeout for monitored process [2022-07-19 15:52:14,994 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-07-19 15:52:14,994 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-07-19 15:52:14,995 INFO L263 TraceCheckSpWp]: Trace formula consists of 183 conjuncts, 8 conjunts are in the unsatisfiable core [2022-07-19 15:52:14,996 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-19 15:52:15,034 INFO L134 CoverageAnalysis]: Checked inductivity of 69 backedges. 16 proven. 5 refuted. 0 times theorem prover too weak. 48 trivial. 0 not checked. [2022-07-19 15:52:15,035 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-19 15:52:15,084 INFO L134 CoverageAnalysis]: Checked inductivity of 69 backedges. 16 proven. 5 refuted. 0 times theorem prover too weak. 48 trivial. 0 not checked. [2022-07-19 15:52:15,084 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-19 15:52:15,084 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1527465168] [2022-07-19 15:52:15,084 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-07-19 15:52:15,085 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [453896340] [2022-07-19 15:52:15,085 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [453896340] provided 0 perfect and 2 imperfect interpolant sequences [2022-07-19 15:52:15,085 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-07-19 15:52:15,085 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 8 [2022-07-19 15:52:15,085 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1607672647] [2022-07-19 15:52:15,085 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-07-19 15:52:15,085 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2022-07-19 15:52:15,086 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-19 15:52:15,086 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2022-07-19 15:52:15,086 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=43, Unknown=0, NotChecked=0, Total=56 [2022-07-19 15:52:15,086 INFO L87 Difference]: Start difference. First operand 178 states and 251 transitions. Second operand has 8 states, 8 states have (on average 3.75) internal successors, (30), 8 states have internal predecessors, (30), 3 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (8), 2 states have call predecessors, (8), 2 states have call successors, (8) [2022-07-19 15:52:15,426 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-19 15:52:15,427 INFO L93 Difference]: Finished difference Result 273 states and 400 transitions. [2022-07-19 15:52:15,427 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2022-07-19 15:52:15,427 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 8 states have (on average 3.75) internal successors, (30), 8 states have internal predecessors, (30), 3 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (8), 2 states have call predecessors, (8), 2 states have call successors, (8) Word has length 65 [2022-07-19 15:52:15,428 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-19 15:52:15,430 INFO L225 Difference]: With dead ends: 273 [2022-07-19 15:52:15,431 INFO L226 Difference]: Without dead ends: 266 [2022-07-19 15:52:15,431 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 144 GetRequests, 125 SyntacticMatches, 2 SemanticMatches, 17 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 42 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=93, Invalid=249, Unknown=0, NotChecked=0, Total=342 [2022-07-19 15:52:15,431 INFO L413 NwaCegarLoop]: 83 mSDtfsCounter, 48 mSDsluCounter, 205 mSDsCounter, 0 mSdLazyCounter, 280 mSolverCounterSat, 84 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 52 SdHoareTripleChecker+Valid, 288 SdHoareTripleChecker+Invalid, 364 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 84 IncrementalHoareTripleChecker+Valid, 280 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2022-07-19 15:52:15,432 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [52 Valid, 288 Invalid, 364 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [84 Valid, 280 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2022-07-19 15:52:15,432 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 266 states. [2022-07-19 15:52:15,452 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 266 to 193. [2022-07-19 15:52:15,452 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 193 states, 112 states have (on average 1.2053571428571428) internal successors, (135), 117 states have internal predecessors, (135), 69 states have call successors, (69), 11 states have call predecessors, (69), 11 states have return successors, (68), 64 states have call predecessors, (68), 68 states have call successors, (68) [2022-07-19 15:52:15,453 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 193 states to 193 states and 272 transitions. [2022-07-19 15:52:15,454 INFO L78 Accepts]: Start accepts. Automaton has 193 states and 272 transitions. Word has length 65 [2022-07-19 15:52:15,454 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-19 15:52:15,454 INFO L495 AbstractCegarLoop]: Abstraction has 193 states and 272 transitions. [2022-07-19 15:52:15,454 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 8 states have (on average 3.75) internal successors, (30), 8 states have internal predecessors, (30), 3 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (8), 2 states have call predecessors, (8), 2 states have call successors, (8) [2022-07-19 15:52:15,454 INFO L276 IsEmpty]: Start isEmpty. Operand 193 states and 272 transitions. [2022-07-19 15:52:15,455 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 69 [2022-07-19 15:52:15,455 INFO L187 NwaCegarLoop]: Found error trace [2022-07-19 15:52:15,455 INFO L195 NwaCegarLoop]: trace histogram [7, 6, 6, 4, 4, 4, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-19 15:52:15,473 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Forceful destruction successful, exit code 0 [2022-07-19 15:52:15,671 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,SelfDestructingSolverStorable11 [2022-07-19 15:52:15,672 INFO L420 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-19 15:52:15,672 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-19 15:52:15,672 INFO L85 PathProgramCache]: Analyzing trace with hash -492391883, now seen corresponding path program 1 times [2022-07-19 15:52:15,672 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-19 15:52:15,672 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1333332244] [2022-07-19 15:52:15,672 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-19 15:52:15,672 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-19 15:52:15,680 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-07-19 15:52:15,684 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1045145681] [2022-07-19 15:52:15,684 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-19 15:52:15,684 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-19 15:52:15,684 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-19 15:52:15,691 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) [2022-07-19 15:52:15,692 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Waiting until timeout for monitored process [2022-07-19 15:52:15,737 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-19 15:52:15,738 INFO L263 TraceCheckSpWp]: Trace formula consists of 167 conjuncts, 4 conjunts are in the unsatisfiable core [2022-07-19 15:52:15,739 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-19 15:52:15,763 INFO L134 CoverageAnalysis]: Checked inductivity of 102 backedges. 46 proven. 0 refuted. 0 times theorem prover too weak. 56 trivial. 0 not checked. [2022-07-19 15:52:15,764 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-07-19 15:52:15,764 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-19 15:52:15,764 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1333332244] [2022-07-19 15:52:15,764 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-07-19 15:52:15,764 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1045145681] [2022-07-19 15:52:15,764 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1045145681] provided 1 perfect and 0 imperfect interpolant sequences [2022-07-19 15:52:15,764 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-07-19 15:52:15,764 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-07-19 15:52:15,765 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [641478311] [2022-07-19 15:52:15,765 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-07-19 15:52:15,765 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-07-19 15:52:15,765 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-19 15:52:15,765 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-07-19 15:52:15,765 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2022-07-19 15:52:15,766 INFO L87 Difference]: Start difference. First operand 193 states and 272 transitions. Second operand has 5 states, 5 states have (on average 5.0) internal successors, (25), 5 states have internal predecessors, (25), 3 states have call successors, (11), 2 states have call predecessors, (11), 2 states have return successors, (10), 3 states have call predecessors, (10), 3 states have call successors, (10) [2022-07-19 15:52:15,818 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-19 15:52:15,819 INFO L93 Difference]: Finished difference Result 324 states and 455 transitions. [2022-07-19 15:52:15,819 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2022-07-19 15:52:15,819 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 5.0) internal successors, (25), 5 states have internal predecessors, (25), 3 states have call successors, (11), 2 states have call predecessors, (11), 2 states have return successors, (10), 3 states have call predecessors, (10), 3 states have call successors, (10) Word has length 68 [2022-07-19 15:52:15,819 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-19 15:52:15,820 INFO L225 Difference]: With dead ends: 324 [2022-07-19 15:52:15,820 INFO L226 Difference]: Without dead ends: 210 [2022-07-19 15:52:15,821 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 69 GetRequests, 65 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=12, Invalid=18, Unknown=0, NotChecked=0, Total=30 [2022-07-19 15:52:15,821 INFO L413 NwaCegarLoop]: 41 mSDtfsCounter, 3 mSDsluCounter, 82 mSDsCounter, 0 mSdLazyCounter, 55 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 3 SdHoareTripleChecker+Valid, 123 SdHoareTripleChecker+Invalid, 57 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 55 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-07-19 15:52:15,821 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [3 Valid, 123 Invalid, 57 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 55 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-07-19 15:52:15,822 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 210 states. [2022-07-19 15:52:15,835 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 210 to 194. [2022-07-19 15:52:15,836 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 194 states, 113 states have (on average 1.2035398230088497) internal successors, (136), 114 states have internal predecessors, (136), 69 states have call successors, (69), 11 states have call predecessors, (69), 11 states have return successors, (68), 68 states have call predecessors, (68), 68 states have call successors, (68) [2022-07-19 15:52:15,837 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 194 states to 194 states and 273 transitions. [2022-07-19 15:52:15,837 INFO L78 Accepts]: Start accepts. Automaton has 194 states and 273 transitions. Word has length 68 [2022-07-19 15:52:15,837 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-19 15:52:15,837 INFO L495 AbstractCegarLoop]: Abstraction has 194 states and 273 transitions. [2022-07-19 15:52:15,837 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 5.0) internal successors, (25), 5 states have internal predecessors, (25), 3 states have call successors, (11), 2 states have call predecessors, (11), 2 states have return successors, (10), 3 states have call predecessors, (10), 3 states have call successors, (10) [2022-07-19 15:52:15,837 INFO L276 IsEmpty]: Start isEmpty. Operand 194 states and 273 transitions. [2022-07-19 15:52:15,838 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 71 [2022-07-19 15:52:15,838 INFO L187 NwaCegarLoop]: Found error trace [2022-07-19 15:52:15,838 INFO L195 NwaCegarLoop]: trace histogram [8, 7, 7, 4, 4, 4, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-19 15:52:15,857 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Forceful destruction successful, exit code 0 [2022-07-19 15:52:16,054 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,SelfDestructingSolverStorable12 [2022-07-19 15:52:16,055 INFO L420 AbstractCegarLoop]: === Iteration 14 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-19 15:52:16,055 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-19 15:52:16,055 INFO L85 PathProgramCache]: Analyzing trace with hash 1607561902, now seen corresponding path program 1 times [2022-07-19 15:52:16,055 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-19 15:52:16,056 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [734882051] [2022-07-19 15:52:16,056 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-19 15:52:16,056 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-19 15:52:16,064 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-07-19 15:52:16,064 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [247784295] [2022-07-19 15:52:16,064 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-19 15:52:16,065 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-19 15:52:16,065 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-19 15:52:16,080 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) [2022-07-19 15:52:16,083 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Waiting until timeout for monitored process [2022-07-19 15:52:16,132 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-19 15:52:16,133 INFO L263 TraceCheckSpWp]: Trace formula consists of 170 conjuncts, 18 conjunts are in the unsatisfiable core [2022-07-19 15:52:16,134 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-19 15:52:16,225 INFO L134 CoverageAnalysis]: Checked inductivity of 127 backedges. 23 proven. 5 refuted. 0 times theorem prover too weak. 99 trivial. 0 not checked. [2022-07-19 15:52:16,225 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-19 15:52:16,300 INFO L134 CoverageAnalysis]: Checked inductivity of 127 backedges. 14 proven. 0 refuted. 0 times theorem prover too weak. 113 trivial. 0 not checked. [2022-07-19 15:52:16,301 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-19 15:52:16,301 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [734882051] [2022-07-19 15:52:16,301 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-07-19 15:52:16,301 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [247784295] [2022-07-19 15:52:16,301 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [247784295] provided 1 perfect and 1 imperfect interpolant sequences [2022-07-19 15:52:16,301 INFO L184 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2022-07-19 15:52:16,301 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [10] total 11 [2022-07-19 15:52:16,303 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [303998771] [2022-07-19 15:52:16,303 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-07-19 15:52:16,303 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-07-19 15:52:16,303 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-19 15:52:16,303 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-07-19 15:52:16,304 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=23, Invalid=87, Unknown=0, NotChecked=0, Total=110 [2022-07-19 15:52:16,304 INFO L87 Difference]: Start difference. First operand 194 states and 273 transitions. Second operand has 5 states, 5 states have (on average 3.8) internal successors, (19), 4 states have internal predecessors, (19), 2 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (8), 2 states have call predecessors, (8), 2 states have call successors, (8) [2022-07-19 15:52:16,347 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-19 15:52:16,347 INFO L93 Difference]: Finished difference Result 200 states and 278 transitions. [2022-07-19 15:52:16,348 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-07-19 15:52:16,348 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.8) internal successors, (19), 4 states have internal predecessors, (19), 2 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (8), 2 states have call predecessors, (8), 2 states have call successors, (8) Word has length 70 [2022-07-19 15:52:16,348 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-19 15:52:16,350 INFO L225 Difference]: With dead ends: 200 [2022-07-19 15:52:16,350 INFO L226 Difference]: Without dead ends: 198 [2022-07-19 15:52:16,351 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 139 GetRequests, 127 SyntacticMatches, 2 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 12 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=27, Invalid=105, Unknown=0, NotChecked=0, Total=132 [2022-07-19 15:52:16,351 INFO L413 NwaCegarLoop]: 38 mSDtfsCounter, 9 mSDsluCounter, 85 mSDsCounter, 0 mSdLazyCounter, 46 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 9 SdHoareTripleChecker+Valid, 123 SdHoareTripleChecker+Invalid, 46 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 46 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-07-19 15:52:16,351 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [9 Valid, 123 Invalid, 46 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 46 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-07-19 15:52:16,352 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 198 states. [2022-07-19 15:52:16,373 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 198 to 198. [2022-07-19 15:52:16,374 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 198 states, 116 states have (on average 1.1982758620689655) internal successors, (139), 117 states have internal predecessors, (139), 69 states have call successors, (69), 12 states have call predecessors, (69), 12 states have return successors, (68), 68 states have call predecessors, (68), 68 states have call successors, (68) [2022-07-19 15:52:16,375 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 198 states to 198 states and 276 transitions. [2022-07-19 15:52:16,375 INFO L78 Accepts]: Start accepts. Automaton has 198 states and 276 transitions. Word has length 70 [2022-07-19 15:52:16,375 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-19 15:52:16,375 INFO L495 AbstractCegarLoop]: Abstraction has 198 states and 276 transitions. [2022-07-19 15:52:16,375 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.8) internal successors, (19), 4 states have internal predecessors, (19), 2 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (8), 2 states have call predecessors, (8), 2 states have call successors, (8) [2022-07-19 15:52:16,375 INFO L276 IsEmpty]: Start isEmpty. Operand 198 states and 276 transitions. [2022-07-19 15:52:16,376 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 69 [2022-07-19 15:52:16,376 INFO L187 NwaCegarLoop]: Found error trace [2022-07-19 15:52:16,376 INFO L195 NwaCegarLoop]: trace histogram [5, 4, 4, 4, 4, 4, 4, 3, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-19 15:52:16,394 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Ended with exit code 0 [2022-07-19 15:52:16,589 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,SelfDestructingSolverStorable13 [2022-07-19 15:52:16,589 INFO L420 AbstractCegarLoop]: === Iteration 15 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-19 15:52:16,589 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-19 15:52:16,589 INFO L85 PathProgramCache]: Analyzing trace with hash -1439093215, now seen corresponding path program 1 times [2022-07-19 15:52:16,589 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-19 15:52:16,589 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [573972407] [2022-07-19 15:52:16,589 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-19 15:52:16,590 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-19 15:52:16,597 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-07-19 15:52:16,597 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [37911606] [2022-07-19 15:52:16,597 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-19 15:52:16,598 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-19 15:52:16,598 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-19 15:52:16,603 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) [2022-07-19 15:52:16,604 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Waiting until timeout for monitored process [2022-07-19 15:52:16,640 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-19 15:52:16,641 INFO L263 TraceCheckSpWp]: Trace formula consists of 193 conjuncts, 47 conjunts are in the unsatisfiable core [2022-07-19 15:52:16,642 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-19 15:52:16,859 INFO L134 CoverageAnalysis]: Checked inductivity of 77 backedges. 15 proven. 24 refuted. 0 times theorem prover too weak. 38 trivial. 0 not checked. [2022-07-19 15:52:16,860 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-19 15:52:17,015 INFO L134 CoverageAnalysis]: Checked inductivity of 77 backedges. 30 proven. 7 refuted. 0 times theorem prover too weak. 40 trivial. 0 not checked. [2022-07-19 15:52:17,015 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-19 15:52:17,015 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [573972407] [2022-07-19 15:52:17,015 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-07-19 15:52:17,015 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [37911606] [2022-07-19 15:52:17,015 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [37911606] provided 0 perfect and 2 imperfect interpolant sequences [2022-07-19 15:52:17,016 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-07-19 15:52:17,016 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 9] total 15 [2022-07-19 15:52:17,016 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1596897977] [2022-07-19 15:52:17,016 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-07-19 15:52:17,016 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 15 states [2022-07-19 15:52:17,016 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-19 15:52:17,017 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2022-07-19 15:52:17,017 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=40, Invalid=170, Unknown=0, NotChecked=0, Total=210 [2022-07-19 15:52:17,017 INFO L87 Difference]: Start difference. First operand 198 states and 276 transitions. Second operand has 15 states, 14 states have (on average 3.9285714285714284) internal successors, (55), 13 states have internal predecessors, (55), 5 states have call successors, (14), 2 states have call predecessors, (14), 2 states have return successors, (12), 5 states have call predecessors, (12), 3 states have call successors, (12) [2022-07-19 15:52:17,660 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-19 15:52:17,660 INFO L93 Difference]: Finished difference Result 268 states and 365 transitions. [2022-07-19 15:52:17,660 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2022-07-19 15:52:17,661 INFO L78 Accepts]: Start accepts. Automaton has has 15 states, 14 states have (on average 3.9285714285714284) internal successors, (55), 13 states have internal predecessors, (55), 5 states have call successors, (14), 2 states have call predecessors, (14), 2 states have return successors, (12), 5 states have call predecessors, (12), 3 states have call successors, (12) Word has length 68 [2022-07-19 15:52:17,661 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-19 15:52:17,662 INFO L225 Difference]: With dead ends: 268 [2022-07-19 15:52:17,662 INFO L226 Difference]: Without dead ends: 266 [2022-07-19 15:52:17,663 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 148 GetRequests, 124 SyntacticMatches, 3 SemanticMatches, 21 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 71 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=101, Invalid=405, Unknown=0, NotChecked=0, Total=506 [2022-07-19 15:52:17,663 INFO L413 NwaCegarLoop]: 36 mSDtfsCounter, 100 mSDsluCounter, 150 mSDsCounter, 0 mSdLazyCounter, 403 mSolverCounterSat, 130 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 104 SdHoareTripleChecker+Valid, 186 SdHoareTripleChecker+Invalid, 533 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 130 IncrementalHoareTripleChecker+Valid, 403 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.5s IncrementalHoareTripleChecker+Time [2022-07-19 15:52:17,663 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [104 Valid, 186 Invalid, 533 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [130 Valid, 403 Invalid, 0 Unknown, 0 Unchecked, 0.5s Time] [2022-07-19 15:52:17,664 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 266 states. [2022-07-19 15:52:17,680 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 266 to 210. [2022-07-19 15:52:17,681 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 210 states, 125 states have (on average 1.184) internal successors, (148), 126 states have internal predecessors, (148), 69 states have call successors, (69), 15 states have call predecessors, (69), 15 states have return successors, (68), 68 states have call predecessors, (68), 68 states have call successors, (68) [2022-07-19 15:52:17,681 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 210 states to 210 states and 285 transitions. [2022-07-19 15:52:17,681 INFO L78 Accepts]: Start accepts. Automaton has 210 states and 285 transitions. Word has length 68 [2022-07-19 15:52:17,682 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-19 15:52:17,682 INFO L495 AbstractCegarLoop]: Abstraction has 210 states and 285 transitions. [2022-07-19 15:52:17,682 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 15 states, 14 states have (on average 3.9285714285714284) internal successors, (55), 13 states have internal predecessors, (55), 5 states have call successors, (14), 2 states have call predecessors, (14), 2 states have return successors, (12), 5 states have call predecessors, (12), 3 states have call successors, (12) [2022-07-19 15:52:17,682 INFO L276 IsEmpty]: Start isEmpty. Operand 210 states and 285 transitions. [2022-07-19 15:52:17,683 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 74 [2022-07-19 15:52:17,683 INFO L187 NwaCegarLoop]: Found error trace [2022-07-19 15:52:17,683 INFO L195 NwaCegarLoop]: trace histogram [6, 5, 5, 4, 4, 4, 4, 3, 3, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-19 15:52:17,711 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Ended with exit code 0 [2022-07-19 15:52:17,899 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable14,15 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-19 15:52:17,899 INFO L420 AbstractCegarLoop]: === Iteration 16 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-19 15:52:17,899 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-19 15:52:17,900 INFO L85 PathProgramCache]: Analyzing trace with hash -1622368081, now seen corresponding path program 2 times [2022-07-19 15:52:17,900 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-19 15:52:17,900 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [349319103] [2022-07-19 15:52:17,900 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-19 15:52:17,900 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-19 15:52:17,907 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-07-19 15:52:17,923 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [573732546] [2022-07-19 15:52:17,923 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-07-19 15:52:17,923 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-19 15:52:17,923 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-19 15:52:17,925 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) [2022-07-19 15:52:17,926 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Waiting until timeout for monitored process [2022-07-19 15:52:17,978 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-07-19 15:52:17,978 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-07-19 15:52:17,979 INFO L263 TraceCheckSpWp]: Trace formula consists of 202 conjuncts, 65 conjunts are in the unsatisfiable core [2022-07-19 15:52:17,981 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-19 15:52:18,476 INFO L134 CoverageAnalysis]: Checked inductivity of 96 backedges. 8 proven. 42 refuted. 0 times theorem prover too weak. 46 trivial. 0 not checked. [2022-07-19 15:52:18,476 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-19 15:52:19,717 INFO L134 CoverageAnalysis]: Checked inductivity of 96 backedges. 21 proven. 27 refuted. 0 times theorem prover too weak. 48 trivial. 0 not checked. [2022-07-19 15:52:19,717 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-19 15:52:19,718 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [349319103] [2022-07-19 15:52:19,718 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-07-19 15:52:19,718 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [573732546] [2022-07-19 15:52:19,718 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [573732546] provided 0 perfect and 2 imperfect interpolant sequences [2022-07-19 15:52:19,718 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-07-19 15:52:19,718 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [17, 13] total 25 [2022-07-19 15:52:19,718 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1638778682] [2022-07-19 15:52:19,718 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-07-19 15:52:19,718 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 25 states [2022-07-19 15:52:19,718 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-19 15:52:19,719 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 25 interpolants. [2022-07-19 15:52:19,719 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=106, Invalid=494, Unknown=0, NotChecked=0, Total=600 [2022-07-19 15:52:19,719 INFO L87 Difference]: Start difference. First operand 210 states and 285 transitions. Second operand has 25 states, 23 states have (on average 2.5217391304347827) internal successors, (58), 20 states have internal predecessors, (58), 9 states have call successors, (16), 2 states have call predecessors, (16), 2 states have return successors, (14), 7 states have call predecessors, (14), 9 states have call successors, (14) [2022-07-19 15:52:29,172 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-07-19 15:52:35,452 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-07-19 15:52:39,165 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-19 15:52:39,165 INFO L93 Difference]: Finished difference Result 297 states and 390 transitions. [2022-07-19 15:52:39,166 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 33 states. [2022-07-19 15:52:39,166 INFO L78 Accepts]: Start accepts. Automaton has has 25 states, 23 states have (on average 2.5217391304347827) internal successors, (58), 20 states have internal predecessors, (58), 9 states have call successors, (16), 2 states have call predecessors, (16), 2 states have return successors, (14), 7 states have call predecessors, (14), 9 states have call successors, (14) Word has length 73 [2022-07-19 15:52:39,166 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-19 15:52:39,167 INFO L225 Difference]: With dead ends: 297 [2022-07-19 15:52:39,167 INFO L226 Difference]: Without dead ends: 295 [2022-07-19 15:52:39,168 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 173 GetRequests, 127 SyntacticMatches, 1 SemanticMatches, 45 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 454 ImplicationChecksByTransitivity, 7.9s TimeCoverageRelationStatistics Valid=390, Invalid=1772, Unknown=0, NotChecked=0, Total=2162 [2022-07-19 15:52:39,168 INFO L413 NwaCegarLoop]: 44 mSDtfsCounter, 128 mSDsluCounter, 265 mSDsCounter, 0 mSdLazyCounter, 1012 mSolverCounterSat, 293 mSolverCounterUnsat, 2 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 12.6s Time, 0 mProtectedPredicate, 0 mProtectedAction, 136 SdHoareTripleChecker+Valid, 309 SdHoareTripleChecker+Invalid, 1307 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 293 IncrementalHoareTripleChecker+Valid, 1012 IncrementalHoareTripleChecker+Invalid, 2 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 12.7s IncrementalHoareTripleChecker+Time [2022-07-19 15:52:39,174 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [136 Valid, 309 Invalid, 1307 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [293 Valid, 1012 Invalid, 2 Unknown, 0 Unchecked, 12.7s Time] [2022-07-19 15:52:39,175 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 295 states. [2022-07-19 15:52:39,216 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 295 to 245. [2022-07-19 15:52:39,217 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 245 states, 152 states have (on average 1.1578947368421053) internal successors, (176), 154 states have internal predecessors, (176), 71 states have call successors, (71), 21 states have call predecessors, (71), 21 states have return successors, (70), 69 states have call predecessors, (70), 70 states have call successors, (70) [2022-07-19 15:52:39,218 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 245 states to 245 states and 317 transitions. [2022-07-19 15:52:39,218 INFO L78 Accepts]: Start accepts. Automaton has 245 states and 317 transitions. Word has length 73 [2022-07-19 15:52:39,218 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-19 15:52:39,218 INFO L495 AbstractCegarLoop]: Abstraction has 245 states and 317 transitions. [2022-07-19 15:52:39,218 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 25 states, 23 states have (on average 2.5217391304347827) internal successors, (58), 20 states have internal predecessors, (58), 9 states have call successors, (16), 2 states have call predecessors, (16), 2 states have return successors, (14), 7 states have call predecessors, (14), 9 states have call successors, (14) [2022-07-19 15:52:39,219 INFO L276 IsEmpty]: Start isEmpty. Operand 245 states and 317 transitions. [2022-07-19 15:52:39,219 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 83 [2022-07-19 15:52:39,219 INFO L187 NwaCegarLoop]: Found error trace [2022-07-19 15:52:39,219 INFO L195 NwaCegarLoop]: trace histogram [9, 8, 8, 4, 4, 4, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-19 15:52:39,236 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Forceful destruction successful, exit code 0 [2022-07-19 15:52:39,427 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 16 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable15 [2022-07-19 15:52:39,428 INFO L420 AbstractCegarLoop]: === Iteration 17 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-19 15:52:39,428 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-19 15:52:39,428 INFO L85 PathProgramCache]: Analyzing trace with hash 593432004, now seen corresponding path program 1 times [2022-07-19 15:52:39,428 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-19 15:52:39,428 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [882389405] [2022-07-19 15:52:39,428 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-19 15:52:39,428 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-19 15:52:39,435 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-07-19 15:52:39,435 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1481257530] [2022-07-19 15:52:39,435 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-19 15:52:39,435 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-19 15:52:39,435 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-19 15:52:39,444 INFO L229 MonitoredProcess]: Starting monitored process 17 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-07-19 15:52:39,445 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Waiting until timeout for monitored process [2022-07-19 15:52:39,488 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-19 15:52:39,489 INFO L263 TraceCheckSpWp]: Trace formula consists of 203 conjuncts, 54 conjunts are in the unsatisfiable core [2022-07-19 15:52:39,490 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-19 15:52:39,890 INFO L134 CoverageAnalysis]: Checked inductivity of 162 backedges. 30 proven. 17 refuted. 0 times theorem prover too weak. 115 trivial. 0 not checked. [2022-07-19 15:52:39,890 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-19 15:52:41,592 INFO L134 CoverageAnalysis]: Checked inductivity of 162 backedges. 30 proven. 17 refuted. 0 times theorem prover too weak. 115 trivial. 0 not checked. [2022-07-19 15:52:41,592 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-19 15:52:41,593 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [882389405] [2022-07-19 15:52:41,593 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-07-19 15:52:41,593 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1481257530] [2022-07-19 15:52:41,593 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1481257530] provided 0 perfect and 2 imperfect interpolant sequences [2022-07-19 15:52:41,593 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-07-19 15:52:41,593 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 14] total 22 [2022-07-19 15:52:41,593 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [107826941] [2022-07-19 15:52:41,593 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-07-19 15:52:41,594 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 22 states [2022-07-19 15:52:41,594 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-19 15:52:41,595 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 22 interpolants. [2022-07-19 15:52:41,595 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=70, Invalid=392, Unknown=0, NotChecked=0, Total=462 [2022-07-19 15:52:41,595 INFO L87 Difference]: Start difference. First operand 245 states and 317 transitions. Second operand has 22 states, 20 states have (on average 2.35) internal successors, (47), 21 states have internal predecessors, (47), 8 states have call successors, (22), 2 states have call predecessors, (22), 2 states have return successors, (20), 6 states have call predecessors, (20), 6 states have call successors, (20) [2022-07-19 15:52:46,547 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.18s for a HTC check with result VALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-07-19 15:52:49,723 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-07-19 15:52:52,180 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-07-19 15:53:00,998 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.92s for a HTC check with result VALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-07-19 15:53:04,862 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-19 15:53:04,862 INFO L93 Difference]: Finished difference Result 488 states and 679 transitions. [2022-07-19 15:53:04,862 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 43 states. [2022-07-19 15:53:04,862 INFO L78 Accepts]: Start accepts. Automaton has has 22 states, 20 states have (on average 2.35) internal successors, (47), 21 states have internal predecessors, (47), 8 states have call successors, (22), 2 states have call predecessors, (22), 2 states have return successors, (20), 6 states have call predecessors, (20), 6 states have call successors, (20) Word has length 82 [2022-07-19 15:53:04,863 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-19 15:53:04,864 INFO L225 Difference]: With dead ends: 488 [2022-07-19 15:53:04,864 INFO L226 Difference]: Without dead ends: 480 [2022-07-19 15:53:04,865 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 197 GetRequests, 140 SyntacticMatches, 2 SemanticMatches, 55 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 697 ImplicationChecksByTransitivity, 4.9s TimeCoverageRelationStatistics Valid=560, Invalid=2632, Unknown=0, NotChecked=0, Total=3192 [2022-07-19 15:53:04,865 INFO L413 NwaCegarLoop]: 52 mSDtfsCounter, 132 mSDsluCounter, 336 mSDsCounter, 0 mSdLazyCounter, 1685 mSolverCounterSat, 378 mSolverCounterUnsat, 2 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 18.9s Time, 0 mProtectedPredicate, 0 mProtectedAction, 139 SdHoareTripleChecker+Valid, 388 SdHoareTripleChecker+Invalid, 2065 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 378 IncrementalHoareTripleChecker+Valid, 1685 IncrementalHoareTripleChecker+Invalid, 2 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 19.2s IncrementalHoareTripleChecker+Time [2022-07-19 15:53:04,865 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [139 Valid, 388 Invalid, 2065 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [378 Valid, 1685 Invalid, 2 Unknown, 0 Unchecked, 19.2s Time] [2022-07-19 15:53:04,866 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 480 states. [2022-07-19 15:53:04,954 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 480 to 390. [2022-07-19 15:53:04,960 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 390 states, 243 states have (on average 1.1851851851851851) internal successors, (288), 246 states have internal predecessors, (288), 121 states have call successors, (121), 25 states have call predecessors, (121), 25 states have return successors, (120), 118 states have call predecessors, (120), 120 states have call successors, (120) [2022-07-19 15:53:04,972 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 390 states to 390 states and 529 transitions. [2022-07-19 15:53:04,972 INFO L78 Accepts]: Start accepts. Automaton has 390 states and 529 transitions. Word has length 82 [2022-07-19 15:53:04,972 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-19 15:53:04,973 INFO L495 AbstractCegarLoop]: Abstraction has 390 states and 529 transitions. [2022-07-19 15:53:04,973 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 22 states, 20 states have (on average 2.35) internal successors, (47), 21 states have internal predecessors, (47), 8 states have call successors, (22), 2 states have call predecessors, (22), 2 states have return successors, (20), 6 states have call predecessors, (20), 6 states have call successors, (20) [2022-07-19 15:53:04,973 INFO L276 IsEmpty]: Start isEmpty. Operand 390 states and 529 transitions. [2022-07-19 15:53:04,974 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 110 [2022-07-19 15:53:04,977 INFO L187 NwaCegarLoop]: Found error trace [2022-07-19 15:53:04,977 INFO L195 NwaCegarLoop]: trace histogram [13, 12, 12, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-19 15:53:04,994 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Forceful destruction successful, exit code 0 [2022-07-19 15:53:05,177 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 17 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable16 [2022-07-19 15:53:05,177 INFO L420 AbstractCegarLoop]: === Iteration 18 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-19 15:53:05,178 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-19 15:53:05,178 INFO L85 PathProgramCache]: Analyzing trace with hash 28846429, now seen corresponding path program 2 times [2022-07-19 15:53:05,178 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-19 15:53:05,178 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1749635318] [2022-07-19 15:53:05,178 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-19 15:53:05,178 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-19 15:53:05,188 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-07-19 15:53:05,190 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [764708916] [2022-07-19 15:53:05,190 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-07-19 15:53:05,190 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-19 15:53:05,191 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-19 15:53:05,192 INFO L229 MonitoredProcess]: Starting monitored process 18 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-07-19 15:53:05,194 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (18)] Waiting until timeout for monitored process [2022-07-19 15:53:05,246 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-07-19 15:53:05,246 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-07-19 15:53:05,248 INFO L263 TraceCheckSpWp]: Trace formula consists of 267 conjuncts, 95 conjunts are in the unsatisfiable core [2022-07-19 15:53:05,250 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-19 15:53:06,486 INFO L134 CoverageAnalysis]: Checked inductivity of 343 backedges. 86 proven. 74 refuted. 0 times theorem prover too weak. 183 trivial. 0 not checked. [2022-07-19 15:53:06,486 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-19 15:53:11,919 INFO L134 CoverageAnalysis]: Checked inductivity of 343 backedges. 93 proven. 41 refuted. 0 times theorem prover too weak. 209 trivial. 0 not checked. [2022-07-19 15:53:11,919 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-19 15:53:11,919 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1749635318] [2022-07-19 15:53:11,919 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-07-19 15:53:11,919 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [764708916] [2022-07-19 15:53:11,919 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [764708916] provided 0 perfect and 2 imperfect interpolant sequences [2022-07-19 15:53:11,919 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-07-19 15:53:11,920 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [22, 17] total 34 [2022-07-19 15:53:11,920 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2102162329] [2022-07-19 15:53:11,921 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-07-19 15:53:11,921 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 34 states [2022-07-19 15:53:11,921 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-19 15:53:11,922 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 34 interpolants. [2022-07-19 15:53:11,922 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=168, Invalid=954, Unknown=0, NotChecked=0, Total=1122 [2022-07-19 15:53:11,922 INFO L87 Difference]: Start difference. First operand 390 states and 529 transitions. Second operand has 34 states, 30 states have (on average 2.1) internal successors, (63), 29 states have internal predecessors, (63), 14 states have call successors, (32), 2 states have call predecessors, (32), 3 states have return successors, (31), 11 states have call predecessors, (31), 12 states have call successors, (31) [2022-07-19 15:53:27,417 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-07-19 15:53:41,847 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-07-19 15:53:44,976 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-07-19 15:53:56,294 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-07-19 15:54:20,865 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.65s for a HTC check with result VALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-07-19 15:54:21,971 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.11s for a HTC check with result VALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-07-19 15:54:38,752 WARN L233 SmtUtils]: Spent 6.15s on a formula simplification. DAG size of input: 113 DAG size of output: 109 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-07-19 15:54:55,837 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-19 15:54:55,838 INFO L93 Difference]: Finished difference Result 623 states and 870 transitions. [2022-07-19 15:54:55,838 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 99 states. [2022-07-19 15:54:55,839 INFO L78 Accepts]: Start accepts. Automaton has has 34 states, 30 states have (on average 2.1) internal successors, (63), 29 states have internal predecessors, (63), 14 states have call successors, (32), 2 states have call predecessors, (32), 3 states have return successors, (31), 11 states have call predecessors, (31), 12 states have call successors, (31) Word has length 109 [2022-07-19 15:54:55,839 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-19 15:54:55,842 INFO L225 Difference]: With dead ends: 623 [2022-07-19 15:54:55,842 INFO L226 Difference]: Without dead ends: 615 [2022-07-19 15:54:55,845 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 326 GetRequests, 198 SyntacticMatches, 4 SemanticMatches, 124 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 5025 ImplicationChecksByTransitivity, 76.7s TimeCoverageRelationStatistics Valid=2578, Invalid=13172, Unknown=0, NotChecked=0, Total=15750 [2022-07-19 15:54:55,845 INFO L413 NwaCegarLoop]: 65 mSDtfsCounter, 259 mSDsluCounter, 448 mSDsCounter, 0 mSdLazyCounter, 2950 mSolverCounterSat, 736 mSolverCounterUnsat, 4 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 29.7s Time, 0 mProtectedPredicate, 0 mProtectedAction, 259 SdHoareTripleChecker+Valid, 513 SdHoareTripleChecker+Invalid, 3690 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 736 IncrementalHoareTripleChecker+Valid, 2950 IncrementalHoareTripleChecker+Invalid, 4 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 30.0s IncrementalHoareTripleChecker+Time [2022-07-19 15:54:55,846 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [259 Valid, 513 Invalid, 3690 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [736 Valid, 2950 Invalid, 4 Unknown, 0 Unchecked, 30.0s Time] [2022-07-19 15:54:55,846 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 615 states. [2022-07-19 15:54:55,987 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 615 to 467. [2022-07-19 15:54:55,988 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 467 states, 282 states have (on average 1.1879432624113475) internal successors, (335), 285 states have internal predecessors, (335), 153 states have call successors, (153), 31 states have call predecessors, (153), 31 states have return successors, (152), 150 states have call predecessors, (152), 152 states have call successors, (152) [2022-07-19 15:54:55,990 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 467 states to 467 states and 640 transitions. [2022-07-19 15:54:55,990 INFO L78 Accepts]: Start accepts. Automaton has 467 states and 640 transitions. Word has length 109 [2022-07-19 15:54:55,990 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-19 15:54:55,991 INFO L495 AbstractCegarLoop]: Abstraction has 467 states and 640 transitions. [2022-07-19 15:54:55,991 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 34 states, 30 states have (on average 2.1) internal successors, (63), 29 states have internal predecessors, (63), 14 states have call successors, (32), 2 states have call predecessors, (32), 3 states have return successors, (31), 11 states have call predecessors, (31), 12 states have call successors, (31) [2022-07-19 15:54:55,991 INFO L276 IsEmpty]: Start isEmpty. Operand 467 states and 640 transitions. [2022-07-19 15:54:55,992 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 113 [2022-07-19 15:54:55,992 INFO L187 NwaCegarLoop]: Found error trace [2022-07-19 15:54:55,992 INFO L195 NwaCegarLoop]: trace histogram [13, 12, 12, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-19 15:54:56,009 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (18)] Forceful destruction successful, exit code 0 [2022-07-19 15:54:56,207 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 18 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable17 [2022-07-19 15:54:56,208 INFO L420 AbstractCegarLoop]: === Iteration 19 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-19 15:54:56,208 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-19 15:54:56,208 INFO L85 PathProgramCache]: Analyzing trace with hash -876975624, now seen corresponding path program 3 times [2022-07-19 15:54:56,208 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-19 15:54:56,208 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [730273235] [2022-07-19 15:54:56,208 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-19 15:54:56,209 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-19 15:54:56,214 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-07-19 15:54:56,214 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1238135787] [2022-07-19 15:54:56,215 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2022-07-19 15:54:56,215 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-19 15:54:56,215 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-19 15:54:56,216 INFO L229 MonitoredProcess]: Starting monitored process 19 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-07-19 15:54:56,217 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (19)] Waiting until timeout for monitored process [2022-07-19 15:54:56,270 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 5 check-sat command(s) [2022-07-19 15:54:56,270 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-07-19 15:54:56,272 INFO L263 TraceCheckSpWp]: Trace formula consists of 219 conjuncts, 81 conjunts are in the unsatisfiable core [2022-07-19 15:54:56,274 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-19 15:54:57,282 INFO L134 CoverageAnalysis]: Checked inductivity of 350 backedges. 82 proven. 40 refuted. 0 times theorem prover too weak. 228 trivial. 0 not checked. [2022-07-19 15:54:57,282 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-19 15:55:05,307 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-19 15:55:05,307 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [730273235] [2022-07-19 15:55:05,307 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-07-19 15:55:05,307 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1238135787] [2022-07-19 15:55:05,307 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1238135787] provided 0 perfect and 1 imperfect interpolant sequences [2022-07-19 15:55:05,307 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-07-19 15:55:05,307 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [18] total 18 [2022-07-19 15:55:05,307 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [12331555] [2022-07-19 15:55:05,307 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2022-07-19 15:55:05,308 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 18 states [2022-07-19 15:55:05,309 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-19 15:55:05,310 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 18 interpolants. [2022-07-19 15:55:05,310 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=130, Invalid=624, Unknown=2, NotChecked=0, Total=756 [2022-07-19 15:55:05,310 INFO L87 Difference]: Start difference. First operand 467 states and 640 transitions. Second operand has 18 states, 17 states have (on average 2.3529411764705883) internal successors, (40), 17 states have internal predecessors, (40), 6 states have call successors, (17), 2 states have call predecessors, (17), 2 states have return successors, (16), 5 states have call predecessors, (16), 5 states have call successors, (16) [2022-07-19 15:55:07,206 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-19 15:55:07,207 INFO L93 Difference]: Finished difference Result 577 states and 789 transitions. [2022-07-19 15:55:07,207 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 18 states. [2022-07-19 15:55:07,208 INFO L78 Accepts]: Start accepts. Automaton has has 18 states, 17 states have (on average 2.3529411764705883) internal successors, (40), 17 states have internal predecessors, (40), 6 states have call successors, (17), 2 states have call predecessors, (17), 2 states have return successors, (16), 5 states have call predecessors, (16), 5 states have call successors, (16) Word has length 112 [2022-07-19 15:55:07,208 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-19 15:55:07,210 INFO L225 Difference]: With dead ends: 577 [2022-07-19 15:55:07,210 INFO L226 Difference]: Without dead ends: 570 [2022-07-19 15:55:07,210 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 176 GetRequests, 142 SyntacticMatches, 2 SemanticMatches, 32 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 226 ImplicationChecksByTransitivity, 7.0s TimeCoverageRelationStatistics Valid=189, Invalid=931, Unknown=2, NotChecked=0, Total=1122 [2022-07-19 15:55:07,211 INFO L413 NwaCegarLoop]: 56 mSDtfsCounter, 68 mSDsluCounter, 310 mSDsCounter, 0 mSdLazyCounter, 1236 mSolverCounterSat, 85 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 89 SdHoareTripleChecker+Valid, 366 SdHoareTripleChecker+Invalid, 1321 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 85 IncrementalHoareTripleChecker+Valid, 1236 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.4s IncrementalHoareTripleChecker+Time [2022-07-19 15:55:07,211 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [89 Valid, 366 Invalid, 1321 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [85 Valid, 1236 Invalid, 0 Unknown, 0 Unchecked, 1.4s Time] [2022-07-19 15:55:07,212 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 570 states. [2022-07-19 15:55:07,399 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 570 to 542. [2022-07-19 15:55:07,400 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 542 states, 325 states have (on average 1.1938461538461538) internal successors, (388), 328 states have internal predecessors, (388), 181 states have call successors, (181), 35 states have call predecessors, (181), 35 states have return successors, (180), 178 states have call predecessors, (180), 180 states have call successors, (180) [2022-07-19 15:55:07,402 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 542 states to 542 states and 749 transitions. [2022-07-19 15:55:07,402 INFO L78 Accepts]: Start accepts. Automaton has 542 states and 749 transitions. Word has length 112 [2022-07-19 15:55:07,402 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-19 15:55:07,402 INFO L495 AbstractCegarLoop]: Abstraction has 542 states and 749 transitions. [2022-07-19 15:55:07,403 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 18 states, 17 states have (on average 2.3529411764705883) internal successors, (40), 17 states have internal predecessors, (40), 6 states have call successors, (17), 2 states have call predecessors, (17), 2 states have return successors, (16), 5 states have call predecessors, (16), 5 states have call successors, (16) [2022-07-19 15:55:07,403 INFO L276 IsEmpty]: Start isEmpty. Operand 542 states and 749 transitions. [2022-07-19 15:55:07,404 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 118 [2022-07-19 15:55:07,404 INFO L187 NwaCegarLoop]: Found error trace [2022-07-19 15:55:07,404 INFO L195 NwaCegarLoop]: trace histogram [13, 12, 12, 5, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-19 15:55:07,433 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (19)] Forceful destruction successful, exit code 0 [2022-07-19 15:55:07,619 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable18,19 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-19 15:55:07,620 INFO L420 AbstractCegarLoop]: === Iteration 20 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-19 15:55:07,620 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-19 15:55:07,620 INFO L85 PathProgramCache]: Analyzing trace with hash 1746474790, now seen corresponding path program 4 times [2022-07-19 15:55:07,620 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-19 15:55:07,620 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [389415762] [2022-07-19 15:55:07,620 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-19 15:55:07,621 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-19 15:55:07,640 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-07-19 15:55:07,640 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1674413750] [2022-07-19 15:55:07,640 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2022-07-19 15:55:07,640 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-19 15:55:07,640 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-19 15:55:07,641 INFO L229 MonitoredProcess]: Starting monitored process 20 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-07-19 15:55:07,642 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (20)] Waiting until timeout for monitored process [2022-07-19 15:55:07,700 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2022-07-19 15:55:07,700 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-07-19 15:55:07,702 INFO L263 TraceCheckSpWp]: Trace formula consists of 258 conjuncts, 85 conjunts are in the unsatisfiable core [2022-07-19 15:55:07,704 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-19 15:55:08,262 INFO L134 CoverageAnalysis]: Checked inductivity of 366 backedges. 55 proven. 81 refuted. 0 times theorem prover too weak. 230 trivial. 0 not checked. [2022-07-19 15:55:08,263 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-19 15:55:09,946 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-19 15:55:09,946 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [389415762] [2022-07-19 15:55:09,946 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-07-19 15:55:09,946 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1674413750] [2022-07-19 15:55:09,946 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1674413750] provided 0 perfect and 1 imperfect interpolant sequences [2022-07-19 15:55:09,947 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-07-19 15:55:09,947 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [18] total 18 [2022-07-19 15:55:09,947 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1504608821] [2022-07-19 15:55:09,947 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2022-07-19 15:55:09,947 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 18 states [2022-07-19 15:55:09,947 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-19 15:55:09,947 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 18 interpolants. [2022-07-19 15:55:09,947 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=61, Invalid=445, Unknown=0, NotChecked=0, Total=506 [2022-07-19 15:55:09,948 INFO L87 Difference]: Start difference. First operand 542 states and 749 transitions. Second operand has 18 states, 17 states have (on average 2.588235294117647) internal successors, (44), 17 states have internal predecessors, (44), 6 states have call successors, (17), 2 states have call predecessors, (17), 2 states have return successors, (16), 6 states have call predecessors, (16), 5 states have call successors, (16) [2022-07-19 15:55:11,406 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-19 15:55:11,407 INFO L93 Difference]: Finished difference Result 779 states and 1090 transitions. [2022-07-19 15:55:11,407 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 22 states. [2022-07-19 15:55:11,407 INFO L78 Accepts]: Start accepts. Automaton has has 18 states, 17 states have (on average 2.588235294117647) internal successors, (44), 17 states have internal predecessors, (44), 6 states have call successors, (17), 2 states have call predecessors, (17), 2 states have return successors, (16), 6 states have call predecessors, (16), 5 states have call successors, (16) Word has length 117 [2022-07-19 15:55:11,410 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-19 15:55:11,413 INFO L225 Difference]: With dead ends: 779 [2022-07-19 15:55:11,413 INFO L226 Difference]: Without dead ends: 776 [2022-07-19 15:55:11,414 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 151 GetRequests, 115 SyntacticMatches, 2 SemanticMatches, 34 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 210 ImplicationChecksByTransitivity, 2.1s TimeCoverageRelationStatistics Valid=168, Invalid=1092, Unknown=0, NotChecked=0, Total=1260 [2022-07-19 15:55:11,414 INFO L413 NwaCegarLoop]: 64 mSDtfsCounter, 116 mSDsluCounter, 327 mSDsCounter, 0 mSdLazyCounter, 1377 mSolverCounterSat, 157 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.6s Time, 0 mProtectedPredicate, 0 mProtectedAction, 133 SdHoareTripleChecker+Valid, 391 SdHoareTripleChecker+Invalid, 1534 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 157 IncrementalHoareTripleChecker+Valid, 1377 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.8s IncrementalHoareTripleChecker+Time [2022-07-19 15:55:11,415 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [133 Valid, 391 Invalid, 1534 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [157 Valid, 1377 Invalid, 0 Unknown, 0 Unchecked, 0.8s Time] [2022-07-19 15:55:11,415 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 776 states. [2022-07-19 15:55:11,664 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 776 to 738. [2022-07-19 15:55:11,666 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 738 states, 428 states have (on average 1.2126168224299065) internal successors, (519), 431 states have internal predecessors, (519), 265 states have call successors, (265), 44 states have call predecessors, (265), 44 states have return successors, (264), 262 states have call predecessors, (264), 264 states have call successors, (264) [2022-07-19 15:55:11,668 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 738 states to 738 states and 1048 transitions. [2022-07-19 15:55:11,668 INFO L78 Accepts]: Start accepts. Automaton has 738 states and 1048 transitions. Word has length 117 [2022-07-19 15:55:11,669 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-19 15:55:11,669 INFO L495 AbstractCegarLoop]: Abstraction has 738 states and 1048 transitions. [2022-07-19 15:55:11,669 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 18 states, 17 states have (on average 2.588235294117647) internal successors, (44), 17 states have internal predecessors, (44), 6 states have call successors, (17), 2 states have call predecessors, (17), 2 states have return successors, (16), 6 states have call predecessors, (16), 5 states have call successors, (16) [2022-07-19 15:55:11,669 INFO L276 IsEmpty]: Start isEmpty. Operand 738 states and 1048 transitions. [2022-07-19 15:55:11,670 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 121 [2022-07-19 15:55:11,670 INFO L187 NwaCegarLoop]: Found error trace [2022-07-19 15:55:11,671 INFO L195 NwaCegarLoop]: trace histogram [15, 14, 14, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-19 15:55:11,689 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (20)] Forceful destruction successful, exit code 0 [2022-07-19 15:55:11,883 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable19,20 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-19 15:55:11,884 INFO L420 AbstractCegarLoop]: === Iteration 21 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-19 15:55:11,884 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-19 15:55:11,884 INFO L85 PathProgramCache]: Analyzing trace with hash 1576994048, now seen corresponding path program 1 times [2022-07-19 15:55:11,884 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-19 15:55:11,884 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [604164155] [2022-07-19 15:55:11,884 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-19 15:55:11,885 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-19 15:55:11,898 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-07-19 15:55:11,899 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1982893130] [2022-07-19 15:55:11,899 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-19 15:55:11,899 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-19 15:55:11,899 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-19 15:55:11,901 INFO L229 MonitoredProcess]: Starting monitored process 21 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-07-19 15:55:11,901 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (21)] Waiting until timeout for monitored process [2022-07-19 15:55:11,947 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-19 15:55:11,949 INFO L263 TraceCheckSpWp]: Trace formula consists of 279 conjuncts, 30 conjunts are in the unsatisfiable core [2022-07-19 15:55:11,951 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-19 15:55:12,765 INFO L134 CoverageAnalysis]: Checked inductivity of 461 backedges. 74 proven. 38 refuted. 0 times theorem prover too weak. 349 trivial. 0 not checked. [2022-07-19 15:55:12,765 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-19 15:55:13,534 INFO L134 CoverageAnalysis]: Checked inductivity of 461 backedges. 95 proven. 13 refuted. 0 times theorem prover too weak. 353 trivial. 0 not checked. [2022-07-19 15:55:13,534 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-19 15:55:13,534 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [604164155] [2022-07-19 15:55:13,534 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-07-19 15:55:13,535 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1982893130] [2022-07-19 15:55:13,535 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1982893130] provided 0 perfect and 2 imperfect interpolant sequences [2022-07-19 15:55:13,535 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-07-19 15:55:13,535 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [17, 13] total 25 [2022-07-19 15:55:13,535 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1809803564] [2022-07-19 15:55:13,535 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-07-19 15:55:13,535 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 25 states [2022-07-19 15:55:13,535 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-19 15:55:13,535 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 25 interpolants. [2022-07-19 15:55:13,536 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=132, Invalid=468, Unknown=0, NotChecked=0, Total=600 [2022-07-19 15:55:13,536 INFO L87 Difference]: Start difference. First operand 738 states and 1048 transitions. Second operand has 25 states, 25 states have (on average 2.28) internal successors, (57), 22 states have internal predecessors, (57), 8 states have call successors, (34), 2 states have call predecessors, (34), 2 states have return successors, (32), 10 states have call predecessors, (32), 8 states have call successors, (32) [2022-07-19 15:55:16,091 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-19 15:55:16,091 INFO L93 Difference]: Finished difference Result 1277 states and 1787 transitions. [2022-07-19 15:55:16,092 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 36 states. [2022-07-19 15:55:16,092 INFO L78 Accepts]: Start accepts. Automaton has has 25 states, 25 states have (on average 2.28) internal successors, (57), 22 states have internal predecessors, (57), 8 states have call successors, (34), 2 states have call predecessors, (34), 2 states have return successors, (32), 10 states have call predecessors, (32), 8 states have call successors, (32) Word has length 120 [2022-07-19 15:55:16,092 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-19 15:55:16,095 INFO L225 Difference]: With dead ends: 1277 [2022-07-19 15:55:16,095 INFO L226 Difference]: Without dead ends: 844 [2022-07-19 15:55:16,096 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 267 GetRequests, 217 SyntacticMatches, 1 SemanticMatches, 49 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 679 ImplicationChecksByTransitivity, 1.8s TimeCoverageRelationStatistics Valid=552, Invalid=1998, Unknown=0, NotChecked=0, Total=2550 [2022-07-19 15:55:16,097 INFO L413 NwaCegarLoop]: 48 mSDtfsCounter, 106 mSDsluCounter, 258 mSDsCounter, 0 mSdLazyCounter, 791 mSolverCounterSat, 210 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 109 SdHoareTripleChecker+Valid, 306 SdHoareTripleChecker+Invalid, 1001 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 210 IncrementalHoareTripleChecker+Valid, 791 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.2s IncrementalHoareTripleChecker+Time [2022-07-19 15:55:16,097 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [109 Valid, 306 Invalid, 1001 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [210 Valid, 791 Invalid, 0 Unknown, 0 Unchecked, 1.2s Time] [2022-07-19 15:55:16,098 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 844 states. [2022-07-19 15:55:16,378 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 844 to 774. [2022-07-19 15:55:16,380 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 774 states, 460 states have (on average 1.1956521739130435) internal successors, (550), 468 states have internal predecessors, (550), 263 states have call successors, (263), 50 states have call predecessors, (263), 50 states have return successors, (262), 255 states have call predecessors, (262), 262 states have call successors, (262) [2022-07-19 15:55:16,382 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 774 states to 774 states and 1075 transitions. [2022-07-19 15:55:16,382 INFO L78 Accepts]: Start accepts. Automaton has 774 states and 1075 transitions. Word has length 120 [2022-07-19 15:55:16,383 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-19 15:55:16,383 INFO L495 AbstractCegarLoop]: Abstraction has 774 states and 1075 transitions. [2022-07-19 15:55:16,383 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 25 states, 25 states have (on average 2.28) internal successors, (57), 22 states have internal predecessors, (57), 8 states have call successors, (34), 2 states have call predecessors, (34), 2 states have return successors, (32), 10 states have call predecessors, (32), 8 states have call successors, (32) [2022-07-19 15:55:16,383 INFO L276 IsEmpty]: Start isEmpty. Operand 774 states and 1075 transitions. [2022-07-19 15:55:16,385 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 121 [2022-07-19 15:55:16,385 INFO L187 NwaCegarLoop]: Found error trace [2022-07-19 15:55:16,386 INFO L195 NwaCegarLoop]: trace histogram [14, 13, 13, 5, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-19 15:55:16,403 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (21)] Ended with exit code 0 [2022-07-19 15:55:16,606 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 21 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable20 [2022-07-19 15:55:16,606 INFO L420 AbstractCegarLoop]: === Iteration 22 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-19 15:55:16,606 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-19 15:55:16,606 INFO L85 PathProgramCache]: Analyzing trace with hash -843376510, now seen corresponding path program 2 times [2022-07-19 15:55:16,607 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-19 15:55:16,607 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1335924364] [2022-07-19 15:55:16,607 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-19 15:55:16,607 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-19 15:55:16,620 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-07-19 15:55:16,620 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [484810025] [2022-07-19 15:55:16,620 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-07-19 15:55:16,620 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-19 15:55:16,620 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-19 15:55:16,621 INFO L229 MonitoredProcess]: Starting monitored process 22 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-07-19 15:55:16,637 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (22)] Waiting until timeout for monitored process [2022-07-19 15:55:16,678 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-07-19 15:55:16,678 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-07-19 15:55:16,680 INFO L263 TraceCheckSpWp]: Trace formula consists of 292 conjuncts, 91 conjunts are in the unsatisfiable core [2022-07-19 15:55:16,682 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-19 15:55:17,389 INFO L134 CoverageAnalysis]: Checked inductivity of 417 backedges. 118 proven. 71 refuted. 0 times theorem prover too weak. 228 trivial. 0 not checked. [2022-07-19 15:55:17,390 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-19 15:55:24,245 INFO L134 CoverageAnalysis]: Checked inductivity of 417 backedges. 146 proven. 19 refuted. 0 times theorem prover too weak. 252 trivial. 0 not checked. [2022-07-19 15:55:24,245 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-19 15:55:24,245 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1335924364] [2022-07-19 15:55:24,245 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-07-19 15:55:24,245 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [484810025] [2022-07-19 15:55:24,245 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [484810025] provided 0 perfect and 2 imperfect interpolant sequences [2022-07-19 15:55:24,246 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-07-19 15:55:24,246 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [18, 13] total 26 [2022-07-19 15:55:24,246 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [221990723] [2022-07-19 15:55:24,246 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-07-19 15:55:24,246 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 26 states [2022-07-19 15:55:24,246 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-19 15:55:24,246 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 26 interpolants. [2022-07-19 15:55:24,247 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=100, Invalid=548, Unknown=2, NotChecked=0, Total=650 [2022-07-19 15:55:24,247 INFO L87 Difference]: Start difference. First operand 774 states and 1075 transitions. Second operand has 26 states, 23 states have (on average 3.0434782608695654) internal successors, (70), 22 states have internal predecessors, (70), 11 states have call successors, (31), 2 states have call predecessors, (31), 2 states have return successors, (30), 9 states have call predecessors, (30), 9 states have call successors, (30) [2022-07-19 15:55:28,309 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.19s for a HTC check with result VALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-07-19 15:55:30,311 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-07-19 15:55:34,983 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-07-19 15:55:39,032 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-07-19 15:55:41,078 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-07-19 15:55:45,199 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-07-19 15:55:47,298 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-07-19 15:55:52,429 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-07-19 15:56:09,925 WARN L233 SmtUtils]: Spent 14.50s on a formula simplification. DAG size of input: 75 DAG size of output: 67 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-07-19 15:56:11,813 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.09s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-07-19 15:56:18,157 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.09s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-07-19 15:56:20,160 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-07-19 15:56:23,102 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.81s for a HTC check with result VALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-07-19 15:56:27,492 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-07-19 15:56:27,628 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-19 15:56:27,629 INFO L93 Difference]: Finished difference Result 894 states and 1228 transitions. [2022-07-19 15:56:27,631 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 32 states. [2022-07-19 15:56:27,631 INFO L78 Accepts]: Start accepts. Automaton has has 26 states, 23 states have (on average 3.0434782608695654) internal successors, (70), 22 states have internal predecessors, (70), 11 states have call successors, (31), 2 states have call predecessors, (31), 2 states have return successors, (30), 9 states have call predecessors, (30), 9 states have call successors, (30) Word has length 120 [2022-07-19 15:56:27,632 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-19 15:56:27,635 INFO L225 Difference]: With dead ends: 894 [2022-07-19 15:56:27,635 INFO L226 Difference]: Without dead ends: 890 [2022-07-19 15:56:27,636 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 269 GetRequests, 217 SyntacticMatches, 4 SemanticMatches, 48 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 487 ImplicationChecksByTransitivity, 32.3s TimeCoverageRelationStatistics Valid=409, Invalid=2035, Unknown=6, NotChecked=0, Total=2450 [2022-07-19 15:56:27,636 INFO L413 NwaCegarLoop]: 62 mSDtfsCounter, 123 mSDsluCounter, 374 mSDsCounter, 0 mSdLazyCounter, 1463 mSolverCounterSat, 326 mSolverCounterUnsat, 9 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 37.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 125 SdHoareTripleChecker+Valid, 436 SdHoareTripleChecker+Invalid, 1798 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 326 IncrementalHoareTripleChecker+Valid, 1463 IncrementalHoareTripleChecker+Invalid, 9 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 37.4s IncrementalHoareTripleChecker+Time [2022-07-19 15:56:27,636 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [125 Valid, 436 Invalid, 1798 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [326 Valid, 1463 Invalid, 9 Unknown, 0 Unchecked, 37.4s Time] [2022-07-19 15:56:27,637 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 890 states. [2022-07-19 15:56:27,963 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 890 to 854. [2022-07-19 15:56:27,964 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 854 states, 507 states have (on average 1.193293885601578) internal successors, (605), 515 states have internal predecessors, (605), 290 states have call successors, (290), 57 states have call predecessors, (290), 56 states have return successors, (289), 281 states have call predecessors, (289), 289 states have call successors, (289) [2022-07-19 15:56:27,967 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 854 states to 854 states and 1184 transitions. [2022-07-19 15:56:27,967 INFO L78 Accepts]: Start accepts. Automaton has 854 states and 1184 transitions. Word has length 120 [2022-07-19 15:56:27,967 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-19 15:56:27,968 INFO L495 AbstractCegarLoop]: Abstraction has 854 states and 1184 transitions. [2022-07-19 15:56:27,968 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 26 states, 23 states have (on average 3.0434782608695654) internal successors, (70), 22 states have internal predecessors, (70), 11 states have call successors, (31), 2 states have call predecessors, (31), 2 states have return successors, (30), 9 states have call predecessors, (30), 9 states have call successors, (30) [2022-07-19 15:56:27,968 INFO L276 IsEmpty]: Start isEmpty. Operand 854 states and 1184 transitions. [2022-07-19 15:56:27,969 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 130 [2022-07-19 15:56:27,969 INFO L187 NwaCegarLoop]: Found error trace [2022-07-19 15:56:27,970 INFO L195 NwaCegarLoop]: trace histogram [17, 16, 16, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-19 15:56:27,989 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (22)] Forceful destruction successful, exit code 0 [2022-07-19 15:56:28,183 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 22 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable21 [2022-07-19 15:56:28,183 INFO L420 AbstractCegarLoop]: === Iteration 23 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-19 15:56:28,183 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-19 15:56:28,183 INFO L85 PathProgramCache]: Analyzing trace with hash -1278110097, now seen corresponding path program 5 times [2022-07-19 15:56:28,184 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-19 15:56:28,184 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2074392894] [2022-07-19 15:56:28,184 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-19 15:56:28,184 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-19 15:56:28,189 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-07-19 15:56:28,190 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1034778131] [2022-07-19 15:56:28,190 INFO L93 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2022-07-19 15:56:28,190 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-19 15:56:28,190 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-19 15:56:28,191 INFO L229 MonitoredProcess]: Starting monitored process 23 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-07-19 15:56:28,193 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (23)] Waiting until timeout for monitored process [2022-07-19 15:56:28,265 INFO L228 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 9 check-sat command(s) [2022-07-19 15:56:28,265 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-07-19 15:56:28,267 INFO L263 TraceCheckSpWp]: Trace formula consists of 293 conjuncts, 78 conjunts are in the unsatisfiable core [2022-07-19 15:56:28,273 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-19 15:56:29,692 INFO L134 CoverageAnalysis]: Checked inductivity of 581 backedges. 98 proven. 105 refuted. 0 times theorem prover too weak. 378 trivial. 0 not checked. [2022-07-19 15:56:29,692 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-19 15:56:32,976 INFO L134 CoverageAnalysis]: Checked inductivity of 581 backedges. 89 proven. 105 refuted. 0 times theorem prover too weak. 387 trivial. 0 not checked. [2022-07-19 15:56:32,976 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-19 15:56:32,976 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2074392894] [2022-07-19 15:56:32,976 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-07-19 15:56:32,976 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1034778131] [2022-07-19 15:56:32,976 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1034778131] provided 0 perfect and 2 imperfect interpolant sequences [2022-07-19 15:56:32,976 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-07-19 15:56:32,976 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [20, 19] total 34 [2022-07-19 15:56:32,976 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [938162384] [2022-07-19 15:56:32,977 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-07-19 15:56:32,977 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 34 states [2022-07-19 15:56:32,977 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-19 15:56:32,977 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 34 interpolants. [2022-07-19 15:56:32,978 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=170, Invalid=952, Unknown=0, NotChecked=0, Total=1122 [2022-07-19 15:56:32,978 INFO L87 Difference]: Start difference. First operand 854 states and 1184 transitions. Second operand has 34 states, 32 states have (on average 2.0) internal successors, (64), 29 states have internal predecessors, (64), 12 states have call successors, (38), 2 states have call predecessors, (38), 3 states have return successors, (37), 14 states have call predecessors, (37), 10 states have call successors, (37)