./Ultimate.py --spec ../sv-benchmarks/c/properties/unreach-call.prp --file ../sv-benchmarks/c/nla-digbench-scaling/ps4-ll_unwindbound10.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version 35987657 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/ps4-ll_unwindbound10.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 34fd2c5bce28a2f0a39de6b9c2d306403d911c32b4998862fc7a657ddcb319f4 --- Real Ultimate output --- This is Ultimate 0.2.2-?-3598765 [2022-07-21 04:08:35,696 INFO L177 SettingsManager]: Resetting all preferences to default values... [2022-07-21 04:08:35,698 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2022-07-21 04:08:35,719 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2022-07-21 04:08:35,720 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2022-07-21 04:08:35,721 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2022-07-21 04:08:35,723 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2022-07-21 04:08:35,726 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2022-07-21 04:08:35,727 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2022-07-21 04:08:35,728 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2022-07-21 04:08:35,729 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2022-07-21 04:08:35,731 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2022-07-21 04:08:35,732 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2022-07-21 04:08:35,734 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2022-07-21 04:08:35,736 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2022-07-21 04:08:35,736 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2022-07-21 04:08:35,738 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2022-07-21 04:08:35,741 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2022-07-21 04:08:35,742 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2022-07-21 04:08:35,745 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2022-07-21 04:08:35,748 INFO L181 SettingsManager]: Resetting HornVerifier preferences to default values [2022-07-21 04:08:35,751 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2022-07-21 04:08:35,751 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2022-07-21 04:08:35,752 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2022-07-21 04:08:35,753 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2022-07-21 04:08:35,755 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2022-07-21 04:08:35,755 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2022-07-21 04:08:35,756 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2022-07-21 04:08:35,756 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2022-07-21 04:08:35,757 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2022-07-21 04:08:35,757 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2022-07-21 04:08:35,757 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2022-07-21 04:08:35,758 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2022-07-21 04:08:35,758 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2022-07-21 04:08:35,759 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2022-07-21 04:08:35,759 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2022-07-21 04:08:35,760 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2022-07-21 04:08:35,760 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2022-07-21 04:08:35,760 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2022-07-21 04:08:35,761 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2022-07-21 04:08:35,761 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2022-07-21 04:08:35,766 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2022-07-21 04:08:35,770 INFO L101 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf [2022-07-21 04:08:35,787 INFO L113 SettingsManager]: Loading preferences was successful [2022-07-21 04:08:35,788 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2022-07-21 04:08:35,788 INFO L136 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2022-07-21 04:08:35,788 INFO L138 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2022-07-21 04:08:35,789 INFO L136 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2022-07-21 04:08:35,789 INFO L138 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2022-07-21 04:08:35,789 INFO L136 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2022-07-21 04:08:35,790 INFO L138 SettingsManager]: * Create parallel compositions if possible=false [2022-07-21 04:08:35,790 INFO L138 SettingsManager]: * Use SBE=true [2022-07-21 04:08:35,790 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2022-07-21 04:08:35,790 INFO L138 SettingsManager]: * sizeof long=4 [2022-07-21 04:08:35,790 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2022-07-21 04:08:35,790 INFO L138 SettingsManager]: * sizeof POINTER=4 [2022-07-21 04:08:35,791 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2022-07-21 04:08:35,805 INFO L138 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2022-07-21 04:08:35,805 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2022-07-21 04:08:35,806 INFO L138 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2022-07-21 04:08:35,806 INFO L138 SettingsManager]: * sizeof long double=12 [2022-07-21 04:08:35,806 INFO L138 SettingsManager]: * Check if freed pointer was valid=false [2022-07-21 04:08:35,806 INFO L138 SettingsManager]: * Use constant arrays=true [2022-07-21 04:08:35,807 INFO L138 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2022-07-21 04:08:35,807 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2022-07-21 04:08:35,808 INFO L138 SettingsManager]: * Size of a code block=SequenceOfStatements [2022-07-21 04:08:35,808 INFO L138 SettingsManager]: * SMT solver=External_DefaultMode [2022-07-21 04:08:35,808 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-07-21 04:08:35,808 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2022-07-21 04:08:35,808 INFO L138 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2022-07-21 04:08:35,809 INFO L138 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2022-07-21 04:08:35,809 INFO L138 SettingsManager]: * Trace refinement strategy=CAMEL [2022-07-21 04:08:35,810 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2022-07-21 04:08:35,810 INFO L138 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2022-07-21 04:08:35,810 INFO L138 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2022-07-21 04:08:35,810 INFO L138 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2022-07-21 04:08:35,811 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 -> 34fd2c5bce28a2f0a39de6b9c2d306403d911c32b4998862fc7a657ddcb319f4 [2022-07-21 04:08:36,085 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2022-07-21 04:08:36,121 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2022-07-21 04:08:36,123 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2022-07-21 04:08:36,124 INFO L271 PluginConnector]: Initializing CDTParser... [2022-07-21 04:08:36,124 INFO L275 PluginConnector]: CDTParser initialized [2022-07-21 04:08:36,125 INFO L432 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/nla-digbench-scaling/ps4-ll_unwindbound10.c [2022-07-21 04:08:36,191 INFO L220 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/c0e844a6f/718d2d49aaac49eab0d396960974507d/FLAGd59bfb496 [2022-07-21 04:08:36,530 INFO L306 CDTParser]: Found 1 translation units. [2022-07-21 04:08:36,530 INFO L160 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/ps4-ll_unwindbound10.c [2022-07-21 04:08:36,534 INFO L349 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/c0e844a6f/718d2d49aaac49eab0d396960974507d/FLAGd59bfb496 [2022-07-21 04:08:36,547 INFO L357 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/c0e844a6f/718d2d49aaac49eab0d396960974507d [2022-07-21 04:08:36,549 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2022-07-21 04:08:36,550 INFO L131 ToolchainWalker]: Walking toolchain with 6 elements. [2022-07-21 04:08:36,553 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2022-07-21 04:08:36,553 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2022-07-21 04:08:36,555 INFO L275 PluginConnector]: CACSL2BoogieTranslator initialized [2022-07-21 04:08:36,556 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 21.07 04:08:36" (1/1) ... [2022-07-21 04:08:36,557 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@122606e7 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.07 04:08:36, skipping insertion in model container [2022-07-21 04:08:36,557 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 21.07 04:08:36" (1/1) ... [2022-07-21 04:08:36,561 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2022-07-21 04:08:36,572 INFO L178 MainTranslator]: Built tables and reachable declarations [2022-07-21 04:08:36,687 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/ps4-ll_unwindbound10.c[458,471] [2022-07-21 04:08:36,712 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-07-21 04:08:36,723 INFO L203 MainTranslator]: Completed pre-run [2022-07-21 04:08:36,738 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/ps4-ll_unwindbound10.c[458,471] [2022-07-21 04:08:36,757 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-07-21 04:08:36,776 INFO L208 MainTranslator]: Completed translation [2022-07-21 04:08:36,776 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.07 04:08:36 WrapperNode [2022-07-21 04:08:36,777 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2022-07-21 04:08:36,777 INFO L113 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2022-07-21 04:08:36,777 INFO L271 PluginConnector]: Initializing Boogie Procedure Inliner... [2022-07-21 04:08:36,778 INFO L275 PluginConnector]: Boogie Procedure Inliner initialized [2022-07-21 04:08:36,782 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.07 04:08:36" (1/1) ... [2022-07-21 04:08:36,787 INFO L185 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.07 04:08:36" (1/1) ... [2022-07-21 04:08:36,799 INFO L137 Inliner]: procedures = 14, calls = 10, calls flagged for inlining = 2, calls inlined = 2, statements flattened = 39 [2022-07-21 04:08:36,799 INFO L132 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2022-07-21 04:08:36,800 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2022-07-21 04:08:36,801 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2022-07-21 04:08:36,801 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2022-07-21 04:08:36,806 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.07 04:08:36" (1/1) ... [2022-07-21 04:08:36,806 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.07 04:08:36" (1/1) ... [2022-07-21 04:08:36,815 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.07 04:08:36" (1/1) ... [2022-07-21 04:08:36,816 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.07 04:08:36" (1/1) ... [2022-07-21 04:08:36,823 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.07 04:08:36" (1/1) ... [2022-07-21 04:08:36,826 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.07 04:08:36" (1/1) ... [2022-07-21 04:08:36,827 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.07 04:08:36" (1/1) ... [2022-07-21 04:08:36,830 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2022-07-21 04:08:36,831 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2022-07-21 04:08:36,832 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2022-07-21 04:08:36,832 INFO L275 PluginConnector]: RCFGBuilder initialized [2022-07-21 04:08:36,832 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.07 04:08:36" (1/1) ... [2022-07-21 04:08:36,837 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-07-21 04:08:36,844 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-21 04:08:36,895 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-21 04:08:36,900 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-21 04:08:36,919 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2022-07-21 04:08:36,920 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2022-07-21 04:08:36,920 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2022-07-21 04:08:36,921 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2022-07-21 04:08:36,921 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2022-07-21 04:08:36,921 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2022-07-21 04:08:36,977 INFO L234 CfgBuilder]: Building ICFG [2022-07-21 04:08:36,978 INFO L260 CfgBuilder]: Building CFG for each procedure with an implementation [2022-07-21 04:08:37,116 INFO L275 CfgBuilder]: Performing block encoding [2022-07-21 04:08:37,120 INFO L294 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2022-07-21 04:08:37,120 INFO L299 CfgBuilder]: Removed 1 assume(true) statements. [2022-07-21 04:08:37,122 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 21.07 04:08:37 BoogieIcfgContainer [2022-07-21 04:08:37,122 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2022-07-21 04:08:37,136 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2022-07-21 04:08:37,136 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2022-07-21 04:08:37,139 INFO L275 PluginConnector]: TraceAbstraction initialized [2022-07-21 04:08:37,139 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 21.07 04:08:36" (1/3) ... [2022-07-21 04:08:37,139 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@3f3ecf46 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 21.07 04:08:37, skipping insertion in model container [2022-07-21 04:08:37,139 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.07 04:08:36" (2/3) ... [2022-07-21 04:08:37,140 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@3f3ecf46 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 21.07 04:08:37, skipping insertion in model container [2022-07-21 04:08:37,140 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 21.07 04:08:37" (3/3) ... [2022-07-21 04:08:37,141 INFO L111 eAbstractionObserver]: Analyzing ICFG ps4-ll_unwindbound10.c [2022-07-21 04:08:37,176 INFO L201 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2022-07-21 04:08:37,177 INFO L160 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2022-07-21 04:08:37,220 INFO L356 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2022-07-21 04:08:37,225 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@617aa579, mLbeIndependenceSettings=de.uni_freiburg.informatik.ultimate.lib.tracecheckerutils.partialorder.independence.IndependenceSettings@426aa0b2 [2022-07-21 04:08:37,225 INFO L358 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2022-07-21 04:08:37,228 INFO L276 IsEmpty]: Start isEmpty. Operand has 18 states, 12 states have (on average 1.4166666666666667) internal successors, (17), 13 states have internal predecessors, (17), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2022-07-21 04:08:37,233 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 8 [2022-07-21 04:08:37,234 INFO L187 NwaCegarLoop]: Found error trace [2022-07-21 04:08:37,234 INFO L195 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1] [2022-07-21 04:08:37,235 INFO L420 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-21 04:08:37,238 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-21 04:08:37,238 INFO L85 PathProgramCache]: Analyzing trace with hash 1819788390, now seen corresponding path program 1 times [2022-07-21 04:08:37,245 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-21 04:08:37,245 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [80935260] [2022-07-21 04:08:37,246 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-21 04:08:37,246 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-21 04:08:37,325 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-21 04:08:37,354 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-07-21 04:08:37,355 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-21 04:08:37,356 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [80935260] [2022-07-21 04:08:37,357 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [80935260] provided 1 perfect and 0 imperfect interpolant sequences [2022-07-21 04:08:37,357 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-07-21 04:08:37,358 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2022-07-21 04:08:37,359 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [478697696] [2022-07-21 04:08:37,359 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-07-21 04:08:37,363 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2022-07-21 04:08:37,364 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-21 04:08:37,384 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2022-07-21 04:08:37,386 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2022-07-21 04:08:37,388 INFO L87 Difference]: Start difference. First operand has 18 states, 12 states have (on average 1.4166666666666667) internal successors, (17), 13 states have internal predecessors, (17), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) Second operand has 2 states, 2 states have (on average 3.0) internal successors, (6), 2 states have internal predecessors, (6), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-07-21 04:08:37,402 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-21 04:08:37,402 INFO L93 Difference]: Finished difference Result 34 states and 47 transitions. [2022-07-21 04:08:37,403 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2022-07-21 04:08:37,404 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 3.0) internal successors, (6), 2 states have internal predecessors, (6), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 7 [2022-07-21 04:08:37,404 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-21 04:08:37,408 INFO L225 Difference]: With dead ends: 34 [2022-07-21 04:08:37,409 INFO L226 Difference]: Without dead ends: 14 [2022-07-21 04:08:37,411 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 2 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 0 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2022-07-21 04:08:37,414 INFO L413 NwaCegarLoop]: 21 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, 21 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-21 04:08:37,414 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 21 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 0 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-07-21 04:08:37,425 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 14 states. [2022-07-21 04:08:37,435 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 14 to 14. [2022-07-21 04:08:37,436 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 14 states, 9 states have (on average 1.3333333333333333) internal successors, (12), 10 states have internal predecessors, (12), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2022-07-21 04:08:37,437 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 14 states to 14 states and 17 transitions. [2022-07-21 04:08:37,438 INFO L78 Accepts]: Start accepts. Automaton has 14 states and 17 transitions. Word has length 7 [2022-07-21 04:08:37,438 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-21 04:08:37,438 INFO L495 AbstractCegarLoop]: Abstraction has 14 states and 17 transitions. [2022-07-21 04:08:37,439 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 2 states have (on average 3.0) internal successors, (6), 2 states have internal predecessors, (6), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-07-21 04:08:37,439 INFO L276 IsEmpty]: Start isEmpty. Operand 14 states and 17 transitions. [2022-07-21 04:08:37,440 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 9 [2022-07-21 04:08:37,440 INFO L187 NwaCegarLoop]: Found error trace [2022-07-21 04:08:37,440 INFO L195 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1] [2022-07-21 04:08:37,440 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2022-07-21 04:08:37,440 INFO L420 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-21 04:08:37,442 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-21 04:08:37,442 INFO L85 PathProgramCache]: Analyzing trace with hash 178441499, now seen corresponding path program 1 times [2022-07-21 04:08:37,442 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-21 04:08:37,442 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1936927738] [2022-07-21 04:08:37,443 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-21 04:08:37,443 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-21 04:08:37,467 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-07-21 04:08:37,468 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [13033533] [2022-07-21 04:08:37,468 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-21 04:08:37,468 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-21 04:08:37,468 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-21 04:08:37,472 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-21 04:08:37,501 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-21 04:08:37,521 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-21 04:08:37,523 INFO L263 TraceCheckSpWp]: Trace formula consists of 49 conjuncts, 3 conjunts are in the unsatisfiable core [2022-07-21 04:08:37,525 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-21 04:08:37,585 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-07-21 04:08:37,585 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-07-21 04:08:37,586 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-21 04:08:37,586 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1936927738] [2022-07-21 04:08:37,586 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-07-21 04:08:37,586 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [13033533] [2022-07-21 04:08:37,586 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [13033533] provided 1 perfect and 0 imperfect interpolant sequences [2022-07-21 04:08:37,586 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-07-21 04:08:37,586 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2022-07-21 04:08:37,587 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [769606807] [2022-07-21 04:08:37,587 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-07-21 04:08:37,587 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2022-07-21 04:08:37,587 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-21 04:08:37,588 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2022-07-21 04:08:37,588 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2022-07-21 04:08:37,588 INFO L87 Difference]: Start difference. First operand 14 states and 17 transitions. Second operand has 4 states, 4 states have (on average 1.75) internal successors, (7), 3 states have internal predecessors, (7), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-07-21 04:08:37,598 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-21 04:08:37,598 INFO L93 Difference]: Finished difference Result 24 states and 28 transitions. [2022-07-21 04:08:37,598 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2022-07-21 04:08:37,598 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 1.75) internal successors, (7), 3 states have internal predecessors, (7), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 8 [2022-07-21 04:08:37,598 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-21 04:08:37,599 INFO L225 Difference]: With dead ends: 24 [2022-07-21 04:08:37,599 INFO L226 Difference]: Without dead ends: 16 [2022-07-21 04:08:37,599 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 7 GetRequests, 5 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2022-07-21 04:08:37,600 INFO L413 NwaCegarLoop]: 15 mSDtfsCounter, 0 mSDsluCounter, 26 mSDsCounter, 0 mSdLazyCounter, 8 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 41 SdHoareTripleChecker+Invalid, 8 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 8 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-07-21 04:08:37,600 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 41 Invalid, 8 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 8 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-07-21 04:08:37,601 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 16 states. [2022-07-21 04:08:37,602 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 16 to 16. [2022-07-21 04:08:37,603 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 16 states, 11 states have (on average 1.2727272727272727) internal successors, (14), 12 states have internal predecessors, (14), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2022-07-21 04:08:37,603 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 16 states to 16 states and 19 transitions. [2022-07-21 04:08:37,603 INFO L78 Accepts]: Start accepts. Automaton has 16 states and 19 transitions. Word has length 8 [2022-07-21 04:08:37,603 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-21 04:08:37,603 INFO L495 AbstractCegarLoop]: Abstraction has 16 states and 19 transitions. [2022-07-21 04:08:37,603 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 1.75) internal successors, (7), 3 states have internal predecessors, (7), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-07-21 04:08:37,603 INFO L276 IsEmpty]: Start isEmpty. Operand 16 states and 19 transitions. [2022-07-21 04:08:37,604 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 9 [2022-07-21 04:08:37,604 INFO L187 NwaCegarLoop]: Found error trace [2022-07-21 04:08:37,604 INFO L195 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1] [2022-07-21 04:08:37,622 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Forceful destruction successful, exit code 0 [2022-07-21 04:08:37,804 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-21 04:08:37,805 INFO L420 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-21 04:08:37,805 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-21 04:08:37,805 INFO L85 PathProgramCache]: Analyzing trace with hash 180228959, now seen corresponding path program 1 times [2022-07-21 04:08:37,805 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-21 04:08:37,805 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [814178411] [2022-07-21 04:08:37,805 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-21 04:08:37,805 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-21 04:08:37,812 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-07-21 04:08:37,812 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1711021915] [2022-07-21 04:08:37,812 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-21 04:08:37,812 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-21 04:08:37,813 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-21 04:08:37,815 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-21 04:08:37,818 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-21 04:08:37,849 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-21 04:08:37,849 INFO L263 TraceCheckSpWp]: Trace formula consists of 49 conjuncts, 7 conjunts are in the unsatisfiable core [2022-07-21 04:08:37,851 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-21 04:08:37,895 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-07-21 04:08:37,895 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-07-21 04:08:37,895 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-21 04:08:37,895 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [814178411] [2022-07-21 04:08:37,895 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-07-21 04:08:37,896 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1711021915] [2022-07-21 04:08:37,896 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1711021915] provided 1 perfect and 0 imperfect interpolant sequences [2022-07-21 04:08:37,896 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-07-21 04:08:37,896 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-07-21 04:08:37,896 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [131567732] [2022-07-21 04:08:37,896 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-07-21 04:08:37,896 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-07-21 04:08:37,896 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-21 04:08:37,897 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-07-21 04:08:37,897 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-07-21 04:08:37,897 INFO L87 Difference]: Start difference. First operand 16 states and 19 transitions. Second operand has 5 states, 5 states have (on average 1.4) internal successors, (7), 4 states have internal predecessors, (7), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-07-21 04:08:37,971 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-21 04:08:37,972 INFO L93 Difference]: Finished difference Result 26 states and 31 transitions. [2022-07-21 04:08:37,972 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-07-21 04:08:37,972 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 1.4) internal successors, (7), 4 states have internal predecessors, (7), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 8 [2022-07-21 04:08:37,972 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-21 04:08:37,973 INFO L225 Difference]: With dead ends: 26 [2022-07-21 04:08:37,973 INFO L226 Difference]: Without dead ends: 22 [2022-07-21 04:08:37,973 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 8 GetRequests, 4 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-21 04:08:37,974 INFO L413 NwaCegarLoop]: 15 mSDtfsCounter, 6 mSDsluCounter, 33 mSDsCounter, 0 mSdLazyCounter, 28 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 8 SdHoareTripleChecker+Valid, 48 SdHoareTripleChecker+Invalid, 30 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 28 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-07-21 04:08:37,974 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [8 Valid, 48 Invalid, 30 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 28 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-07-21 04:08:37,975 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 22 states. [2022-07-21 04:08:37,978 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 22 to 22. [2022-07-21 04:08:37,978 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 22 states, 15 states have (on average 1.2) internal successors, (18), 16 states have internal predecessors, (18), 4 states have call successors, (4), 2 states have call predecessors, (4), 2 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2022-07-21 04:08:37,978 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 22 states to 22 states and 25 transitions. [2022-07-21 04:08:37,979 INFO L78 Accepts]: Start accepts. Automaton has 22 states and 25 transitions. Word has length 8 [2022-07-21 04:08:37,979 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-21 04:08:37,979 INFO L495 AbstractCegarLoop]: Abstraction has 22 states and 25 transitions. [2022-07-21 04:08:37,979 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 1.4) internal successors, (7), 4 states have internal predecessors, (7), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-07-21 04:08:37,979 INFO L276 IsEmpty]: Start isEmpty. Operand 22 states and 25 transitions. [2022-07-21 04:08:37,979 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 17 [2022-07-21 04:08:37,979 INFO L187 NwaCegarLoop]: Found error trace [2022-07-21 04:08:37,980 INFO L195 NwaCegarLoop]: trace histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-21 04:08:38,006 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2022-07-21 04:08:38,180 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-21 04:08:38,180 INFO L420 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-21 04:08:38,181 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-21 04:08:38,181 INFO L85 PathProgramCache]: Analyzing trace with hash 823572993, now seen corresponding path program 1 times [2022-07-21 04:08:38,181 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-21 04:08:38,181 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [819866652] [2022-07-21 04:08:38,181 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-21 04:08:38,182 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-21 04:08:38,190 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-07-21 04:08:38,190 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2053743101] [2022-07-21 04:08:38,190 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-21 04:08:38,191 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-21 04:08:38,191 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-21 04:08:38,192 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-21 04:08:38,193 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-21 04:08:38,224 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-21 04:08:38,225 INFO L263 TraceCheckSpWp]: Trace formula consists of 70 conjuncts, 5 conjunts are in the unsatisfiable core [2022-07-21 04:08:38,226 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-21 04:08:38,269 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 2 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-07-21 04:08:38,270 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-21 04:08:38,321 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 2 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-07-21 04:08:38,321 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-21 04:08:38,321 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [819866652] [2022-07-21 04:08:38,321 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-07-21 04:08:38,322 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2053743101] [2022-07-21 04:08:38,322 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2053743101] provided 0 perfect and 2 imperfect interpolant sequences [2022-07-21 04:08:38,322 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-07-21 04:08:38,322 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 5] total 8 [2022-07-21 04:08:38,322 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2065088113] [2022-07-21 04:08:38,322 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-07-21 04:08:38,323 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2022-07-21 04:08:38,323 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-21 04:08:38,324 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2022-07-21 04:08:38,325 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=20, Invalid=36, Unknown=0, NotChecked=0, Total=56 [2022-07-21 04:08:38,325 INFO L87 Difference]: Start difference. First operand 22 states and 25 transitions. Second operand has 8 states, 8 states have (on average 2.875) internal successors, (23), 8 states have internal predecessors, (23), 3 states have call successors, (3), 3 states have call predecessors, (3), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2022-07-21 04:08:38,396 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-21 04:08:38,396 INFO L93 Difference]: Finished difference Result 56 states and 66 transitions. [2022-07-21 04:08:38,397 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2022-07-21 04:08:38,397 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 8 states have (on average 2.875) internal successors, (23), 8 states have internal predecessors, (23), 3 states have call successors, (3), 3 states have call predecessors, (3), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) Word has length 16 [2022-07-21 04:08:38,397 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-21 04:08:38,398 INFO L225 Difference]: With dead ends: 56 [2022-07-21 04:08:38,398 INFO L226 Difference]: Without dead ends: 48 [2022-07-21 04:08:38,398 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 33 GetRequests, 24 SyntacticMatches, 0 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 7 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=40, Invalid=70, Unknown=0, NotChecked=0, Total=110 [2022-07-21 04:08:38,399 INFO L413 NwaCegarLoop]: 20 mSDtfsCounter, 27 mSDsluCounter, 73 mSDsCounter, 0 mSdLazyCounter, 32 mSolverCounterSat, 7 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 27 SdHoareTripleChecker+Valid, 93 SdHoareTripleChecker+Invalid, 39 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 7 IncrementalHoareTripleChecker+Valid, 32 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-07-21 04:08:38,399 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [27 Valid, 93 Invalid, 39 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [7 Valid, 32 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-07-21 04:08:38,400 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 48 states. [2022-07-21 04:08:38,405 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 48 to 44. [2022-07-21 04:08:38,405 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 44 states, 29 states have (on average 1.2413793103448276) internal successors, (36), 32 states have internal predecessors, (36), 10 states have call successors, (10), 4 states have call predecessors, (10), 4 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2022-07-21 04:08:38,406 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 44 states to 44 states and 53 transitions. [2022-07-21 04:08:38,406 INFO L78 Accepts]: Start accepts. Automaton has 44 states and 53 transitions. Word has length 16 [2022-07-21 04:08:38,406 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-21 04:08:38,406 INFO L495 AbstractCegarLoop]: Abstraction has 44 states and 53 transitions. [2022-07-21 04:08:38,406 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 8 states have (on average 2.875) internal successors, (23), 8 states have internal predecessors, (23), 3 states have call successors, (3), 3 states have call predecessors, (3), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2022-07-21 04:08:38,406 INFO L276 IsEmpty]: Start isEmpty. Operand 44 states and 53 transitions. [2022-07-21 04:08:38,407 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 17 [2022-07-21 04:08:38,407 INFO L187 NwaCegarLoop]: Found error trace [2022-07-21 04:08:38,407 INFO L195 NwaCegarLoop]: trace histogram [2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-21 04:08:38,429 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-21 04:08:38,631 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-21 04:08:38,632 INFO L420 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-21 04:08:38,632 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-21 04:08:38,632 INFO L85 PathProgramCache]: Analyzing trace with hash 825360453, now seen corresponding path program 1 times [2022-07-21 04:08:38,632 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-21 04:08:38,632 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1413641920] [2022-07-21 04:08:38,632 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-21 04:08:38,632 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-21 04:08:38,638 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-07-21 04:08:38,638 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [762817313] [2022-07-21 04:08:38,638 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-21 04:08:38,638 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-21 04:08:38,639 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-21 04:08:38,640 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-21 04:08:38,641 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-21 04:08:38,667 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-21 04:08:38,668 INFO L263 TraceCheckSpWp]: Trace formula consists of 70 conjuncts, 11 conjunts are in the unsatisfiable core [2022-07-21 04:08:38,669 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-21 04:08:38,730 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 2 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-07-21 04:08:38,730 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-21 04:08:38,947 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2022-07-21 04:08:38,947 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-21 04:08:38,947 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1413641920] [2022-07-21 04:08:38,947 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-07-21 04:08:38,948 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [762817313] [2022-07-21 04:08:38,948 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [762817313] provided 1 perfect and 1 imperfect interpolant sequences [2022-07-21 04:08:38,948 INFO L184 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2022-07-21 04:08:38,948 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [6] total 7 [2022-07-21 04:08:38,948 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1981973060] [2022-07-21 04:08:38,948 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-07-21 04:08:38,949 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-07-21 04:08:38,949 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-21 04:08:38,949 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-07-21 04:08:38,949 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=29, Unknown=0, NotChecked=0, Total=42 [2022-07-21 04:08:38,950 INFO L87 Difference]: Start difference. First operand 44 states and 53 transitions. Second operand has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 1 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-07-21 04:08:38,975 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-21 04:08:38,975 INFO L93 Difference]: Finished difference Result 58 states and 66 transitions. [2022-07-21 04:08:38,976 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-07-21 04:08:38,976 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 1 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 16 [2022-07-21 04:08:38,976 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-21 04:08:38,977 INFO L225 Difference]: With dead ends: 58 [2022-07-21 04:08:38,977 INFO L226 Difference]: Without dead ends: 47 [2022-07-21 04:08:38,977 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 31 GetRequests, 23 SyntacticMatches, 2 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=17, Invalid=39, Unknown=0, NotChecked=0, Total=56 [2022-07-21 04:08:38,978 INFO L413 NwaCegarLoop]: 13 mSDtfsCounter, 7 mSDsluCounter, 24 mSDsCounter, 0 mSdLazyCounter, 21 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 8 SdHoareTripleChecker+Valid, 37 SdHoareTripleChecker+Invalid, 22 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 21 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-07-21 04:08:38,978 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [8 Valid, 37 Invalid, 22 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 21 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-07-21 04:08:38,979 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 47 states. [2022-07-21 04:08:38,983 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 47 to 41. [2022-07-21 04:08:38,983 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 41 states, 31 states have (on average 1.1290322580645162) internal successors, (35), 31 states have internal predecessors, (35), 5 states have call successors, (5), 5 states have call predecessors, (5), 4 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) [2022-07-21 04:08:38,984 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 41 states to 41 states and 44 transitions. [2022-07-21 04:08:38,984 INFO L78 Accepts]: Start accepts. Automaton has 41 states and 44 transitions. Word has length 16 [2022-07-21 04:08:38,984 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-21 04:08:38,984 INFO L495 AbstractCegarLoop]: Abstraction has 41 states and 44 transitions. [2022-07-21 04:08:38,984 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 1 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-07-21 04:08:38,984 INFO L276 IsEmpty]: Start isEmpty. Operand 41 states and 44 transitions. [2022-07-21 04:08:38,985 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 23 [2022-07-21 04:08:38,985 INFO L187 NwaCegarLoop]: Found error trace [2022-07-21 04:08:38,985 INFO L195 NwaCegarLoop]: trace histogram [3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1] [2022-07-21 04:08:39,015 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-21 04:08:39,199 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-21 04:08:39,199 INFO L420 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-21 04:08:39,200 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-21 04:08:39,200 INFO L85 PathProgramCache]: Analyzing trace with hash -1696898494, now seen corresponding path program 1 times [2022-07-21 04:08:39,200 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-21 04:08:39,200 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [262723651] [2022-07-21 04:08:39,200 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-21 04:08:39,200 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-21 04:08:39,221 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-07-21 04:08:39,222 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [589189856] [2022-07-21 04:08:39,222 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-21 04:08:39,222 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-21 04:08:39,222 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-21 04:08:39,223 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-21 04:08:39,224 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-21 04:08:39,255 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-21 04:08:39,257 INFO L263 TraceCheckSpWp]: Trace formula consists of 80 conjuncts, 12 conjunts are in the unsatisfiable core [2022-07-21 04:08:39,258 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-21 04:08:39,341 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 4 proven. 4 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2022-07-21 04:08:39,341 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-21 04:08:39,479 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-21 04:08:39,479 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [262723651] [2022-07-21 04:08:39,479 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-07-21 04:08:39,479 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [589189856] [2022-07-21 04:08:39,479 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [589189856] provided 0 perfect and 1 imperfect interpolant sequences [2022-07-21 04:08:39,479 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-07-21 04:08:39,479 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7] total 7 [2022-07-21 04:08:39,479 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [603678720] [2022-07-21 04:08:39,480 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2022-07-21 04:08:39,480 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2022-07-21 04:08:39,480 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-21 04:08:39,480 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2022-07-21 04:08:39,480 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=24, Invalid=66, Unknown=0, NotChecked=0, Total=90 [2022-07-21 04:08:39,480 INFO L87 Difference]: Start difference. First operand 41 states and 44 transitions. Second operand has 7 states, 6 states have (on average 2.3333333333333335) internal successors, (14), 6 states have internal predecessors, (14), 3 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2022-07-21 04:08:39,530 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-21 04:08:39,530 INFO L93 Difference]: Finished difference Result 46 states and 48 transitions. [2022-07-21 04:08:39,531 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2022-07-21 04:08:39,531 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 6 states have (on average 2.3333333333333335) internal successors, (14), 6 states have internal predecessors, (14), 3 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) Word has length 22 [2022-07-21 04:08:39,533 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-21 04:08:39,533 INFO L225 Difference]: With dead ends: 46 [2022-07-21 04:08:39,534 INFO L226 Difference]: Without dead ends: 41 [2022-07-21 04:08:39,534 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 37 GetRequests, 26 SyntacticMatches, 1 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=34, Invalid=98, Unknown=0, NotChecked=0, Total=132 [2022-07-21 04:08:39,536 INFO L413 NwaCegarLoop]: 18 mSDtfsCounter, 2 mSDsluCounter, 58 mSDsCounter, 0 mSdLazyCounter, 46 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 76 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-21 04:08:39,536 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [2 Valid, 76 Invalid, 46 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 46 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-07-21 04:08:39,537 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 41 states. [2022-07-21 04:08:39,546 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 41 to 41. [2022-07-21 04:08:39,546 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 41 states, 31 states have (on average 1.096774193548387) internal successors, (34), 31 states have internal predecessors, (34), 5 states have call successors, (5), 5 states have call predecessors, (5), 4 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) [2022-07-21 04:08:39,548 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 41 states to 41 states and 43 transitions. [2022-07-21 04:08:39,548 INFO L78 Accepts]: Start accepts. Automaton has 41 states and 43 transitions. Word has length 22 [2022-07-21 04:08:39,548 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-21 04:08:39,548 INFO L495 AbstractCegarLoop]: Abstraction has 41 states and 43 transitions. [2022-07-21 04:08:39,549 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 6 states have (on average 2.3333333333333335) internal successors, (14), 6 states have internal predecessors, (14), 3 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2022-07-21 04:08:39,549 INFO L276 IsEmpty]: Start isEmpty. Operand 41 states and 43 transitions. [2022-07-21 04:08:39,550 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 31 [2022-07-21 04:08:39,550 INFO L187 NwaCegarLoop]: Found error trace [2022-07-21 04:08:39,550 INFO L195 NwaCegarLoop]: trace histogram [4, 3, 3, 3, 3, 3, 3, 2, 1, 1, 1, 1, 1, 1] [2022-07-21 04:08:39,572 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Forceful destruction successful, exit code 0 [2022-07-21 04:08:39,763 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-21 04:08:39,763 INFO L420 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-21 04:08:39,764 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-21 04:08:39,764 INFO L85 PathProgramCache]: Analyzing trace with hash -47987544, now seen corresponding path program 2 times [2022-07-21 04:08:39,764 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-21 04:08:39,764 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1323285816] [2022-07-21 04:08:39,764 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-21 04:08:39,764 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-21 04:08:39,771 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-07-21 04:08:39,771 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1370758669] [2022-07-21 04:08:39,771 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-07-21 04:08:39,771 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-21 04:08:39,771 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-21 04:08:39,773 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-21 04:08:39,774 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-21 04:08:39,811 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-07-21 04:08:39,811 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-07-21 04:08:39,812 INFO L263 TraceCheckSpWp]: Trace formula consists of 101 conjuncts, 17 conjunts are in the unsatisfiable core [2022-07-21 04:08:39,813 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-21 04:08:39,920 INFO L134 CoverageAnalysis]: Checked inductivity of 30 backedges. 6 proven. 12 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2022-07-21 04:08:39,920 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-21 04:08:40,191 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-21 04:08:40,191 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1323285816] [2022-07-21 04:08:40,191 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-07-21 04:08:40,192 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1370758669] [2022-07-21 04:08:40,192 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1370758669] provided 0 perfect and 1 imperfect interpolant sequences [2022-07-21 04:08:40,192 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-07-21 04:08:40,192 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8] total 8 [2022-07-21 04:08:40,192 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [265381366] [2022-07-21 04:08:40,192 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2022-07-21 04:08:40,193 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2022-07-21 04:08:40,193 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-21 04:08:40,194 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2022-07-21 04:08:40,194 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=32, Invalid=100, Unknown=0, NotChecked=0, Total=132 [2022-07-21 04:08:40,194 INFO L87 Difference]: Start difference. First operand 41 states and 43 transitions. Second operand has 8 states, 7 states have (on average 2.4285714285714284) internal successors, (17), 7 states have internal predecessors, (17), 4 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2022-07-21 04:08:40,259 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-21 04:08:40,259 INFO L93 Difference]: Finished difference Result 46 states and 47 transitions. [2022-07-21 04:08:40,259 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2022-07-21 04:08:40,259 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 7 states have (on average 2.4285714285714284) internal successors, (17), 7 states have internal predecessors, (17), 4 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) Word has length 30 [2022-07-21 04:08:40,260 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-21 04:08:40,260 INFO L225 Difference]: With dead ends: 46 [2022-07-21 04:08:40,260 INFO L226 Difference]: Without dead ends: 41 [2022-07-21 04:08:40,260 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 53 GetRequests, 40 SyntacticMatches, 1 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 5 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=42, Invalid=140, Unknown=0, NotChecked=0, Total=182 [2022-07-21 04:08:40,261 INFO L413 NwaCegarLoop]: 22 mSDtfsCounter, 2 mSDsluCounter, 82 mSDsCounter, 0 mSdLazyCounter, 71 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 104 SdHoareTripleChecker+Invalid, 71 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 71 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-07-21 04:08:40,261 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [2 Valid, 104 Invalid, 71 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 71 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-07-21 04:08:40,261 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 41 states. [2022-07-21 04:08:40,265 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 41 to 41. [2022-07-21 04:08:40,266 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 41 states, 31 states have (on average 1.064516129032258) internal successors, (33), 31 states have internal predecessors, (33), 5 states have call successors, (5), 5 states have call predecessors, (5), 4 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) [2022-07-21 04:08:40,266 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 41 states to 41 states and 42 transitions. [2022-07-21 04:08:40,266 INFO L78 Accepts]: Start accepts. Automaton has 41 states and 42 transitions. Word has length 30 [2022-07-21 04:08:40,266 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-21 04:08:40,266 INFO L495 AbstractCegarLoop]: Abstraction has 41 states and 42 transitions. [2022-07-21 04:08:40,266 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 7 states have (on average 2.4285714285714284) internal successors, (17), 7 states have internal predecessors, (17), 4 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2022-07-21 04:08:40,266 INFO L276 IsEmpty]: Start isEmpty. Operand 41 states and 42 transitions. [2022-07-21 04:08:40,267 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 39 [2022-07-21 04:08:40,267 INFO L187 NwaCegarLoop]: Found error trace [2022-07-21 04:08:40,270 INFO L195 NwaCegarLoop]: trace histogram [5, 4, 4, 4, 4, 4, 4, 3, 1, 1, 1, 1, 1, 1] [2022-07-21 04:08:40,289 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-21 04:08:40,491 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-21 04:08:40,492 INFO L420 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-21 04:08:40,492 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-21 04:08:40,492 INFO L85 PathProgramCache]: Analyzing trace with hash -584163058, now seen corresponding path program 3 times [2022-07-21 04:08:40,492 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-21 04:08:40,492 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1443880323] [2022-07-21 04:08:40,492 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-21 04:08:40,492 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-21 04:08:40,498 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-07-21 04:08:40,499 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1321403534] [2022-07-21 04:08:40,499 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2022-07-21 04:08:40,499 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-21 04:08:40,499 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-21 04:08:40,501 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-21 04:08:40,502 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-21 04:08:40,540 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2022-07-21 04:08:40,540 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-07-21 04:08:40,541 INFO L263 TraceCheckSpWp]: Trace formula consists of 122 conjuncts, 20 conjunts are in the unsatisfiable core [2022-07-21 04:08:40,542 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-21 04:08:40,643 INFO L134 CoverageAnalysis]: Checked inductivity of 56 backedges. 8 proven. 24 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2022-07-21 04:08:40,643 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-21 04:08:40,732 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-21 04:08:40,732 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1443880323] [2022-07-21 04:08:40,732 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-07-21 04:08:40,732 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1321403534] [2022-07-21 04:08:40,732 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1321403534] provided 0 perfect and 1 imperfect interpolant sequences [2022-07-21 04:08:40,732 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-07-21 04:08:40,732 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9] total 9 [2022-07-21 04:08:40,733 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1123397983] [2022-07-21 04:08:40,733 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2022-07-21 04:08:40,733 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2022-07-21 04:08:40,733 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-21 04:08:40,734 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2022-07-21 04:08:40,734 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=30, Invalid=102, Unknown=0, NotChecked=0, Total=132 [2022-07-21 04:08:40,734 INFO L87 Difference]: Start difference. First operand 41 states and 42 transitions. Second operand has 9 states, 8 states have (on average 2.5) internal successors, (20), 8 states have internal predecessors, (20), 5 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) [2022-07-21 04:08:40,822 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-21 04:08:40,822 INFO L93 Difference]: Finished difference Result 48 states and 50 transitions. [2022-07-21 04:08:40,822 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2022-07-21 04:08:40,822 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 8 states have (on average 2.5) internal successors, (20), 8 states have internal predecessors, (20), 5 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) Word has length 38 [2022-07-21 04:08:40,823 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-21 04:08:40,823 INFO L225 Difference]: With dead ends: 48 [2022-07-21 04:08:40,823 INFO L226 Difference]: Without dead ends: 43 [2022-07-21 04:08:40,823 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 53 GetRequests, 40 SyntacticMatches, 1 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=40, Invalid=142, Unknown=0, NotChecked=0, Total=182 [2022-07-21 04:08:40,824 INFO L413 NwaCegarLoop]: 26 mSDtfsCounter, 2 mSDsluCounter, 110 mSDsCounter, 0 mSdLazyCounter, 102 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 136 SdHoareTripleChecker+Invalid, 102 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 102 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-07-21 04:08:40,824 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [2 Valid, 136 Invalid, 102 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 102 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-07-21 04:08:40,824 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 43 states. [2022-07-21 04:08:40,835 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 43 to 43. [2022-07-21 04:08:40,836 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 43 states, 32 states have (on average 1.0625) internal successors, (34), 32 states have internal predecessors, (34), 6 states have call successors, (6), 5 states have call predecessors, (6), 4 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) [2022-07-21 04:08:40,836 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 43 states to 43 states and 45 transitions. [2022-07-21 04:08:40,837 INFO L78 Accepts]: Start accepts. Automaton has 43 states and 45 transitions. Word has length 38 [2022-07-21 04:08:40,838 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-21 04:08:40,838 INFO L495 AbstractCegarLoop]: Abstraction has 43 states and 45 transitions. [2022-07-21 04:08:40,838 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 8 states have (on average 2.5) internal successors, (20), 8 states have internal predecessors, (20), 5 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) [2022-07-21 04:08:40,838 INFO L276 IsEmpty]: Start isEmpty. Operand 43 states and 45 transitions. [2022-07-21 04:08:40,839 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 41 [2022-07-21 04:08:40,840 INFO L187 NwaCegarLoop]: Found error trace [2022-07-21 04:08:40,840 INFO L195 NwaCegarLoop]: trace histogram [5, 5, 4, 4, 4, 4, 4, 4, 1, 1, 1, 1, 1, 1] [2022-07-21 04:08:40,865 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-21 04:08:41,051 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-21 04:08:41,051 INFO L420 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-21 04:08:41,052 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-21 04:08:41,052 INFO L85 PathProgramCache]: Analyzing trace with hash 2045303987, now seen corresponding path program 2 times [2022-07-21 04:08:41,052 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-21 04:08:41,052 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1037388846] [2022-07-21 04:08:41,052 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-21 04:08:41,052 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-21 04:08:41,058 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-07-21 04:08:41,061 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1540164029] [2022-07-21 04:08:41,061 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-07-21 04:08:41,061 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-21 04:08:41,061 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-21 04:08:41,062 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-21 04:08:41,063 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-21 04:08:41,095 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-07-21 04:08:41,095 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-07-21 04:08:41,096 INFO L263 TraceCheckSpWp]: Trace formula consists of 133 conjuncts, 11 conjunts are in the unsatisfiable core [2022-07-21 04:08:41,097 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-21 04:08:41,151 INFO L134 CoverageAnalysis]: Checked inductivity of 64 backedges. 8 proven. 56 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-07-21 04:08:41,151 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-21 04:08:41,225 INFO L134 CoverageAnalysis]: Checked inductivity of 64 backedges. 8 proven. 32 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2022-07-21 04:08:41,225 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-21 04:08:41,229 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1037388846] [2022-07-21 04:08:41,229 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-07-21 04:08:41,229 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1540164029] [2022-07-21 04:08:41,229 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1540164029] provided 0 perfect and 2 imperfect interpolant sequences [2022-07-21 04:08:41,229 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-07-21 04:08:41,229 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 8] total 14 [2022-07-21 04:08:41,231 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [815598602] [2022-07-21 04:08:41,231 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-07-21 04:08:41,232 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2022-07-21 04:08:41,234 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-21 04:08:41,234 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2022-07-21 04:08:41,234 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=71, Invalid=111, Unknown=0, NotChecked=0, Total=182 [2022-07-21 04:08:41,235 INFO L87 Difference]: Start difference. First operand 43 states and 45 transitions. Second operand has 14 states, 14 states have (on average 3.5714285714285716) internal successors, (50), 14 states have internal predecessors, (50), 9 states have call successors, (9), 6 states have call predecessors, (9), 5 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2022-07-21 04:08:41,391 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-21 04:08:41,392 INFO L93 Difference]: Finished difference Result 119 states and 125 transitions. [2022-07-21 04:08:41,392 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 22 states. [2022-07-21 04:08:41,392 INFO L78 Accepts]: Start accepts. Automaton has has 14 states, 14 states have (on average 3.5714285714285716) internal successors, (50), 14 states have internal predecessors, (50), 9 states have call successors, (9), 6 states have call predecessors, (9), 5 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) Word has length 40 [2022-07-21 04:08:41,393 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-21 04:08:41,395 INFO L225 Difference]: With dead ends: 119 [2022-07-21 04:08:41,395 INFO L226 Difference]: Without dead ends: 114 [2022-07-21 04:08:41,396 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 87 GetRequests, 66 SyntacticMatches, 0 SemanticMatches, 21 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 55 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=184, Invalid=322, Unknown=0, NotChecked=0, Total=506 [2022-07-21 04:08:41,398 INFO L413 NwaCegarLoop]: 22 mSDtfsCounter, 107 mSDsluCounter, 97 mSDsCounter, 0 mSdLazyCounter, 78 mSolverCounterSat, 35 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 107 SdHoareTripleChecker+Valid, 119 SdHoareTripleChecker+Invalid, 113 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 35 IncrementalHoareTripleChecker+Valid, 78 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-07-21 04:08:41,398 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [107 Valid, 119 Invalid, 113 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [35 Valid, 78 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-07-21 04:08:41,399 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 114 states. [2022-07-21 04:08:41,411 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 114 to 89. [2022-07-21 04:08:41,412 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 89 states, 67 states have (on average 1.1044776119402986) internal successors, (74), 67 states have internal predecessors, (74), 11 states have call successors, (11), 11 states have call predecessors, (11), 10 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2022-07-21 04:08:41,416 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 89 states to 89 states and 95 transitions. [2022-07-21 04:08:41,416 INFO L78 Accepts]: Start accepts. Automaton has 89 states and 95 transitions. Word has length 40 [2022-07-21 04:08:41,416 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-21 04:08:41,417 INFO L495 AbstractCegarLoop]: Abstraction has 89 states and 95 transitions. [2022-07-21 04:08:41,417 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 14 states, 14 states have (on average 3.5714285714285716) internal successors, (50), 14 states have internal predecessors, (50), 9 states have call successors, (9), 6 states have call predecessors, (9), 5 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2022-07-21 04:08:41,417 INFO L276 IsEmpty]: Start isEmpty. Operand 89 states and 95 transitions. [2022-07-21 04:08:41,420 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 47 [2022-07-21 04:08:41,421 INFO L187 NwaCegarLoop]: Found error trace [2022-07-21 04:08:41,421 INFO L195 NwaCegarLoop]: trace histogram [6, 5, 5, 5, 5, 5, 5, 4, 1, 1, 1, 1, 1, 1] [2022-07-21 04:08:41,447 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Forceful destruction successful, exit code 0 [2022-07-21 04:08:41,649 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-21 04:08:41,649 INFO L420 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-21 04:08:41,650 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-21 04:08:41,650 INFO L85 PathProgramCache]: Analyzing trace with hash -635357324, now seen corresponding path program 4 times [2022-07-21 04:08:41,650 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-21 04:08:41,650 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1943612460] [2022-07-21 04:08:41,650 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-21 04:08:41,650 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-21 04:08:41,655 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-07-21 04:08:41,656 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [794401945] [2022-07-21 04:08:41,656 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2022-07-21 04:08:41,656 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-21 04:08:41,656 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-21 04:08:41,657 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-21 04:08:41,658 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-21 04:08:41,761 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2022-07-21 04:08:41,761 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-07-21 04:08:41,763 INFO L263 TraceCheckSpWp]: Trace formula consists of 143 conjuncts, 24 conjunts are in the unsatisfiable core [2022-07-21 04:08:41,764 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-21 04:08:41,882 INFO L134 CoverageAnalysis]: Checked inductivity of 90 backedges. 10 proven. 40 refuted. 0 times theorem prover too weak. 40 trivial. 0 not checked. [2022-07-21 04:08:41,883 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-21 04:08:42,013 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-21 04:08:42,013 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1943612460] [2022-07-21 04:08:42,013 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-07-21 04:08:42,013 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [794401945] [2022-07-21 04:08:42,013 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [794401945] provided 0 perfect and 1 imperfect interpolant sequences [2022-07-21 04:08:42,013 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-07-21 04:08:42,013 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10] total 10 [2022-07-21 04:08:42,013 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1670373878] [2022-07-21 04:08:42,013 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2022-07-21 04:08:42,014 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2022-07-21 04:08:42,014 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-21 04:08:42,014 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2022-07-21 04:08:42,014 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=33, Invalid=123, Unknown=0, NotChecked=0, Total=156 [2022-07-21 04:08:42,014 INFO L87 Difference]: Start difference. First operand 89 states and 95 transitions. Second operand has 10 states, 9 states have (on average 2.5555555555555554) internal successors, (23), 9 states have internal predecessors, (23), 6 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) [2022-07-21 04:08:42,115 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-21 04:08:42,115 INFO L93 Difference]: Finished difference Result 94 states and 99 transitions. [2022-07-21 04:08:42,115 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2022-07-21 04:08:42,116 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 9 states have (on average 2.5555555555555554) internal successors, (23), 9 states have internal predecessors, (23), 6 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) Word has length 46 [2022-07-21 04:08:42,116 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-21 04:08:42,116 INFO L225 Difference]: With dead ends: 94 [2022-07-21 04:08:42,117 INFO L226 Difference]: Without dead ends: 89 [2022-07-21 04:08:42,117 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 61 GetRequests, 47 SyntacticMatches, 1 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=43, Invalid=167, Unknown=0, NotChecked=0, Total=210 [2022-07-21 04:08:42,117 INFO L413 NwaCegarLoop]: 30 mSDtfsCounter, 2 mSDsluCounter, 142 mSDsCounter, 0 mSdLazyCounter, 139 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 172 SdHoareTripleChecker+Invalid, 139 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 139 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-07-21 04:08:42,117 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [2 Valid, 172 Invalid, 139 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 139 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-07-21 04:08:42,118 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 89 states. [2022-07-21 04:08:42,122 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 89 to 89. [2022-07-21 04:08:42,122 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 89 states, 67 states have (on average 1.0895522388059702) internal successors, (73), 67 states have internal predecessors, (73), 11 states have call successors, (11), 11 states have call predecessors, (11), 10 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2022-07-21 04:08:42,123 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 89 states to 89 states and 94 transitions. [2022-07-21 04:08:42,123 INFO L78 Accepts]: Start accepts. Automaton has 89 states and 94 transitions. Word has length 46 [2022-07-21 04:08:42,123 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-21 04:08:42,123 INFO L495 AbstractCegarLoop]: Abstraction has 89 states and 94 transitions. [2022-07-21 04:08:42,123 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 9 states have (on average 2.5555555555555554) internal successors, (23), 9 states have internal predecessors, (23), 6 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) [2022-07-21 04:08:42,123 INFO L276 IsEmpty]: Start isEmpty. Operand 89 states and 94 transitions. [2022-07-21 04:08:42,124 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 55 [2022-07-21 04:08:42,124 INFO L187 NwaCegarLoop]: Found error trace [2022-07-21 04:08:42,124 INFO L195 NwaCegarLoop]: trace histogram [7, 6, 6, 6, 6, 6, 6, 5, 1, 1, 1, 1, 1, 1] [2022-07-21 04:08:42,137 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Forceful destruction successful, exit code 0 [2022-07-21 04:08:42,324 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-21 04:08:42,324 INFO L420 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-21 04:08:42,325 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-21 04:08:42,325 INFO L85 PathProgramCache]: Analyzing trace with hash 220350426, now seen corresponding path program 5 times [2022-07-21 04:08:42,325 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-21 04:08:42,325 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1625207572] [2022-07-21 04:08:42,325 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-21 04:08:42,325 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-21 04:08:42,330 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-07-21 04:08:42,331 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [633875723] [2022-07-21 04:08:42,331 INFO L93 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2022-07-21 04:08:42,331 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-21 04:08:42,331 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-21 04:08:42,335 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-21 04:08:42,338 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-21 04:08:42,516 INFO L228 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 6 check-sat command(s) [2022-07-21 04:08:42,517 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-07-21 04:08:42,518 INFO L263 TraceCheckSpWp]: Trace formula consists of 164 conjuncts, 28 conjunts are in the unsatisfiable core [2022-07-21 04:08:42,520 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-21 04:08:42,643 INFO L134 CoverageAnalysis]: Checked inductivity of 132 backedges. 12 proven. 60 refuted. 0 times theorem prover too weak. 60 trivial. 0 not checked. [2022-07-21 04:08:42,643 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-21 04:08:42,767 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-21 04:08:42,768 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1625207572] [2022-07-21 04:08:42,768 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-07-21 04:08:42,768 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [633875723] [2022-07-21 04:08:42,768 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [633875723] provided 0 perfect and 1 imperfect interpolant sequences [2022-07-21 04:08:42,768 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-07-21 04:08:42,768 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11] total 11 [2022-07-21 04:08:42,768 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [693261936] [2022-07-21 04:08:42,768 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2022-07-21 04:08:42,768 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 11 states [2022-07-21 04:08:42,768 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-21 04:08:42,769 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2022-07-21 04:08:42,769 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=36, Invalid=146, Unknown=0, NotChecked=0, Total=182 [2022-07-21 04:08:42,769 INFO L87 Difference]: Start difference. First operand 89 states and 94 transitions. Second operand has 11 states, 10 states have (on average 2.6) internal successors, (26), 10 states have internal predecessors, (26), 7 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2022-07-21 04:08:42,887 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-21 04:08:42,887 INFO L93 Difference]: Finished difference Result 94 states and 98 transitions. [2022-07-21 04:08:42,888 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2022-07-21 04:08:42,888 INFO L78 Accepts]: Start accepts. Automaton has has 11 states, 10 states have (on average 2.6) internal successors, (26), 10 states have internal predecessors, (26), 7 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) Word has length 54 [2022-07-21 04:08:42,888 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-21 04:08:42,889 INFO L225 Difference]: With dead ends: 94 [2022-07-21 04:08:42,889 INFO L226 Difference]: Without dead ends: 89 [2022-07-21 04:08:42,889 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 69 GetRequests, 54 SyntacticMatches, 1 SemanticMatches, 14 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=46, Invalid=194, Unknown=0, NotChecked=0, Total=240 [2022-07-21 04:08:42,889 INFO L413 NwaCegarLoop]: 34 mSDtfsCounter, 2 mSDsluCounter, 178 mSDsCounter, 0 mSdLazyCounter, 182 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 212 SdHoareTripleChecker+Invalid, 182 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 182 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-07-21 04:08:42,889 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [2 Valid, 212 Invalid, 182 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 182 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-07-21 04:08:42,890 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 89 states. [2022-07-21 04:08:42,894 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 89 to 89. [2022-07-21 04:08:42,894 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 89 states, 67 states have (on average 1.0746268656716418) internal successors, (72), 67 states have internal predecessors, (72), 11 states have call successors, (11), 11 states have call predecessors, (11), 10 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2022-07-21 04:08:42,894 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 89 states to 89 states and 93 transitions. [2022-07-21 04:08:42,895 INFO L78 Accepts]: Start accepts. Automaton has 89 states and 93 transitions. Word has length 54 [2022-07-21 04:08:42,895 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-21 04:08:42,895 INFO L495 AbstractCegarLoop]: Abstraction has 89 states and 93 transitions. [2022-07-21 04:08:42,895 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 11 states, 10 states have (on average 2.6) internal successors, (26), 10 states have internal predecessors, (26), 7 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2022-07-21 04:08:42,895 INFO L276 IsEmpty]: Start isEmpty. Operand 89 states and 93 transitions. [2022-07-21 04:08:42,895 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 63 [2022-07-21 04:08:42,895 INFO L187 NwaCegarLoop]: Found error trace [2022-07-21 04:08:42,895 INFO L195 NwaCegarLoop]: trace histogram [8, 7, 7, 7, 7, 7, 7, 6, 1, 1, 1, 1, 1, 1] [2022-07-21 04:08:42,908 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Forceful destruction successful, exit code 0 [2022-07-21 04:08:43,096 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-21 04:08:43,096 INFO L420 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-21 04:08:43,096 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-21 04:08:43,096 INFO L85 PathProgramCache]: Analyzing trace with hash 156734016, now seen corresponding path program 6 times [2022-07-21 04:08:43,096 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-21 04:08:43,096 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1225026831] [2022-07-21 04:08:43,097 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-21 04:08:43,097 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-21 04:08:43,102 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-07-21 04:08:43,102 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [427441513] [2022-07-21 04:08:43,102 INFO L93 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2022-07-21 04:08:43,102 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-21 04:08:43,102 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-21 04:08:43,105 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-21 04:08:43,105 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-21 04:08:43,221 INFO L228 tOrderPrioritization]: Assert order MIX_INSIDE_OUTSIDE issued 7 check-sat command(s) [2022-07-21 04:08:43,221 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-07-21 04:08:43,223 INFO L263 TraceCheckSpWp]: Trace formula consists of 185 conjuncts, 32 conjunts are in the unsatisfiable core [2022-07-21 04:08:43,224 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-21 04:08:43,366 INFO L134 CoverageAnalysis]: Checked inductivity of 182 backedges. 14 proven. 84 refuted. 0 times theorem prover too weak. 84 trivial. 0 not checked. [2022-07-21 04:08:43,367 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-21 04:08:43,566 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-21 04:08:43,566 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1225026831] [2022-07-21 04:08:43,566 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-07-21 04:08:43,566 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [427441513] [2022-07-21 04:08:43,567 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [427441513] provided 0 perfect and 1 imperfect interpolant sequences [2022-07-21 04:08:43,567 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-07-21 04:08:43,567 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12] total 12 [2022-07-21 04:08:43,567 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1602469525] [2022-07-21 04:08:43,567 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2022-07-21 04:08:43,567 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2022-07-21 04:08:43,567 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-21 04:08:43,567 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2022-07-21 04:08:43,568 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=39, Invalid=171, Unknown=0, NotChecked=0, Total=210 [2022-07-21 04:08:43,568 INFO L87 Difference]: Start difference. First operand 89 states and 93 transitions. Second operand has 12 states, 11 states have (on average 2.6363636363636362) internal successors, (29), 11 states have internal predecessors, (29), 8 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2022-07-21 04:08:43,711 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-21 04:08:43,711 INFO L93 Difference]: Finished difference Result 94 states and 97 transitions. [2022-07-21 04:08:43,711 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2022-07-21 04:08:43,711 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 11 states have (on average 2.6363636363636362) internal successors, (29), 11 states have internal predecessors, (29), 8 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) Word has length 62 [2022-07-21 04:08:43,712 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-21 04:08:43,712 INFO L225 Difference]: With dead ends: 94 [2022-07-21 04:08:43,712 INFO L226 Difference]: Without dead ends: 89 [2022-07-21 04:08:43,712 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 77 GetRequests, 61 SyntacticMatches, 1 SemanticMatches, 15 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=49, Invalid=223, Unknown=0, NotChecked=0, Total=272 [2022-07-21 04:08:43,713 INFO L413 NwaCegarLoop]: 38 mSDtfsCounter, 2 mSDsluCounter, 218 mSDsCounter, 0 mSdLazyCounter, 231 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 256 SdHoareTripleChecker+Invalid, 231 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 231 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-07-21 04:08:43,713 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [2 Valid, 256 Invalid, 231 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 231 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-07-21 04:08:43,713 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 89 states. [2022-07-21 04:08:43,717 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 89 to 89. [2022-07-21 04:08:43,717 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 89 states, 67 states have (on average 1.0597014925373134) internal successors, (71), 67 states have internal predecessors, (71), 11 states have call successors, (11), 11 states have call predecessors, (11), 10 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2022-07-21 04:08:43,717 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 89 states to 89 states and 92 transitions. [2022-07-21 04:08:43,718 INFO L78 Accepts]: Start accepts. Automaton has 89 states and 92 transitions. Word has length 62 [2022-07-21 04:08:43,718 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-21 04:08:43,718 INFO L495 AbstractCegarLoop]: Abstraction has 89 states and 92 transitions. [2022-07-21 04:08:43,718 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 11 states have (on average 2.6363636363636362) internal successors, (29), 11 states have internal predecessors, (29), 8 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2022-07-21 04:08:43,718 INFO L276 IsEmpty]: Start isEmpty. Operand 89 states and 92 transitions. [2022-07-21 04:08:43,718 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 71 [2022-07-21 04:08:43,718 INFO L187 NwaCegarLoop]: Found error trace [2022-07-21 04:08:43,718 INFO L195 NwaCegarLoop]: trace histogram [9, 8, 8, 8, 8, 8, 8, 7, 1, 1, 1, 1, 1, 1] [2022-07-21 04:08:43,724 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-21 04:08:43,922 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-21 04:08:43,923 INFO L420 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-21 04:08:43,923 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-21 04:08:43,923 INFO L85 PathProgramCache]: Analyzing trace with hash -605612378, now seen corresponding path program 7 times [2022-07-21 04:08:43,923 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-21 04:08:43,923 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [401471178] [2022-07-21 04:08:43,923 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-21 04:08:43,923 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-21 04:08:43,929 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-07-21 04:08:43,929 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [597704116] [2022-07-21 04:08:43,929 INFO L93 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2022-07-21 04:08:43,929 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-21 04:08:43,929 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-21 04:08:43,930 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-21 04:08:43,931 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-21 04:08:44,350 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-21 04:08:44,351 INFO L263 TraceCheckSpWp]: Trace formula consists of 206 conjuncts, 36 conjunts are in the unsatisfiable core [2022-07-21 04:08:44,353 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-21 04:08:44,501 INFO L134 CoverageAnalysis]: Checked inductivity of 240 backedges. 16 proven. 112 refuted. 0 times theorem prover too weak. 112 trivial. 0 not checked. [2022-07-21 04:08:44,501 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-21 04:08:44,594 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-21 04:08:44,595 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [401471178] [2022-07-21 04:08:44,595 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-07-21 04:08:44,595 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [597704116] [2022-07-21 04:08:44,595 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [597704116] provided 0 perfect and 1 imperfect interpolant sequences [2022-07-21 04:08:44,595 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-07-21 04:08:44,595 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13] total 13 [2022-07-21 04:08:44,595 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [550751730] [2022-07-21 04:08:44,595 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2022-07-21 04:08:44,595 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 13 states [2022-07-21 04:08:44,595 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-21 04:08:44,596 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2022-07-21 04:08:44,596 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=42, Invalid=198, Unknown=0, NotChecked=0, Total=240 [2022-07-21 04:08:44,596 INFO L87 Difference]: Start difference. First operand 89 states and 92 transitions. Second operand has 13 states, 12 states have (on average 2.6666666666666665) internal successors, (32), 12 states have internal predecessors, (32), 9 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2022-07-21 04:08:44,773 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-21 04:08:44,774 INFO L93 Difference]: Finished difference Result 94 states and 96 transitions. [2022-07-21 04:08:44,774 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2022-07-21 04:08:44,774 INFO L78 Accepts]: Start accepts. Automaton has has 13 states, 12 states have (on average 2.6666666666666665) internal successors, (32), 12 states have internal predecessors, (32), 9 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) Word has length 70 [2022-07-21 04:08:44,774 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-21 04:08:44,776 INFO L225 Difference]: With dead ends: 94 [2022-07-21 04:08:44,776 INFO L226 Difference]: Without dead ends: 89 [2022-07-21 04:08:44,776 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 85 GetRequests, 68 SyntacticMatches, 1 SemanticMatches, 16 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=52, Invalid=254, Unknown=0, NotChecked=0, Total=306 [2022-07-21 04:08:44,777 INFO L413 NwaCegarLoop]: 42 mSDtfsCounter, 2 mSDsluCounter, 262 mSDsCounter, 0 mSdLazyCounter, 286 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 304 SdHoareTripleChecker+Invalid, 286 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 286 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-07-21 04:08:44,777 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [2 Valid, 304 Invalid, 286 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 286 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-07-21 04:08:44,777 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 89 states. [2022-07-21 04:08:44,781 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 89 to 89. [2022-07-21 04:08:44,781 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 89 states, 67 states have (on average 1.044776119402985) internal successors, (70), 67 states have internal predecessors, (70), 11 states have call successors, (11), 11 states have call predecessors, (11), 10 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2022-07-21 04:08:44,782 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 89 states to 89 states and 91 transitions. [2022-07-21 04:08:44,782 INFO L78 Accepts]: Start accepts. Automaton has 89 states and 91 transitions. Word has length 70 [2022-07-21 04:08:44,782 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-21 04:08:44,782 INFO L495 AbstractCegarLoop]: Abstraction has 89 states and 91 transitions. [2022-07-21 04:08:44,782 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 13 states, 12 states have (on average 2.6666666666666665) internal successors, (32), 12 states have internal predecessors, (32), 9 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2022-07-21 04:08:44,782 INFO L276 IsEmpty]: Start isEmpty. Operand 89 states and 91 transitions. [2022-07-21 04:08:44,783 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 79 [2022-07-21 04:08:44,784 INFO L187 NwaCegarLoop]: Found error trace [2022-07-21 04:08:44,784 INFO L195 NwaCegarLoop]: trace histogram [10, 9, 9, 9, 9, 9, 9, 8, 1, 1, 1, 1, 1, 1] [2022-07-21 04:08:44,793 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-21 04:08:44,989 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-21 04:08:44,989 INFO L420 AbstractCegarLoop]: === Iteration 14 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-21 04:08:44,990 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-21 04:08:44,990 INFO L85 PathProgramCache]: Analyzing trace with hash 200725772, now seen corresponding path program 8 times [2022-07-21 04:08:44,990 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-21 04:08:44,990 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1630847492] [2022-07-21 04:08:44,990 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-21 04:08:44,990 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-21 04:08:44,995 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-07-21 04:08:44,995 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1544859494] [2022-07-21 04:08:44,995 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-07-21 04:08:44,995 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-21 04:08:44,996 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-21 04:08:44,996 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-21 04:08:44,997 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-21 04:08:45,385 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-07-21 04:08:45,385 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-07-21 04:08:45,387 INFO L263 TraceCheckSpWp]: Trace formula consists of 227 conjuncts, 40 conjunts are in the unsatisfiable core [2022-07-21 04:08:45,388 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-21 04:08:45,575 INFO L134 CoverageAnalysis]: Checked inductivity of 306 backedges. 18 proven. 144 refuted. 0 times theorem prover too weak. 144 trivial. 0 not checked. [2022-07-21 04:08:45,575 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-21 04:08:45,683 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-21 04:08:45,683 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1630847492] [2022-07-21 04:08:45,683 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-07-21 04:08:45,683 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1544859494] [2022-07-21 04:08:45,683 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1544859494] provided 0 perfect and 1 imperfect interpolant sequences [2022-07-21 04:08:45,683 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-07-21 04:08:45,683 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [14] total 14 [2022-07-21 04:08:45,683 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1297116784] [2022-07-21 04:08:45,683 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2022-07-21 04:08:45,684 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2022-07-21 04:08:45,684 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-21 04:08:45,684 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2022-07-21 04:08:45,684 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=45, Invalid=227, Unknown=0, NotChecked=0, Total=272 [2022-07-21 04:08:45,684 INFO L87 Difference]: Start difference. First operand 89 states and 91 transitions. Second operand has 14 states, 13 states have (on average 2.6923076923076925) internal successors, (35), 13 states have internal predecessors, (35), 10 states have call successors, (10), 2 states have call predecessors, (10), 1 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2022-07-21 04:08:45,880 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-21 04:08:45,880 INFO L93 Difference]: Finished difference Result 94 states and 95 transitions. [2022-07-21 04:08:45,887 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2022-07-21 04:08:45,887 INFO L78 Accepts]: Start accepts. Automaton has has 14 states, 13 states have (on average 2.6923076923076925) internal successors, (35), 13 states have internal predecessors, (35), 10 states have call successors, (10), 2 states have call predecessors, (10), 1 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) Word has length 78 [2022-07-21 04:08:45,887 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-21 04:08:45,888 INFO L225 Difference]: With dead ends: 94 [2022-07-21 04:08:45,888 INFO L226 Difference]: Without dead ends: 89 [2022-07-21 04:08:45,888 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 93 GetRequests, 75 SyntacticMatches, 1 SemanticMatches, 17 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=55, Invalid=287, Unknown=0, NotChecked=0, Total=342 [2022-07-21 04:08:45,889 INFO L413 NwaCegarLoop]: 46 mSDtfsCounter, 2 mSDsluCounter, 310 mSDsCounter, 0 mSdLazyCounter, 347 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 356 SdHoareTripleChecker+Invalid, 347 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 347 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2022-07-21 04:08:45,889 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [2 Valid, 356 Invalid, 347 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 347 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2022-07-21 04:08:45,889 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 89 states. [2022-07-21 04:08:45,893 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 89 to 89. [2022-07-21 04:08:45,893 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 89 states, 67 states have (on average 1.0298507462686568) internal successors, (69), 67 states have internal predecessors, (69), 11 states have call successors, (11), 11 states have call predecessors, (11), 10 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2022-07-21 04:08:45,893 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 89 states to 89 states and 90 transitions. [2022-07-21 04:08:45,893 INFO L78 Accepts]: Start accepts. Automaton has 89 states and 90 transitions. Word has length 78 [2022-07-21 04:08:45,894 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-21 04:08:45,894 INFO L495 AbstractCegarLoop]: Abstraction has 89 states and 90 transitions. [2022-07-21 04:08:45,894 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 14 states, 13 states have (on average 2.6923076923076925) internal successors, (35), 13 states have internal predecessors, (35), 10 states have call successors, (10), 2 states have call predecessors, (10), 1 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2022-07-21 04:08:45,894 INFO L276 IsEmpty]: Start isEmpty. Operand 89 states and 90 transitions. [2022-07-21 04:08:45,894 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 87 [2022-07-21 04:08:45,895 INFO L187 NwaCegarLoop]: Found error trace [2022-07-21 04:08:45,895 INFO L195 NwaCegarLoop]: trace histogram [11, 10, 10, 10, 10, 10, 10, 9, 1, 1, 1, 1, 1, 1] [2022-07-21 04:08:45,900 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-21 04:08:46,100 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-21 04:08:46,100 INFO L420 AbstractCegarLoop]: === Iteration 15 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-21 04:08:46,100 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-21 04:08:46,101 INFO L85 PathProgramCache]: Analyzing trace with hash -1699951246, now seen corresponding path program 9 times [2022-07-21 04:08:46,101 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-21 04:08:46,101 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [277989638] [2022-07-21 04:08:46,101 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-21 04:08:46,101 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-21 04:08:46,107 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-07-21 04:08:46,107 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [253149185] [2022-07-21 04:08:46,107 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2022-07-21 04:08:46,107 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-21 04:08:46,108 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-21 04:08:46,108 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-21 04:08:46,109 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-21 04:08:46,396 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 10 check-sat command(s) [2022-07-21 04:08:46,396 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-07-21 04:08:46,398 INFO L263 TraceCheckSpWp]: Trace formula consists of 248 conjuncts, 44 conjunts are in the unsatisfiable core [2022-07-21 04:08:46,400 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-21 04:08:46,617 INFO L134 CoverageAnalysis]: Checked inductivity of 380 backedges. 20 proven. 180 refuted. 0 times theorem prover too weak. 180 trivial. 0 not checked. [2022-07-21 04:08:46,617 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-21 04:08:46,773 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-21 04:08:46,773 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [277989638] [2022-07-21 04:08:46,773 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-07-21 04:08:46,773 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [253149185] [2022-07-21 04:08:46,773 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [253149185] provided 0 perfect and 1 imperfect interpolant sequences [2022-07-21 04:08:46,773 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-07-21 04:08:46,773 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [15] total 15 [2022-07-21 04:08:46,774 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1165397394] [2022-07-21 04:08:46,774 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2022-07-21 04:08:46,774 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 15 states [2022-07-21 04:08:46,774 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-21 04:08:46,774 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2022-07-21 04:08:46,774 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=48, Invalid=258, Unknown=0, NotChecked=0, Total=306 [2022-07-21 04:08:46,775 INFO L87 Difference]: Start difference. First operand 89 states and 90 transitions. Second operand has 15 states, 14 states have (on average 2.7142857142857144) internal successors, (38), 14 states have internal predecessors, (38), 11 states have call successors, (11), 2 states have call predecessors, (11), 1 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2022-07-21 04:08:47,000 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-21 04:08:47,000 INFO L93 Difference]: Finished difference Result 96 states and 98 transitions. [2022-07-21 04:08:47,001 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2022-07-21 04:08:47,001 INFO L78 Accepts]: Start accepts. Automaton has has 15 states, 14 states have (on average 2.7142857142857144) internal successors, (38), 14 states have internal predecessors, (38), 11 states have call successors, (11), 2 states have call predecessors, (11), 1 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) Word has length 86 [2022-07-21 04:08:47,001 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-21 04:08:47,002 INFO L225 Difference]: With dead ends: 96 [2022-07-21 04:08:47,002 INFO L226 Difference]: Without dead ends: 91 [2022-07-21 04:08:47,002 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 101 GetRequests, 82 SyntacticMatches, 1 SemanticMatches, 18 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=58, Invalid=322, Unknown=0, NotChecked=0, Total=380 [2022-07-21 04:08:47,002 INFO L413 NwaCegarLoop]: 50 mSDtfsCounter, 2 mSDsluCounter, 362 mSDsCounter, 0 mSdLazyCounter, 414 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 412 SdHoareTripleChecker+Invalid, 414 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 414 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2022-07-21 04:08:47,003 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [2 Valid, 412 Invalid, 414 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 414 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2022-07-21 04:08:47,003 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 91 states. [2022-07-21 04:08:47,009 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 91 to 91. [2022-07-21 04:08:47,010 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 91 states, 68 states have (on average 1.0294117647058822) internal successors, (70), 68 states have internal predecessors, (70), 12 states have call successors, (12), 11 states have call predecessors, (12), 10 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2022-07-21 04:08:47,010 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 91 states to 91 states and 93 transitions. [2022-07-21 04:08:47,010 INFO L78 Accepts]: Start accepts. Automaton has 91 states and 93 transitions. Word has length 86 [2022-07-21 04:08:47,010 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-21 04:08:47,010 INFO L495 AbstractCegarLoop]: Abstraction has 91 states and 93 transitions. [2022-07-21 04:08:47,010 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 15 states, 14 states have (on average 2.7142857142857144) internal successors, (38), 14 states have internal predecessors, (38), 11 states have call successors, (11), 2 states have call predecessors, (11), 1 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2022-07-21 04:08:47,010 INFO L276 IsEmpty]: Start isEmpty. Operand 91 states and 93 transitions. [2022-07-21 04:08:47,011 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 89 [2022-07-21 04:08:47,011 INFO L187 NwaCegarLoop]: Found error trace [2022-07-21 04:08:47,011 INFO L195 NwaCegarLoop]: trace histogram [11, 11, 10, 10, 10, 10, 10, 10, 1, 1, 1, 1, 1, 1] [2022-07-21 04:08:47,018 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Forceful destruction successful, exit code 0 [2022-07-21 04:08:47,216 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-21 04:08:47,217 INFO L420 AbstractCegarLoop]: === Iteration 16 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-21 04:08:47,217 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-21 04:08:47,217 INFO L85 PathProgramCache]: Analyzing trace with hash -780287977, now seen corresponding path program 3 times [2022-07-21 04:08:47,217 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-21 04:08:47,217 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1008898971] [2022-07-21 04:08:47,217 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-21 04:08:47,217 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-21 04:08:47,239 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-07-21 04:08:47,239 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1723644780] [2022-07-21 04:08:47,240 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2022-07-21 04:08:47,240 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-21 04:08:47,240 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-21 04:08:47,241 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-21 04:08:47,242 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-21 04:08:47,866 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 11 check-sat command(s) [2022-07-21 04:08:47,866 INFO L229 tOrderPrioritization]: Conjunction of SSA is sat [2022-07-21 04:08:47,866 INFO L352 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2022-07-21 04:08:47,897 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2022-07-21 04:08:47,941 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2022-07-21 04:08:47,941 INFO L271 BasicCegarLoop]: Counterexample is feasible [2022-07-21 04:08:47,942 INFO L805 garLoopResultBuilder]: Registering result UNSAFE for location __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION (0 of 1 remaining) [2022-07-21 04:08:47,955 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-21 04:08:48,156 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-21 04:08:48,159 INFO L356 BasicCegarLoop]: Path program histogram: [9, 3, 1, 1, 1, 1] [2022-07-21 04:08:48,161 INFO L176 ceAbstractionStarter]: Computing trace abstraction results [2022-07-21 04:08:48,202 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 21.07 04:08:48 BoogieIcfgContainer [2022-07-21 04:08:48,205 INFO L132 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2022-07-21 04:08:48,206 INFO L113 PluginConnector]: ------------------------Witness Printer---------------------------- [2022-07-21 04:08:48,206 INFO L271 PluginConnector]: Initializing Witness Printer... [2022-07-21 04:08:48,206 INFO L275 PluginConnector]: Witness Printer initialized [2022-07-21 04:08:48,207 INFO L185 PluginConnector]: Executing the observer RCFGCatcher from plugin Witness Printer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 21.07 04:08:37" (3/4) ... [2022-07-21 04:08:48,208 INFO L131 WitnessPrinter]: Generating witness for reachability counterexample [2022-07-21 04:08:48,248 INFO L141 WitnessManager]: Wrote witness to /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/witness.graphml [2022-07-21 04:08:48,248 INFO L132 PluginConnector]: ------------------------ END Witness Printer---------------------------- [2022-07-21 04:08:48,248 INFO L158 Benchmark]: Toolchain (without parser) took 11698.37ms. Allocated memory was 56.6MB in the beginning and 69.2MB in the end (delta: 12.6MB). Free memory was 35.6MB in the beginning and 23.5MB in the end (delta: 12.1MB). Peak memory consumption was 22.9MB. Max. memory is 16.1GB. [2022-07-21 04:08:48,249 INFO L158 Benchmark]: CDTParser took 0.29ms. Allocated memory is still 56.6MB. Free memory is still 38.6MB. There was no memory consumed. Max. memory is 16.1GB. [2022-07-21 04:08:48,249 INFO L158 Benchmark]: CACSL2BoogieTranslator took 224.10ms. Allocated memory is still 56.6MB. Free memory was 35.4MB in the beginning and 40.0MB in the end (delta: -4.6MB). Peak memory consumption was 12.6MB. Max. memory is 16.1GB. [2022-07-21 04:08:48,249 INFO L158 Benchmark]: Boogie Procedure Inliner took 22.14ms. Allocated memory is still 56.6MB. Free memory was 40.0MB in the beginning and 38.6MB in the end (delta: 1.5MB). There was no memory consumed. Max. memory is 16.1GB. [2022-07-21 04:08:48,249 INFO L158 Benchmark]: Boogie Preprocessor took 30.16ms. Allocated memory is still 56.6MB. Free memory was 38.6MB in the beginning and 37.6MB in the end (delta: 944.3kB). There was no memory consumed. Max. memory is 16.1GB. [2022-07-21 04:08:48,249 INFO L158 Benchmark]: RCFGBuilder took 303.88ms. Allocated memory is still 56.6MB. Free memory was 37.6MB in the beginning and 28.7MB in the end (delta: 8.9MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. [2022-07-21 04:08:48,250 INFO L158 Benchmark]: TraceAbstraction took 11068.88ms. Allocated memory was 56.6MB in the beginning and 69.2MB in the end (delta: 12.6MB). Free memory was 28.1MB in the beginning and 27.7MB in the end (delta: 407.0kB). Peak memory consumption was 13.6MB. Max. memory is 16.1GB. [2022-07-21 04:08:48,250 INFO L158 Benchmark]: Witness Printer took 42.42ms. Allocated memory is still 69.2MB. Free memory was 27.7MB in the beginning and 23.5MB in the end (delta: 4.2MB). Peak memory consumption was 4.2MB. Max. memory is 16.1GB. [2022-07-21 04:08:48,251 INFO L339 ainManager$Toolchain]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * CDTParser took 0.29ms. Allocated memory is still 56.6MB. Free memory is still 38.6MB. There was no memory consumed. Max. memory is 16.1GB. * CACSL2BoogieTranslator took 224.10ms. Allocated memory is still 56.6MB. Free memory was 35.4MB in the beginning and 40.0MB in the end (delta: -4.6MB). Peak memory consumption was 12.6MB. Max. memory is 16.1GB. * Boogie Procedure Inliner took 22.14ms. Allocated memory is still 56.6MB. Free memory was 40.0MB in the beginning and 38.6MB in the end (delta: 1.5MB). There was no memory consumed. Max. memory is 16.1GB. * Boogie Preprocessor took 30.16ms. Allocated memory is still 56.6MB. Free memory was 38.6MB in the beginning and 37.6MB in the end (delta: 944.3kB). There was no memory consumed. Max. memory is 16.1GB. * RCFGBuilder took 303.88ms. Allocated memory is still 56.6MB. Free memory was 37.6MB in the beginning and 28.7MB in the end (delta: 8.9MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. * TraceAbstraction took 11068.88ms. Allocated memory was 56.6MB in the beginning and 69.2MB in the end (delta: 12.6MB). Free memory was 28.1MB in the beginning and 27.7MB in the end (delta: 407.0kB). Peak memory consumption was 13.6MB. Max. memory is 16.1GB. * Witness Printer took 42.42ms. Allocated memory is still 69.2MB. Free memory was 27.7MB in the beginning and 23.5MB in the end (delta: 4.2MB). Peak memory consumption was 4.2MB. Max. memory is 16.1GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - StatisticsResult: ErrorAutomatonStatistics NumberErrorTraces: 0, NumberStatementsAllTraces: 0, NumberRelevantStatements: 0, 0.0s ErrorAutomatonConstructionTimeTotal, 0.0s FaulLocalizationTime, NumberStatementsFirstTrace: -1, TraceLengthAvg: 0, 0.0s ErrorAutomatonConstructionTimeAvg, 0.0s ErrorAutomatonDifferenceTimeAvg, 0.0s ErrorAutomatonDifferenceTimeTotal, NumberOfNoEnhancement: 0, NumberOfFiniteEnhancement: 0, NumberOfInfiniteEnhancement: 0 - CounterExampleResult [Line: 12]: a call to reach_error is reachable a call to reach_error is reachable We found a FailurePath: [L17] int counter = 0; VAL [counter=0] [L19] short k; [L20] long long y, x, c; [L21] k = __VERIFIER_nondet_short() [L23] y = 0 [L24] x = 0 [L25] c = 0 VAL [c=0, counter=0, k=11, x=0, y=0] [L27] EXPR counter++ VAL [c=0, counter=1, counter++=0, k=11, x=0, y=0] [L27] COND TRUE counter++<10 [L28] CALL __VERIFIER_assert(4*x - y*y*y*y - 2*y*y*y - y*y == 0) VAL [\old(cond)=1, counter=1] [L10] COND FALSE !(!(cond)) VAL [\old(cond)=1, cond=1, counter=1] [L28] RET __VERIFIER_assert(4*x - y*y*y*y - 2*y*y*y - y*y == 0) VAL [c=0, counter=1, k=11, x=0, y=0] [L30] COND FALSE !(!(c < k)) [L33] c = c + 1 [L34] y = y + 1 [L35] x = y * y * y + x VAL [c=1, counter=1, k=11, x=1, y=1] [L27] EXPR counter++ VAL [c=1, counter=2, counter++=1, k=11, x=1, y=1] [L27] COND TRUE counter++<10 [L28] CALL __VERIFIER_assert(4*x - y*y*y*y - 2*y*y*y - y*y == 0) VAL [\old(cond)=1, counter=2] [L10] COND FALSE !(!(cond)) VAL [\old(cond)=1, cond=1, counter=2] [L28] RET __VERIFIER_assert(4*x - y*y*y*y - 2*y*y*y - y*y == 0) VAL [c=1, counter=2, k=11, x=1, y=1] [L30] COND FALSE !(!(c < k)) [L33] c = c + 1 [L34] y = y + 1 [L35] x = y * y * y + x VAL [c=2, counter=2, k=11, x=9, y=2] [L27] EXPR counter++ VAL [c=2, counter=3, counter++=2, k=11, x=9, y=2] [L27] COND TRUE counter++<10 [L28] CALL __VERIFIER_assert(4*x - y*y*y*y - 2*y*y*y - y*y == 0) VAL [\old(cond)=1, counter=3] [L10] COND FALSE !(!(cond)) VAL [\old(cond)=1, cond=1, counter=3] [L28] RET __VERIFIER_assert(4*x - y*y*y*y - 2*y*y*y - y*y == 0) VAL [c=2, counter=3, k=11, x=9, y=2] [L30] COND FALSE !(!(c < k)) [L33] c = c + 1 [L34] y = y + 1 [L35] x = y * y * y + x VAL [c=3, counter=3, k=11, x=36, y=3] [L27] EXPR counter++ VAL [c=3, counter=4, counter++=3, k=11, x=36, y=3] [L27] COND TRUE counter++<10 [L28] CALL __VERIFIER_assert(4*x - y*y*y*y - 2*y*y*y - y*y == 0) VAL [\old(cond)=1, counter=4] [L10] COND FALSE !(!(cond)) VAL [\old(cond)=1, cond=1, counter=4] [L28] RET __VERIFIER_assert(4*x - y*y*y*y - 2*y*y*y - y*y == 0) VAL [c=3, counter=4, k=11, x=36, y=3] [L30] COND FALSE !(!(c < k)) [L33] c = c + 1 [L34] y = y + 1 [L35] x = y * y * y + x VAL [c=4, counter=4, k=11, x=100, y=4] [L27] EXPR counter++ VAL [c=4, counter=5, counter++=4, k=11, x=100, y=4] [L27] COND TRUE counter++<10 [L28] CALL __VERIFIER_assert(4*x - y*y*y*y - 2*y*y*y - y*y == 0) VAL [\old(cond)=1, counter=5] [L10] COND FALSE !(!(cond)) VAL [\old(cond)=1, cond=1, counter=5] [L28] RET __VERIFIER_assert(4*x - y*y*y*y - 2*y*y*y - y*y == 0) VAL [c=4, counter=5, k=11, x=100, y=4] [L30] COND FALSE !(!(c < k)) [L33] c = c + 1 [L34] y = y + 1 [L35] x = y * y * y + x VAL [c=5, counter=5, k=11, x=225, y=5] [L27] EXPR counter++ VAL [c=5, counter=6, counter++=5, k=11, x=225, y=5] [L27] COND TRUE counter++<10 [L28] CALL __VERIFIER_assert(4*x - y*y*y*y - 2*y*y*y - y*y == 0) VAL [\old(cond)=1, counter=6] [L10] COND FALSE !(!(cond)) VAL [\old(cond)=1, cond=1, counter=6] [L28] RET __VERIFIER_assert(4*x - y*y*y*y - 2*y*y*y - y*y == 0) VAL [c=5, counter=6, k=11, x=225, y=5] [L30] COND FALSE !(!(c < k)) [L33] c = c + 1 [L34] y = y + 1 [L35] x = y * y * y + x VAL [c=6, counter=6, k=11, x=441, y=6] [L27] EXPR counter++ VAL [c=6, counter=7, counter++=6, k=11, x=441, y=6] [L27] COND TRUE counter++<10 [L28] CALL __VERIFIER_assert(4*x - y*y*y*y - 2*y*y*y - y*y == 0) VAL [\old(cond)=1, counter=7] [L10] COND FALSE !(!(cond)) VAL [\old(cond)=1, cond=1, counter=7] [L28] RET __VERIFIER_assert(4*x - y*y*y*y - 2*y*y*y - y*y == 0) VAL [c=6, counter=7, k=11, x=441, y=6] [L30] COND FALSE !(!(c < k)) [L33] c = c + 1 [L34] y = y + 1 [L35] x = y * y * y + x VAL [c=7, counter=7, k=11, x=784, y=7] [L27] EXPR counter++ VAL [c=7, counter=8, counter++=7, k=11, x=784, y=7] [L27] COND TRUE counter++<10 [L28] CALL __VERIFIER_assert(4*x - y*y*y*y - 2*y*y*y - y*y == 0) VAL [\old(cond)=1, counter=8] [L10] COND FALSE !(!(cond)) VAL [\old(cond)=1, cond=1, counter=8] [L28] RET __VERIFIER_assert(4*x - y*y*y*y - 2*y*y*y - y*y == 0) VAL [c=7, counter=8, k=11, x=784, y=7] [L30] COND FALSE !(!(c < k)) [L33] c = c + 1 [L34] y = y + 1 [L35] x = y * y * y + x VAL [c=8, counter=8, k=11, x=1296, y=8] [L27] EXPR counter++ VAL [c=8, counter=9, counter++=8, k=11, x=1296, y=8] [L27] COND TRUE counter++<10 [L28] CALL __VERIFIER_assert(4*x - y*y*y*y - 2*y*y*y - y*y == 0) VAL [\old(cond)=1, counter=9] [L10] COND FALSE !(!(cond)) VAL [\old(cond)=1, cond=1, counter=9] [L28] RET __VERIFIER_assert(4*x - y*y*y*y - 2*y*y*y - y*y == 0) VAL [c=8, counter=9, k=11, x=1296, y=8] [L30] COND FALSE !(!(c < k)) [L33] c = c + 1 [L34] y = y + 1 [L35] x = y * y * y + x VAL [c=9, counter=9, k=11, x=2025, y=9] [L27] EXPR counter++ VAL [c=9, counter=10, counter++=9, k=11, x=2025, y=9] [L27] COND TRUE counter++<10 [L28] CALL __VERIFIER_assert(4*x - y*y*y*y - 2*y*y*y - y*y == 0) VAL [\old(cond)=1, counter=10] [L10] COND FALSE !(!(cond)) VAL [\old(cond)=1, cond=1, counter=10] [L28] RET __VERIFIER_assert(4*x - y*y*y*y - 2*y*y*y - y*y == 0) VAL [c=9, counter=10, k=11, x=2025, y=9] [L30] COND FALSE !(!(c < k)) [L33] c = c + 1 [L34] y = y + 1 [L35] x = y * y * y + x VAL [c=10, counter=10, k=11, x=3025, y=10] [L27] EXPR counter++ VAL [c=10, counter=11, counter++=10, k=11, x=3025, y=10] [L27] COND FALSE !(counter++<10) [L37] CALL __VERIFIER_assert(k*y - (y*y) == 0) VAL [\old(cond)=0, counter=11] [L10] COND TRUE !(cond) VAL [\old(cond)=0, cond=0, counter=11] [L12] reach_error() VAL [\old(cond)=0, cond=0, counter=11] - StatisticsResult: Ultimate Automizer benchmark data CFG has 2 procedures, 18 locations, 1 error locations. Started 1 CEGAR loops. OverallTime: 11.0s, OverallIterations: 16, TraceHistogramMax: 11, PathProgramHistogramMax: 9, EmptinessCheckTime: 0.0s, AutomataDifference: 1.6s, DeadEndRemovalTime: 0.0s, HoareAnnotationTime: 0.0s, InitialAbstractionConstructionTime: 0.0s, HoareTripleCheckerStatistics: 0 mSolverCounterUnknown, 168 SdHoareTripleChecker+Valid, 1.1s IncrementalHoareTripleChecker+Time, 0 mSdLazyCounter, 165 mSDsluCounter, 2387 SdHoareTripleChecker+Invalid, 1.0s Time, 0 mProtectedAction, 0 SdHoareTripleChecker+Unchecked, 0 IncrementalHoareTripleChecker+Unchecked, 1975 mSDsCounter, 45 IncrementalHoareTripleChecker+Valid, 0 mProtectedPredicate, 1985 IncrementalHoareTripleChecker+Invalid, 2030 SdHoareTripleChecker+Unknown, 0 mSolverCounterNotChecked, 45 mSolverCounterUnsat, 412 mSDtfsCounter, 1985 mSolverCounterSat, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Unknown, PredicateUnifierStatistics: 0 DeclaredPredicates, 797 GetRequests, 617 SyntacticMatches, 11 SemanticMatches, 169 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 91 ImplicationChecksByTransitivity, 1.8s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=91occurred in iteration=15, InterpolantAutomatonStates: 147, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 0.0s DumpTime, AutomataMinimizationStatistics: 0.1s AutomataMinimizationTime, 15 MinimizatonAttempts, 35 StatesRemovedByMinimization, 3 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TRACE_CHECK: 0.1s SsaConstructionTime, 2.2s SatisfiabilityAnalysisTime, 3.2s InterpolantComputationTime, 669 NumberOfCodeBlocks, 669 NumberOfCodeBlocksAsserted, 53 NumberOfCheckSat, 635 ConstructedInterpolants, 0 QuantifiedInterpolants, 2868 SizeOfPredicates, 25 NumberOfNonLiveVariables, 1847 ConjunctsInSsa, 290 ConjunctsInUnsatCore, 18 InterpolantComputations, 4 PerfectInterpolantSequences, 819/1574 InterpolantCoveringCapability, INVARIANT_SYNTHESIS: No data available, INTERPOLANT_CONSOLIDATION: No data available, ABSTRACT_INTERPRETATION: No data available, PDR: No data available, ACCELERATED_INTERPOLATION: No data available, SIFA: No data available, ReuseStatistics: No data available RESULT: Ultimate proved your program to be incorrect! [2022-07-21 04:08:48,268 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Forceful destruction successful, exit code 0 Received shutdown request... --- End real Ultimate output --- Execution finished normally Writing output log to file Ultimate.log Writing human readable error path to file UltimateCounterExample.errorpath Result: FALSE