./Ultimate.py --spec ../sv-benchmarks/c/properties/unreach-call.prp --file ../sv-benchmarks/c/nla-digbench-scaling/ps4-ll_valuebound50.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version ae007674 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_valuebound50.c -s /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf --cacsl2boogietranslator.entry.function main --witnessprinter.witness.directory /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux --witnessprinter.witness.filename witness.graphml --witnessprinter.write.witness.besides.input.file false --witnessprinter.graph.data.specification CHECK( init(main()), LTL(G ! call(reach_error())) ) --witnessprinter.graph.data.producer Automizer --witnessprinter.graph.data.architecture 32bit --witnessprinter.graph.data.programhash dcebefc76bde79b9a5fa67feebc75881761b0a4209b78516b385f787f62f9340 --- Real Ultimate output --- This is Ultimate 0.2.2-dev-ae00767 [2021-12-28 00:32:02,699 INFO L177 SettingsManager]: Resetting all preferences to default values... [2021-12-28 00:32:02,701 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2021-12-28 00:32:02,731 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2021-12-28 00:32:02,732 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2021-12-28 00:32:02,734 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2021-12-28 00:32:02,735 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2021-12-28 00:32:02,738 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2021-12-28 00:32:02,740 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2021-12-28 00:32:02,743 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2021-12-28 00:32:02,744 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2021-12-28 00:32:02,745 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2021-12-28 00:32:02,750 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2021-12-28 00:32:02,752 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2021-12-28 00:32:02,753 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2021-12-28 00:32:02,755 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2021-12-28 00:32:02,756 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2021-12-28 00:32:02,756 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2021-12-28 00:32:02,760 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2021-12-28 00:32:02,764 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2021-12-28 00:32:02,765 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2021-12-28 00:32:02,766 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2021-12-28 00:32:02,767 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2021-12-28 00:32:02,768 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2021-12-28 00:32:02,772 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2021-12-28 00:32:02,773 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2021-12-28 00:32:02,773 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2021-12-28 00:32:02,774 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2021-12-28 00:32:02,774 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2021-12-28 00:32:02,775 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2021-12-28 00:32:02,775 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2021-12-28 00:32:02,776 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2021-12-28 00:32:02,777 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2021-12-28 00:32:02,777 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2021-12-28 00:32:02,778 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2021-12-28 00:32:02,778 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2021-12-28 00:32:02,779 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2021-12-28 00:32:02,779 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2021-12-28 00:32:02,779 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2021-12-28 00:32:02,780 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2021-12-28 00:32:02,781 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2021-12-28 00:32:02,784 INFO L101 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf [2021-12-28 00:32:02,812 INFO L113 SettingsManager]: Loading preferences was successful [2021-12-28 00:32:02,812 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2021-12-28 00:32:02,813 INFO L136 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2021-12-28 00:32:02,813 INFO L138 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2021-12-28 00:32:02,814 INFO L136 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2021-12-28 00:32:02,814 INFO L138 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2021-12-28 00:32:02,815 INFO L136 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2021-12-28 00:32:02,815 INFO L138 SettingsManager]: * Create parallel compositions if possible=false [2021-12-28 00:32:02,815 INFO L138 SettingsManager]: * Use SBE=true [2021-12-28 00:32:02,816 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2021-12-28 00:32:02,816 INFO L138 SettingsManager]: * sizeof long=4 [2021-12-28 00:32:02,817 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2021-12-28 00:32:02,817 INFO L138 SettingsManager]: * sizeof POINTER=4 [2021-12-28 00:32:02,817 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2021-12-28 00:32:02,817 INFO L138 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2021-12-28 00:32:02,817 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2021-12-28 00:32:02,817 INFO L138 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2021-12-28 00:32:02,818 INFO L138 SettingsManager]: * sizeof long double=12 [2021-12-28 00:32:02,818 INFO L138 SettingsManager]: * Check if freed pointer was valid=false [2021-12-28 00:32:02,818 INFO L138 SettingsManager]: * Use constant arrays=true [2021-12-28 00:32:02,818 INFO L138 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2021-12-28 00:32:02,818 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2021-12-28 00:32:02,818 INFO L138 SettingsManager]: * Size of a code block=SequenceOfStatements [2021-12-28 00:32:02,819 INFO L138 SettingsManager]: * SMT solver=External_DefaultMode [2021-12-28 00:32:02,819 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2021-12-28 00:32:02,819 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2021-12-28 00:32:02,819 INFO L138 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2021-12-28 00:32:02,819 INFO L138 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2021-12-28 00:32:02,820 INFO L138 SettingsManager]: * Trace refinement strategy=CAMEL [2021-12-28 00:32:02,820 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2021-12-28 00:32:02,820 INFO L138 SettingsManager]: * Large block encoding in concurrent analysis=OFF [2021-12-28 00:32:02,820 INFO L138 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2021-12-28 00:32:02,820 INFO L138 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2021-12-28 00:32:02,820 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 -> dcebefc76bde79b9a5fa67feebc75881761b0a4209b78516b385f787f62f9340 [2021-12-28 00:32:03,061 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2021-12-28 00:32:03,077 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2021-12-28 00:32:03,079 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2021-12-28 00:32:03,079 INFO L271 PluginConnector]: Initializing CDTParser... [2021-12-28 00:32:03,081 INFO L275 PluginConnector]: CDTParser initialized [2021-12-28 00:32:03,082 INFO L432 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/nla-digbench-scaling/ps4-ll_valuebound50.c [2021-12-28 00:32:03,142 INFO L220 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/589361346/79cd4f45267148838d35d00ab629a495/FLAGb6aff55a4 [2021-12-28 00:32:03,502 INFO L306 CDTParser]: Found 1 translation units. [2021-12-28 00:32:03,502 INFO L160 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/ps4-ll_valuebound50.c [2021-12-28 00:32:03,517 INFO L349 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/589361346/79cd4f45267148838d35d00ab629a495/FLAGb6aff55a4 [2021-12-28 00:32:03,937 INFO L357 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/589361346/79cd4f45267148838d35d00ab629a495 [2021-12-28 00:32:03,952 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2021-12-28 00:32:03,953 INFO L131 ToolchainWalker]: Walking toolchain with 6 elements. [2021-12-28 00:32:03,954 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2021-12-28 00:32:03,954 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2021-12-28 00:32:03,956 INFO L275 PluginConnector]: CACSL2BoogieTranslator initialized [2021-12-28 00:32:03,957 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 28.12 12:32:03" (1/1) ... [2021-12-28 00:32:03,957 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@1df788b2 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.12 12:32:03, skipping insertion in model container [2021-12-28 00:32:03,958 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 28.12 12:32:03" (1/1) ... [2021-12-28 00:32:03,962 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2021-12-28 00:32:03,969 INFO L178 MainTranslator]: Built tables and reachable declarations [2021-12-28 00:32:04,085 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_valuebound50.c[458,471] [2021-12-28 00:32:04,099 INFO L209 PostProcessor]: Analyzing one entry point: main [2021-12-28 00:32:04,104 INFO L203 MainTranslator]: Completed pre-run [2021-12-28 00:32:04,113 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_valuebound50.c[458,471] [2021-12-28 00:32:04,127 INFO L209 PostProcessor]: Analyzing one entry point: main [2021-12-28 00:32:04,136 INFO L208 MainTranslator]: Completed translation [2021-12-28 00:32:04,136 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.12 12:32:04 WrapperNode [2021-12-28 00:32:04,136 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2021-12-28 00:32:04,138 INFO L113 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2021-12-28 00:32:04,139 INFO L271 PluginConnector]: Initializing Boogie Procedure Inliner... [2021-12-28 00:32:04,139 INFO L275 PluginConnector]: Boogie Procedure Inliner initialized [2021-12-28 00:32:04,143 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.12 12:32:04" (1/1) ... [2021-12-28 00:32:04,151 INFO L185 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.12 12:32:04" (1/1) ... [2021-12-28 00:32:04,171 INFO L137 Inliner]: procedures = 14, calls = 11, calls flagged for inlining = 3, calls inlined = 3, statements flattened = 38 [2021-12-28 00:32:04,172 INFO L132 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2021-12-28 00:32:04,173 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2021-12-28 00:32:04,173 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2021-12-28 00:32:04,173 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2021-12-28 00:32:04,178 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.12 12:32:04" (1/1) ... [2021-12-28 00:32:04,178 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.12 12:32:04" (1/1) ... [2021-12-28 00:32:04,185 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.12 12:32:04" (1/1) ... [2021-12-28 00:32:04,185 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.12 12:32:04" (1/1) ... [2021-12-28 00:32:04,192 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.12 12:32:04" (1/1) ... [2021-12-28 00:32:04,197 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.12 12:32:04" (1/1) ... [2021-12-28 00:32:04,201 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.12 12:32:04" (1/1) ... [2021-12-28 00:32:04,202 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2021-12-28 00:32:04,202 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2021-12-28 00:32:04,203 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2021-12-28 00:32:04,203 INFO L275 PluginConnector]: RCFGBuilder initialized [2021-12-28 00:32:04,204 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.12 12:32:04" (1/1) ... [2021-12-28 00:32:04,208 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2021-12-28 00:32:04,215 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-28 00:32:04,250 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) [2021-12-28 00:32:04,303 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 [2021-12-28 00:32:04,326 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2021-12-28 00:32:04,326 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2021-12-28 00:32:04,326 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2021-12-28 00:32:04,326 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2021-12-28 00:32:04,327 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2021-12-28 00:32:04,327 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2021-12-28 00:32:04,370 INFO L234 CfgBuilder]: Building ICFG [2021-12-28 00:32:04,371 INFO L260 CfgBuilder]: Building CFG for each procedure with an implementation [2021-12-28 00:32:04,462 INFO L275 CfgBuilder]: Performing block encoding [2021-12-28 00:32:04,466 INFO L294 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2021-12-28 00:32:04,466 INFO L299 CfgBuilder]: Removed 1 assume(true) statements. [2021-12-28 00:32:04,467 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 28.12 12:32:04 BoogieIcfgContainer [2021-12-28 00:32:04,467 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2021-12-28 00:32:04,468 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2021-12-28 00:32:04,469 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2021-12-28 00:32:04,470 INFO L275 PluginConnector]: TraceAbstraction initialized [2021-12-28 00:32:04,470 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 28.12 12:32:03" (1/3) ... [2021-12-28 00:32:04,471 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@223b855e and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 28.12 12:32:04, skipping insertion in model container [2021-12-28 00:32:04,471 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.12 12:32:04" (2/3) ... [2021-12-28 00:32:04,471 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@223b855e and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 28.12 12:32:04, skipping insertion in model container [2021-12-28 00:32:04,472 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 28.12 12:32:04" (3/3) ... [2021-12-28 00:32:04,472 INFO L111 eAbstractionObserver]: Analyzing ICFG ps4-ll_valuebound50.c [2021-12-28 00:32:04,475 INFO L204 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2021-12-28 00:32:04,476 INFO L163 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2021-12-28 00:32:04,508 INFO L338 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2021-12-28 00:32:04,512 INFO L339 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, mLoopAccelerationTechnique=FAST_UPR [2021-12-28 00:32:04,513 INFO L340 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2021-12-28 00:32:04,522 INFO L276 IsEmpty]: Start isEmpty. Operand has 19 states, 13 states have (on average 1.4615384615384615) internal successors, (19), 14 states have internal predecessors, (19), 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) [2021-12-28 00:32:04,524 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 10 [2021-12-28 00:32:04,524 INFO L506 BasicCegarLoop]: Found error trace [2021-12-28 00:32:04,525 INFO L514 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-28 00:32:04,525 INFO L402 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-12-28 00:32:04,528 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-28 00:32:04,529 INFO L85 PathProgramCache]: Analyzing trace with hash -589436290, now seen corresponding path program 1 times [2021-12-28 00:32:04,534 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-28 00:32:04,534 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1564703410] [2021-12-28 00:32:04,535 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-28 00:32:04,535 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-28 00:32:04,591 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-28 00:32:04,618 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2021-12-28 00:32:04,618 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-28 00:32:04,619 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1564703410] [2021-12-28 00:32:04,619 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1564703410] provided 1 perfect and 0 imperfect interpolant sequences [2021-12-28 00:32:04,620 INFO L186 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2021-12-28 00:32:04,620 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2021-12-28 00:32:04,621 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1173531727] [2021-12-28 00:32:04,621 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2021-12-28 00:32:04,624 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2021-12-28 00:32:04,624 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-28 00:32:04,639 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2021-12-28 00:32:04,640 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2021-12-28 00:32:04,641 INFO L87 Difference]: Start difference. First operand has 19 states, 13 states have (on average 1.4615384615384615) internal successors, (19), 14 states have internal predecessors, (19), 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 4.0) internal successors, (8), 2 states have internal predecessors, (8), 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) [2021-12-28 00:32:04,652 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-28 00:32:04,653 INFO L93 Difference]: Finished difference Result 35 states and 49 transitions. [2021-12-28 00:32:04,653 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2021-12-28 00:32:04,654 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 4.0) internal successors, (8), 2 states have internal predecessors, (8), 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 9 [2021-12-28 00:32:04,654 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-28 00:32:04,658 INFO L225 Difference]: With dead ends: 35 [2021-12-28 00:32:04,658 INFO L226 Difference]: Without dead ends: 15 [2021-12-28 00:32:04,660 INFO L932 BasicCegarLoop]: 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 [2021-12-28 00:32:04,663 INFO L933 BasicCegarLoop]: 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 [2021-12-28 00:32:04,663 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [0 Valid, 21 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 0 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2021-12-28 00:32:04,673 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 15 states. [2021-12-28 00:32:04,682 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 15 to 15. [2021-12-28 00:32:04,683 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 15 states, 10 states have (on average 1.2) internal successors, (12), 11 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) [2021-12-28 00:32:04,683 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 15 states to 15 states and 17 transitions. [2021-12-28 00:32:04,684 INFO L78 Accepts]: Start accepts. Automaton has 15 states and 17 transitions. Word has length 9 [2021-12-28 00:32:04,684 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-28 00:32:04,684 INFO L470 AbstractCegarLoop]: Abstraction has 15 states and 17 transitions. [2021-12-28 00:32:04,685 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 2 states have (on average 4.0) internal successors, (8), 2 states have internal predecessors, (8), 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) [2021-12-28 00:32:04,685 INFO L276 IsEmpty]: Start isEmpty. Operand 15 states and 17 transitions. [2021-12-28 00:32:04,685 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 10 [2021-12-28 00:32:04,685 INFO L506 BasicCegarLoop]: Found error trace [2021-12-28 00:32:04,685 INFO L514 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-28 00:32:04,686 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2021-12-28 00:32:04,686 INFO L402 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-12-28 00:32:04,687 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-28 00:32:04,687 INFO L85 PathProgramCache]: Analyzing trace with hash 1187358532, now seen corresponding path program 1 times [2021-12-28 00:32:04,687 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-28 00:32:04,687 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [441703060] [2021-12-28 00:32:04,687 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-28 00:32:04,687 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-28 00:32:04,696 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-12-28 00:32:04,697 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1029527354] [2021-12-28 00:32:04,697 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-28 00:32:04,697 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-28 00:32:04,697 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-28 00:32:04,703 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) [2021-12-28 00:32:04,721 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2021-12-28 00:32:04,759 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-28 00:32:04,761 INFO L263 TraceCheckSpWp]: Trace formula consists of 48 conjuncts, 7 conjunts are in the unsatisfiable core [2021-12-28 00:32:04,772 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-28 00:32:04,847 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2021-12-28 00:32:04,848 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2021-12-28 00:32:04,848 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-28 00:32:04,848 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [441703060] [2021-12-28 00:32:04,848 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-12-28 00:32:04,848 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1029527354] [2021-12-28 00:32:04,849 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1029527354] provided 1 perfect and 0 imperfect interpolant sequences [2021-12-28 00:32:04,849 INFO L186 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2021-12-28 00:32:04,849 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2021-12-28 00:32:04,850 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1727477476] [2021-12-28 00:32:04,850 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2021-12-28 00:32:04,850 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2021-12-28 00:32:04,850 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-28 00:32:04,851 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2021-12-28 00:32:04,851 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2021-12-28 00:32:04,851 INFO L87 Difference]: Start difference. First operand 15 states and 17 transitions. Second operand has 5 states, 5 states have (on average 1.6) internal successors, (8), 4 states have internal predecessors, (8), 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) [2021-12-28 00:32:04,883 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-28 00:32:04,883 INFO L93 Difference]: Finished difference Result 26 states and 30 transitions. [2021-12-28 00:32:04,884 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2021-12-28 00:32:04,884 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 1.6) internal successors, (8), 4 states have internal predecessors, (8), 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 9 [2021-12-28 00:32:04,884 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-28 00:32:04,885 INFO L225 Difference]: With dead ends: 26 [2021-12-28 00:32:04,885 INFO L226 Difference]: Without dead ends: 22 [2021-12-28 00:32:04,885 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 9 GetRequests, 5 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2021-12-28 00:32:04,886 INFO L933 BasicCegarLoop]: 14 mSDtfsCounter, 6 mSDsluCounter, 37 mSDsCounter, 0 mSdLazyCounter, 22 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 8 SdHoareTripleChecker+Valid, 51 SdHoareTripleChecker+Invalid, 24 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 22 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2021-12-28 00:32:04,887 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [8 Valid, 51 Invalid, 24 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 22 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2021-12-28 00:32:04,887 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 22 states. [2021-12-28 00:32:04,891 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 22 to 22. [2021-12-28 00:32:04,891 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 22 states, 15 states have (on average 1.1333333333333333) internal successors, (17), 16 states have internal predecessors, (17), 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) [2021-12-28 00:32:04,891 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 22 states to 22 states and 24 transitions. [2021-12-28 00:32:04,892 INFO L78 Accepts]: Start accepts. Automaton has 22 states and 24 transitions. Word has length 9 [2021-12-28 00:32:04,892 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-28 00:32:04,892 INFO L470 AbstractCegarLoop]: Abstraction has 22 states and 24 transitions. [2021-12-28 00:32:04,892 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 1.6) internal successors, (8), 4 states have internal predecessors, (8), 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) [2021-12-28 00:32:04,892 INFO L276 IsEmpty]: Start isEmpty. Operand 22 states and 24 transitions. [2021-12-28 00:32:04,893 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 17 [2021-12-28 00:32:04,893 INFO L506 BasicCegarLoop]: Found error trace [2021-12-28 00:32:04,893 INFO L514 BasicCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-28 00:32:04,914 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Forceful destruction successful, exit code 0 [2021-12-28 00:32:05,111 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1,2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-28 00:32:05,112 INFO L402 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-12-28 00:32:05,112 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-28 00:32:05,112 INFO L85 PathProgramCache]: Analyzing trace with hash -1781398469, now seen corresponding path program 1 times [2021-12-28 00:32:05,113 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-28 00:32:05,113 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [108040605] [2021-12-28 00:32:05,113 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-28 00:32:05,113 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-28 00:32:05,136 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-12-28 00:32:05,136 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [842659478] [2021-12-28 00:32:05,136 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-28 00:32:05,136 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-28 00:32:05,136 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-28 00:32:05,137 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) [2021-12-28 00:32:05,140 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2021-12-28 00:32:05,190 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-28 00:32:05,212 INFO L263 TraceCheckSpWp]: Trace formula consists of 65 conjuncts, 11 conjunts are in the unsatisfiable core [2021-12-28 00:32:05,213 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-28 00:32:05,346 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 2 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2021-12-28 00:32:05,347 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-28 00:32:05,545 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2021-12-28 00:32:05,545 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-28 00:32:05,546 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [108040605] [2021-12-28 00:32:05,546 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-12-28 00:32:05,546 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [842659478] [2021-12-28 00:32:05,546 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [842659478] provided 1 perfect and 1 imperfect interpolant sequences [2021-12-28 00:32:05,546 INFO L186 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2021-12-28 00:32:05,547 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [6] total 7 [2021-12-28 00:32:05,547 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [466346025] [2021-12-28 00:32:05,547 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2021-12-28 00:32:05,547 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2021-12-28 00:32:05,547 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-28 00:32:05,548 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2021-12-28 00:32:05,548 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=29, Unknown=0, NotChecked=0, Total=42 [2021-12-28 00:32:05,548 INFO L87 Difference]: Start difference. First operand 22 states and 24 transitions. Second operand has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 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) [2021-12-28 00:32:05,571 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-28 00:32:05,571 INFO L93 Difference]: Finished difference Result 28 states and 29 transitions. [2021-12-28 00:32:05,571 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2021-12-28 00:32:05,572 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 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 [2021-12-28 00:32:05,572 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-28 00:32:05,572 INFO L225 Difference]: With dead ends: 28 [2021-12-28 00:32:05,572 INFO L226 Difference]: Without dead ends: 23 [2021-12-28 00:32:05,573 INFO L932 BasicCegarLoop]: 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 [2021-12-28 00:32:05,573 INFO L933 BasicCegarLoop]: 13 mSDtfsCounter, 6 mSDsluCounter, 31 mSDsCounter, 0 mSdLazyCounter, 16 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 7 SdHoareTripleChecker+Valid, 44 SdHoareTripleChecker+Invalid, 17 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 16 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2021-12-28 00:32:05,574 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [7 Valid, 44 Invalid, 17 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 16 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2021-12-28 00:32:05,574 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 23 states. [2021-12-28 00:32:05,585 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 23 to 23. [2021-12-28 00:32:05,587 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 23 states, 17 states have (on average 1.0588235294117647) internal successors, (18), 17 states have internal predecessors, (18), 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) [2021-12-28 00:32:05,599 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 23 states to 23 states and 23 transitions. [2021-12-28 00:32:05,599 INFO L78 Accepts]: Start accepts. Automaton has 23 states and 23 transitions. Word has length 16 [2021-12-28 00:32:05,599 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-28 00:32:05,600 INFO L470 AbstractCegarLoop]: Abstraction has 23 states and 23 transitions. [2021-12-28 00:32:05,600 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 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) [2021-12-28 00:32:05,600 INFO L276 IsEmpty]: Start isEmpty. Operand 23 states and 23 transitions. [2021-12-28 00:32:05,600 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 23 [2021-12-28 00:32:05,600 INFO L506 BasicCegarLoop]: Found error trace [2021-12-28 00:32:05,601 INFO L514 BasicCegarLoop]: trace histogram [3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-28 00:32:05,620 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2021-12-28 00:32:05,816 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 3 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable2 [2021-12-28 00:32:05,816 INFO L402 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-12-28 00:32:05,817 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-28 00:32:05,817 INFO L85 PathProgramCache]: Analyzing trace with hash -1711372296, now seen corresponding path program 1 times [2021-12-28 00:32:05,817 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-28 00:32:05,818 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [80070605] [2021-12-28 00:32:05,818 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-28 00:32:05,818 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-28 00:32:05,825 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-12-28 00:32:05,825 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [640882608] [2021-12-28 00:32:05,826 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-28 00:32:05,826 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-28 00:32:05,826 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-28 00:32:05,829 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) [2021-12-28 00:32:05,830 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2021-12-28 00:32:05,861 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-28 00:32:05,862 INFO L263 TraceCheckSpWp]: Trace formula consists of 75 conjuncts, 12 conjunts are in the unsatisfiable core [2021-12-28 00:32:05,863 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-28 00:32:05,989 INFO L134 CoverageAnalysis]: Checked inductivity of 11 backedges. 4 proven. 3 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2021-12-28 00:32:05,989 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-28 00:32:06,107 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-28 00:32:06,107 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [80070605] [2021-12-28 00:32:06,108 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-12-28 00:32:06,108 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [640882608] [2021-12-28 00:32:06,108 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [640882608] provided 0 perfect and 1 imperfect interpolant sequences [2021-12-28 00:32:06,108 INFO L186 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2021-12-28 00:32:06,108 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7] total 7 [2021-12-28 00:32:06,108 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [573178619] [2021-12-28 00:32:06,108 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2021-12-28 00:32:06,108 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2021-12-28 00:32:06,108 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-28 00:32:06,109 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2021-12-28 00:32:06,109 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=24, Invalid=66, Unknown=0, NotChecked=0, Total=90 [2021-12-28 00:32:06,109 INFO L87 Difference]: Start difference. First operand 23 states and 23 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) [2021-12-28 00:32:06,164 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-28 00:32:06,164 INFO L93 Difference]: Finished difference Result 31 states and 32 transitions. [2021-12-28 00:32:06,164 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2021-12-28 00:32:06,164 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 [2021-12-28 00:32:06,165 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-28 00:32:06,165 INFO L225 Difference]: With dead ends: 31 [2021-12-28 00:32:06,165 INFO L226 Difference]: Without dead ends: 26 [2021-12-28 00:32:06,165 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 36 GetRequests, 25 SyntacticMatches, 1 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=34, Invalid=98, Unknown=0, NotChecked=0, Total=132 [2021-12-28 00:32:06,166 INFO L933 BasicCegarLoop]: 17 mSDtfsCounter, 2 mSDsluCounter, 64 mSDsCounter, 0 mSdLazyCounter, 37 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 81 SdHoareTripleChecker+Invalid, 37 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 37 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2021-12-28 00:32:06,166 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 81 Invalid, 37 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 37 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2021-12-28 00:32:06,167 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 26 states. [2021-12-28 00:32:06,169 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 26 to 26. [2021-12-28 00:32:06,169 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 26 states, 19 states have (on average 1.0526315789473684) internal successors, (20), 19 states have internal predecessors, (20), 4 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2021-12-28 00:32:06,170 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 26 states to 26 states and 27 transitions. [2021-12-28 00:32:06,170 INFO L78 Accepts]: Start accepts. Automaton has 26 states and 27 transitions. Word has length 22 [2021-12-28 00:32:06,170 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-28 00:32:06,170 INFO L470 AbstractCegarLoop]: Abstraction has 26 states and 27 transitions. [2021-12-28 00:32:06,170 INFO L471 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) [2021-12-28 00:32:06,171 INFO L276 IsEmpty]: Start isEmpty. Operand 26 states and 27 transitions. [2021-12-28 00:32:06,171 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 30 [2021-12-28 00:32:06,171 INFO L506 BasicCegarLoop]: Found error trace [2021-12-28 00:32:06,171 INFO L514 BasicCegarLoop]: trace histogram [4, 3, 3, 3, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-28 00:32:06,204 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Ended with exit code 0 [2021-12-28 00:32:06,404 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-28 00:32:06,405 INFO L402 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-12-28 00:32:06,406 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-28 00:32:06,406 INFO L85 PathProgramCache]: Analyzing trace with hash -1075497887, now seen corresponding path program 2 times [2021-12-28 00:32:06,406 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-28 00:32:06,406 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [451048895] [2021-12-28 00:32:06,406 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-28 00:32:06,407 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-28 00:32:06,426 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-12-28 00:32:06,426 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [604618689] [2021-12-28 00:32:06,426 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2021-12-28 00:32:06,426 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-28 00:32:06,427 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-28 00:32:06,430 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) [2021-12-28 00:32:06,431 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2021-12-28 00:32:06,472 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2021-12-28 00:32:06,472 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2021-12-28 00:32:06,473 INFO L263 TraceCheckSpWp]: Trace formula consists of 92 conjuncts, 16 conjunts are in the unsatisfiable core [2021-12-28 00:32:06,475 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-28 00:32:06,634 INFO L134 CoverageAnalysis]: Checked inductivity of 27 backedges. 6 proven. 9 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2021-12-28 00:32:06,635 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-28 00:32:06,821 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-28 00:32:06,821 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [451048895] [2021-12-28 00:32:06,821 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-12-28 00:32:06,821 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [604618689] [2021-12-28 00:32:06,821 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [604618689] provided 0 perfect and 1 imperfect interpolant sequences [2021-12-28 00:32:06,821 INFO L186 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2021-12-28 00:32:06,822 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8] total 8 [2021-12-28 00:32:06,822 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1421834249] [2021-12-28 00:32:06,822 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2021-12-28 00:32:06,822 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2021-12-28 00:32:06,822 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-28 00:32:06,822 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2021-12-28 00:32:06,822 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=27, Invalid=83, Unknown=0, NotChecked=0, Total=110 [2021-12-28 00:32:06,822 INFO L87 Difference]: Start difference. First operand 26 states and 27 transitions. Second operand has 8 states, 7 states have (on average 2.2857142857142856) internal successors, (16), 7 states have internal predecessors, (16), 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) [2021-12-28 00:32:06,878 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-28 00:32:06,878 INFO L93 Difference]: Finished difference Result 34 states and 36 transitions. [2021-12-28 00:32:06,878 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2021-12-28 00:32:06,879 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 7 states have (on average 2.2857142857142856) internal successors, (16), 7 states have internal predecessors, (16), 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 29 [2021-12-28 00:32:06,879 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-28 00:32:06,879 INFO L225 Difference]: With dead ends: 34 [2021-12-28 00:32:06,879 INFO L226 Difference]: Without dead ends: 29 [2021-12-28 00:32:06,879 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 43 GetRequests, 31 SyntacticMatches, 1 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=37, Invalid=119, Unknown=0, NotChecked=0, Total=156 [2021-12-28 00:32:06,880 INFO L933 BasicCegarLoop]: 20 mSDtfsCounter, 2 mSDsluCounter, 89 mSDsCounter, 0 mSdLazyCounter, 55 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 109 SdHoareTripleChecker+Invalid, 55 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 55 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2021-12-28 00:32:06,880 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 109 Invalid, 55 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 55 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2021-12-28 00:32:06,880 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 29 states. [2021-12-28 00:32:06,883 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 29 to 29. [2021-12-28 00:32:06,884 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 29 states, 21 states have (on average 1.0476190476190477) internal successors, (22), 21 states have internal predecessors, (22), 5 states have call successors, (5), 3 states have call predecessors, (5), 2 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) [2021-12-28 00:32:06,884 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 29 states to 29 states and 31 transitions. [2021-12-28 00:32:06,884 INFO L78 Accepts]: Start accepts. Automaton has 29 states and 31 transitions. Word has length 29 [2021-12-28 00:32:06,884 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-28 00:32:06,884 INFO L470 AbstractCegarLoop]: Abstraction has 29 states and 31 transitions. [2021-12-28 00:32:06,884 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 7 states have (on average 2.2857142857142856) internal successors, (16), 7 states have internal predecessors, (16), 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) [2021-12-28 00:32:06,885 INFO L276 IsEmpty]: Start isEmpty. Operand 29 states and 31 transitions. [2021-12-28 00:32:06,885 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 37 [2021-12-28 00:32:06,885 INFO L506 BasicCegarLoop]: Found error trace [2021-12-28 00:32:06,885 INFO L514 BasicCegarLoop]: trace histogram [5, 4, 4, 4, 4, 4, 3, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-28 00:32:06,915 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Forceful destruction successful, exit code 0 [2021-12-28 00:32:07,095 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-28 00:32:07,095 INFO L402 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-12-28 00:32:07,096 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-28 00:32:07,096 INFO L85 PathProgramCache]: Analyzing trace with hash 817917912, now seen corresponding path program 3 times [2021-12-28 00:32:07,096 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-28 00:32:07,096 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2053135087] [2021-12-28 00:32:07,096 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-28 00:32:07,096 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-28 00:32:07,104 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-12-28 00:32:07,104 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2130569324] [2021-12-28 00:32:07,105 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2021-12-28 00:32:07,105 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-28 00:32:07,105 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-28 00:32:07,106 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) [2021-12-28 00:32:07,131 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2021-12-28 00:32:07,165 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2021-12-28 00:32:07,165 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2021-12-28 00:32:07,166 INFO L263 TraceCheckSpWp]: Trace formula consists of 109 conjuncts, 32 conjunts are in the unsatisfiable core [2021-12-28 00:32:07,168 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-28 00:32:07,382 INFO L134 CoverageAnalysis]: Checked inductivity of 50 backedges. 18 proven. 20 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2021-12-28 00:32:07,382 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-28 00:32:26,480 WARN L838 $PredicateComparison]: unable to prove that (or (not (= (mod (+ (* (- 1) |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1|) (* (- 1) |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1|) (* |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| (- 2))) 4) 0)) (forall ((|ULTIMATE.start_main_~k~0#1| Int)) (or (let ((.cse0 (+ |c_ULTIMATE.start_main_~y~0#1| 1))) (= (* |ULTIMATE.start_main_~k~0#1| .cse0) (* .cse0 .cse0))) (not (< |c_ULTIMATE.start_main_~c~0#1| |ULTIMATE.start_main_~k~0#1|)) (< (+ |c_ULTIMATE.start_main_~c~0#1| 1) |ULTIMATE.start_main_~k~0#1|)))) is different from false [2021-12-28 00:32:26,483 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-28 00:32:26,483 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2053135087] [2021-12-28 00:32:26,483 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-12-28 00:32:26,483 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2130569324] [2021-12-28 00:32:26,483 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2130569324] provided 0 perfect and 1 imperfect interpolant sequences [2021-12-28 00:32:26,483 INFO L186 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2021-12-28 00:32:26,483 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13] total 13 [2021-12-28 00:32:26,484 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2076644607] [2021-12-28 00:32:26,484 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2021-12-28 00:32:26,484 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 13 states [2021-12-28 00:32:26,484 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-28 00:32:26,484 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2021-12-28 00:32:26,484 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=58, Invalid=251, Unknown=1, NotChecked=32, Total=342 [2021-12-28 00:32:26,485 INFO L87 Difference]: Start difference. First operand 29 states and 31 transitions. Second operand has 13 states, 12 states have (on average 1.75) internal successors, (21), 10 states have internal predecessors, (21), 5 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) [2021-12-28 00:32:26,639 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-28 00:32:26,639 INFO L93 Difference]: Finished difference Result 41 states and 43 transitions. [2021-12-28 00:32:26,640 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2021-12-28 00:32:26,640 INFO L78 Accepts]: Start accepts. Automaton has has 13 states, 12 states have (on average 1.75) internal successors, (21), 10 states have internal predecessors, (21), 5 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) Word has length 36 [2021-12-28 00:32:26,640 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-28 00:32:26,640 INFO L225 Difference]: With dead ends: 41 [2021-12-28 00:32:26,640 INFO L226 Difference]: Without dead ends: 36 [2021-12-28 00:32:26,641 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 51 GetRequests, 30 SyntacticMatches, 1 SemanticMatches, 20 ConstructedPredicates, 1 IntricatePredicates, 0 DeprecatedPredicates, 40 ImplicationChecksByTransitivity, 17.1s TimeCoverageRelationStatistics Valid=79, Invalid=344, Unknown=1, NotChecked=38, Total=462 [2021-12-28 00:32:26,641 INFO L933 BasicCegarLoop]: 17 mSDtfsCounter, 12 mSDsluCounter, 114 mSDsCounter, 0 mSdLazyCounter, 148 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 14 SdHoareTripleChecker+Valid, 131 SdHoareTripleChecker+Invalid, 151 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 148 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2021-12-28 00:32:26,641 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [14 Valid, 131 Invalid, 151 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 148 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2021-12-28 00:32:26,642 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 36 states. [2021-12-28 00:32:26,646 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 36 to 36. [2021-12-28 00:32:26,646 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 36 states, 26 states have (on average 1.0384615384615385) internal successors, (27), 26 states have internal predecessors, (27), 6 states have call successors, (6), 4 states have call predecessors, (6), 3 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) [2021-12-28 00:32:26,646 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 36 states to 36 states and 38 transitions. [2021-12-28 00:32:26,647 INFO L78 Accepts]: Start accepts. Automaton has 36 states and 38 transitions. Word has length 36 [2021-12-28 00:32:26,647 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-28 00:32:26,647 INFO L470 AbstractCegarLoop]: Abstraction has 36 states and 38 transitions. [2021-12-28 00:32:26,647 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 13 states, 12 states have (on average 1.75) internal successors, (21), 10 states have internal predecessors, (21), 5 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) [2021-12-28 00:32:26,647 INFO L276 IsEmpty]: Start isEmpty. Operand 36 states and 38 transitions. [2021-12-28 00:32:26,648 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 44 [2021-12-28 00:32:26,648 INFO L506 BasicCegarLoop]: Found error trace [2021-12-28 00:32:26,648 INFO L514 BasicCegarLoop]: trace histogram [6, 5, 5, 5, 5, 5, 4, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-28 00:32:26,669 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Forceful destruction successful, exit code 0 [2021-12-28 00:32:26,865 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-28 00:32:26,865 INFO L402 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-12-28 00:32:26,866 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-28 00:32:26,866 INFO L85 PathProgramCache]: Analyzing trace with hash 1384689793, now seen corresponding path program 4 times [2021-12-28 00:32:26,866 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-28 00:32:26,866 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1357734136] [2021-12-28 00:32:26,866 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-28 00:32:26,866 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-28 00:32:26,872 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-12-28 00:32:26,872 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [290897401] [2021-12-28 00:32:26,872 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2021-12-28 00:32:26,872 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-28 00:32:26,872 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-28 00:32:26,873 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) [2021-12-28 00:32:26,892 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2021-12-28 00:32:26,954 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2021-12-28 00:32:26,954 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2021-12-28 00:32:26,955 INFO L263 TraceCheckSpWp]: Trace formula consists of 97 conjuncts, 24 conjunts are in the unsatisfiable core [2021-12-28 00:32:26,957 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-28 00:32:27,175 INFO L134 CoverageAnalysis]: Checked inductivity of 80 backedges. 10 proven. 30 refuted. 0 times theorem prover too weak. 40 trivial. 0 not checked. [2021-12-28 00:32:27,176 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-28 00:32:27,338 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-28 00:32:27,338 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1357734136] [2021-12-28 00:32:27,338 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-12-28 00:32:27,338 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [290897401] [2021-12-28 00:32:27,338 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [290897401] provided 0 perfect and 1 imperfect interpolant sequences [2021-12-28 00:32:27,338 INFO L186 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2021-12-28 00:32:27,338 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10] total 10 [2021-12-28 00:32:27,339 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1751720852] [2021-12-28 00:32:27,339 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2021-12-28 00:32:27,339 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2021-12-28 00:32:27,339 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-28 00:32:27,339 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2021-12-28 00:32:27,339 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=33, Invalid=123, Unknown=0, NotChecked=0, Total=156 [2021-12-28 00:32:27,339 INFO L87 Difference]: Start difference. First operand 36 states and 38 transitions. Second operand has 10 states, 9 states have (on average 2.2222222222222223) internal successors, (20), 9 states have internal predecessors, (20), 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) [2021-12-28 00:32:27,432 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-28 00:32:27,432 INFO L93 Difference]: Finished difference Result 44 states and 47 transitions. [2021-12-28 00:32:27,433 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2021-12-28 00:32:27,433 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 9 states have (on average 2.2222222222222223) internal successors, (20), 9 states have internal predecessors, (20), 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 43 [2021-12-28 00:32:27,433 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-28 00:32:27,433 INFO L225 Difference]: With dead ends: 44 [2021-12-28 00:32:27,434 INFO L226 Difference]: Without dead ends: 39 [2021-12-28 00:32:27,434 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 57 GetRequests, 43 SyntacticMatches, 1 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=43, Invalid=167, Unknown=0, NotChecked=0, Total=210 [2021-12-28 00:32:27,434 INFO L933 BasicCegarLoop]: 26 mSDtfsCounter, 2 mSDsluCounter, 151 mSDsCounter, 0 mSdLazyCounter, 103 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 177 SdHoareTripleChecker+Invalid, 103 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 103 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2021-12-28 00:32:27,434 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 177 Invalid, 103 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 103 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2021-12-28 00:32:27,435 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 39 states. [2021-12-28 00:32:27,438 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 39 to 39. [2021-12-28 00:32:27,439 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 39 states, 28 states have (on average 1.0357142857142858) internal successors, (29), 28 states have internal predecessors, (29), 7 states have call successors, (7), 4 states have call predecessors, (7), 3 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2021-12-28 00:32:27,439 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 39 states to 39 states and 42 transitions. [2021-12-28 00:32:27,439 INFO L78 Accepts]: Start accepts. Automaton has 39 states and 42 transitions. Word has length 43 [2021-12-28 00:32:27,439 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-28 00:32:27,439 INFO L470 AbstractCegarLoop]: Abstraction has 39 states and 42 transitions. [2021-12-28 00:32:27,440 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 9 states have (on average 2.2222222222222223) internal successors, (20), 9 states have internal predecessors, (20), 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) [2021-12-28 00:32:27,440 INFO L276 IsEmpty]: Start isEmpty. Operand 39 states and 42 transitions. [2021-12-28 00:32:27,440 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 51 [2021-12-28 00:32:27,440 INFO L506 BasicCegarLoop]: Found error trace [2021-12-28 00:32:27,440 INFO L514 BasicCegarLoop]: trace histogram [7, 6, 6, 6, 6, 6, 5, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-28 00:32:27,471 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Forceful destruction successful, exit code 0 [2021-12-28 00:32:27,651 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-28 00:32:27,652 INFO L402 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-12-28 00:32:27,652 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-28 00:32:27,652 INFO L85 PathProgramCache]: Analyzing trace with hash -23130184, now seen corresponding path program 5 times [2021-12-28 00:32:27,652 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-28 00:32:27,652 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [580773617] [2021-12-28 00:32:27,652 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-28 00:32:27,652 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-28 00:32:27,658 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-12-28 00:32:27,658 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [220856876] [2021-12-28 00:32:27,658 INFO L93 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2021-12-28 00:32:27,658 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-28 00:32:27,658 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-28 00:32:27,659 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) [2021-12-28 00:32:27,660 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2021-12-28 00:32:27,705 INFO L228 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 6 check-sat command(s) [2021-12-28 00:32:27,705 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2021-12-28 00:32:27,706 INFO L263 TraceCheckSpWp]: Trace formula consists of 143 conjuncts, 29 conjunts are in the unsatisfiable core [2021-12-28 00:32:27,708 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-28 00:32:27,902 INFO L134 CoverageAnalysis]: Checked inductivity of 117 backedges. 12 proven. 45 refuted. 0 times theorem prover too weak. 60 trivial. 0 not checked. [2021-12-28 00:32:27,903 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-28 00:32:28,322 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-28 00:32:28,323 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [580773617] [2021-12-28 00:32:28,323 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-12-28 00:32:28,323 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [220856876] [2021-12-28 00:32:28,323 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [220856876] provided 0 perfect and 1 imperfect interpolant sequences [2021-12-28 00:32:28,323 INFO L186 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2021-12-28 00:32:28,323 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11] total 11 [2021-12-28 00:32:28,323 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [443654899] [2021-12-28 00:32:28,323 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2021-12-28 00:32:28,323 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 11 states [2021-12-28 00:32:28,323 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-28 00:32:28,324 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2021-12-28 00:32:28,324 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=65, Invalid=241, Unknown=0, NotChecked=0, Total=306 [2021-12-28 00:32:28,324 INFO L87 Difference]: Start difference. First operand 39 states and 42 transitions. Second operand has 11 states, 10 states have (on average 2.2) internal successors, (22), 10 states have internal predecessors, (22), 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) [2021-12-28 00:32:28,433 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-28 00:32:28,433 INFO L93 Difference]: Finished difference Result 47 states and 51 transitions. [2021-12-28 00:32:28,433 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2021-12-28 00:32:28,433 INFO L78 Accepts]: Start accepts. Automaton has has 11 states, 10 states have (on average 2.2) internal successors, (22), 10 states have internal predecessors, (22), 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 50 [2021-12-28 00:32:28,434 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-28 00:32:28,434 INFO L225 Difference]: With dead ends: 47 [2021-12-28 00:32:28,434 INFO L226 Difference]: Without dead ends: 42 [2021-12-28 00:32:28,434 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 92 GetRequests, 73 SyntacticMatches, 1 SemanticMatches, 18 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 11 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=75, Invalid=305, Unknown=0, NotChecked=0, Total=380 [2021-12-28 00:32:28,435 INFO L933 BasicCegarLoop]: 29 mSDtfsCounter, 2 mSDsluCounter, 188 mSDsCounter, 0 mSdLazyCounter, 133 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 217 SdHoareTripleChecker+Invalid, 133 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 133 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2021-12-28 00:32:28,435 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 217 Invalid, 133 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 133 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2021-12-28 00:32:28,435 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 42 states. [2021-12-28 00:32:28,440 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 42 to 42. [2021-12-28 00:32:28,440 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 42 states, 30 states have (on average 1.0333333333333334) internal successors, (31), 30 states have internal predecessors, (31), 8 states have call successors, (8), 4 states have call predecessors, (8), 3 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2021-12-28 00:32:28,440 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 42 states to 42 states and 46 transitions. [2021-12-28 00:32:28,440 INFO L78 Accepts]: Start accepts. Automaton has 42 states and 46 transitions. Word has length 50 [2021-12-28 00:32:28,441 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-28 00:32:28,441 INFO L470 AbstractCegarLoop]: Abstraction has 42 states and 46 transitions. [2021-12-28 00:32:28,441 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 11 states, 10 states have (on average 2.2) internal successors, (22), 10 states have internal predecessors, (22), 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) [2021-12-28 00:32:28,441 INFO L276 IsEmpty]: Start isEmpty. Operand 42 states and 46 transitions. [2021-12-28 00:32:28,442 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 58 [2021-12-28 00:32:28,442 INFO L506 BasicCegarLoop]: Found error trace [2021-12-28 00:32:28,442 INFO L514 BasicCegarLoop]: trace histogram [8, 7, 7, 7, 7, 7, 6, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-28 00:32:28,467 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Forceful destruction successful, exit code 0 [2021-12-28 00:32:28,645 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-28 00:32:28,646 INFO L402 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-12-28 00:32:28,646 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-28 00:32:28,646 INFO L85 PathProgramCache]: Analyzing trace with hash -1898941279, now seen corresponding path program 6 times [2021-12-28 00:32:28,646 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-28 00:32:28,646 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2002774253] [2021-12-28 00:32:28,646 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-28 00:32:28,646 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-28 00:32:28,652 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-12-28 00:32:28,652 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1605396960] [2021-12-28 00:32:28,652 INFO L93 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2021-12-28 00:32:28,652 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-28 00:32:28,652 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-28 00:32:28,653 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) [2021-12-28 00:32:28,654 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2021-12-28 00:32:28,698 INFO L228 tOrderPrioritization]: Assert order MIX_INSIDE_OUTSIDE issued 7 check-sat command(s) [2021-12-28 00:32:28,698 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2021-12-28 00:32:28,698 INFO L263 TraceCheckSpWp]: Trace formula consists of 160 conjuncts, 32 conjunts are in the unsatisfiable core [2021-12-28 00:32:28,700 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-28 00:32:28,880 INFO L134 CoverageAnalysis]: Checked inductivity of 161 backedges. 14 proven. 63 refuted. 0 times theorem prover too weak. 84 trivial. 0 not checked. [2021-12-28 00:32:28,881 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-28 00:32:29,033 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-28 00:32:29,035 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2002774253] [2021-12-28 00:32:29,035 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-12-28 00:32:29,035 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1605396960] [2021-12-28 00:32:29,035 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1605396960] provided 0 perfect and 1 imperfect interpolant sequences [2021-12-28 00:32:29,035 INFO L186 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2021-12-28 00:32:29,035 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12] total 12 [2021-12-28 00:32:29,035 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1476690069] [2021-12-28 00:32:29,035 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2021-12-28 00:32:29,036 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2021-12-28 00:32:29,036 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-28 00:32:29,036 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2021-12-28 00:32:29,036 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=39, Invalid=171, Unknown=0, NotChecked=0, Total=210 [2021-12-28 00:32:29,036 INFO L87 Difference]: Start difference. First operand 42 states and 46 transitions. Second operand has 12 states, 11 states have (on average 2.1818181818181817) internal successors, (24), 11 states have internal predecessors, (24), 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) [2021-12-28 00:32:29,158 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-28 00:32:29,159 INFO L93 Difference]: Finished difference Result 50 states and 55 transitions. [2021-12-28 00:32:29,159 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2021-12-28 00:32:29,159 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 11 states have (on average 2.1818181818181817) internal successors, (24), 11 states have internal predecessors, (24), 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 57 [2021-12-28 00:32:29,159 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-28 00:32:29,160 INFO L225 Difference]: With dead ends: 50 [2021-12-28 00:32:29,160 INFO L226 Difference]: Without dead ends: 45 [2021-12-28 00:32:29,160 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 71 GetRequests, 55 SyntacticMatches, 1 SemanticMatches, 15 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=49, Invalid=223, Unknown=0, NotChecked=0, Total=272 [2021-12-28 00:32:29,160 INFO L933 BasicCegarLoop]: 32 mSDtfsCounter, 2 mSDsluCounter, 229 mSDsCounter, 0 mSdLazyCounter, 167 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 261 SdHoareTripleChecker+Invalid, 167 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 167 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2021-12-28 00:32:29,161 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 261 Invalid, 167 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 167 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2021-12-28 00:32:29,161 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 45 states. [2021-12-28 00:32:29,165 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 45 to 45. [2021-12-28 00:32:29,165 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 45 states, 32 states have (on average 1.03125) internal successors, (33), 32 states have internal predecessors, (33), 9 states have call successors, (9), 4 states have call predecessors, (9), 3 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2021-12-28 00:32:29,166 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 45 states to 45 states and 50 transitions. [2021-12-28 00:32:29,166 INFO L78 Accepts]: Start accepts. Automaton has 45 states and 50 transitions. Word has length 57 [2021-12-28 00:32:29,166 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-28 00:32:29,166 INFO L470 AbstractCegarLoop]: Abstraction has 45 states and 50 transitions. [2021-12-28 00:32:29,166 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 11 states have (on average 2.1818181818181817) internal successors, (24), 11 states have internal predecessors, (24), 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) [2021-12-28 00:32:29,166 INFO L276 IsEmpty]: Start isEmpty. Operand 45 states and 50 transitions. [2021-12-28 00:32:29,167 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 65 [2021-12-28 00:32:29,167 INFO L506 BasicCegarLoop]: Found error trace [2021-12-28 00:32:29,167 INFO L514 BasicCegarLoop]: trace histogram [9, 8, 8, 8, 8, 8, 7, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-28 00:32:29,187 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Forceful destruction successful, exit code 0 [2021-12-28 00:32:29,383 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 9 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable8 [2021-12-28 00:32:29,384 INFO L402 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-12-28 00:32:29,384 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-28 00:32:29,384 INFO L85 PathProgramCache]: Analyzing trace with hash 385378200, now seen corresponding path program 7 times [2021-12-28 00:32:29,384 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-28 00:32:29,384 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [503495155] [2021-12-28 00:32:29,384 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-28 00:32:29,384 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-28 00:32:29,390 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-12-28 00:32:29,390 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1984606860] [2021-12-28 00:32:29,390 INFO L93 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2021-12-28 00:32:29,390 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-28 00:32:29,390 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-28 00:32:29,391 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) [2021-12-28 00:32:29,392 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Waiting until timeout for monitored process [2021-12-28 00:32:29,630 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-28 00:32:29,631 INFO L263 TraceCheckSpWp]: Trace formula consists of 177 conjuncts, 36 conjunts are in the unsatisfiable core [2021-12-28 00:32:29,633 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-28 00:32:29,850 INFO L134 CoverageAnalysis]: Checked inductivity of 212 backedges. 16 proven. 84 refuted. 0 times theorem prover too weak. 112 trivial. 0 not checked. [2021-12-28 00:32:29,850 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-28 00:32:29,957 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-28 00:32:29,957 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [503495155] [2021-12-28 00:32:29,958 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-12-28 00:32:29,958 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1984606860] [2021-12-28 00:32:29,958 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1984606860] provided 0 perfect and 1 imperfect interpolant sequences [2021-12-28 00:32:29,958 INFO L186 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2021-12-28 00:32:29,958 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13] total 13 [2021-12-28 00:32:29,958 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [412109795] [2021-12-28 00:32:29,958 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2021-12-28 00:32:29,958 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 13 states [2021-12-28 00:32:29,958 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-28 00:32:29,959 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2021-12-28 00:32:29,959 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=42, Invalid=198, Unknown=0, NotChecked=0, Total=240 [2021-12-28 00:32:29,959 INFO L87 Difference]: Start difference. First operand 45 states and 50 transitions. Second operand has 13 states, 12 states have (on average 2.1666666666666665) internal successors, (26), 12 states have internal predecessors, (26), 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) [2021-12-28 00:32:30,107 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-28 00:32:30,108 INFO L93 Difference]: Finished difference Result 53 states and 59 transitions. [2021-12-28 00:32:30,108 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2021-12-28 00:32:30,108 INFO L78 Accepts]: Start accepts. Automaton has has 13 states, 12 states have (on average 2.1666666666666665) internal successors, (26), 12 states have internal predecessors, (26), 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 64 [2021-12-28 00:32:30,108 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-28 00:32:30,109 INFO L225 Difference]: With dead ends: 53 [2021-12-28 00:32:30,109 INFO L226 Difference]: Without dead ends: 48 [2021-12-28 00:32:30,109 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 78 GetRequests, 61 SyntacticMatches, 1 SemanticMatches, 16 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=52, Invalid=254, Unknown=0, NotChecked=0, Total=306 [2021-12-28 00:32:30,110 INFO L933 BasicCegarLoop]: 35 mSDtfsCounter, 2 mSDsluCounter, 274 mSDsCounter, 0 mSdLazyCounter, 205 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 309 SdHoareTripleChecker+Invalid, 205 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 205 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2021-12-28 00:32:30,110 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 309 Invalid, 205 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 205 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2021-12-28 00:32:30,110 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 48 states. [2021-12-28 00:32:30,114 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 48 to 48. [2021-12-28 00:32:30,114 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 48 states, 34 states have (on average 1.0294117647058822) internal successors, (35), 34 states have internal predecessors, (35), 10 states have call successors, (10), 4 states have call predecessors, (10), 3 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2021-12-28 00:32:30,115 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 48 states to 48 states and 54 transitions. [2021-12-28 00:32:30,115 INFO L78 Accepts]: Start accepts. Automaton has 48 states and 54 transitions. Word has length 64 [2021-12-28 00:32:30,115 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-28 00:32:30,115 INFO L470 AbstractCegarLoop]: Abstraction has 48 states and 54 transitions. [2021-12-28 00:32:30,116 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 13 states, 12 states have (on average 2.1666666666666665) internal successors, (26), 12 states have internal predecessors, (26), 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) [2021-12-28 00:32:30,116 INFO L276 IsEmpty]: Start isEmpty. Operand 48 states and 54 transitions. [2021-12-28 00:32:30,116 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 72 [2021-12-28 00:32:30,116 INFO L506 BasicCegarLoop]: Found error trace [2021-12-28 00:32:30,116 INFO L514 BasicCegarLoop]: trace histogram [10, 9, 9, 9, 9, 9, 8, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-28 00:32:30,123 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Forceful destruction successful, exit code 0 [2021-12-28 00:32:30,320 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 10 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable9 [2021-12-28 00:32:30,321 INFO L402 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-12-28 00:32:30,321 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-28 00:32:30,321 INFO L85 PathProgramCache]: Analyzing trace with hash 2073985217, now seen corresponding path program 8 times [2021-12-28 00:32:30,321 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-28 00:32:30,321 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1272254719] [2021-12-28 00:32:30,321 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-28 00:32:30,321 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-28 00:32:30,334 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-12-28 00:32:30,335 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [799143671] [2021-12-28 00:32:30,335 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2021-12-28 00:32:30,335 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-28 00:32:30,335 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-28 00:32:30,336 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) [2021-12-28 00:32:30,369 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Waiting until timeout for monitored process [2021-12-28 00:32:30,617 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2021-12-28 00:32:30,618 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2021-12-28 00:32:30,619 INFO L263 TraceCheckSpWp]: Trace formula consists of 194 conjuncts, 40 conjunts are in the unsatisfiable core [2021-12-28 00:32:30,621 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-28 00:32:30,842 INFO L134 CoverageAnalysis]: Checked inductivity of 270 backedges. 18 proven. 108 refuted. 0 times theorem prover too weak. 144 trivial. 0 not checked. [2021-12-28 00:32:30,843 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-28 00:32:30,951 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-28 00:32:30,951 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1272254719] [2021-12-28 00:32:30,951 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-12-28 00:32:30,951 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [799143671] [2021-12-28 00:32:30,951 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [799143671] provided 0 perfect and 1 imperfect interpolant sequences [2021-12-28 00:32:30,951 INFO L186 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2021-12-28 00:32:30,951 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [14] total 14 [2021-12-28 00:32:30,951 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [202853344] [2021-12-28 00:32:30,951 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2021-12-28 00:32:30,952 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2021-12-28 00:32:30,952 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-28 00:32:30,952 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2021-12-28 00:32:30,952 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=45, Invalid=227, Unknown=0, NotChecked=0, Total=272 [2021-12-28 00:32:30,952 INFO L87 Difference]: Start difference. First operand 48 states and 54 transitions. Second operand has 14 states, 13 states have (on average 2.1538461538461537) internal successors, (28), 13 states have internal predecessors, (28), 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) [2021-12-28 00:32:31,106 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-28 00:32:31,106 INFO L93 Difference]: Finished difference Result 56 states and 63 transitions. [2021-12-28 00:32:31,106 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2021-12-28 00:32:31,107 INFO L78 Accepts]: Start accepts. Automaton has has 14 states, 13 states have (on average 2.1538461538461537) internal successors, (28), 13 states have internal predecessors, (28), 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 71 [2021-12-28 00:32:31,107 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-28 00:32:31,107 INFO L225 Difference]: With dead ends: 56 [2021-12-28 00:32:31,107 INFO L226 Difference]: Without dead ends: 51 [2021-12-28 00:32:31,108 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 85 GetRequests, 67 SyntacticMatches, 1 SemanticMatches, 17 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=55, Invalid=287, Unknown=0, NotChecked=0, Total=342 [2021-12-28 00:32:31,108 INFO L933 BasicCegarLoop]: 38 mSDtfsCounter, 2 mSDsluCounter, 323 mSDsCounter, 0 mSdLazyCounter, 247 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 361 SdHoareTripleChecker+Invalid, 247 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 247 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2021-12-28 00:32:31,108 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 361 Invalid, 247 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 247 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2021-12-28 00:32:31,108 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 51 states. [2021-12-28 00:32:31,118 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 51 to 51. [2021-12-28 00:32:31,118 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 51 states, 36 states have (on average 1.0277777777777777) internal successors, (37), 36 states have internal predecessors, (37), 11 states have call successors, (11), 4 states have call predecessors, (11), 3 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2021-12-28 00:32:31,119 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 51 states to 51 states and 58 transitions. [2021-12-28 00:32:31,119 INFO L78 Accepts]: Start accepts. Automaton has 51 states and 58 transitions. Word has length 71 [2021-12-28 00:32:31,119 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-28 00:32:31,119 INFO L470 AbstractCegarLoop]: Abstraction has 51 states and 58 transitions. [2021-12-28 00:32:31,119 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 14 states, 13 states have (on average 2.1538461538461537) internal successors, (28), 13 states have internal predecessors, (28), 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) [2021-12-28 00:32:31,119 INFO L276 IsEmpty]: Start isEmpty. Operand 51 states and 58 transitions. [2021-12-28 00:32:31,120 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 79 [2021-12-28 00:32:31,120 INFO L506 BasicCegarLoop]: Found error trace [2021-12-28 00:32:31,120 INFO L514 BasicCegarLoop]: trace histogram [11, 10, 10, 10, 10, 10, 9, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-28 00:32:31,128 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Forceful destruction successful, exit code 0 [2021-12-28 00:32:31,320 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 11 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable10 [2021-12-28 00:32:31,321 INFO L402 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-12-28 00:32:31,321 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-28 00:32:31,321 INFO L85 PathProgramCache]: Analyzing trace with hash 1353348984, now seen corresponding path program 9 times [2021-12-28 00:32:31,321 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-28 00:32:31,321 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1490872660] [2021-12-28 00:32:31,321 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-28 00:32:31,321 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-28 00:32:31,326 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-12-28 00:32:31,326 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1869773320] [2021-12-28 00:32:31,326 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2021-12-28 00:32:31,326 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-28 00:32:31,327 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-28 00:32:31,347 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) [2021-12-28 00:32:31,363 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Waiting until timeout for monitored process [2021-12-28 00:32:31,646 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 10 check-sat command(s) [2021-12-28 00:32:31,647 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2021-12-28 00:32:31,648 INFO L263 TraceCheckSpWp]: Trace formula consists of 211 conjuncts, 44 conjunts are in the unsatisfiable core [2021-12-28 00:32:31,649 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-28 00:32:31,968 INFO L134 CoverageAnalysis]: Checked inductivity of 335 backedges. 20 proven. 135 refuted. 0 times theorem prover too weak. 180 trivial. 0 not checked. [2021-12-28 00:32:31,968 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-28 00:32:32,136 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-28 00:32:32,136 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1490872660] [2021-12-28 00:32:32,136 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-12-28 00:32:32,136 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1869773320] [2021-12-28 00:32:32,136 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1869773320] provided 0 perfect and 1 imperfect interpolant sequences [2021-12-28 00:32:32,136 INFO L186 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2021-12-28 00:32:32,137 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [15] total 15 [2021-12-28 00:32:32,137 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1216502447] [2021-12-28 00:32:32,137 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2021-12-28 00:32:32,137 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 15 states [2021-12-28 00:32:32,137 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-28 00:32:32,138 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2021-12-28 00:32:32,138 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=48, Invalid=258, Unknown=0, NotChecked=0, Total=306 [2021-12-28 00:32:32,138 INFO L87 Difference]: Start difference. First operand 51 states and 58 transitions. Second operand has 15 states, 14 states have (on average 2.142857142857143) internal successors, (30), 14 states have internal predecessors, (30), 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) [2021-12-28 00:32:32,321 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-28 00:32:32,321 INFO L93 Difference]: Finished difference Result 59 states and 67 transitions. [2021-12-28 00:32:32,322 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2021-12-28 00:32:32,322 INFO L78 Accepts]: Start accepts. Automaton has has 15 states, 14 states have (on average 2.142857142857143) internal successors, (30), 14 states have internal predecessors, (30), 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 78 [2021-12-28 00:32:32,322 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-28 00:32:32,323 INFO L225 Difference]: With dead ends: 59 [2021-12-28 00:32:32,323 INFO L226 Difference]: Without dead ends: 54 [2021-12-28 00:32:32,323 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 92 GetRequests, 73 SyntacticMatches, 1 SemanticMatches, 18 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=58, Invalid=322, Unknown=0, NotChecked=0, Total=380 [2021-12-28 00:32:32,323 INFO L933 BasicCegarLoop]: 41 mSDtfsCounter, 2 mSDsluCounter, 376 mSDsCounter, 0 mSdLazyCounter, 293 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 417 SdHoareTripleChecker+Invalid, 293 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 293 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2021-12-28 00:32:32,323 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 417 Invalid, 293 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 293 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2021-12-28 00:32:32,324 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 54 states. [2021-12-28 00:32:32,328 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 54 to 54. [2021-12-28 00:32:32,328 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 54 states, 38 states have (on average 1.0263157894736843) internal successors, (39), 38 states have internal predecessors, (39), 12 states have call successors, (12), 4 states have call predecessors, (12), 3 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2021-12-28 00:32:32,329 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 54 states to 54 states and 62 transitions. [2021-12-28 00:32:32,329 INFO L78 Accepts]: Start accepts. Automaton has 54 states and 62 transitions. Word has length 78 [2021-12-28 00:32:32,329 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-28 00:32:32,329 INFO L470 AbstractCegarLoop]: Abstraction has 54 states and 62 transitions. [2021-12-28 00:32:32,329 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 15 states, 14 states have (on average 2.142857142857143) internal successors, (30), 14 states have internal predecessors, (30), 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) [2021-12-28 00:32:32,329 INFO L276 IsEmpty]: Start isEmpty. Operand 54 states and 62 transitions. [2021-12-28 00:32:32,330 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 86 [2021-12-28 00:32:32,330 INFO L506 BasicCegarLoop]: Found error trace [2021-12-28 00:32:32,330 INFO L514 BasicCegarLoop]: trace histogram [12, 11, 11, 11, 11, 11, 10, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-28 00:32:32,338 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Forceful destruction successful, exit code 0 [2021-12-28 00:32:32,538 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 12 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable11 [2021-12-28 00:32:32,539 INFO L402 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-12-28 00:32:32,539 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-28 00:32:32,539 INFO L85 PathProgramCache]: Analyzing trace with hash 1817498849, now seen corresponding path program 10 times [2021-12-28 00:32:32,539 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-28 00:32:32,539 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1430292034] [2021-12-28 00:32:32,539 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-28 00:32:32,540 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-28 00:32:32,555 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-12-28 00:32:32,557 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1448205887] [2021-12-28 00:32:32,557 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2021-12-28 00:32:32,557 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-28 00:32:32,557 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-28 00:32:32,558 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) [2021-12-28 00:32:32,563 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Waiting until timeout for monitored process [2021-12-28 00:32:32,799 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2021-12-28 00:32:32,799 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2021-12-28 00:32:32,801 INFO L263 TraceCheckSpWp]: Trace formula consists of 199 conjuncts, 48 conjunts are in the unsatisfiable core [2021-12-28 00:32:32,802 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-28 00:32:33,145 INFO L134 CoverageAnalysis]: Checked inductivity of 407 backedges. 22 proven. 165 refuted. 0 times theorem prover too weak. 220 trivial. 0 not checked. [2021-12-28 00:32:33,146 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-28 00:32:33,297 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-28 00:32:33,297 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1430292034] [2021-12-28 00:32:33,298 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-12-28 00:32:33,298 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1448205887] [2021-12-28 00:32:33,298 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1448205887] provided 0 perfect and 1 imperfect interpolant sequences [2021-12-28 00:32:33,298 INFO L186 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2021-12-28 00:32:33,298 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [16] total 16 [2021-12-28 00:32:33,298 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [606021317] [2021-12-28 00:32:33,298 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2021-12-28 00:32:33,298 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2021-12-28 00:32:33,298 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-28 00:32:33,299 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2021-12-28 00:32:33,299 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=51, Invalid=291, Unknown=0, NotChecked=0, Total=342 [2021-12-28 00:32:33,299 INFO L87 Difference]: Start difference. First operand 54 states and 62 transitions. Second operand has 16 states, 15 states have (on average 2.1333333333333333) internal successors, (32), 15 states have internal predecessors, (32), 12 states have call successors, (12), 2 states have call predecessors, (12), 1 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2021-12-28 00:32:33,488 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-28 00:32:33,488 INFO L93 Difference]: Finished difference Result 62 states and 71 transitions. [2021-12-28 00:32:33,488 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2021-12-28 00:32:33,489 INFO L78 Accepts]: Start accepts. Automaton has has 16 states, 15 states have (on average 2.1333333333333333) internal successors, (32), 15 states have internal predecessors, (32), 12 states have call successors, (12), 2 states have call predecessors, (12), 1 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) Word has length 85 [2021-12-28 00:32:33,489 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-28 00:32:33,489 INFO L225 Difference]: With dead ends: 62 [2021-12-28 00:32:33,489 INFO L226 Difference]: Without dead ends: 57 [2021-12-28 00:32:33,489 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 99 GetRequests, 79 SyntacticMatches, 1 SemanticMatches, 19 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=61, Invalid=359, Unknown=0, NotChecked=0, Total=420 [2021-12-28 00:32:33,490 INFO L933 BasicCegarLoop]: 44 mSDtfsCounter, 2 mSDsluCounter, 433 mSDsCounter, 0 mSdLazyCounter, 343 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 477 SdHoareTripleChecker+Invalid, 343 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 343 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2021-12-28 00:32:33,490 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 477 Invalid, 343 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 343 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2021-12-28 00:32:33,490 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 57 states. [2021-12-28 00:32:33,494 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 57 to 57. [2021-12-28 00:32:33,495 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 57 states, 40 states have (on average 1.025) internal successors, (41), 40 states have internal predecessors, (41), 13 states have call successors, (13), 4 states have call predecessors, (13), 3 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) [2021-12-28 00:32:33,495 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 57 states to 57 states and 66 transitions. [2021-12-28 00:32:33,495 INFO L78 Accepts]: Start accepts. Automaton has 57 states and 66 transitions. Word has length 85 [2021-12-28 00:32:33,495 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-28 00:32:33,495 INFO L470 AbstractCegarLoop]: Abstraction has 57 states and 66 transitions. [2021-12-28 00:32:33,496 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 16 states, 15 states have (on average 2.1333333333333333) internal successors, (32), 15 states have internal predecessors, (32), 12 states have call successors, (12), 2 states have call predecessors, (12), 1 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2021-12-28 00:32:33,496 INFO L276 IsEmpty]: Start isEmpty. Operand 57 states and 66 transitions. [2021-12-28 00:32:33,496 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 93 [2021-12-28 00:32:33,496 INFO L506 BasicCegarLoop]: Found error trace [2021-12-28 00:32:33,496 INFO L514 BasicCegarLoop]: trace histogram [13, 12, 12, 12, 12, 12, 11, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-28 00:32:33,503 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Ended with exit code 0 [2021-12-28 00:32:33,703 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 13 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable12 [2021-12-28 00:32:33,703 INFO L402 AbstractCegarLoop]: === Iteration 14 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-12-28 00:32:33,704 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-28 00:32:33,704 INFO L85 PathProgramCache]: Analyzing trace with hash 638795608, now seen corresponding path program 11 times [2021-12-28 00:32:33,704 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-28 00:32:33,704 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [265365178] [2021-12-28 00:32:33,704 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-28 00:32:33,704 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-28 00:32:33,709 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-12-28 00:32:33,709 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1029078811] [2021-12-28 00:32:33,709 INFO L93 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2021-12-28 00:32:33,709 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-28 00:32:33,709 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-28 00:32:33,710 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) [2021-12-28 00:32:33,711 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Waiting until timeout for monitored process [2021-12-28 00:32:34,906 INFO L228 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 12 check-sat command(s) [2021-12-28 00:32:34,907 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2021-12-28 00:32:34,912 INFO L263 TraceCheckSpWp]: Trace formula consists of 245 conjuncts, 52 conjunts are in the unsatisfiable core [2021-12-28 00:32:34,913 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-28 00:32:35,220 INFO L134 CoverageAnalysis]: Checked inductivity of 486 backedges. 24 proven. 198 refuted. 0 times theorem prover too weak. 264 trivial. 0 not checked. [2021-12-28 00:32:35,220 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-28 00:32:35,321 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-28 00:32:35,322 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [265365178] [2021-12-28 00:32:35,322 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-12-28 00:32:35,322 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1029078811] [2021-12-28 00:32:35,322 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1029078811] provided 0 perfect and 1 imperfect interpolant sequences [2021-12-28 00:32:35,322 INFO L186 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2021-12-28 00:32:35,322 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [17] total 17 [2021-12-28 00:32:35,322 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1027020905] [2021-12-28 00:32:35,322 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2021-12-28 00:32:35,322 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 17 states [2021-12-28 00:32:35,322 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-28 00:32:35,323 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2021-12-28 00:32:35,323 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=54, Invalid=326, Unknown=0, NotChecked=0, Total=380 [2021-12-28 00:32:35,323 INFO L87 Difference]: Start difference. First operand 57 states and 66 transitions. Second operand has 17 states, 16 states have (on average 2.125) internal successors, (34), 16 states have internal predecessors, (34), 13 states have call successors, (13), 2 states have call predecessors, (13), 1 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) [2021-12-28 00:32:35,502 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-28 00:32:35,502 INFO L93 Difference]: Finished difference Result 65 states and 75 transitions. [2021-12-28 00:32:35,503 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 17 states. [2021-12-28 00:32:35,503 INFO L78 Accepts]: Start accepts. Automaton has has 17 states, 16 states have (on average 2.125) internal successors, (34), 16 states have internal predecessors, (34), 13 states have call successors, (13), 2 states have call predecessors, (13), 1 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) Word has length 92 [2021-12-28 00:32:35,503 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-28 00:32:35,503 INFO L225 Difference]: With dead ends: 65 [2021-12-28 00:32:35,504 INFO L226 Difference]: Without dead ends: 60 [2021-12-28 00:32:35,504 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 106 GetRequests, 85 SyntacticMatches, 1 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=64, Invalid=398, Unknown=0, NotChecked=0, Total=462 [2021-12-28 00:32:35,504 INFO L933 BasicCegarLoop]: 47 mSDtfsCounter, 2 mSDsluCounter, 494 mSDsCounter, 0 mSdLazyCounter, 397 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 541 SdHoareTripleChecker+Invalid, 397 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 397 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2021-12-28 00:32:35,504 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 541 Invalid, 397 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 397 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2021-12-28 00:32:35,505 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 60 states. [2021-12-28 00:32:35,509 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 60 to 60. [2021-12-28 00:32:35,510 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 60 states, 42 states have (on average 1.0238095238095237) internal successors, (43), 42 states have internal predecessors, (43), 14 states have call successors, (14), 4 states have call predecessors, (14), 3 states have return successors, (13), 13 states have call predecessors, (13), 13 states have call successors, (13) [2021-12-28 00:32:35,510 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 60 states to 60 states and 70 transitions. [2021-12-28 00:32:35,510 INFO L78 Accepts]: Start accepts. Automaton has 60 states and 70 transitions. Word has length 92 [2021-12-28 00:32:35,510 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-28 00:32:35,510 INFO L470 AbstractCegarLoop]: Abstraction has 60 states and 70 transitions. [2021-12-28 00:32:35,511 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 17 states, 16 states have (on average 2.125) internal successors, (34), 16 states have internal predecessors, (34), 13 states have call successors, (13), 2 states have call predecessors, (13), 1 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) [2021-12-28 00:32:35,511 INFO L276 IsEmpty]: Start isEmpty. Operand 60 states and 70 transitions. [2021-12-28 00:32:35,517 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 100 [2021-12-28 00:32:35,518 INFO L506 BasicCegarLoop]: Found error trace [2021-12-28 00:32:35,518 INFO L514 BasicCegarLoop]: trace histogram [14, 13, 13, 13, 13, 13, 12, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-28 00:32:35,542 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Forceful destruction successful, exit code 0 [2021-12-28 00:32:35,719 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 14 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable13 [2021-12-28 00:32:35,719 INFO L402 AbstractCegarLoop]: === Iteration 15 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-12-28 00:32:35,719 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-28 00:32:35,720 INFO L85 PathProgramCache]: Analyzing trace with hash 550859009, now seen corresponding path program 12 times [2021-12-28 00:32:35,720 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-28 00:32:35,720 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [455876749] [2021-12-28 00:32:35,720 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-28 00:32:35,720 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-28 00:32:35,725 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-12-28 00:32:35,725 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1518958542] [2021-12-28 00:32:35,725 INFO L93 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2021-12-28 00:32:35,725 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-28 00:32:35,725 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-28 00:32:35,733 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) [2021-12-28 00:32:35,734 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Waiting until timeout for monitored process [2021-12-28 00:32:36,064 INFO L228 tOrderPrioritization]: Assert order MIX_INSIDE_OUTSIDE issued 13 check-sat command(s) [2021-12-28 00:32:36,064 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2021-12-28 00:32:36,066 INFO L263 TraceCheckSpWp]: Trace formula consists of 262 conjuncts, 57 conjunts are in the unsatisfiable core [2021-12-28 00:32:36,068 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-28 00:32:36,365 INFO L134 CoverageAnalysis]: Checked inductivity of 572 backedges. 26 proven. 234 refuted. 0 times theorem prover too weak. 312 trivial. 0 not checked. [2021-12-28 00:32:36,365 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-28 00:32:36,753 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-28 00:32:36,753 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [455876749] [2021-12-28 00:32:36,753 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-12-28 00:32:36,754 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1518958542] [2021-12-28 00:32:36,754 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1518958542] provided 0 perfect and 1 imperfect interpolant sequences [2021-12-28 00:32:36,754 INFO L186 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2021-12-28 00:32:36,754 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [18] total 18 [2021-12-28 00:32:36,754 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [148011357] [2021-12-28 00:32:36,754 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2021-12-28 00:32:36,754 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 18 states [2021-12-28 00:32:36,754 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-28 00:32:36,754 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 18 interpolants. [2021-12-28 00:32:36,755 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=142, Invalid=560, Unknown=0, NotChecked=0, Total=702 [2021-12-28 00:32:36,755 INFO L87 Difference]: Start difference. First operand 60 states and 70 transitions. Second operand has 18 states, 17 states have (on average 2.1176470588235294) internal successors, (36), 17 states have internal predecessors, (36), 14 states have call successors, (14), 2 states have call predecessors, (14), 1 states have return successors, (13), 13 states have call predecessors, (13), 13 states have call successors, (13) [2021-12-28 00:32:37,000 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-28 00:32:37,000 INFO L93 Difference]: Finished difference Result 68 states and 79 transitions. [2021-12-28 00:32:37,000 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 18 states. [2021-12-28 00:32:37,000 INFO L78 Accepts]: Start accepts. Automaton has has 18 states, 17 states have (on average 2.1176470588235294) internal successors, (36), 17 states have internal predecessors, (36), 14 states have call successors, (14), 2 states have call predecessors, (14), 1 states have return successors, (13), 13 states have call predecessors, (13), 13 states have call successors, (13) Word has length 99 [2021-12-28 00:32:37,000 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-28 00:32:37,001 INFO L225 Difference]: With dead ends: 68 [2021-12-28 00:32:37,001 INFO L226 Difference]: Without dead ends: 63 [2021-12-28 00:32:37,001 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 155 GetRequests, 127 SyntacticMatches, 1 SemanticMatches, 27 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 15 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=152, Invalid=660, Unknown=0, NotChecked=0, Total=812 [2021-12-28 00:32:37,002 INFO L933 BasicCegarLoop]: 50 mSDtfsCounter, 2 mSDsluCounter, 559 mSDsCounter, 0 mSdLazyCounter, 455 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 609 SdHoareTripleChecker+Invalid, 455 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 455 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2021-12-28 00:32:37,002 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 609 Invalid, 455 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 455 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2021-12-28 00:32:37,002 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 63 states. [2021-12-28 00:32:37,007 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 63 to 63. [2021-12-28 00:32:37,007 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 63 states, 44 states have (on average 1.0227272727272727) internal successors, (45), 44 states have internal predecessors, (45), 15 states have call successors, (15), 4 states have call predecessors, (15), 3 states have return successors, (14), 14 states have call predecessors, (14), 14 states have call successors, (14) [2021-12-28 00:32:37,008 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 63 states to 63 states and 74 transitions. [2021-12-28 00:32:37,008 INFO L78 Accepts]: Start accepts. Automaton has 63 states and 74 transitions. Word has length 99 [2021-12-28 00:32:37,008 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-28 00:32:37,008 INFO L470 AbstractCegarLoop]: Abstraction has 63 states and 74 transitions. [2021-12-28 00:32:37,008 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 18 states, 17 states have (on average 2.1176470588235294) internal successors, (36), 17 states have internal predecessors, (36), 14 states have call successors, (14), 2 states have call predecessors, (14), 1 states have return successors, (13), 13 states have call predecessors, (13), 13 states have call successors, (13) [2021-12-28 00:32:37,008 INFO L276 IsEmpty]: Start isEmpty. Operand 63 states and 74 transitions. [2021-12-28 00:32:37,009 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 107 [2021-12-28 00:32:37,009 INFO L506 BasicCegarLoop]: Found error trace [2021-12-28 00:32:37,009 INFO L514 BasicCegarLoop]: trace histogram [15, 14, 14, 14, 14, 14, 13, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-28 00:32:37,016 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Forceful destruction successful, exit code 0 [2021-12-28 00:32:37,214 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable14,15 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-28 00:32:37,214 INFO L402 AbstractCegarLoop]: === Iteration 16 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-12-28 00:32:37,215 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-28 00:32:37,215 INFO L85 PathProgramCache]: Analyzing trace with hash -1794064584, now seen corresponding path program 13 times [2021-12-28 00:32:37,215 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-28 00:32:37,215 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [501570745] [2021-12-28 00:32:37,215 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-28 00:32:37,215 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-28 00:32:37,224 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-12-28 00:32:37,224 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [183415116] [2021-12-28 00:32:37,224 INFO L93 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2021-12-28 00:32:37,224 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-28 00:32:37,224 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-28 00:32:37,225 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) [2021-12-28 00:32:37,226 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Waiting until timeout for monitored process [2021-12-28 00:32:38,363 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-28 00:32:38,365 INFO L263 TraceCheckSpWp]: Trace formula consists of 279 conjuncts, 60 conjunts are in the unsatisfiable core [2021-12-28 00:32:38,367 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-28 00:32:38,728 INFO L134 CoverageAnalysis]: Checked inductivity of 665 backedges. 28 proven. 273 refuted. 0 times theorem prover too weak. 364 trivial. 0 not checked. [2021-12-28 00:32:38,728 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-28 00:32:38,849 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-28 00:32:38,849 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [501570745] [2021-12-28 00:32:38,849 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-12-28 00:32:38,849 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [183415116] [2021-12-28 00:32:38,849 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [183415116] provided 0 perfect and 1 imperfect interpolant sequences [2021-12-28 00:32:38,849 INFO L186 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2021-12-28 00:32:38,849 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [19] total 19 [2021-12-28 00:32:38,849 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1751742342] [2021-12-28 00:32:38,850 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2021-12-28 00:32:38,850 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 19 states [2021-12-28 00:32:38,850 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-28 00:32:38,850 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 19 interpolants. [2021-12-28 00:32:38,850 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=60, Invalid=402, Unknown=0, NotChecked=0, Total=462 [2021-12-28 00:32:38,851 INFO L87 Difference]: Start difference. First operand 63 states and 74 transitions. Second operand has 19 states, 18 states have (on average 2.111111111111111) internal successors, (38), 18 states have internal predecessors, (38), 15 states have call successors, (15), 2 states have call predecessors, (15), 1 states have return successors, (14), 14 states have call predecessors, (14), 14 states have call successors, (14) [2021-12-28 00:32:39,199 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-28 00:32:39,199 INFO L93 Difference]: Finished difference Result 71 states and 83 transitions. [2021-12-28 00:32:39,200 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 19 states. [2021-12-28 00:32:39,200 INFO L78 Accepts]: Start accepts. Automaton has has 19 states, 18 states have (on average 2.111111111111111) internal successors, (38), 18 states have internal predecessors, (38), 15 states have call successors, (15), 2 states have call predecessors, (15), 1 states have return successors, (14), 14 states have call predecessors, (14), 14 states have call successors, (14) Word has length 106 [2021-12-28 00:32:39,200 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-28 00:32:39,201 INFO L225 Difference]: With dead ends: 71 [2021-12-28 00:32:39,201 INFO L226 Difference]: Without dead ends: 66 [2021-12-28 00:32:39,201 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 120 GetRequests, 97 SyntacticMatches, 1 SemanticMatches, 22 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=70, Invalid=482, Unknown=0, NotChecked=0, Total=552 [2021-12-28 00:32:39,201 INFO L933 BasicCegarLoop]: 53 mSDtfsCounter, 2 mSDsluCounter, 628 mSDsCounter, 0 mSdLazyCounter, 517 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 681 SdHoareTripleChecker+Invalid, 517 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 517 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2021-12-28 00:32:39,202 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 681 Invalid, 517 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 517 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2021-12-28 00:32:39,202 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 66 states. [2021-12-28 00:32:39,217 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 66 to 66. [2021-12-28 00:32:39,218 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 66 states, 46 states have (on average 1.0217391304347827) internal successors, (47), 46 states have internal predecessors, (47), 16 states have call successors, (16), 4 states have call predecessors, (16), 3 states have return successors, (15), 15 states have call predecessors, (15), 15 states have call successors, (15) [2021-12-28 00:32:39,218 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 66 states to 66 states and 78 transitions. [2021-12-28 00:32:39,218 INFO L78 Accepts]: Start accepts. Automaton has 66 states and 78 transitions. Word has length 106 [2021-12-28 00:32:39,218 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-28 00:32:39,218 INFO L470 AbstractCegarLoop]: Abstraction has 66 states and 78 transitions. [2021-12-28 00:32:39,219 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 19 states, 18 states have (on average 2.111111111111111) internal successors, (38), 18 states have internal predecessors, (38), 15 states have call successors, (15), 2 states have call predecessors, (15), 1 states have return successors, (14), 14 states have call predecessors, (14), 14 states have call successors, (14) [2021-12-28 00:32:39,219 INFO L276 IsEmpty]: Start isEmpty. Operand 66 states and 78 transitions. [2021-12-28 00:32:39,219 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 114 [2021-12-28 00:32:39,219 INFO L506 BasicCegarLoop]: Found error trace [2021-12-28 00:32:39,219 INFO L514 BasicCegarLoop]: trace histogram [16, 15, 15, 15, 15, 15, 14, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-28 00:32:39,225 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Forceful destruction successful, exit code 0 [2021-12-28 00:32:39,425 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 16 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable15 [2021-12-28 00:32:39,425 INFO L402 AbstractCegarLoop]: === Iteration 17 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-12-28 00:32:39,426 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-28 00:32:39,426 INFO L85 PathProgramCache]: Analyzing trace with hash -444443359, now seen corresponding path program 14 times [2021-12-28 00:32:39,426 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-28 00:32:39,426 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [40331820] [2021-12-28 00:32:39,426 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-28 00:32:39,426 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-28 00:32:39,431 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-12-28 00:32:39,432 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1192929902] [2021-12-28 00:32:39,432 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2021-12-28 00:32:39,432 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-28 00:32:39,432 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-28 00:32:39,433 INFO L229 MonitoredProcess]: Starting monitored process 17 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2021-12-28 00:32:39,434 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Waiting until timeout for monitored process [2021-12-28 00:32:40,532 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2021-12-28 00:32:40,533 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2021-12-28 00:32:40,534 INFO L263 TraceCheckSpWp]: Trace formula consists of 296 conjuncts, 64 conjunts are in the unsatisfiable core [2021-12-28 00:32:40,539 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-28 00:32:40,883 INFO L134 CoverageAnalysis]: Checked inductivity of 765 backedges. 30 proven. 315 refuted. 0 times theorem prover too weak. 420 trivial. 0 not checked. [2021-12-28 00:32:40,883 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-28 00:32:41,027 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-28 00:32:41,028 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [40331820] [2021-12-28 00:32:41,028 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-12-28 00:32:41,028 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1192929902] [2021-12-28 00:32:41,028 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1192929902] provided 0 perfect and 1 imperfect interpolant sequences [2021-12-28 00:32:41,028 INFO L186 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2021-12-28 00:32:41,028 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [20] total 20 [2021-12-28 00:32:41,030 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [22850536] [2021-12-28 00:32:41,030 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2021-12-28 00:32:41,030 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 20 states [2021-12-28 00:32:41,030 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-28 00:32:41,031 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 20 interpolants. [2021-12-28 00:32:41,031 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=63, Invalid=443, Unknown=0, NotChecked=0, Total=506 [2021-12-28 00:32:41,032 INFO L87 Difference]: Start difference. First operand 66 states and 78 transitions. Second operand has 20 states, 19 states have (on average 2.1052631578947367) internal successors, (40), 19 states have internal predecessors, (40), 16 states have call successors, (16), 2 states have call predecessors, (16), 1 states have return successors, (15), 15 states have call predecessors, (15), 15 states have call successors, (15) [2021-12-28 00:32:41,319 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-28 00:32:41,320 INFO L93 Difference]: Finished difference Result 74 states and 87 transitions. [2021-12-28 00:32:41,320 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 20 states. [2021-12-28 00:32:41,320 INFO L78 Accepts]: Start accepts. Automaton has has 20 states, 19 states have (on average 2.1052631578947367) internal successors, (40), 19 states have internal predecessors, (40), 16 states have call successors, (16), 2 states have call predecessors, (16), 1 states have return successors, (15), 15 states have call predecessors, (15), 15 states have call successors, (15) Word has length 113 [2021-12-28 00:32:41,320 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-28 00:32:41,321 INFO L225 Difference]: With dead ends: 74 [2021-12-28 00:32:41,321 INFO L226 Difference]: Without dead ends: 69 [2021-12-28 00:32:41,321 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 127 GetRequests, 103 SyntacticMatches, 1 SemanticMatches, 23 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=73, Invalid=527, Unknown=0, NotChecked=0, Total=600 [2021-12-28 00:32:41,321 INFO L933 BasicCegarLoop]: 56 mSDtfsCounter, 2 mSDsluCounter, 701 mSDsCounter, 0 mSdLazyCounter, 583 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 757 SdHoareTripleChecker+Invalid, 583 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 583 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2021-12-28 00:32:41,321 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 757 Invalid, 583 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 583 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2021-12-28 00:32:41,322 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 69 states. [2021-12-28 00:32:41,326 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 69 to 69. [2021-12-28 00:32:41,326 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 69 states, 48 states have (on average 1.0208333333333333) internal successors, (49), 48 states have internal predecessors, (49), 17 states have call successors, (17), 4 states have call predecessors, (17), 3 states have return successors, (16), 16 states have call predecessors, (16), 16 states have call successors, (16) [2021-12-28 00:32:41,327 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 69 states to 69 states and 82 transitions. [2021-12-28 00:32:41,327 INFO L78 Accepts]: Start accepts. Automaton has 69 states and 82 transitions. Word has length 113 [2021-12-28 00:32:41,330 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-28 00:32:41,330 INFO L470 AbstractCegarLoop]: Abstraction has 69 states and 82 transitions. [2021-12-28 00:32:41,330 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 20 states, 19 states have (on average 2.1052631578947367) internal successors, (40), 19 states have internal predecessors, (40), 16 states have call successors, (16), 2 states have call predecessors, (16), 1 states have return successors, (15), 15 states have call predecessors, (15), 15 states have call successors, (15) [2021-12-28 00:32:41,330 INFO L276 IsEmpty]: Start isEmpty. Operand 69 states and 82 transitions. [2021-12-28 00:32:41,331 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 121 [2021-12-28 00:32:41,331 INFO L506 BasicCegarLoop]: Found error trace [2021-12-28 00:32:41,331 INFO L514 BasicCegarLoop]: trace histogram [17, 16, 16, 16, 16, 16, 15, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-28 00:32:41,347 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Forceful destruction successful, exit code 0 [2021-12-28 00:32:41,536 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 17 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable16 [2021-12-28 00:32:41,536 INFO L402 AbstractCegarLoop]: === Iteration 18 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-12-28 00:32:41,537 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-28 00:32:41,537 INFO L85 PathProgramCache]: Analyzing trace with hash -16713960, now seen corresponding path program 15 times [2021-12-28 00:32:41,537 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-28 00:32:41,537 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1251771952] [2021-12-28 00:32:41,537 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-28 00:32:41,538 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-28 00:32:41,546 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-12-28 00:32:41,547 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [61602687] [2021-12-28 00:32:41,547 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2021-12-28 00:32:41,547 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-28 00:32:41,547 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-28 00:32:41,553 INFO L229 MonitoredProcess]: Starting monitored process 18 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2021-12-28 00:32:41,554 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (18)] Waiting until timeout for monitored process [2021-12-28 00:32:41,880 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 16 check-sat command(s) [2021-12-28 00:32:41,881 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2021-12-28 00:32:41,883 INFO L263 TraceCheckSpWp]: Trace formula consists of 313 conjuncts, 68 conjunts are in the unsatisfiable core [2021-12-28 00:32:41,885 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-28 00:32:42,251 INFO L134 CoverageAnalysis]: Checked inductivity of 872 backedges. 32 proven. 360 refuted. 0 times theorem prover too weak. 480 trivial. 0 not checked. [2021-12-28 00:32:42,252 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-28 00:32:42,456 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-28 00:32:42,457 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1251771952] [2021-12-28 00:32:42,457 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-12-28 00:32:42,457 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [61602687] [2021-12-28 00:32:42,457 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [61602687] provided 0 perfect and 1 imperfect interpolant sequences [2021-12-28 00:32:42,457 INFO L186 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2021-12-28 00:32:42,457 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [21] total 21 [2021-12-28 00:32:42,457 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2111239560] [2021-12-28 00:32:42,458 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2021-12-28 00:32:42,458 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 21 states [2021-12-28 00:32:42,458 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-28 00:32:42,458 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2021-12-28 00:32:42,458 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=66, Invalid=486, Unknown=0, NotChecked=0, Total=552 [2021-12-28 00:32:42,459 INFO L87 Difference]: Start difference. First operand 69 states and 82 transitions. Second operand has 21 states, 20 states have (on average 2.1) internal successors, (42), 20 states have internal predecessors, (42), 17 states have call successors, (17), 2 states have call predecessors, (17), 1 states have return successors, (16), 16 states have call predecessors, (16), 16 states have call successors, (16) [2021-12-28 00:32:42,726 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-28 00:32:42,726 INFO L93 Difference]: Finished difference Result 77 states and 91 transitions. [2021-12-28 00:32:42,726 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 21 states. [2021-12-28 00:32:42,727 INFO L78 Accepts]: Start accepts. Automaton has has 21 states, 20 states have (on average 2.1) internal successors, (42), 20 states have internal predecessors, (42), 17 states have call successors, (17), 2 states have call predecessors, (17), 1 states have return successors, (16), 16 states have call predecessors, (16), 16 states have call successors, (16) Word has length 120 [2021-12-28 00:32:42,727 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-28 00:32:42,727 INFO L225 Difference]: With dead ends: 77 [2021-12-28 00:32:42,728 INFO L226 Difference]: Without dead ends: 72 [2021-12-28 00:32:42,728 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 134 GetRequests, 109 SyntacticMatches, 1 SemanticMatches, 24 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=76, Invalid=574, Unknown=0, NotChecked=0, Total=650 [2021-12-28 00:32:42,729 INFO L933 BasicCegarLoop]: 59 mSDtfsCounter, 2 mSDsluCounter, 778 mSDsCounter, 0 mSdLazyCounter, 653 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 837 SdHoareTripleChecker+Invalid, 653 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 653 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2021-12-28 00:32:42,729 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 837 Invalid, 653 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 653 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2021-12-28 00:32:42,730 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 72 states. [2021-12-28 00:32:42,734 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 72 to 72. [2021-12-28 00:32:42,734 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 72 states, 50 states have (on average 1.02) internal successors, (51), 50 states have internal predecessors, (51), 18 states have call successors, (18), 4 states have call predecessors, (18), 3 states have return successors, (17), 17 states have call predecessors, (17), 17 states have call successors, (17) [2021-12-28 00:32:42,735 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 72 states to 72 states and 86 transitions. [2021-12-28 00:32:42,735 INFO L78 Accepts]: Start accepts. Automaton has 72 states and 86 transitions. Word has length 120 [2021-12-28 00:32:42,735 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-28 00:32:42,735 INFO L470 AbstractCegarLoop]: Abstraction has 72 states and 86 transitions. [2021-12-28 00:32:42,735 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 21 states, 20 states have (on average 2.1) internal successors, (42), 20 states have internal predecessors, (42), 17 states have call successors, (17), 2 states have call predecessors, (17), 1 states have return successors, (16), 16 states have call predecessors, (16), 16 states have call successors, (16) [2021-12-28 00:32:42,736 INFO L276 IsEmpty]: Start isEmpty. Operand 72 states and 86 transitions. [2021-12-28 00:32:42,736 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 128 [2021-12-28 00:32:42,736 INFO L506 BasicCegarLoop]: Found error trace [2021-12-28 00:32:42,736 INFO L514 BasicCegarLoop]: trace histogram [18, 17, 17, 17, 17, 17, 16, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-28 00:32:42,741 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (18)] Forceful destruction successful, exit code 0 [2021-12-28 00:32:42,941 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 18 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable17 [2021-12-28 00:32:42,942 INFO L402 AbstractCegarLoop]: === Iteration 19 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-12-28 00:32:42,942 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-28 00:32:42,942 INFO L85 PathProgramCache]: Analyzing trace with hash -1287814847, now seen corresponding path program 16 times [2021-12-28 00:32:42,942 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-28 00:32:42,942 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [635587356] [2021-12-28 00:32:42,942 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-28 00:32:42,943 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-28 00:32:42,948 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-12-28 00:32:42,948 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1361149296] [2021-12-28 00:32:42,948 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2021-12-28 00:32:42,948 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-28 00:32:42,948 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-28 00:32:42,949 INFO L229 MonitoredProcess]: Starting monitored process 19 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2021-12-28 00:32:42,957 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (19)] Waiting until timeout for monitored process [2021-12-28 00:32:43,958 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2021-12-28 00:32:43,958 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2021-12-28 00:32:43,960 INFO L263 TraceCheckSpWp]: Trace formula consists of 301 conjuncts, 72 conjunts are in the unsatisfiable core [2021-12-28 00:32:43,962 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-28 00:32:44,272 INFO L134 CoverageAnalysis]: Checked inductivity of 986 backedges. 34 proven. 408 refuted. 0 times theorem prover too weak. 544 trivial. 0 not checked. [2021-12-28 00:32:44,273 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-28 00:32:44,472 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-28 00:32:44,472 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [635587356] [2021-12-28 00:32:44,472 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-12-28 00:32:44,472 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1361149296] [2021-12-28 00:32:44,472 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1361149296] provided 0 perfect and 1 imperfect interpolant sequences [2021-12-28 00:32:44,472 INFO L186 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2021-12-28 00:32:44,473 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [22] total 22 [2021-12-28 00:32:44,475 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [646432722] [2021-12-28 00:32:44,475 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2021-12-28 00:32:44,476 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 22 states [2021-12-28 00:32:44,476 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-28 00:32:44,476 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 22 interpolants. [2021-12-28 00:32:44,476 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=69, Invalid=531, Unknown=0, NotChecked=0, Total=600 [2021-12-28 00:32:44,477 INFO L87 Difference]: Start difference. First operand 72 states and 86 transitions. Second operand has 22 states, 21 states have (on average 2.0952380952380953) internal successors, (44), 21 states have internal predecessors, (44), 18 states have call successors, (18), 2 states have call predecessors, (18), 1 states have return successors, (17), 17 states have call predecessors, (17), 17 states have call successors, (17) [2021-12-28 00:32:44,757 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-28 00:32:44,757 INFO L93 Difference]: Finished difference Result 80 states and 95 transitions. [2021-12-28 00:32:44,757 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 22 states. [2021-12-28 00:32:44,757 INFO L78 Accepts]: Start accepts. Automaton has has 22 states, 21 states have (on average 2.0952380952380953) internal successors, (44), 21 states have internal predecessors, (44), 18 states have call successors, (18), 2 states have call predecessors, (18), 1 states have return successors, (17), 17 states have call predecessors, (17), 17 states have call successors, (17) Word has length 127 [2021-12-28 00:32:44,760 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-28 00:32:44,760 INFO L225 Difference]: With dead ends: 80 [2021-12-28 00:32:44,760 INFO L226 Difference]: Without dead ends: 75 [2021-12-28 00:32:44,761 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 141 GetRequests, 115 SyntacticMatches, 1 SemanticMatches, 25 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=79, Invalid=623, Unknown=0, NotChecked=0, Total=702 [2021-12-28 00:32:44,761 INFO L933 BasicCegarLoop]: 62 mSDtfsCounter, 2 mSDsluCounter, 859 mSDsCounter, 0 mSdLazyCounter, 727 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 921 SdHoareTripleChecker+Invalid, 727 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 727 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2021-12-28 00:32:44,762 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 921 Invalid, 727 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 727 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2021-12-28 00:32:44,762 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 75 states. [2021-12-28 00:32:44,781 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 75 to 75. [2021-12-28 00:32:44,781 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 75 states, 52 states have (on average 1.0192307692307692) internal successors, (53), 52 states have internal predecessors, (53), 19 states have call successors, (19), 4 states have call predecessors, (19), 3 states have return successors, (18), 18 states have call predecessors, (18), 18 states have call successors, (18) [2021-12-28 00:32:44,783 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 75 states to 75 states and 90 transitions. [2021-12-28 00:32:44,783 INFO L78 Accepts]: Start accepts. Automaton has 75 states and 90 transitions. Word has length 127 [2021-12-28 00:32:44,788 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-28 00:32:44,789 INFO L470 AbstractCegarLoop]: Abstraction has 75 states and 90 transitions. [2021-12-28 00:32:44,789 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 22 states, 21 states have (on average 2.0952380952380953) internal successors, (44), 21 states have internal predecessors, (44), 18 states have call successors, (18), 2 states have call predecessors, (18), 1 states have return successors, (17), 17 states have call predecessors, (17), 17 states have call successors, (17) [2021-12-28 00:32:44,789 INFO L276 IsEmpty]: Start isEmpty. Operand 75 states and 90 transitions. [2021-12-28 00:32:44,790 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 135 [2021-12-28 00:32:44,790 INFO L506 BasicCegarLoop]: Found error trace [2021-12-28 00:32:44,790 INFO L514 BasicCegarLoop]: trace histogram [19, 18, 18, 18, 18, 18, 17, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-28 00:32:44,795 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (19)] Forceful destruction successful, exit code 0 [2021-12-28 00:32:44,991 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable18,19 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-28 00:32:44,991 INFO L402 AbstractCegarLoop]: === Iteration 20 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-12-28 00:32:44,992 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-28 00:32:44,992 INFO L85 PathProgramCache]: Analyzing trace with hash 146925304, now seen corresponding path program 17 times [2021-12-28 00:32:44,992 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-28 00:32:44,992 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [766967504] [2021-12-28 00:32:44,992 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-28 00:32:44,992 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-28 00:32:45,001 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-12-28 00:32:45,002 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2016141355] [2021-12-28 00:32:45,002 INFO L93 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2021-12-28 00:32:45,002 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-28 00:32:45,002 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-28 00:32:45,003 INFO L229 MonitoredProcess]: Starting monitored process 20 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2021-12-28 00:32:45,006 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (20)] Waiting until timeout for monitored process [2021-12-28 00:32:46,320 INFO L228 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 18 check-sat command(s) [2021-12-28 00:32:46,320 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2021-12-28 00:32:46,323 INFO L263 TraceCheckSpWp]: Trace formula consists of 347 conjuncts, 76 conjunts are in the unsatisfiable core [2021-12-28 00:32:46,325 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-28 00:32:46,636 INFO L134 CoverageAnalysis]: Checked inductivity of 1107 backedges. 36 proven. 459 refuted. 0 times theorem prover too weak. 612 trivial. 0 not checked. [2021-12-28 00:32:46,636 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-28 00:32:46,746 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-28 00:32:46,747 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [766967504] [2021-12-28 00:32:46,747 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-12-28 00:32:46,747 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2016141355] [2021-12-28 00:32:46,748 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2016141355] provided 0 perfect and 1 imperfect interpolant sequences [2021-12-28 00:32:46,748 INFO L186 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2021-12-28 00:32:46,748 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [23] total 23 [2021-12-28 00:32:46,748 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1018024809] [2021-12-28 00:32:46,748 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2021-12-28 00:32:46,749 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 23 states [2021-12-28 00:32:46,749 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-28 00:32:46,750 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 23 interpolants. [2021-12-28 00:32:46,750 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=72, Invalid=578, Unknown=0, NotChecked=0, Total=650 [2021-12-28 00:32:46,750 INFO L87 Difference]: Start difference. First operand 75 states and 90 transitions. Second operand has 23 states, 22 states have (on average 2.090909090909091) internal successors, (46), 22 states have internal predecessors, (46), 19 states have call successors, (19), 2 states have call predecessors, (19), 1 states have return successors, (18), 18 states have call predecessors, (18), 18 states have call successors, (18) [2021-12-28 00:32:47,076 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-28 00:32:47,076 INFO L93 Difference]: Finished difference Result 83 states and 99 transitions. [2021-12-28 00:32:47,077 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 23 states. [2021-12-28 00:32:47,077 INFO L78 Accepts]: Start accepts. Automaton has has 23 states, 22 states have (on average 2.090909090909091) internal successors, (46), 22 states have internal predecessors, (46), 19 states have call successors, (19), 2 states have call predecessors, (19), 1 states have return successors, (18), 18 states have call predecessors, (18), 18 states have call successors, (18) Word has length 134 [2021-12-28 00:32:47,077 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-28 00:32:47,079 INFO L225 Difference]: With dead ends: 83 [2021-12-28 00:32:47,079 INFO L226 Difference]: Without dead ends: 78 [2021-12-28 00:32:47,080 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 148 GetRequests, 121 SyntacticMatches, 1 SemanticMatches, 26 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=82, Invalid=674, Unknown=0, NotChecked=0, Total=756 [2021-12-28 00:32:47,084 INFO L933 BasicCegarLoop]: 65 mSDtfsCounter, 2 mSDsluCounter, 944 mSDsCounter, 0 mSdLazyCounter, 805 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 1009 SdHoareTripleChecker+Invalid, 805 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 805 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2021-12-28 00:32:47,084 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 1009 Invalid, 805 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 805 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2021-12-28 00:32:47,088 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 78 states. [2021-12-28 00:32:47,097 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 78 to 78. [2021-12-28 00:32:47,098 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 78 states, 54 states have (on average 1.0185185185185186) internal successors, (55), 54 states have internal predecessors, (55), 20 states have call successors, (20), 4 states have call predecessors, (20), 3 states have return successors, (19), 19 states have call predecessors, (19), 19 states have call successors, (19) [2021-12-28 00:32:47,102 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 78 states to 78 states and 94 transitions. [2021-12-28 00:32:47,102 INFO L78 Accepts]: Start accepts. Automaton has 78 states and 94 transitions. Word has length 134 [2021-12-28 00:32:47,102 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-28 00:32:47,102 INFO L470 AbstractCegarLoop]: Abstraction has 78 states and 94 transitions. [2021-12-28 00:32:47,102 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 23 states, 22 states have (on average 2.090909090909091) internal successors, (46), 22 states have internal predecessors, (46), 19 states have call successors, (19), 2 states have call predecessors, (19), 1 states have return successors, (18), 18 states have call predecessors, (18), 18 states have call successors, (18) [2021-12-28 00:32:47,102 INFO L276 IsEmpty]: Start isEmpty. Operand 78 states and 94 transitions. [2021-12-28 00:32:47,103 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 142 [2021-12-28 00:32:47,104 INFO L506 BasicCegarLoop]: Found error trace [2021-12-28 00:32:47,104 INFO L514 BasicCegarLoop]: trace histogram [20, 19, 19, 19, 19, 19, 18, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-28 00:32:47,109 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (20)] Forceful destruction successful, exit code 0 [2021-12-28 00:32:47,309 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable19,20 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-28 00:32:47,309 INFO L402 AbstractCegarLoop]: === Iteration 21 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-12-28 00:32:47,309 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-28 00:32:47,310 INFO L85 PathProgramCache]: Analyzing trace with hash 1332278625, now seen corresponding path program 18 times [2021-12-28 00:32:47,310 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-28 00:32:47,310 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [357232328] [2021-12-28 00:32:47,310 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-28 00:32:47,310 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-28 00:32:47,326 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-12-28 00:32:47,326 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [856211967] [2021-12-28 00:32:47,327 INFO L93 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2021-12-28 00:32:47,327 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-28 00:32:47,327 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-28 00:32:47,328 INFO L229 MonitoredProcess]: Starting monitored process 21 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2021-12-28 00:32:47,329 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (21)] Waiting until timeout for monitored process [2021-12-28 00:32:48,034 INFO L228 tOrderPrioritization]: Assert order MIX_INSIDE_OUTSIDE issued 19 check-sat command(s) [2021-12-28 00:32:48,035 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2021-12-28 00:32:48,039 INFO L263 TraceCheckSpWp]: Trace formula consists of 364 conjuncts, 80 conjunts are in the unsatisfiable core [2021-12-28 00:32:48,041 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-28 00:32:48,557 INFO L134 CoverageAnalysis]: Checked inductivity of 1235 backedges. 38 proven. 513 refuted. 0 times theorem prover too weak. 684 trivial. 0 not checked. [2021-12-28 00:32:48,558 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-28 00:32:48,670 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-28 00:32:48,671 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [357232328] [2021-12-28 00:32:48,671 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-12-28 00:32:48,671 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [856211967] [2021-12-28 00:32:48,671 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [856211967] provided 0 perfect and 1 imperfect interpolant sequences [2021-12-28 00:32:48,671 INFO L186 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2021-12-28 00:32:48,672 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [24] total 24 [2021-12-28 00:32:48,672 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [98877507] [2021-12-28 00:32:48,672 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2021-12-28 00:32:48,672 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 24 states [2021-12-28 00:32:48,672 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-28 00:32:48,682 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 24 interpolants. [2021-12-28 00:32:48,682 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=75, Invalid=627, Unknown=0, NotChecked=0, Total=702 [2021-12-28 00:32:48,682 INFO L87 Difference]: Start difference. First operand 78 states and 94 transitions. Second operand has 24 states, 23 states have (on average 2.0869565217391304) internal successors, (48), 23 states have internal predecessors, (48), 20 states have call successors, (20), 2 states have call predecessors, (20), 1 states have return successors, (19), 19 states have call predecessors, (19), 19 states have call successors, (19) [2021-12-28 00:32:49,119 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-28 00:32:49,120 INFO L93 Difference]: Finished difference Result 86 states and 103 transitions. [2021-12-28 00:32:49,120 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 24 states. [2021-12-28 00:32:49,120 INFO L78 Accepts]: Start accepts. Automaton has has 24 states, 23 states have (on average 2.0869565217391304) internal successors, (48), 23 states have internal predecessors, (48), 20 states have call successors, (20), 2 states have call predecessors, (20), 1 states have return successors, (19), 19 states have call predecessors, (19), 19 states have call successors, (19) Word has length 141 [2021-12-28 00:32:49,120 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-28 00:32:49,121 INFO L225 Difference]: With dead ends: 86 [2021-12-28 00:32:49,121 INFO L226 Difference]: Without dead ends: 81 [2021-12-28 00:32:49,121 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 155 GetRequests, 127 SyntacticMatches, 1 SemanticMatches, 27 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=85, Invalid=727, Unknown=0, NotChecked=0, Total=812 [2021-12-28 00:32:49,121 INFO L933 BasicCegarLoop]: 68 mSDtfsCounter, 2 mSDsluCounter, 1033 mSDsCounter, 0 mSdLazyCounter, 887 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 1101 SdHoareTripleChecker+Invalid, 887 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 887 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2021-12-28 00:32:49,121 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 1101 Invalid, 887 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 887 Invalid, 0 Unknown, 0 Unchecked, 0.4s Time] [2021-12-28 00:32:49,122 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 81 states. [2021-12-28 00:32:49,127 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 81 to 81. [2021-12-28 00:32:49,127 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 81 states, 56 states have (on average 1.0178571428571428) internal successors, (57), 56 states have internal predecessors, (57), 21 states have call successors, (21), 4 states have call predecessors, (21), 3 states have return successors, (20), 20 states have call predecessors, (20), 20 states have call successors, (20) [2021-12-28 00:32:49,127 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 81 states to 81 states and 98 transitions. [2021-12-28 00:32:49,127 INFO L78 Accepts]: Start accepts. Automaton has 81 states and 98 transitions. Word has length 141 [2021-12-28 00:32:49,127 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-28 00:32:49,127 INFO L470 AbstractCegarLoop]: Abstraction has 81 states and 98 transitions. [2021-12-28 00:32:49,128 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 24 states, 23 states have (on average 2.0869565217391304) internal successors, (48), 23 states have internal predecessors, (48), 20 states have call successors, (20), 2 states have call predecessors, (20), 1 states have return successors, (19), 19 states have call predecessors, (19), 19 states have call successors, (19) [2021-12-28 00:32:49,128 INFO L276 IsEmpty]: Start isEmpty. Operand 81 states and 98 transitions. [2021-12-28 00:32:49,128 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 149 [2021-12-28 00:32:49,128 INFO L506 BasicCegarLoop]: Found error trace [2021-12-28 00:32:49,128 INFO L514 BasicCegarLoop]: trace histogram [21, 20, 20, 20, 20, 20, 19, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-28 00:32:49,134 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (21)] Forceful destruction successful, exit code 0 [2021-12-28 00:32:49,329 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 21 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable20 [2021-12-28 00:32:49,329 INFO L402 AbstractCegarLoop]: === Iteration 22 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-12-28 00:32:49,329 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-28 00:32:49,329 INFO L85 PathProgramCache]: Analyzing trace with hash 2058456792, now seen corresponding path program 19 times [2021-12-28 00:32:49,329 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-28 00:32:49,329 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1658640185] [2021-12-28 00:32:49,329 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-28 00:32:49,330 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-28 00:32:49,341 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-12-28 00:32:49,341 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [625110145] [2021-12-28 00:32:49,341 INFO L93 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2021-12-28 00:32:49,341 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-28 00:32:49,341 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-28 00:32:49,342 INFO L229 MonitoredProcess]: Starting monitored process 22 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2021-12-28 00:32:49,343 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (22)] Waiting until timeout for monitored process [2021-12-28 00:32:50,386 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-28 00:32:50,389 INFO L263 TraceCheckSpWp]: Trace formula consists of 381 conjuncts, 84 conjunts are in the unsatisfiable core [2021-12-28 00:32:50,391 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-28 00:32:50,950 INFO L134 CoverageAnalysis]: Checked inductivity of 1370 backedges. 40 proven. 570 refuted. 0 times theorem prover too weak. 760 trivial. 0 not checked. [2021-12-28 00:32:50,950 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-28 00:32:51,130 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-28 00:32:51,130 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1658640185] [2021-12-28 00:32:51,130 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-12-28 00:32:51,130 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [625110145] [2021-12-28 00:32:51,130 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [625110145] provided 0 perfect and 1 imperfect interpolant sequences [2021-12-28 00:32:51,130 INFO L186 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2021-12-28 00:32:51,130 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [25] total 25 [2021-12-28 00:32:51,130 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [920892085] [2021-12-28 00:32:51,130 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2021-12-28 00:32:51,131 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 25 states [2021-12-28 00:32:51,131 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-28 00:32:51,131 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 25 interpolants. [2021-12-28 00:32:51,131 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=78, Invalid=678, Unknown=0, NotChecked=0, Total=756 [2021-12-28 00:32:51,131 INFO L87 Difference]: Start difference. First operand 81 states and 98 transitions. Second operand has 25 states, 24 states have (on average 2.0833333333333335) internal successors, (50), 24 states have internal predecessors, (50), 21 states have call successors, (21), 2 states have call predecessors, (21), 1 states have return successors, (20), 20 states have call predecessors, (20), 20 states have call successors, (20) [2021-12-28 00:32:51,649 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-28 00:32:51,649 INFO L93 Difference]: Finished difference Result 89 states and 107 transitions. [2021-12-28 00:32:51,651 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 25 states. [2021-12-28 00:32:51,651 INFO L78 Accepts]: Start accepts. Automaton has has 25 states, 24 states have (on average 2.0833333333333335) internal successors, (50), 24 states have internal predecessors, (50), 21 states have call successors, (21), 2 states have call predecessors, (21), 1 states have return successors, (20), 20 states have call predecessors, (20), 20 states have call successors, (20) Word has length 148 [2021-12-28 00:32:51,651 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-28 00:32:51,652 INFO L225 Difference]: With dead ends: 89 [2021-12-28 00:32:51,652 INFO L226 Difference]: Without dead ends: 84 [2021-12-28 00:32:51,652 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 162 GetRequests, 133 SyntacticMatches, 1 SemanticMatches, 28 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=88, Invalid=782, Unknown=0, NotChecked=0, Total=870 [2021-12-28 00:32:51,652 INFO L933 BasicCegarLoop]: 71 mSDtfsCounter, 2 mSDsluCounter, 1126 mSDsCounter, 0 mSdLazyCounter, 973 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 1197 SdHoareTripleChecker+Invalid, 973 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 973 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.5s IncrementalHoareTripleChecker+Time [2021-12-28 00:32:51,653 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 1197 Invalid, 973 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 973 Invalid, 0 Unknown, 0 Unchecked, 0.5s Time] [2021-12-28 00:32:51,653 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 84 states. [2021-12-28 00:32:51,662 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 84 to 84. [2021-12-28 00:32:51,663 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 84 states, 58 states have (on average 1.0172413793103448) internal successors, (59), 58 states have internal predecessors, (59), 22 states have call successors, (22), 4 states have call predecessors, (22), 3 states have return successors, (21), 21 states have call predecessors, (21), 21 states have call successors, (21) [2021-12-28 00:32:51,664 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 84 states to 84 states and 102 transitions. [2021-12-28 00:32:51,665 INFO L78 Accepts]: Start accepts. Automaton has 84 states and 102 transitions. Word has length 148 [2021-12-28 00:32:51,665 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-28 00:32:51,666 INFO L470 AbstractCegarLoop]: Abstraction has 84 states and 102 transitions. [2021-12-28 00:32:51,666 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 25 states, 24 states have (on average 2.0833333333333335) internal successors, (50), 24 states have internal predecessors, (50), 21 states have call successors, (21), 2 states have call predecessors, (21), 1 states have return successors, (20), 20 states have call predecessors, (20), 20 states have call successors, (20) [2021-12-28 00:32:51,666 INFO L276 IsEmpty]: Start isEmpty. Operand 84 states and 102 transitions. [2021-12-28 00:32:51,667 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 156 [2021-12-28 00:32:51,667 INFO L506 BasicCegarLoop]: Found error trace [2021-12-28 00:32:51,667 INFO L514 BasicCegarLoop]: trace histogram [22, 21, 21, 21, 21, 21, 20, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-28 00:32:51,672 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (22)] Forceful destruction successful, exit code 0 [2021-12-28 00:32:51,872 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 22 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable21 [2021-12-28 00:32:51,872 INFO L402 AbstractCegarLoop]: === Iteration 23 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-12-28 00:32:51,873 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-28 00:32:51,873 INFO L85 PathProgramCache]: Analyzing trace with hash 1810280833, now seen corresponding path program 20 times [2021-12-28 00:32:51,873 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-28 00:32:51,873 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1727681283] [2021-12-28 00:32:51,873 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-28 00:32:51,873 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-28 00:32:51,880 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-12-28 00:32:51,880 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1352097891] [2021-12-28 00:32:51,881 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2021-12-28 00:32:51,881 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-28 00:32:51,881 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-28 00:32:51,882 INFO L229 MonitoredProcess]: Starting monitored process 23 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2021-12-28 00:32:51,883 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (23)] Waiting until timeout for monitored process [2021-12-28 00:32:52,643 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2021-12-28 00:32:52,643 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2021-12-28 00:32:52,646 INFO L263 TraceCheckSpWp]: Trace formula consists of 398 conjuncts, 88 conjunts are in the unsatisfiable core [2021-12-28 00:32:52,648 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-28 00:32:53,072 INFO L134 CoverageAnalysis]: Checked inductivity of 1512 backedges. 42 proven. 630 refuted. 0 times theorem prover too weak. 840 trivial. 0 not checked. [2021-12-28 00:32:53,073 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-28 00:32:53,289 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-28 00:32:53,290 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1727681283] [2021-12-28 00:32:53,290 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-12-28 00:32:53,290 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1352097891] [2021-12-28 00:32:53,290 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1352097891] provided 0 perfect and 1 imperfect interpolant sequences [2021-12-28 00:32:53,290 INFO L186 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2021-12-28 00:32:53,290 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [26] total 26 [2021-12-28 00:32:53,290 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [585820514] [2021-12-28 00:32:53,290 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2021-12-28 00:32:53,290 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 26 states [2021-12-28 00:32:53,290 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-28 00:32:53,291 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 26 interpolants. [2021-12-28 00:32:53,291 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=81, Invalid=731, Unknown=0, NotChecked=0, Total=812 [2021-12-28 00:32:53,291 INFO L87 Difference]: Start difference. First operand 84 states and 102 transitions. Second operand has 26 states, 25 states have (on average 2.08) internal successors, (52), 25 states have internal predecessors, (52), 22 states have call successors, (22), 2 states have call predecessors, (22), 1 states have return successors, (21), 21 states have call predecessors, (21), 21 states have call successors, (21) [2021-12-28 00:32:53,706 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-28 00:32:53,707 INFO L93 Difference]: Finished difference Result 92 states and 111 transitions. [2021-12-28 00:32:53,707 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 26 states. [2021-12-28 00:32:53,707 INFO L78 Accepts]: Start accepts. Automaton has has 26 states, 25 states have (on average 2.08) internal successors, (52), 25 states have internal predecessors, (52), 22 states have call successors, (22), 2 states have call predecessors, (22), 1 states have return successors, (21), 21 states have call predecessors, (21), 21 states have call successors, (21) Word has length 155 [2021-12-28 00:32:53,707 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-28 00:32:53,708 INFO L225 Difference]: With dead ends: 92 [2021-12-28 00:32:53,708 INFO L226 Difference]: Without dead ends: 87 [2021-12-28 00:32:53,709 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 169 GetRequests, 139 SyntacticMatches, 1 SemanticMatches, 29 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=91, Invalid=839, Unknown=0, NotChecked=0, Total=930 [2021-12-28 00:32:53,712 INFO L933 BasicCegarLoop]: 74 mSDtfsCounter, 2 mSDsluCounter, 1223 mSDsCounter, 0 mSdLazyCounter, 1063 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 1297 SdHoareTripleChecker+Invalid, 1063 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 1063 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2021-12-28 00:32:53,712 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 1297 Invalid, 1063 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 1063 Invalid, 0 Unknown, 0 Unchecked, 0.4s Time] [2021-12-28 00:32:53,713 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 87 states. [2021-12-28 00:32:53,729 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 87 to 87. [2021-12-28 00:32:53,729 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 87 states, 60 states have (on average 1.0166666666666666) internal successors, (61), 60 states have internal predecessors, (61), 23 states have call successors, (23), 4 states have call predecessors, (23), 3 states have return successors, (22), 22 states have call predecessors, (22), 22 states have call successors, (22) [2021-12-28 00:32:53,730 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 87 states to 87 states and 106 transitions. [2021-12-28 00:32:53,731 INFO L78 Accepts]: Start accepts. Automaton has 87 states and 106 transitions. Word has length 155 [2021-12-28 00:32:53,731 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-28 00:32:53,732 INFO L470 AbstractCegarLoop]: Abstraction has 87 states and 106 transitions. [2021-12-28 00:32:53,732 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 26 states, 25 states have (on average 2.08) internal successors, (52), 25 states have internal predecessors, (52), 22 states have call successors, (22), 2 states have call predecessors, (22), 1 states have return successors, (21), 21 states have call predecessors, (21), 21 states have call successors, (21) [2021-12-28 00:32:53,732 INFO L276 IsEmpty]: Start isEmpty. Operand 87 states and 106 transitions. [2021-12-28 00:32:53,732 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 163 [2021-12-28 00:32:53,733 INFO L506 BasicCegarLoop]: Found error trace [2021-12-28 00:32:53,733 INFO L514 BasicCegarLoop]: trace histogram [23, 22, 22, 22, 22, 22, 21, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-28 00:32:53,737 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (23)] Forceful destruction successful, exit code 0 [2021-12-28 00:32:53,936 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable22,23 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-28 00:32:53,936 INFO L402 AbstractCegarLoop]: === Iteration 24 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-12-28 00:32:53,936 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-28 00:32:53,936 INFO L85 PathProgramCache]: Analyzing trace with hash 548269752, now seen corresponding path program 21 times [2021-12-28 00:32:53,936 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-28 00:32:53,936 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1507768904] [2021-12-28 00:32:53,936 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-28 00:32:53,936 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-28 00:32:53,942 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-12-28 00:32:53,942 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [23640215] [2021-12-28 00:32:53,942 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2021-12-28 00:32:53,942 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-28 00:32:53,942 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-28 00:32:53,943 INFO L229 MonitoredProcess]: Starting monitored process 24 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2021-12-28 00:32:53,945 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (24)] Waiting until timeout for monitored process [2021-12-28 00:32:54,690 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 22 check-sat command(s) [2021-12-28 00:32:54,690 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2021-12-28 00:32:54,694 INFO L263 TraceCheckSpWp]: Trace formula consists of 415 conjuncts, 92 conjunts are in the unsatisfiable core [2021-12-28 00:32:54,696 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-28 00:32:55,227 INFO L134 CoverageAnalysis]: Checked inductivity of 1661 backedges. 44 proven. 693 refuted. 0 times theorem prover too weak. 924 trivial. 0 not checked. [2021-12-28 00:32:55,227 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-28 00:32:55,386 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-28 00:32:55,386 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1507768904] [2021-12-28 00:32:55,386 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-12-28 00:32:55,386 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [23640215] [2021-12-28 00:32:55,386 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [23640215] provided 0 perfect and 1 imperfect interpolant sequences [2021-12-28 00:32:55,386 INFO L186 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2021-12-28 00:32:55,386 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [27] total 27 [2021-12-28 00:32:55,386 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1110650223] [2021-12-28 00:32:55,386 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2021-12-28 00:32:55,386 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 27 states [2021-12-28 00:32:55,387 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-28 00:32:55,387 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 27 interpolants. [2021-12-28 00:32:55,387 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=84, Invalid=786, Unknown=0, NotChecked=0, Total=870 [2021-12-28 00:32:55,387 INFO L87 Difference]: Start difference. First operand 87 states and 106 transitions. Second operand has 27 states, 26 states have (on average 2.076923076923077) internal successors, (54), 26 states have internal predecessors, (54), 23 states have call successors, (23), 2 states have call predecessors, (23), 1 states have return successors, (22), 22 states have call predecessors, (22), 22 states have call successors, (22) [2021-12-28 00:32:55,872 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-28 00:32:55,872 INFO L93 Difference]: Finished difference Result 95 states and 115 transitions. [2021-12-28 00:32:55,872 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 27 states. [2021-12-28 00:32:55,873 INFO L78 Accepts]: Start accepts. Automaton has has 27 states, 26 states have (on average 2.076923076923077) internal successors, (54), 26 states have internal predecessors, (54), 23 states have call successors, (23), 2 states have call predecessors, (23), 1 states have return successors, (22), 22 states have call predecessors, (22), 22 states have call successors, (22) Word has length 162 [2021-12-28 00:32:55,873 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-28 00:32:55,873 INFO L225 Difference]: With dead ends: 95 [2021-12-28 00:32:55,873 INFO L226 Difference]: Without dead ends: 90 [2021-12-28 00:32:55,874 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 176 GetRequests, 145 SyntacticMatches, 1 SemanticMatches, 30 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=94, Invalid=898, Unknown=0, NotChecked=0, Total=992 [2021-12-28 00:32:55,874 INFO L933 BasicCegarLoop]: 77 mSDtfsCounter, 2 mSDsluCounter, 1324 mSDsCounter, 0 mSdLazyCounter, 1157 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 1401 SdHoareTripleChecker+Invalid, 1157 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 1157 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.5s IncrementalHoareTripleChecker+Time [2021-12-28 00:32:55,874 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 1401 Invalid, 1157 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 1157 Invalid, 0 Unknown, 0 Unchecked, 0.5s Time] [2021-12-28 00:32:55,875 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 90 states. [2021-12-28 00:32:55,880 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 90 to 90. [2021-12-28 00:32:55,880 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 90 states, 62 states have (on average 1.0161290322580645) internal successors, (63), 62 states have internal predecessors, (63), 24 states have call successors, (24), 4 states have call predecessors, (24), 3 states have return successors, (23), 23 states have call predecessors, (23), 23 states have call successors, (23) [2021-12-28 00:32:55,880 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 90 states to 90 states and 110 transitions. [2021-12-28 00:32:55,890 INFO L78 Accepts]: Start accepts. Automaton has 90 states and 110 transitions. Word has length 162 [2021-12-28 00:32:55,890 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-28 00:32:55,890 INFO L470 AbstractCegarLoop]: Abstraction has 90 states and 110 transitions. [2021-12-28 00:32:55,890 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 27 states, 26 states have (on average 2.076923076923077) internal successors, (54), 26 states have internal predecessors, (54), 23 states have call successors, (23), 2 states have call predecessors, (23), 1 states have return successors, (22), 22 states have call predecessors, (22), 22 states have call successors, (22) [2021-12-28 00:32:55,890 INFO L276 IsEmpty]: Start isEmpty. Operand 90 states and 110 transitions. [2021-12-28 00:32:55,891 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 170 [2021-12-28 00:32:55,891 INFO L506 BasicCegarLoop]: Found error trace [2021-12-28 00:32:55,891 INFO L514 BasicCegarLoop]: trace histogram [24, 23, 23, 23, 23, 23, 22, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-28 00:32:55,899 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (24)] Forceful destruction successful, exit code 0 [2021-12-28 00:32:56,096 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable23,24 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-28 00:32:56,097 INFO L402 AbstractCegarLoop]: === Iteration 25 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-12-28 00:32:56,097 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-28 00:32:56,097 INFO L85 PathProgramCache]: Analyzing trace with hash -954681951, now seen corresponding path program 22 times [2021-12-28 00:32:56,097 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-28 00:32:56,097 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1610774582] [2021-12-28 00:32:56,097 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-28 00:32:56,097 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-28 00:32:56,103 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-12-28 00:32:56,103 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [296028294] [2021-12-28 00:32:56,103 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2021-12-28 00:32:56,103 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-28 00:32:56,104 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-28 00:32:56,104 INFO L229 MonitoredProcess]: Starting monitored process 25 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2021-12-28 00:32:56,105 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (25)] Waiting until timeout for monitored process [2021-12-28 00:32:56,651 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2021-12-28 00:32:56,652 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2021-12-28 00:32:56,654 INFO L263 TraceCheckSpWp]: Trace formula consists of 403 conjuncts, 96 conjunts are in the unsatisfiable core [2021-12-28 00:32:56,656 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-28 00:32:57,191 INFO L134 CoverageAnalysis]: Checked inductivity of 1817 backedges. 46 proven. 759 refuted. 0 times theorem prover too weak. 1012 trivial. 0 not checked. [2021-12-28 00:32:57,191 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-28 00:32:57,315 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-28 00:32:57,315 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1610774582] [2021-12-28 00:32:57,315 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-12-28 00:32:57,315 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [296028294] [2021-12-28 00:32:57,315 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [296028294] provided 0 perfect and 1 imperfect interpolant sequences [2021-12-28 00:32:57,315 INFO L186 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2021-12-28 00:32:57,315 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [28] total 28 [2021-12-28 00:32:57,316 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [633695270] [2021-12-28 00:32:57,316 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2021-12-28 00:32:57,317 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 28 states [2021-12-28 00:32:57,317 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-28 00:32:57,317 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 28 interpolants. [2021-12-28 00:32:57,317 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=87, Invalid=843, Unknown=0, NotChecked=0, Total=930 [2021-12-28 00:32:57,318 INFO L87 Difference]: Start difference. First operand 90 states and 110 transitions. Second operand has 28 states, 27 states have (on average 2.074074074074074) internal successors, (56), 27 states have internal predecessors, (56), 24 states have call successors, (24), 2 states have call predecessors, (24), 1 states have return successors, (23), 23 states have call predecessors, (23), 23 states have call successors, (23) [2021-12-28 00:32:57,855 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-28 00:32:57,856 INFO L93 Difference]: Finished difference Result 98 states and 119 transitions. [2021-12-28 00:32:57,856 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 28 states. [2021-12-28 00:32:57,856 INFO L78 Accepts]: Start accepts. Automaton has has 28 states, 27 states have (on average 2.074074074074074) internal successors, (56), 27 states have internal predecessors, (56), 24 states have call successors, (24), 2 states have call predecessors, (24), 1 states have return successors, (23), 23 states have call predecessors, (23), 23 states have call successors, (23) Word has length 169 [2021-12-28 00:32:57,856 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-28 00:32:57,857 INFO L225 Difference]: With dead ends: 98 [2021-12-28 00:32:57,857 INFO L226 Difference]: Without dead ends: 93 [2021-12-28 00:32:57,857 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 183 GetRequests, 151 SyntacticMatches, 1 SemanticMatches, 31 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=97, Invalid=959, Unknown=0, NotChecked=0, Total=1056 [2021-12-28 00:32:57,857 INFO L933 BasicCegarLoop]: 80 mSDtfsCounter, 2 mSDsluCounter, 1429 mSDsCounter, 0 mSdLazyCounter, 1255 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 1509 SdHoareTripleChecker+Invalid, 1255 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 1255 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.5s IncrementalHoareTripleChecker+Time [2021-12-28 00:32:57,858 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 1509 Invalid, 1255 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 1255 Invalid, 0 Unknown, 0 Unchecked, 0.5s Time] [2021-12-28 00:32:57,858 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 93 states. [2021-12-28 00:32:57,864 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 93 to 93. [2021-12-28 00:32:57,865 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 93 states, 64 states have (on average 1.015625) internal successors, (65), 64 states have internal predecessors, (65), 25 states have call successors, (25), 4 states have call predecessors, (25), 3 states have return successors, (24), 24 states have call predecessors, (24), 24 states have call successors, (24) [2021-12-28 00:32:57,865 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 93 states to 93 states and 114 transitions. [2021-12-28 00:32:57,865 INFO L78 Accepts]: Start accepts. Automaton has 93 states and 114 transitions. Word has length 169 [2021-12-28 00:32:57,866 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-28 00:32:57,866 INFO L470 AbstractCegarLoop]: Abstraction has 93 states and 114 transitions. [2021-12-28 00:32:57,866 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 28 states, 27 states have (on average 2.074074074074074) internal successors, (56), 27 states have internal predecessors, (56), 24 states have call successors, (24), 2 states have call predecessors, (24), 1 states have return successors, (23), 23 states have call predecessors, (23), 23 states have call successors, (23) [2021-12-28 00:32:57,866 INFO L276 IsEmpty]: Start isEmpty. Operand 93 states and 114 transitions. [2021-12-28 00:32:57,867 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 177 [2021-12-28 00:32:57,867 INFO L506 BasicCegarLoop]: Found error trace [2021-12-28 00:32:57,867 INFO L514 BasicCegarLoop]: trace histogram [25, 24, 24, 24, 24, 24, 23, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-28 00:32:57,872 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (25)] Ended with exit code 0 [2021-12-28 00:32:58,068 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 25 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable24 [2021-12-28 00:32:58,068 INFO L402 AbstractCegarLoop]: === Iteration 26 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-12-28 00:32:58,068 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-28 00:32:58,068 INFO L85 PathProgramCache]: Analyzing trace with hash -1441462632, now seen corresponding path program 23 times [2021-12-28 00:32:58,068 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-28 00:32:58,068 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1649201029] [2021-12-28 00:32:58,068 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-28 00:32:58,068 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-28 00:32:58,074 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-12-28 00:32:58,074 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1203506487] [2021-12-28 00:32:58,074 INFO L93 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2021-12-28 00:32:58,074 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-28 00:32:58,074 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-28 00:32:58,077 INFO L229 MonitoredProcess]: Starting monitored process 26 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2021-12-28 00:32:58,078 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (26)] Waiting until timeout for monitored process