./Ultimate.py --spec ../sv-benchmarks/c/properties/unreach-call.prp --file ../sv-benchmarks/c/nla-digbench/egcd2-ll.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version b5317dae 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/egcd2-ll.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 ed6536c9cb0e4b2be9a327fc4a25c6bfba6e98b1dfb78e314dd25bca8cbdb087 --- Real Ultimate output --- This is Ultimate 0.2.2-?-b5317da-m [2023-02-16 01:38:40,574 INFO L177 SettingsManager]: Resetting all preferences to default values... [2023-02-16 01:38:40,576 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2023-02-16 01:38:40,598 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2023-02-16 01:38:40,598 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2023-02-16 01:38:40,599 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2023-02-16 01:38:40,600 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2023-02-16 01:38:40,601 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2023-02-16 01:38:40,602 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2023-02-16 01:38:40,602 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2023-02-16 01:38:40,603 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2023-02-16 01:38:40,604 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2023-02-16 01:38:40,604 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2023-02-16 01:38:40,605 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2023-02-16 01:38:40,606 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2023-02-16 01:38:40,606 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2023-02-16 01:38:40,607 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2023-02-16 01:38:40,607 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2023-02-16 01:38:40,608 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2023-02-16 01:38:40,609 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2023-02-16 01:38:40,610 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2023-02-16 01:38:40,611 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2023-02-16 01:38:40,612 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2023-02-16 01:38:40,612 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2023-02-16 01:38:40,614 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2023-02-16 01:38:40,615 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2023-02-16 01:38:40,615 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2023-02-16 01:38:40,615 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2023-02-16 01:38:40,616 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2023-02-16 01:38:40,616 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2023-02-16 01:38:40,616 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2023-02-16 01:38:40,617 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2023-02-16 01:38:40,617 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2023-02-16 01:38:40,618 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2023-02-16 01:38:40,618 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2023-02-16 01:38:40,619 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2023-02-16 01:38:40,619 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2023-02-16 01:38:40,619 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2023-02-16 01:38:40,619 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2023-02-16 01:38:40,620 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2023-02-16 01:38:40,620 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2023-02-16 01:38:40,633 INFO L101 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf [2023-02-16 01:38:40,646 INFO L113 SettingsManager]: Loading preferences was successful [2023-02-16 01:38:40,650 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2023-02-16 01:38:40,650 INFO L136 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2023-02-16 01:38:40,650 INFO L138 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2023-02-16 01:38:40,651 INFO L136 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2023-02-16 01:38:40,651 INFO L138 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2023-02-16 01:38:40,651 INFO L136 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2023-02-16 01:38:40,652 INFO L138 SettingsManager]: * Create parallel compositions if possible=false [2023-02-16 01:38:40,652 INFO L138 SettingsManager]: * Use SBE=true [2023-02-16 01:38:40,652 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2023-02-16 01:38:40,652 INFO L138 SettingsManager]: * sizeof long=4 [2023-02-16 01:38:40,652 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2023-02-16 01:38:40,652 INFO L138 SettingsManager]: * sizeof POINTER=4 [2023-02-16 01:38:40,652 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2023-02-16 01:38:40,652 INFO L138 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2023-02-16 01:38:40,653 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2023-02-16 01:38:40,653 INFO L138 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2023-02-16 01:38:40,653 INFO L138 SettingsManager]: * sizeof long double=12 [2023-02-16 01:38:40,653 INFO L138 SettingsManager]: * Check if freed pointer was valid=false [2023-02-16 01:38:40,653 INFO L138 SettingsManager]: * Use constant arrays=true [2023-02-16 01:38:40,653 INFO L138 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2023-02-16 01:38:40,653 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2023-02-16 01:38:40,654 INFO L138 SettingsManager]: * Size of a code block=SequenceOfStatements [2023-02-16 01:38:40,654 INFO L138 SettingsManager]: * SMT solver=External_DefaultMode [2023-02-16 01:38:40,654 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2023-02-16 01:38:40,654 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2023-02-16 01:38:40,654 INFO L138 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2023-02-16 01:38:40,654 INFO L138 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2023-02-16 01:38:40,654 INFO L138 SettingsManager]: * Trace refinement strategy=CAMEL [2023-02-16 01:38:40,654 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2023-02-16 01:38:40,655 INFO L138 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2023-02-16 01:38:40,655 INFO L138 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2023-02-16 01:38:40,655 INFO L138 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2023-02-16 01:38:40,655 INFO L138 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2023-02-16 01:38:40,655 INFO L138 SettingsManager]: * Independence relation used for large block encoding in concurrent analysis=SYNTACTIC [2023-02-16 01:38:40,655 INFO L138 SettingsManager]: * Looper check in Petri net analysis=SEMANTIC 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 -> ed6536c9cb0e4b2be9a327fc4a25c6bfba6e98b1dfb78e314dd25bca8cbdb087 [2023-02-16 01:38:40,838 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2023-02-16 01:38:40,859 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2023-02-16 01:38:40,861 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2023-02-16 01:38:40,862 INFO L271 PluginConnector]: Initializing CDTParser... [2023-02-16 01:38:40,862 INFO L275 PluginConnector]: CDTParser initialized [2023-02-16 01:38:40,863 INFO L432 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/nla-digbench/egcd2-ll.c [2023-02-16 01:38:41,742 INFO L500 CDTParser]: Created temporary CDT project at NULL [2023-02-16 01:38:41,892 INFO L351 CDTParser]: Found 1 translation units. [2023-02-16 01:38:41,893 INFO L172 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench/egcd2-ll.c [2023-02-16 01:38:41,898 INFO L394 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/cfd6401e8/e412c05071294b6f9e3927a19cc05e35/FLAGef99eac4f [2023-02-16 01:38:41,909 INFO L402 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/cfd6401e8/e412c05071294b6f9e3927a19cc05e35 [2023-02-16 01:38:41,912 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2023-02-16 01:38:41,913 INFO L131 ToolchainWalker]: Walking toolchain with 6 elements. [2023-02-16 01:38:41,914 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2023-02-16 01:38:41,914 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2023-02-16 01:38:41,917 INFO L275 PluginConnector]: CACSL2BoogieTranslator initialized [2023-02-16 01:38:41,917 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 16.02 01:38:41" (1/1) ... [2023-02-16 01:38:41,920 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@276a977e and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.02 01:38:41, skipping insertion in model container [2023-02-16 01:38:41,920 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 16.02 01:38:41" (1/1) ... [2023-02-16 01:38:41,924 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2023-02-16 01:38:41,938 INFO L178 MainTranslator]: Built tables and reachable declarations [2023-02-16 01:38:42,045 WARN L237 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/egcd2-ll.c[490,503] [2023-02-16 01:38:42,061 INFO L210 PostProcessor]: Analyzing one entry point: main [2023-02-16 01:38:42,068 INFO L203 MainTranslator]: Completed pre-run [2023-02-16 01:38:42,075 WARN L237 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/egcd2-ll.c[490,503] [2023-02-16 01:38:42,081 INFO L210 PostProcessor]: Analyzing one entry point: main [2023-02-16 01:38:42,092 INFO L208 MainTranslator]: Completed translation [2023-02-16 01:38:42,092 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.02 01:38:42 WrapperNode [2023-02-16 01:38:42,092 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2023-02-16 01:38:42,093 INFO L113 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2023-02-16 01:38:42,093 INFO L271 PluginConnector]: Initializing Boogie Procedure Inliner... [2023-02-16 01:38:42,093 INFO L275 PluginConnector]: Boogie Procedure Inliner initialized [2023-02-16 01:38:42,098 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.02 01:38:42" (1/1) ... [2023-02-16 01:38:42,102 INFO L185 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.02 01:38:42" (1/1) ... [2023-02-16 01:38:42,113 INFO L138 Inliner]: procedures = 14, calls = 17, calls flagged for inlining = 2, calls inlined = 2, statements flattened = 75 [2023-02-16 01:38:42,113 INFO L132 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2023-02-16 01:38:42,114 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2023-02-16 01:38:42,114 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2023-02-16 01:38:42,114 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2023-02-16 01:38:42,119 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.02 01:38:42" (1/1) ... [2023-02-16 01:38:42,119 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.02 01:38:42" (1/1) ... [2023-02-16 01:38:42,124 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.02 01:38:42" (1/1) ... [2023-02-16 01:38:42,125 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.02 01:38:42" (1/1) ... [2023-02-16 01:38:42,127 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.02 01:38:42" (1/1) ... [2023-02-16 01:38:42,129 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.02 01:38:42" (1/1) ... [2023-02-16 01:38:42,130 INFO L185 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.02 01:38:42" (1/1) ... [2023-02-16 01:38:42,130 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.02 01:38:42" (1/1) ... [2023-02-16 01:38:42,131 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2023-02-16 01:38:42,132 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2023-02-16 01:38:42,132 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2023-02-16 01:38:42,132 INFO L275 PluginConnector]: RCFGBuilder initialized [2023-02-16 01:38:42,133 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.02 01:38:42" (1/1) ... [2023-02-16 01:38:42,137 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2023-02-16 01:38:42,144 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-16 01:38:42,159 INFO L229 MonitoredProcess]: Starting monitored process 1 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) [2023-02-16 01:38:42,164 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Waiting until timeout for monitored process [2023-02-16 01:38:42,192 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2023-02-16 01:38:42,192 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2023-02-16 01:38:42,193 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2023-02-16 01:38:42,193 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2023-02-16 01:38:42,193 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2023-02-16 01:38:42,193 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2023-02-16 01:38:42,193 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2023-02-16 01:38:42,193 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2023-02-16 01:38:42,244 INFO L235 CfgBuilder]: Building ICFG [2023-02-16 01:38:42,247 INFO L261 CfgBuilder]: Building CFG for each procedure with an implementation [2023-02-16 01:38:42,419 INFO L276 CfgBuilder]: Performing block encoding [2023-02-16 01:38:42,431 INFO L295 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2023-02-16 01:38:42,432 INFO L300 CfgBuilder]: Removed 2 assume(true) statements. [2023-02-16 01:38:42,433 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 16.02 01:38:42 BoogieIcfgContainer [2023-02-16 01:38:42,433 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2023-02-16 01:38:42,434 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2023-02-16 01:38:42,434 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2023-02-16 01:38:42,437 INFO L275 PluginConnector]: TraceAbstraction initialized [2023-02-16 01:38:42,437 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 16.02 01:38:41" (1/3) ... [2023-02-16 01:38:42,447 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@60aa8b99 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 16.02 01:38:42, skipping insertion in model container [2023-02-16 01:38:42,447 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.02 01:38:42" (2/3) ... [2023-02-16 01:38:42,448 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@60aa8b99 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 16.02 01:38:42, skipping insertion in model container [2023-02-16 01:38:42,448 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 16.02 01:38:42" (3/3) ... [2023-02-16 01:38:42,449 INFO L112 eAbstractionObserver]: Analyzing ICFG egcd2-ll.c [2023-02-16 01:38:42,467 INFO L203 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2023-02-16 01:38:42,467 INFO L162 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2023-02-16 01:38:42,498 INFO L356 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2023-02-16 01:38:42,505 INFO L357 AbstractCegarLoop]: Settings: SEPARATE_VIOLATION_CHECK=true, mInterprocedural=true, mMaxIterations=1000000, mWatchIteration=1000000, mArtifact=RCFG, mInterpolation=FPandBP, mInterpolantAutomaton=STRAIGHT_LINE, mDumpAutomata=false, mAutomataFormat=ATS_NUMERATE, mDumpPath=., mDeterminiation=PREDICATE_ABSTRACTION, mMinimize=MINIMIZE_SEVPA, mHoare=true, mAutomataTypeConcurrency=PETRI_NET, mHoareTripleChecks=INCREMENTAL, mHoareAnnotationPositions=LoopsAndPotentialCycles, mDumpOnlyReuseAutomata=false, mLimitTraceHistogram=0, mErrorLocTimeLimit=0, mLimitPathProgramCount=0, mCollectInterpolantStatistics=true, mHeuristicEmptinessCheck=false, mHeuristicEmptinessCheckAStarHeuristic=ZERO, mHeuristicEmptinessCheckAStarHeuristicRandomSeed=1337, mHeuristicEmptinessCheckSmtFeatureScoringMethod=DAGSIZE, mSMTFeatureExtraction=false, mSMTFeatureExtractionDumpPath=., mOverrideInterpolantAutomaton=false, mMcrInterpolantMethod=WP, mPorIndependenceSettings=[Lde.uni_freiburg.informatik.ultimate.lib.tracecheckerutils.partialorder.independence.IndependenceSettings;@4e75294b, mLbeIndependenceSettings=[IndependenceType=SYNTACTIC, AbstractionType=NONE, UseConditional=, UseSemiCommutativity=, Solver=, SolverTimeout=] [2023-02-16 01:38:42,506 INFO L358 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2023-02-16 01:38:42,508 INFO L276 IsEmpty]: Start isEmpty. Operand has 32 states, 18 states have (on average 1.5) internal successors, (27), 20 states have internal predecessors, (27), 10 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2023-02-16 01:38:42,514 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 29 [2023-02-16 01:38:42,514 INFO L187 NwaCegarLoop]: Found error trace [2023-02-16 01:38:42,514 INFO L195 NwaCegarLoop]: trace histogram [4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-02-16 01:38:42,515 INFO L420 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-02-16 01:38:42,519 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2023-02-16 01:38:42,520 INFO L85 PathProgramCache]: Analyzing trace with hash 223354930, now seen corresponding path program 1 times [2023-02-16 01:38:42,526 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-02-16 01:38:42,526 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1407196966] [2023-02-16 01:38:42,526 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-16 01:38:42,526 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-02-16 01:38:42,608 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-02-16 01:38:42,623 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-02-16 01:38:42,624 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1407196966] [2023-02-16 01:38:42,624 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: Unsupported non-linear arithmetic [2023-02-16 01:38:42,624 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1952921454] [2023-02-16 01:38:42,626 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-16 01:38:42,626 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-02-16 01:38:42,626 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-16 01:38:42,628 INFO L229 MonitoredProcess]: Starting monitored process 2 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-02-16 01:38:42,631 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2023-02-16 01:38:42,697 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-02-16 01:38:42,699 INFO L263 TraceCheckSpWp]: Trace formula consists of 95 conjuncts, 1 conjunts are in the unsatisfiable core [2023-02-16 01:38:42,702 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2023-02-16 01:38:42,718 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 6 proven. 0 refuted. 0 times theorem prover too weak. 18 trivial. 0 not checked. [2023-02-16 01:38:42,719 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2023-02-16 01:38:42,720 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1952921454] provided 1 perfect and 0 imperfect interpolant sequences [2023-02-16 01:38:42,720 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-02-16 01:38:42,721 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2023-02-16 01:38:42,722 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1292594827] [2023-02-16 01:38:42,724 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-02-16 01:38:42,726 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2023-02-16 01:38:42,727 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-02-16 01:38:42,752 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2023-02-16 01:38:42,752 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2023-02-16 01:38:42,754 INFO L87 Difference]: Start difference. First operand has 32 states, 18 states have (on average 1.5) internal successors, (27), 20 states have internal predecessors, (27), 10 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) Second operand has 2 states, 2 states have (on average 6.0) internal successors, (12), 2 states have internal predecessors, (12), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 2 states have call successors, (4) [2023-02-16 01:38:42,777 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-02-16 01:38:42,777 INFO L93 Difference]: Finished difference Result 61 states and 100 transitions. [2023-02-16 01:38:42,778 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2023-02-16 01:38:42,779 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 6.0) internal successors, (12), 2 states have internal predecessors, (12), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 2 states have call successors, (4) Word has length 28 [2023-02-16 01:38:42,779 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-02-16 01:38:42,783 INFO L225 Difference]: With dead ends: 61 [2023-02-16 01:38:42,783 INFO L226 Difference]: Without dead ends: 28 [2023-02-16 01:38:42,785 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 27 GetRequests, 27 SyntacticMatches, 0 SemanticMatches, 0 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2023-02-16 01:38:42,787 INFO L413 NwaCegarLoop]: 41 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, 41 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 [2023-02-16 01:38:42,788 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 41 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 0 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-02-16 01:38:42,799 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 28 states. [2023-02-16 01:38:42,813 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 28 to 28. [2023-02-16 01:38:42,814 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 28 states, 15 states have (on average 1.2) internal successors, (18), 17 states have internal predecessors, (18), 10 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2023-02-16 01:38:42,816 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 28 states to 28 states and 37 transitions. [2023-02-16 01:38:42,818 INFO L78 Accepts]: Start accepts. Automaton has 28 states and 37 transitions. Word has length 28 [2023-02-16 01:38:42,818 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-02-16 01:38:42,818 INFO L495 AbstractCegarLoop]: Abstraction has 28 states and 37 transitions. [2023-02-16 01:38:42,818 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 2 states have (on average 6.0) internal successors, (12), 2 states have internal predecessors, (12), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 2 states have call successors, (4) [2023-02-16 01:38:42,819 INFO L276 IsEmpty]: Start isEmpty. Operand 28 states and 37 transitions. [2023-02-16 01:38:42,821 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 30 [2023-02-16 01:38:42,821 INFO L187 NwaCegarLoop]: Found error trace [2023-02-16 01:38:42,821 INFO L195 NwaCegarLoop]: trace histogram [4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-02-16 01:38:42,828 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Ended with exit code 0 [2023-02-16 01:38:43,026 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable0 [2023-02-16 01:38:43,026 INFO L420 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-02-16 01:38:43,027 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2023-02-16 01:38:43,027 INFO L85 PathProgramCache]: Analyzing trace with hash 727709964, now seen corresponding path program 1 times [2023-02-16 01:38:43,027 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-02-16 01:38:43,027 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [199670306] [2023-02-16 01:38:43,028 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-16 01:38:43,028 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-02-16 01:38:43,039 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-02-16 01:38:43,039 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1604840967] [2023-02-16 01:38:43,041 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-16 01:38:43,041 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-02-16 01:38:43,041 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-16 01:38:43,042 INFO L229 MonitoredProcess]: Starting monitored process 3 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-02-16 01:38:43,044 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2023-02-16 01:38:43,090 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-02-16 01:38:43,091 INFO L263 TraceCheckSpWp]: Trace formula consists of 97 conjuncts, 7 conjunts are in the unsatisfiable core [2023-02-16 01:38:43,093 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2023-02-16 01:38:43,170 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 3 proven. 6 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2023-02-16 01:38:43,170 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2023-02-16 01:38:43,295 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 3 proven. 6 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2023-02-16 01:38:43,295 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-02-16 01:38:43,295 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [199670306] [2023-02-16 01:38:43,295 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-02-16 01:38:43,295 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1604840967] [2023-02-16 01:38:43,296 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1604840967] provided 0 perfect and 2 imperfect interpolant sequences [2023-02-16 01:38:43,296 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-02-16 01:38:43,296 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 7 [2023-02-16 01:38:43,296 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [901237484] [2023-02-16 01:38:43,296 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-02-16 01:38:43,297 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2023-02-16 01:38:43,297 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-02-16 01:38:43,297 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2023-02-16 01:38:43,297 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=29, Unknown=0, NotChecked=0, Total=42 [2023-02-16 01:38:43,299 INFO L87 Difference]: Start difference. First operand 28 states and 37 transitions. Second operand has 7 states, 7 states have (on average 2.2857142857142856) internal successors, (16), 6 states have internal predecessors, (16), 3 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (4), 3 states have call predecessors, (4), 2 states have call successors, (4) [2023-02-16 01:38:43,407 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-02-16 01:38:43,407 INFO L93 Difference]: Finished difference Result 45 states and 60 transitions. [2023-02-16 01:38:43,407 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2023-02-16 01:38:43,407 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 7 states have (on average 2.2857142857142856) internal successors, (16), 6 states have internal predecessors, (16), 3 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (4), 3 states have call predecessors, (4), 2 states have call successors, (4) Word has length 29 [2023-02-16 01:38:43,408 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-02-16 01:38:43,410 INFO L225 Difference]: With dead ends: 45 [2023-02-16 01:38:43,410 INFO L226 Difference]: Without dead ends: 37 [2023-02-16 01:38:43,411 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 58 GetRequests, 48 SyntacticMatches, 3 SemanticMatches, 7 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=22, Invalid=50, Unknown=0, NotChecked=0, Total=72 [2023-02-16 01:38:43,411 INFO L413 NwaCegarLoop]: 31 mSDtfsCounter, 20 mSDsluCounter, 68 mSDsCounter, 0 mSdLazyCounter, 74 mSolverCounterSat, 10 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 25 SdHoareTripleChecker+Valid, 99 SdHoareTripleChecker+Invalid, 84 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 10 IncrementalHoareTripleChecker+Valid, 74 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-02-16 01:38:43,414 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [25 Valid, 99 Invalid, 84 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [10 Valid, 74 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-02-16 01:38:43,415 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 37 states. [2023-02-16 01:38:43,421 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 37 to 30. [2023-02-16 01:38:43,422 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 30 states, 17 states have (on average 1.1764705882352942) internal successors, (20), 18 states have internal predecessors, (20), 10 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2023-02-16 01:38:43,424 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 30 states to 30 states and 39 transitions. [2023-02-16 01:38:43,424 INFO L78 Accepts]: Start accepts. Automaton has 30 states and 39 transitions. Word has length 29 [2023-02-16 01:38:43,425 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-02-16 01:38:43,425 INFO L495 AbstractCegarLoop]: Abstraction has 30 states and 39 transitions. [2023-02-16 01:38:43,425 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 7 states have (on average 2.2857142857142856) internal successors, (16), 6 states have internal predecessors, (16), 3 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (4), 3 states have call predecessors, (4), 2 states have call successors, (4) [2023-02-16 01:38:43,425 INFO L276 IsEmpty]: Start isEmpty. Operand 30 states and 39 transitions. [2023-02-16 01:38:43,426 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 31 [2023-02-16 01:38:43,426 INFO L187 NwaCegarLoop]: Found error trace [2023-02-16 01:38:43,426 INFO L195 NwaCegarLoop]: trace histogram [4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-02-16 01:38:43,440 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2023-02-16 01:38:43,633 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 3 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable1 [2023-02-16 01:38:43,633 INFO L420 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-02-16 01:38:43,635 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2023-02-16 01:38:43,635 INFO L85 PathProgramCache]: Analyzing trace with hash 1088429638, now seen corresponding path program 1 times [2023-02-16 01:38:43,635 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-02-16 01:38:43,635 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [722962663] [2023-02-16 01:38:43,635 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-16 01:38:43,635 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-02-16 01:38:43,648 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-02-16 01:38:43,648 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2048856666] [2023-02-16 01:38:43,648 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-16 01:38:43,648 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-02-16 01:38:43,648 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-16 01:38:43,649 INFO L229 MonitoredProcess]: Starting monitored process 4 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-02-16 01:38:43,651 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2023-02-16 01:38:43,690 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-02-16 01:38:43,690 INFO L263 TraceCheckSpWp]: Trace formula consists of 101 conjuncts, 17 conjunts are in the unsatisfiable core [2023-02-16 01:38:43,692 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2023-02-16 01:38:43,777 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 3 proven. 6 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2023-02-16 01:38:43,778 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2023-02-16 01:38:43,834 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2023-02-16 01:38:43,834 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-02-16 01:38:43,835 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [722962663] [2023-02-16 01:38:43,835 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-02-16 01:38:43,835 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2048856666] [2023-02-16 01:38:43,835 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2048856666] provided 1 perfect and 1 imperfect interpolant sequences [2023-02-16 01:38:43,835 INFO L184 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2023-02-16 01:38:43,835 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [9] total 12 [2023-02-16 01:38:43,835 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1127796473] [2023-02-16 01:38:43,836 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-02-16 01:38:43,836 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2023-02-16 01:38:43,836 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-02-16 01:38:43,837 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2023-02-16 01:38:43,837 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=25, Invalid=107, Unknown=0, NotChecked=0, Total=132 [2023-02-16 01:38:43,837 INFO L87 Difference]: Start difference. First operand 30 states and 39 transitions. Second operand has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2023-02-16 01:38:43,873 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-02-16 01:38:43,874 INFO L93 Difference]: Finished difference Result 36 states and 44 transitions. [2023-02-16 01:38:43,875 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2023-02-16 01:38:43,876 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), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) Word has length 30 [2023-02-16 01:38:43,876 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-02-16 01:38:43,876 INFO L225 Difference]: With dead ends: 36 [2023-02-16 01:38:43,876 INFO L226 Difference]: Without dead ends: 34 [2023-02-16 01:38:43,877 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 59 GetRequests, 48 SyntacticMatches, 0 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 9 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=29, Invalid=127, Unknown=0, NotChecked=0, Total=156 [2023-02-16 01:38:43,877 INFO L413 NwaCegarLoop]: 31 mSDtfsCounter, 7 mSDsluCounter, 69 mSDsCounter, 0 mSdLazyCounter, 37 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 11 SdHoareTripleChecker+Valid, 100 SdHoareTripleChecker+Invalid, 39 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 37 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-02-16 01:38:43,878 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [11 Valid, 100 Invalid, 39 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 37 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-02-16 01:38:43,878 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 34 states. [2023-02-16 01:38:43,883 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 34 to 34. [2023-02-16 01:38:43,883 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 34 states, 20 states have (on average 1.15) internal successors, (23), 21 states have internal predecessors, (23), 10 states have call successors, (10), 3 states have call predecessors, (10), 3 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2023-02-16 01:38:43,883 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 34 states to 34 states and 42 transitions. [2023-02-16 01:38:43,884 INFO L78 Accepts]: Start accepts. Automaton has 34 states and 42 transitions. Word has length 30 [2023-02-16 01:38:43,884 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-02-16 01:38:43,884 INFO L495 AbstractCegarLoop]: Abstraction has 34 states and 42 transitions. [2023-02-16 01:38:43,884 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2023-02-16 01:38:43,884 INFO L276 IsEmpty]: Start isEmpty. Operand 34 states and 42 transitions. [2023-02-16 01:38:43,885 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 36 [2023-02-16 01:38:43,885 INFO L187 NwaCegarLoop]: Found error trace [2023-02-16 01:38:43,885 INFO L195 NwaCegarLoop]: trace histogram [4, 4, 4, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-02-16 01:38:43,896 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Forceful destruction successful, exit code 0 [2023-02-16 01:38:44,089 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-02-16 01:38:44,090 INFO L420 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-02-16 01:38:44,090 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2023-02-16 01:38:44,091 INFO L85 PathProgramCache]: Analyzing trace with hash 161014808, now seen corresponding path program 1 times [2023-02-16 01:38:44,091 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-02-16 01:38:44,093 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [51948531] [2023-02-16 01:38:44,093 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-16 01:38:44,093 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-02-16 01:38:44,103 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-02-16 01:38:44,108 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [49179311] [2023-02-16 01:38:44,108 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-16 01:38:44,108 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-02-16 01:38:44,108 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-16 01:38:44,109 INFO L229 MonitoredProcess]: Starting monitored process 5 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-02-16 01:38:44,110 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2023-02-16 01:38:44,157 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-02-16 01:38:44,158 INFO L263 TraceCheckSpWp]: Trace formula consists of 110 conjuncts, 18 conjunts are in the unsatisfiable core [2023-02-16 01:38:44,161 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2023-02-16 01:38:44,286 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 5 proven. 6 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2023-02-16 01:38:44,286 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2023-02-16 01:38:44,352 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2023-02-16 01:38:44,352 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-02-16 01:38:44,352 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [51948531] [2023-02-16 01:38:44,352 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-02-16 01:38:44,353 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [49179311] [2023-02-16 01:38:44,353 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [49179311] provided 1 perfect and 1 imperfect interpolant sequences [2023-02-16 01:38:44,353 INFO L184 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2023-02-16 01:38:44,353 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [9] total 12 [2023-02-16 01:38:44,353 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1692801369] [2023-02-16 01:38:44,353 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-02-16 01:38:44,354 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2023-02-16 01:38:44,354 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-02-16 01:38:44,354 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2023-02-16 01:38:44,354 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=27, Invalid=105, Unknown=0, NotChecked=0, Total=132 [2023-02-16 01:38:44,355 INFO L87 Difference]: Start difference. First operand 34 states and 42 transitions. Second operand has 5 states, 5 states have (on average 3.0) internal successors, (15), 4 states have internal predecessors, (15), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2023-02-16 01:38:44,391 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-02-16 01:38:44,392 INFO L93 Difference]: Finished difference Result 47 states and 59 transitions. [2023-02-16 01:38:44,392 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2023-02-16 01:38:44,393 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.0) internal successors, (15), 4 states have internal predecessors, (15), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) Word has length 35 [2023-02-16 01:38:44,393 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-02-16 01:38:44,393 INFO L225 Difference]: With dead ends: 47 [2023-02-16 01:38:44,393 INFO L226 Difference]: Without dead ends: 45 [2023-02-16 01:38:44,394 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 69 GetRequests, 58 SyntacticMatches, 0 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 15 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=31, Invalid=125, Unknown=0, NotChecked=0, Total=156 [2023-02-16 01:38:44,394 INFO L413 NwaCegarLoop]: 39 mSDtfsCounter, 6 mSDsluCounter, 85 mSDsCounter, 0 mSdLazyCounter, 37 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 9 SdHoareTripleChecker+Valid, 124 SdHoareTripleChecker+Invalid, 38 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 37 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-02-16 01:38:44,394 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [9 Valid, 124 Invalid, 38 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 37 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-02-16 01:38:44,395 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 45 states. [2023-02-16 01:38:44,401 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 45 to 44. [2023-02-16 01:38:44,402 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 44 states, 25 states have (on average 1.16) internal successors, (29), 26 states have internal predecessors, (29), 14 states have call successors, (14), 4 states have call predecessors, (14), 4 states have return successors, (13), 13 states have call predecessors, (13), 13 states have call successors, (13) [2023-02-16 01:38:44,402 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 44 states to 44 states and 56 transitions. [2023-02-16 01:38:44,402 INFO L78 Accepts]: Start accepts. Automaton has 44 states and 56 transitions. Word has length 35 [2023-02-16 01:38:44,402 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-02-16 01:38:44,402 INFO L495 AbstractCegarLoop]: Abstraction has 44 states and 56 transitions. [2023-02-16 01:38:44,403 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.0) internal successors, (15), 4 states have internal predecessors, (15), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2023-02-16 01:38:44,403 INFO L276 IsEmpty]: Start isEmpty. Operand 44 states and 56 transitions. [2023-02-16 01:38:44,403 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 41 [2023-02-16 01:38:44,403 INFO L187 NwaCegarLoop]: Found error trace [2023-02-16 01:38:44,403 INFO L195 NwaCegarLoop]: trace histogram [4, 4, 4, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-02-16 01:38:44,413 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Forceful destruction successful, exit code 0 [2023-02-16 01:38:44,608 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-02-16 01:38:44,608 INFO L420 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-02-16 01:38:44,608 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2023-02-16 01:38:44,608 INFO L85 PathProgramCache]: Analyzing trace with hash -2062939834, now seen corresponding path program 1 times [2023-02-16 01:38:44,609 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-02-16 01:38:44,609 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1802558239] [2023-02-16 01:38:44,609 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-16 01:38:44,609 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-02-16 01:38:44,626 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-02-16 01:38:44,626 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [105811685] [2023-02-16 01:38:44,626 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-16 01:38:44,626 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-02-16 01:38:44,626 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-16 01:38:44,633 INFO L229 MonitoredProcess]: Starting monitored process 6 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-02-16 01:38:44,636 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2023-02-16 01:38:44,676 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-02-16 01:38:44,677 INFO L263 TraceCheckSpWp]: Trace formula consists of 119 conjuncts, 23 conjunts are in the unsatisfiable core [2023-02-16 01:38:44,681 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2023-02-16 01:38:44,842 INFO L134 CoverageAnalysis]: Checked inductivity of 32 backedges. 3 proven. 13 refuted. 0 times theorem prover too weak. 16 trivial. 0 not checked. [2023-02-16 01:38:44,843 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2023-02-16 01:38:44,926 INFO L134 CoverageAnalysis]: Checked inductivity of 32 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2023-02-16 01:38:44,926 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-02-16 01:38:44,926 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1802558239] [2023-02-16 01:38:44,926 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-02-16 01:38:44,926 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [105811685] [2023-02-16 01:38:44,926 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [105811685] provided 1 perfect and 1 imperfect interpolant sequences [2023-02-16 01:38:44,927 INFO L184 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2023-02-16 01:38:44,927 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [11] total 13 [2023-02-16 01:38:44,927 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [643969069] [2023-02-16 01:38:44,927 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-02-16 01:38:44,927 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2023-02-16 01:38:44,927 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-02-16 01:38:44,929 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2023-02-16 01:38:44,930 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=29, Invalid=127, Unknown=0, NotChecked=0, Total=156 [2023-02-16 01:38:44,930 INFO L87 Difference]: Start difference. First operand 44 states and 56 transitions. Second operand has 5 states, 5 states have (on average 3.0) internal successors, (15), 4 states have internal predecessors, (15), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) [2023-02-16 01:38:44,970 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-02-16 01:38:44,971 INFO L93 Difference]: Finished difference Result 51 states and 62 transitions. [2023-02-16 01:38:44,971 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2023-02-16 01:38:44,971 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.0) internal successors, (15), 4 states have internal predecessors, (15), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) Word has length 40 [2023-02-16 01:38:44,973 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-02-16 01:38:44,974 INFO L225 Difference]: With dead ends: 51 [2023-02-16 01:38:44,974 INFO L226 Difference]: Without dead ends: 49 [2023-02-16 01:38:44,975 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 79 GetRequests, 67 SyntacticMatches, 0 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 18 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=33, Invalid=149, Unknown=0, NotChecked=0, Total=182 [2023-02-16 01:38:44,976 INFO L413 NwaCegarLoop]: 37 mSDtfsCounter, 6 mSDsluCounter, 78 mSDsCounter, 0 mSdLazyCounter, 46 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 8 SdHoareTripleChecker+Valid, 115 SdHoareTripleChecker+Invalid, 47 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 46 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-02-16 01:38:44,978 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [8 Valid, 115 Invalid, 47 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 46 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-02-16 01:38:44,979 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 49 states. [2023-02-16 01:38:44,990 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 49 to 48. [2023-02-16 01:38:44,991 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 48 states, 28 states have (on average 1.1428571428571428) internal successors, (32), 29 states have internal predecessors, (32), 14 states have call successors, (14), 5 states have call predecessors, (14), 5 states have return successors, (13), 13 states have call predecessors, (13), 13 states have call successors, (13) [2023-02-16 01:38:44,991 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 48 states to 48 states and 59 transitions. [2023-02-16 01:38:44,991 INFO L78 Accepts]: Start accepts. Automaton has 48 states and 59 transitions. Word has length 40 [2023-02-16 01:38:44,992 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-02-16 01:38:44,992 INFO L495 AbstractCegarLoop]: Abstraction has 48 states and 59 transitions. [2023-02-16 01:38:44,992 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.0) internal successors, (15), 4 states have internal predecessors, (15), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) [2023-02-16 01:38:44,992 INFO L276 IsEmpty]: Start isEmpty. Operand 48 states and 59 transitions. [2023-02-16 01:38:44,993 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 46 [2023-02-16 01:38:44,993 INFO L187 NwaCegarLoop]: Found error trace [2023-02-16 01:38:44,993 INFO L195 NwaCegarLoop]: trace histogram [4, 4, 4, 4, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-02-16 01:38:45,007 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Forceful destruction successful, exit code 0 [2023-02-16 01:38:45,197 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-02-16 01:38:45,198 INFO L420 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-02-16 01:38:45,198 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2023-02-16 01:38:45,199 INFO L85 PathProgramCache]: Analyzing trace with hash -98301800, now seen corresponding path program 1 times [2023-02-16 01:38:45,199 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-02-16 01:38:45,199 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [541419591] [2023-02-16 01:38:45,199 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-16 01:38:45,199 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-02-16 01:38:45,221 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-02-16 01:38:45,221 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2078727218] [2023-02-16 01:38:45,221 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-16 01:38:45,221 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-02-16 01:38:45,222 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-16 01:38:45,226 INFO L229 MonitoredProcess]: Starting monitored process 7 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-02-16 01:38:45,228 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2023-02-16 01:38:45,273 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-02-16 01:38:45,274 INFO L263 TraceCheckSpWp]: Trace formula consists of 128 conjuncts, 17 conjunts are in the unsatisfiable core [2023-02-16 01:38:45,275 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2023-02-16 01:38:45,363 INFO L134 CoverageAnalysis]: Checked inductivity of 42 backedges. 11 proven. 1 refuted. 0 times theorem prover too weak. 30 trivial. 0 not checked. [2023-02-16 01:38:45,363 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2023-02-16 01:38:45,467 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-02-16 01:38:45,467 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [541419591] [2023-02-16 01:38:45,467 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-02-16 01:38:45,467 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2078727218] [2023-02-16 01:38:45,467 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2078727218] provided 0 perfect and 1 imperfect interpolant sequences [2023-02-16 01:38:45,468 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2023-02-16 01:38:45,468 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8] total 8 [2023-02-16 01:38:45,468 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1027503434] [2023-02-16 01:38:45,468 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2023-02-16 01:38:45,468 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2023-02-16 01:38:45,468 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-02-16 01:38:45,468 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2023-02-16 01:38:45,469 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=25, Invalid=85, Unknown=0, NotChecked=0, Total=110 [2023-02-16 01:38:45,469 INFO L87 Difference]: Start difference. First operand 48 states and 59 transitions. Second operand has 8 states, 7 states have (on average 2.5714285714285716) internal successors, (18), 6 states have internal predecessors, (18), 3 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (7), 3 states have call predecessors, (7), 2 states have call successors, (7) [2023-02-16 01:38:45,580 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-02-16 01:38:45,580 INFO L93 Difference]: Finished difference Result 55 states and 65 transitions. [2023-02-16 01:38:45,580 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2023-02-16 01:38:45,580 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 7 states have (on average 2.5714285714285716) internal successors, (18), 6 states have internal predecessors, (18), 3 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (7), 3 states have call predecessors, (7), 2 states have call successors, (7) Word has length 45 [2023-02-16 01:38:45,581 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-02-16 01:38:45,581 INFO L225 Difference]: With dead ends: 55 [2023-02-16 01:38:45,581 INFO L226 Difference]: Without dead ends: 53 [2023-02-16 01:38:45,581 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 51 GetRequests, 40 SyntacticMatches, 0 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 14 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=38, Invalid=118, Unknown=0, NotChecked=0, Total=156 [2023-02-16 01:38:45,582 INFO L413 NwaCegarLoop]: 27 mSDtfsCounter, 15 mSDsluCounter, 85 mSDsCounter, 0 mSdLazyCounter, 124 mSolverCounterSat, 4 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 20 SdHoareTripleChecker+Valid, 112 SdHoareTripleChecker+Invalid, 128 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 4 IncrementalHoareTripleChecker+Valid, 124 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-02-16 01:38:45,582 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [20 Valid, 112 Invalid, 128 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [4 Valid, 124 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-02-16 01:38:45,583 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 53 states. [2023-02-16 01:38:45,589 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 53 to 52. [2023-02-16 01:38:45,589 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 52 states, 31 states have (on average 1.1290322580645162) internal successors, (35), 32 states have internal predecessors, (35), 14 states have call successors, (14), 6 states have call predecessors, (14), 6 states have return successors, (13), 13 states have call predecessors, (13), 13 states have call successors, (13) [2023-02-16 01:38:45,590 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 52 states to 52 states and 62 transitions. [2023-02-16 01:38:45,590 INFO L78 Accepts]: Start accepts. Automaton has 52 states and 62 transitions. Word has length 45 [2023-02-16 01:38:45,590 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-02-16 01:38:45,590 INFO L495 AbstractCegarLoop]: Abstraction has 52 states and 62 transitions. [2023-02-16 01:38:45,590 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 7 states have (on average 2.5714285714285716) internal successors, (18), 6 states have internal predecessors, (18), 3 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (7), 3 states have call predecessors, (7), 2 states have call successors, (7) [2023-02-16 01:38:45,590 INFO L276 IsEmpty]: Start isEmpty. Operand 52 states and 62 transitions. [2023-02-16 01:38:45,591 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 55 [2023-02-16 01:38:45,591 INFO L187 NwaCegarLoop]: Found error trace [2023-02-16 01:38:45,591 INFO L195 NwaCegarLoop]: trace histogram [5, 4, 4, 4, 4, 4, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-02-16 01:38:45,611 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Ended with exit code 0 [2023-02-16 01:38:45,805 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-02-16 01:38:45,805 INFO L420 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-02-16 01:38:45,805 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2023-02-16 01:38:45,805 INFO L85 PathProgramCache]: Analyzing trace with hash -1721617041, now seen corresponding path program 1 times [2023-02-16 01:38:45,805 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-02-16 01:38:45,806 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1014278920] [2023-02-16 01:38:45,806 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-16 01:38:45,806 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-02-16 01:38:45,812 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-02-16 01:38:45,812 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [107795808] [2023-02-16 01:38:45,812 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-16 01:38:45,812 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-02-16 01:38:45,813 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-16 01:38:45,813 INFO L229 MonitoredProcess]: Starting monitored process 8 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-02-16 01:38:45,815 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2023-02-16 01:38:45,847 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-02-16 01:38:45,853 INFO L263 TraceCheckSpWp]: Trace formula consists of 155 conjuncts, 9 conjunts are in the unsatisfiable core [2023-02-16 01:38:45,855 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2023-02-16 01:38:45,906 INFO L134 CoverageAnalysis]: Checked inductivity of 58 backedges. 8 proven. 11 refuted. 0 times theorem prover too weak. 39 trivial. 0 not checked. [2023-02-16 01:38:45,906 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2023-02-16 01:38:45,984 INFO L134 CoverageAnalysis]: Checked inductivity of 58 backedges. 8 proven. 11 refuted. 0 times theorem prover too weak. 39 trivial. 0 not checked. [2023-02-16 01:38:45,984 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-02-16 01:38:45,984 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1014278920] [2023-02-16 01:38:45,984 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-02-16 01:38:45,984 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [107795808] [2023-02-16 01:38:45,985 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [107795808] provided 0 perfect and 2 imperfect interpolant sequences [2023-02-16 01:38:45,985 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-02-16 01:38:45,985 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 9 [2023-02-16 01:38:45,985 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [531123994] [2023-02-16 01:38:45,985 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-02-16 01:38:45,985 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2023-02-16 01:38:45,986 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-02-16 01:38:45,986 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2023-02-16 01:38:45,986 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=17, Invalid=55, Unknown=0, NotChecked=0, Total=72 [2023-02-16 01:38:45,986 INFO L87 Difference]: Start difference. First operand 52 states and 62 transitions. Second operand has 9 states, 9 states have (on average 2.6666666666666665) internal successors, (24), 8 states have internal predecessors, (24), 5 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (8), 3 states have call predecessors, (8), 4 states have call successors, (8) [2023-02-16 01:38:46,118 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-02-16 01:38:46,118 INFO L93 Difference]: Finished difference Result 99 states and 137 transitions. [2023-02-16 01:38:46,118 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2023-02-16 01:38:46,118 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 9 states have (on average 2.6666666666666665) internal successors, (24), 8 states have internal predecessors, (24), 5 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (8), 3 states have call predecessors, (8), 4 states have call successors, (8) Word has length 54 [2023-02-16 01:38:46,118 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-02-16 01:38:46,119 INFO L225 Difference]: With dead ends: 99 [2023-02-16 01:38:46,119 INFO L226 Difference]: Without dead ends: 91 [2023-02-16 01:38:46,120 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 111 GetRequests, 94 SyntacticMatches, 5 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 6 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=47, Invalid=135, Unknown=0, NotChecked=0, Total=182 [2023-02-16 01:38:46,120 INFO L413 NwaCegarLoop]: 53 mSDtfsCounter, 36 mSDsluCounter, 127 mSDsCounter, 0 mSdLazyCounter, 127 mSolverCounterSat, 47 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 41 SdHoareTripleChecker+Valid, 180 SdHoareTripleChecker+Invalid, 174 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 47 IncrementalHoareTripleChecker+Valid, 127 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-02-16 01:38:46,120 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [41 Valid, 180 Invalid, 174 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [47 Valid, 127 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-02-16 01:38:46,121 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 91 states. [2023-02-16 01:38:46,134 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 91 to 82. [2023-02-16 01:38:46,134 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 82 states, 45 states have (on average 1.2) internal successors, (54), 46 states have internal predecessors, (54), 30 states have call successors, (30), 6 states have call predecessors, (30), 6 states have return successors, (29), 29 states have call predecessors, (29), 29 states have call successors, (29) [2023-02-16 01:38:46,135 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 82 states to 82 states and 113 transitions. [2023-02-16 01:38:46,135 INFO L78 Accepts]: Start accepts. Automaton has 82 states and 113 transitions. Word has length 54 [2023-02-16 01:38:46,135 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-02-16 01:38:46,136 INFO L495 AbstractCegarLoop]: Abstraction has 82 states and 113 transitions. [2023-02-16 01:38:46,136 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 9 states have (on average 2.6666666666666665) internal successors, (24), 8 states have internal predecessors, (24), 5 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (8), 3 states have call predecessors, (8), 4 states have call successors, (8) [2023-02-16 01:38:46,136 INFO L276 IsEmpty]: Start isEmpty. Operand 82 states and 113 transitions. [2023-02-16 01:38:46,136 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 61 [2023-02-16 01:38:46,136 INFO L187 NwaCegarLoop]: Found error trace [2023-02-16 01:38:46,137 INFO L195 NwaCegarLoop]: trace histogram [6, 5, 5, 4, 4, 4, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-02-16 01:38:46,147 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Forceful destruction successful, exit code 0 [2023-02-16 01:38:46,347 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-02-16 01:38:46,349 INFO L420 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-02-16 01:38:46,349 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2023-02-16 01:38:46,350 INFO L85 PathProgramCache]: Analyzing trace with hash -653850053, now seen corresponding path program 1 times [2023-02-16 01:38:46,350 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-02-16 01:38:46,350 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1014342834] [2023-02-16 01:38:46,350 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-16 01:38:46,350 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-02-16 01:38:46,356 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-02-16 01:38:46,356 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [525285995] [2023-02-16 01:38:46,357 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-16 01:38:46,357 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-02-16 01:38:46,357 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-16 01:38:46,358 INFO L229 MonitoredProcess]: Starting monitored process 9 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-02-16 01:38:46,360 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2023-02-16 01:38:46,397 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-02-16 01:38:46,398 INFO L263 TraceCheckSpWp]: Trace formula consists of 168 conjuncts, 26 conjunts are in the unsatisfiable core [2023-02-16 01:38:46,400 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2023-02-16 01:38:46,474 INFO L134 CoverageAnalysis]: Checked inductivity of 79 backedges. 23 proven. 10 refuted. 0 times theorem prover too weak. 46 trivial. 0 not checked. [2023-02-16 01:38:46,474 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2023-02-16 01:38:46,578 INFO L134 CoverageAnalysis]: Checked inductivity of 79 backedges. 20 proven. 7 refuted. 0 times theorem prover too weak. 52 trivial. 0 not checked. [2023-02-16 01:38:46,578 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-02-16 01:38:46,578 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1014342834] [2023-02-16 01:38:46,578 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-02-16 01:38:46,578 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [525285995] [2023-02-16 01:38:46,578 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [525285995] provided 0 perfect and 2 imperfect interpolant sequences [2023-02-16 01:38:46,579 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-02-16 01:38:46,579 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 7] total 13 [2023-02-16 01:38:46,579 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1890876390] [2023-02-16 01:38:46,579 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-02-16 01:38:46,580 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 13 states [2023-02-16 01:38:46,580 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-02-16 01:38:46,580 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2023-02-16 01:38:46,580 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=31, Invalid=125, Unknown=0, NotChecked=0, Total=156 [2023-02-16 01:38:46,581 INFO L87 Difference]: Start difference. First operand 82 states and 113 transitions. Second operand has 13 states, 13 states have (on average 2.769230769230769) internal successors, (36), 12 states have internal predecessors, (36), 6 states have call successors, (18), 3 states have call predecessors, (18), 2 states have return successors, (16), 6 states have call predecessors, (16), 6 states have call successors, (16) [2023-02-16 01:38:46,817 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-02-16 01:38:46,817 INFO L93 Difference]: Finished difference Result 125 states and 178 transitions. [2023-02-16 01:38:46,818 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2023-02-16 01:38:46,818 INFO L78 Accepts]: Start accepts. Automaton has has 13 states, 13 states have (on average 2.769230769230769) internal successors, (36), 12 states have internal predecessors, (36), 6 states have call successors, (18), 3 states have call predecessors, (18), 2 states have return successors, (16), 6 states have call predecessors, (16), 6 states have call successors, (16) Word has length 60 [2023-02-16 01:38:46,818 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-02-16 01:38:46,820 INFO L225 Difference]: With dead ends: 125 [2023-02-16 01:38:46,820 INFO L226 Difference]: Without dead ends: 121 [2023-02-16 01:38:46,820 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 126 GetRequests, 109 SyntacticMatches, 1 SemanticMatches, 16 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 37 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=63, Invalid=243, Unknown=0, NotChecked=0, Total=306 [2023-02-16 01:38:46,821 INFO L413 NwaCegarLoop]: 37 mSDtfsCounter, 32 mSDsluCounter, 113 mSDsCounter, 0 mSdLazyCounter, 273 mSolverCounterSat, 42 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 38 SdHoareTripleChecker+Valid, 150 SdHoareTripleChecker+Invalid, 315 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 42 IncrementalHoareTripleChecker+Valid, 273 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-02-16 01:38:46,821 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [38 Valid, 150 Invalid, 315 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [42 Valid, 273 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-02-16 01:38:46,822 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 121 states. [2023-02-16 01:38:46,837 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 121 to 89. [2023-02-16 01:38:46,838 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 89 states, 49 states have (on average 1.183673469387755) internal successors, (58), 51 states have internal predecessors, (58), 32 states have call successors, (32), 7 states have call predecessors, (32), 7 states have return successors, (31), 30 states have call predecessors, (31), 31 states have call successors, (31) [2023-02-16 01:38:46,838 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 89 states to 89 states and 121 transitions. [2023-02-16 01:38:46,839 INFO L78 Accepts]: Start accepts. Automaton has 89 states and 121 transitions. Word has length 60 [2023-02-16 01:38:46,839 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-02-16 01:38:46,839 INFO L495 AbstractCegarLoop]: Abstraction has 89 states and 121 transitions. [2023-02-16 01:38:46,839 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 13 states, 13 states have (on average 2.769230769230769) internal successors, (36), 12 states have internal predecessors, (36), 6 states have call successors, (18), 3 states have call predecessors, (18), 2 states have return successors, (16), 6 states have call predecessors, (16), 6 states have call successors, (16) [2023-02-16 01:38:46,839 INFO L276 IsEmpty]: Start isEmpty. Operand 89 states and 121 transitions. [2023-02-16 01:38:46,840 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 66 [2023-02-16 01:38:46,840 INFO L187 NwaCegarLoop]: Found error trace [2023-02-16 01:38:46,840 INFO L195 NwaCegarLoop]: trace histogram [7, 6, 6, 4, 4, 4, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-02-16 01:38:46,848 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Forceful destruction successful, exit code 0 [2023-02-16 01:38:47,045 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 9 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable7 [2023-02-16 01:38:47,045 INFO L420 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-02-16 01:38:47,045 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2023-02-16 01:38:47,045 INFO L85 PathProgramCache]: Analyzing trace with hash 1044201731, now seen corresponding path program 2 times [2023-02-16 01:38:47,046 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-02-16 01:38:47,046 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [561553666] [2023-02-16 01:38:47,046 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-16 01:38:47,046 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-02-16 01:38:47,052 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-02-16 01:38:47,052 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1158395403] [2023-02-16 01:38:47,052 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2023-02-16 01:38:47,052 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-02-16 01:38:47,052 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-16 01:38:47,053 INFO L229 MonitoredProcess]: Starting monitored process 10 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-02-16 01:38:47,055 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Waiting until timeout for monitored process [2023-02-16 01:38:47,095 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2023-02-16 01:38:47,095 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-02-16 01:38:47,096 INFO L263 TraceCheckSpWp]: Trace formula consists of 177 conjuncts, 41 conjunts are in the unsatisfiable core [2023-02-16 01:38:47,098 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2023-02-16 01:38:47,352 INFO L134 CoverageAnalysis]: Checked inductivity of 102 backedges. 26 proven. 16 refuted. 0 times theorem prover too weak. 60 trivial. 0 not checked. [2023-02-16 01:38:47,353 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2023-02-16 01:38:47,683 INFO L134 CoverageAnalysis]: Checked inductivity of 102 backedges. 12 proven. 6 refuted. 0 times theorem prover too weak. 84 trivial. 0 not checked. [2023-02-16 01:38:47,683 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-02-16 01:38:47,683 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [561553666] [2023-02-16 01:38:47,683 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-02-16 01:38:47,684 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1158395403] [2023-02-16 01:38:47,684 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1158395403] provided 0 perfect and 2 imperfect interpolant sequences [2023-02-16 01:38:47,684 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-02-16 01:38:47,684 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 8] total 18 [2023-02-16 01:38:47,684 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1902240222] [2023-02-16 01:38:47,684 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-02-16 01:38:47,685 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 18 states [2023-02-16 01:38:47,685 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-02-16 01:38:47,685 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 18 interpolants. [2023-02-16 01:38:47,685 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=48, Invalid=258, Unknown=0, NotChecked=0, Total=306 [2023-02-16 01:38:47,686 INFO L87 Difference]: Start difference. First operand 89 states and 121 transitions. Second operand has 18 states, 18 states have (on average 2.0555555555555554) internal successors, (37), 16 states have internal predecessors, (37), 8 states have call successors, (21), 3 states have call predecessors, (21), 3 states have return successors, (20), 8 states have call predecessors, (20), 8 states have call successors, (20) [2023-02-16 01:38:50,465 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-02-16 01:38:50,465 INFO L93 Difference]: Finished difference Result 131 states and 176 transitions. [2023-02-16 01:38:50,465 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 20 states. [2023-02-16 01:38:50,465 INFO L78 Accepts]: Start accepts. Automaton has has 18 states, 18 states have (on average 2.0555555555555554) internal successors, (37), 16 states have internal predecessors, (37), 8 states have call successors, (21), 3 states have call predecessors, (21), 3 states have return successors, (20), 8 states have call predecessors, (20), 8 states have call successors, (20) Word has length 65 [2023-02-16 01:38:50,466 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-02-16 01:38:50,466 INFO L225 Difference]: With dead ends: 131 [2023-02-16 01:38:50,467 INFO L226 Difference]: Without dead ends: 129 [2023-02-16 01:38:50,467 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 141 GetRequests, 112 SyntacticMatches, 0 SemanticMatches, 29 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 161 ImplicationChecksByTransitivity, 1.1s TimeCoverageRelationStatistics Valid=168, Invalid=762, Unknown=0, NotChecked=0, Total=930 [2023-02-16 01:38:50,467 INFO L413 NwaCegarLoop]: 24 mSDtfsCounter, 86 mSDsluCounter, 129 mSDsCounter, 0 mSdLazyCounter, 645 mSolverCounterSat, 106 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.8s Time, 0 mProtectedPredicate, 0 mProtectedAction, 86 SdHoareTripleChecker+Valid, 153 SdHoareTripleChecker+Invalid, 751 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 106 IncrementalHoareTripleChecker+Valid, 645 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.9s IncrementalHoareTripleChecker+Time [2023-02-16 01:38:50,468 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [86 Valid, 153 Invalid, 751 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [106 Valid, 645 Invalid, 0 Unknown, 0 Unchecked, 1.9s Time] [2023-02-16 01:38:50,468 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 129 states. [2023-02-16 01:38:50,497 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 129 to 110. [2023-02-16 01:38:50,497 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 110 states, 63 states have (on average 1.1746031746031746) internal successors, (74), 65 states have internal predecessors, (74), 36 states have call successors, (36), 10 states have call predecessors, (36), 10 states have return successors, (35), 34 states have call predecessors, (35), 35 states have call successors, (35) [2023-02-16 01:38:50,498 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 110 states to 110 states and 145 transitions. [2023-02-16 01:38:50,498 INFO L78 Accepts]: Start accepts. Automaton has 110 states and 145 transitions. Word has length 65 [2023-02-16 01:38:50,498 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-02-16 01:38:50,498 INFO L495 AbstractCegarLoop]: Abstraction has 110 states and 145 transitions. [2023-02-16 01:38:50,498 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 18 states, 18 states have (on average 2.0555555555555554) internal successors, (37), 16 states have internal predecessors, (37), 8 states have call successors, (21), 3 states have call predecessors, (21), 3 states have return successors, (20), 8 states have call predecessors, (20), 8 states have call successors, (20) [2023-02-16 01:38:50,499 INFO L276 IsEmpty]: Start isEmpty. Operand 110 states and 145 transitions. [2023-02-16 01:38:50,499 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 71 [2023-02-16 01:38:50,499 INFO L187 NwaCegarLoop]: Found error trace [2023-02-16 01:38:50,499 INFO L195 NwaCegarLoop]: trace histogram [8, 7, 7, 4, 4, 4, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-02-16 01:38:50,506 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Ended with exit code 0 [2023-02-16 01:38:50,704 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,10 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-02-16 01:38:50,704 INFO L420 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-02-16 01:38:50,704 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2023-02-16 01:38:50,705 INFO L85 PathProgramCache]: Analyzing trace with hash 635379451, now seen corresponding path program 3 times [2023-02-16 01:38:50,705 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-02-16 01:38:50,705 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1394443387] [2023-02-16 01:38:50,705 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-16 01:38:50,705 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-02-16 01:38:50,711 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-02-16 01:38:50,711 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1065033850] [2023-02-16 01:38:50,711 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2023-02-16 01:38:50,711 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-02-16 01:38:50,711 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-16 01:38:50,714 INFO L229 MonitoredProcess]: Starting monitored process 11 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-02-16 01:38:50,717 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Waiting until timeout for monitored process [2023-02-16 01:38:50,754 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2023-02-16 01:38:50,755 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-02-16 01:38:50,756 INFO L263 TraceCheckSpWp]: Trace formula consists of 150 conjuncts, 42 conjunts are in the unsatisfiable core [2023-02-16 01:38:50,757 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2023-02-16 01:38:51,031 INFO L134 CoverageAnalysis]: Checked inductivity of 129 backedges. 40 proven. 8 refuted. 0 times theorem prover too weak. 81 trivial. 0 not checked. [2023-02-16 01:38:51,032 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2023-02-16 01:38:51,348 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-02-16 01:38:51,348 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1394443387] [2023-02-16 01:38:51,348 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-02-16 01:38:51,348 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1065033850] [2023-02-16 01:38:51,348 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1065033850] provided 0 perfect and 1 imperfect interpolant sequences [2023-02-16 01:38:51,348 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2023-02-16 01:38:51,348 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13] total 13 [2023-02-16 01:38:51,348 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [367198945] [2023-02-16 01:38:51,348 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2023-02-16 01:38:51,349 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 13 states [2023-02-16 01:38:51,349 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-02-16 01:38:51,349 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2023-02-16 01:38:51,350 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=46, Invalid=260, Unknown=0, NotChecked=0, Total=306 [2023-02-16 01:38:51,350 INFO L87 Difference]: Start difference. First operand 110 states and 145 transitions. Second operand has 13 states, 12 states have (on average 2.1666666666666665) internal successors, (26), 12 states have internal predecessors, (26), 4 states have call successors, (12), 2 states have call predecessors, (12), 3 states have return successors, (11), 5 states have call predecessors, (11), 4 states have call successors, (11) [2023-02-16 01:38:51,936 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-02-16 01:38:51,937 INFO L93 Difference]: Finished difference Result 146 states and 187 transitions. [2023-02-16 01:38:51,937 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2023-02-16 01:38:51,937 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), 4 states have call successors, (12), 2 states have call predecessors, (12), 3 states have return successors, (11), 5 states have call predecessors, (11), 4 states have call successors, (11) Word has length 70 [2023-02-16 01:38:51,938 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-02-16 01:38:51,939 INFO L225 Difference]: With dead ends: 146 [2023-02-16 01:38:51,939 INFO L226 Difference]: Without dead ends: 144 [2023-02-16 01:38:51,939 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 98 GetRequests, 77 SyntacticMatches, 1 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 51 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=71, Invalid=391, Unknown=0, NotChecked=0, Total=462 [2023-02-16 01:38:51,940 INFO L413 NwaCegarLoop]: 25 mSDtfsCounter, 31 mSDsluCounter, 111 mSDsCounter, 0 mSdLazyCounter, 436 mSolverCounterSat, 16 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 39 SdHoareTripleChecker+Valid, 136 SdHoareTripleChecker+Invalid, 452 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 16 IncrementalHoareTripleChecker+Valid, 436 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.5s IncrementalHoareTripleChecker+Time [2023-02-16 01:38:51,941 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [39 Valid, 136 Invalid, 452 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [16 Valid, 436 Invalid, 0 Unknown, 0 Unchecked, 0.5s Time] [2023-02-16 01:38:51,941 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 144 states. [2023-02-16 01:38:51,968 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 144 to 141. [2023-02-16 01:38:51,969 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 141 states, 82 states have (on average 1.1585365853658536) internal successors, (95), 84 states have internal predecessors, (95), 44 states have call successors, (44), 14 states have call predecessors, (44), 14 states have return successors, (43), 42 states have call predecessors, (43), 43 states have call successors, (43) [2023-02-16 01:38:51,970 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 141 states to 141 states and 182 transitions. [2023-02-16 01:38:51,970 INFO L78 Accepts]: Start accepts. Automaton has 141 states and 182 transitions. Word has length 70 [2023-02-16 01:38:51,971 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-02-16 01:38:51,971 INFO L495 AbstractCegarLoop]: Abstraction has 141 states and 182 transitions. [2023-02-16 01:38:51,971 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 13 states, 12 states have (on average 2.1666666666666665) internal successors, (26), 12 states have internal predecessors, (26), 4 states have call successors, (12), 2 states have call predecessors, (12), 3 states have return successors, (11), 5 states have call predecessors, (11), 4 states have call successors, (11) [2023-02-16 01:38:51,971 INFO L276 IsEmpty]: Start isEmpty. Operand 141 states and 182 transitions. [2023-02-16 01:38:51,973 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 77 [2023-02-16 01:38:51,973 INFO L187 NwaCegarLoop]: Found error trace [2023-02-16 01:38:51,973 INFO L195 NwaCegarLoop]: trace histogram [9, 8, 8, 4, 4, 4, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-02-16 01:38:51,980 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Forceful destruction successful, exit code 0 [2023-02-16 01:38:52,177 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 11 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable9 [2023-02-16 01:38:52,177 INFO L420 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-02-16 01:38:52,177 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2023-02-16 01:38:52,177 INFO L85 PathProgramCache]: Analyzing trace with hash -375209714, now seen corresponding path program 1 times [2023-02-16 01:38:52,177 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-02-16 01:38:52,177 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1765476009] [2023-02-16 01:38:52,177 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-16 01:38:52,178 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-02-16 01:38:52,183 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-02-16 01:38:52,184 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [461968818] [2023-02-16 01:38:52,184 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-16 01:38:52,184 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-02-16 01:38:52,184 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-16 01:38:52,189 INFO L229 MonitoredProcess]: Starting monitored process 12 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-02-16 01:38:52,191 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Waiting until timeout for monitored process [2023-02-16 01:38:52,234 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-02-16 01:38:52,236 INFO L263 TraceCheckSpWp]: Trace formula consists of 197 conjuncts, 43 conjunts are in the unsatisfiable core [2023-02-16 01:38:52,238 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2023-02-16 01:38:52,571 INFO L134 CoverageAnalysis]: Checked inductivity of 160 backedges. 16 proven. 17 refuted. 0 times theorem prover too weak. 127 trivial. 0 not checked. [2023-02-16 01:38:52,571 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2023-02-16 01:38:53,315 INFO L134 CoverageAnalysis]: Checked inductivity of 160 backedges. 16 proven. 8 refuted. 0 times theorem prover too weak. 136 trivial. 0 not checked. [2023-02-16 01:38:53,316 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-02-16 01:38:53,316 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1765476009] [2023-02-16 01:38:53,316 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-02-16 01:38:53,316 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [461968818] [2023-02-16 01:38:53,316 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [461968818] provided 0 perfect and 2 imperfect interpolant sequences [2023-02-16 01:38:53,316 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-02-16 01:38:53,316 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 10] total 21 [2023-02-16 01:38:53,316 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1057291424] [2023-02-16 01:38:53,317 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-02-16 01:38:53,317 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 21 states [2023-02-16 01:38:53,317 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-02-16 01:38:53,318 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2023-02-16 01:38:53,318 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=64, Invalid=356, Unknown=0, NotChecked=0, Total=420 [2023-02-16 01:38:53,318 INFO L87 Difference]: Start difference. First operand 141 states and 182 transitions. Second operand has 21 states, 19 states have (on average 1.894736842105263) internal successors, (36), 18 states have internal predecessors, (36), 10 states have call successors, (25), 3 states have call predecessors, (25), 2 states have return successors, (24), 8 states have call predecessors, (24), 8 states have call successors, (24) [2023-02-16 01:39:00,793 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-02-16 01:39:00,793 INFO L93 Difference]: Finished difference Result 231 states and 317 transitions. [2023-02-16 01:39:00,793 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 28 states. [2023-02-16 01:39:00,793 INFO L78 Accepts]: Start accepts. Automaton has has 21 states, 19 states have (on average 1.894736842105263) internal successors, (36), 18 states have internal predecessors, (36), 10 states have call successors, (25), 3 states have call predecessors, (25), 2 states have return successors, (24), 8 states have call predecessors, (24), 8 states have call successors, (24) Word has length 76 [2023-02-16 01:39:00,794 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-02-16 01:39:00,794 INFO L225 Difference]: With dead ends: 231 [2023-02-16 01:39:00,795 INFO L226 Difference]: Without dead ends: 223 [2023-02-16 01:39:00,795 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 171 GetRequests, 131 SyntacticMatches, 0 SemanticMatches, 40 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 301 ImplicationChecksByTransitivity, 3.9s TimeCoverageRelationStatistics Valid=309, Invalid=1413, Unknown=0, NotChecked=0, Total=1722 [2023-02-16 01:39:00,796 INFO L413 NwaCegarLoop]: 64 mSDtfsCounter, 92 mSDsluCounter, 295 mSDsCounter, 0 mSdLazyCounter, 884 mSolverCounterSat, 164 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 4.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 96 SdHoareTripleChecker+Valid, 359 SdHoareTripleChecker+Invalid, 1048 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 164 IncrementalHoareTripleChecker+Valid, 884 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 4.1s IncrementalHoareTripleChecker+Time [2023-02-16 01:39:00,796 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [96 Valid, 359 Invalid, 1048 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [164 Valid, 884 Invalid, 0 Unknown, 0 Unchecked, 4.1s Time] [2023-02-16 01:39:00,797 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 223 states. [2023-02-16 01:39:00,853 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 223 to 219. [2023-02-16 01:39:00,853 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 219 states, 121 states have (on average 1.1818181818181819) internal successors, (143), 123 states have internal predecessors, (143), 80 states have call successors, (80), 17 states have call predecessors, (80), 17 states have return successors, (79), 78 states have call predecessors, (79), 79 states have call successors, (79) [2023-02-16 01:39:00,855 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 219 states to 219 states and 302 transitions. [2023-02-16 01:39:00,855 INFO L78 Accepts]: Start accepts. Automaton has 219 states and 302 transitions. Word has length 76 [2023-02-16 01:39:00,855 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-02-16 01:39:00,855 INFO L495 AbstractCegarLoop]: Abstraction has 219 states and 302 transitions. [2023-02-16 01:39:00,855 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 21 states, 19 states have (on average 1.894736842105263) internal successors, (36), 18 states have internal predecessors, (36), 10 states have call successors, (25), 3 states have call predecessors, (25), 2 states have return successors, (24), 8 states have call predecessors, (24), 8 states have call successors, (24) [2023-02-16 01:39:00,856 INFO L276 IsEmpty]: Start isEmpty. Operand 219 states and 302 transitions. [2023-02-16 01:39:00,859 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 93 [2023-02-16 01:39:00,859 INFO L187 NwaCegarLoop]: Found error trace [2023-02-16 01:39:00,859 INFO L195 NwaCegarLoop]: trace histogram [12, 11, 11, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-02-16 01:39:00,864 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Forceful destruction successful, exit code 0 [2023-02-16 01:39:01,063 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 12 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable10 [2023-02-16 01:39:01,064 INFO L420 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-02-16 01:39:01,064 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2023-02-16 01:39:01,064 INFO L85 PathProgramCache]: Analyzing trace with hash 1261079706, now seen corresponding path program 1 times [2023-02-16 01:39:01,064 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-02-16 01:39:01,064 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [175783089] [2023-02-16 01:39:01,064 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-16 01:39:01,064 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-02-16 01:39:01,070 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-02-16 01:39:01,070 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1020356604] [2023-02-16 01:39:01,071 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-16 01:39:01,071 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-02-16 01:39:01,071 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-16 01:39:01,072 INFO L229 MonitoredProcess]: Starting monitored process 13 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-02-16 01:39:01,074 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Waiting until timeout for monitored process [2023-02-16 01:39:01,122 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-02-16 01:39:01,124 INFO L263 TraceCheckSpWp]: Trace formula consists of 228 conjuncts, 50 conjunts are in the unsatisfiable core [2023-02-16 01:39:01,126 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2023-02-16 01:39:01,679 INFO L134 CoverageAnalysis]: Checked inductivity of 284 backedges. 51 proven. 28 refuted. 0 times theorem prover too weak. 205 trivial. 0 not checked. [2023-02-16 01:39:01,679 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2023-02-16 01:39:03,246 INFO L134 CoverageAnalysis]: Checked inductivity of 284 backedges. 51 proven. 19 refuted. 0 times theorem prover too weak. 214 trivial. 0 not checked. [2023-02-16 01:39:03,247 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-02-16 01:39:03,247 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [175783089] [2023-02-16 01:39:03,247 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-02-16 01:39:03,247 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1020356604] [2023-02-16 01:39:03,247 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1020356604] provided 0 perfect and 2 imperfect interpolant sequences [2023-02-16 01:39:03,247 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-02-16 01:39:03,248 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 11] total 22 [2023-02-16 01:39:03,248 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [544279245] [2023-02-16 01:39:03,248 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-02-16 01:39:03,248 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 22 states [2023-02-16 01:39:03,248 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-02-16 01:39:03,249 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 22 interpolants. [2023-02-16 01:39:03,249 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=82, Invalid=380, Unknown=0, NotChecked=0, Total=462 [2023-02-16 01:39:03,249 INFO L87 Difference]: Start difference. First operand 219 states and 302 transitions. Second operand has 22 states, 21 states have (on average 2.0476190476190474) internal successors, (43), 19 states have internal predecessors, (43), 11 states have call successors, (31), 3 states have call predecessors, (31), 3 states have return successors, (30), 11 states have call predecessors, (30), 10 states have call successors, (30) [2023-02-16 01:39:05,395 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-02-16 01:39:18,121 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.01s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-02-16 01:39:20,715 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-02-16 01:39:24,410 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-02-16 01:39:32,205 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.70s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-02-16 01:39:32,252 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-02-16 01:39:32,252 INFO L93 Difference]: Finished difference Result 319 states and 456 transitions. [2023-02-16 01:39:32,252 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 31 states. [2023-02-16 01:39:32,253 INFO L78 Accepts]: Start accepts. Automaton has has 22 states, 21 states have (on average 2.0476190476190474) internal successors, (43), 19 states have internal predecessors, (43), 11 states have call successors, (31), 3 states have call predecessors, (31), 3 states have return successors, (30), 11 states have call predecessors, (30), 10 states have call successors, (30) Word has length 92 [2023-02-16 01:39:32,253 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-02-16 01:39:32,254 INFO L225 Difference]: With dead ends: 319 [2023-02-16 01:39:32,254 INFO L226 Difference]: Without dead ends: 317 [2023-02-16 01:39:32,255 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 202 GetRequests, 161 SyntacticMatches, 1 SemanticMatches, 40 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 354 ImplicationChecksByTransitivity, 9.3s TimeCoverageRelationStatistics Valid=365, Invalid=1357, Unknown=0, NotChecked=0, Total=1722 [2023-02-16 01:39:32,256 INFO L413 NwaCegarLoop]: 28 mSDtfsCounter, 92 mSDsluCounter, 150 mSDsCounter, 0 mSdLazyCounter, 1119 mSolverCounterSat, 115 mSolverCounterUnsat, 4 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 20.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 104 SdHoareTripleChecker+Valid, 178 SdHoareTripleChecker+Invalid, 1238 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 115 IncrementalHoareTripleChecker+Valid, 1119 IncrementalHoareTripleChecker+Invalid, 4 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 20.4s IncrementalHoareTripleChecker+Time [2023-02-16 01:39:32,256 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [104 Valid, 178 Invalid, 1238 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [115 Valid, 1119 Invalid, 4 Unknown, 0 Unchecked, 20.4s Time] [2023-02-16 01:39:32,256 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 317 states. [2023-02-16 01:39:32,347 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 317 to 264. [2023-02-16 01:39:32,347 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 264 states, 146 states have (on average 1.178082191780822) internal successors, (172), 151 states have internal predecessors, (172), 99 states have call successors, (99), 18 states have call predecessors, (99), 18 states have return successors, (98), 94 states have call predecessors, (98), 98 states have call successors, (98) [2023-02-16 01:39:32,349 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 264 states to 264 states and 369 transitions. [2023-02-16 01:39:32,349 INFO L78 Accepts]: Start accepts. Automaton has 264 states and 369 transitions. Word has length 92 [2023-02-16 01:39:32,349 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-02-16 01:39:32,349 INFO L495 AbstractCegarLoop]: Abstraction has 264 states and 369 transitions. [2023-02-16 01:39:32,349 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 22 states, 21 states have (on average 2.0476190476190474) internal successors, (43), 19 states have internal predecessors, (43), 11 states have call successors, (31), 3 states have call predecessors, (31), 3 states have return successors, (30), 11 states have call predecessors, (30), 10 states have call successors, (30) [2023-02-16 01:39:32,350 INFO L276 IsEmpty]: Start isEmpty. Operand 264 states and 369 transitions. [2023-02-16 01:39:32,350 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 96 [2023-02-16 01:39:32,350 INFO L187 NwaCegarLoop]: Found error trace [2023-02-16 01:39:32,350 INFO L195 NwaCegarLoop]: trace histogram [12, 11, 11, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-02-16 01:39:32,360 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Forceful destruction successful, exit code 0 [2023-02-16 01:39:32,555 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 13 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable11 [2023-02-16 01:39:32,555 INFO L420 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-02-16 01:39:32,556 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2023-02-16 01:39:32,556 INFO L85 PathProgramCache]: Analyzing trace with hash 1991503352, now seen corresponding path program 4 times [2023-02-16 01:39:32,556 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-02-16 01:39:32,556 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1097816977] [2023-02-16 01:39:32,556 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-16 01:39:32,556 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-02-16 01:39:32,562 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-02-16 01:39:32,562 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1591938639] [2023-02-16 01:39:32,562 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2023-02-16 01:39:32,562 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-02-16 01:39:32,562 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-16 01:39:32,564 INFO L229 MonitoredProcess]: Starting monitored process 14 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-02-16 01:39:32,566 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Waiting until timeout for monitored process [2023-02-16 01:39:32,625 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2023-02-16 01:39:32,625 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-02-16 01:39:32,626 INFO L263 TraceCheckSpWp]: Trace formula consists of 209 conjuncts, 5 conjunts are in the unsatisfiable core [2023-02-16 01:39:32,627 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2023-02-16 01:39:32,647 INFO L134 CoverageAnalysis]: Checked inductivity of 289 backedges. 135 proven. 0 refuted. 0 times theorem prover too weak. 154 trivial. 0 not checked. [2023-02-16 01:39:32,647 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2023-02-16 01:39:32,648 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-02-16 01:39:32,648 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1097816977] [2023-02-16 01:39:32,648 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-02-16 01:39:32,648 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1591938639] [2023-02-16 01:39:32,648 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1591938639] provided 1 perfect and 0 imperfect interpolant sequences [2023-02-16 01:39:32,648 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-02-16 01:39:32,648 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2023-02-16 01:39:32,648 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2073430830] [2023-02-16 01:39:32,649 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-02-16 01:39:32,649 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2023-02-16 01:39:32,649 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-02-16 01:39:32,650 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2023-02-16 01:39:32,650 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2023-02-16 01:39:32,650 INFO L87 Difference]: Start difference. First operand 264 states and 369 transitions. Second operand has 5 states, 5 states have (on average 5.4) internal successors, (27), 5 states have internal predecessors, (27), 3 states have call successors, (16), 2 states have call predecessors, (16), 2 states have return successors, (15), 3 states have call predecessors, (15), 3 states have call successors, (15) [2023-02-16 01:39:32,803 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-02-16 01:39:32,803 INFO L93 Difference]: Finished difference Result 347 states and 483 transitions. [2023-02-16 01:39:32,803 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2023-02-16 01:39:32,803 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 5.4) internal successors, (27), 5 states have internal predecessors, (27), 3 states have call successors, (16), 2 states have call predecessors, (16), 2 states have return successors, (15), 3 states have call predecessors, (15), 3 states have call successors, (15) Word has length 95 [2023-02-16 01:39:32,804 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-02-16 01:39:32,805 INFO L225 Difference]: With dead ends: 347 [2023-02-16 01:39:32,805 INFO L226 Difference]: Without dead ends: 233 [2023-02-16 01:39:32,806 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 96 GetRequests, 91 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=15, Invalid=27, Unknown=0, NotChecked=0, Total=42 [2023-02-16 01:39:32,806 INFO L413 NwaCegarLoop]: 47 mSDtfsCounter, 7 mSDsluCounter, 78 mSDsCounter, 0 mSdLazyCounter, 64 mSolverCounterSat, 4 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 11 SdHoareTripleChecker+Valid, 125 SdHoareTripleChecker+Invalid, 68 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 4 IncrementalHoareTripleChecker+Valid, 64 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-02-16 01:39:32,807 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [11 Valid, 125 Invalid, 68 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [4 Valid, 64 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-02-16 01:39:32,807 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 233 states. [2023-02-16 01:39:32,880 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 233 to 216. [2023-02-16 01:39:32,880 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 216 states, 121 states have (on average 1.1322314049586777) internal successors, (137), 124 states have internal predecessors, (137), 76 states have call successors, (76), 18 states have call predecessors, (76), 18 states have return successors, (75), 73 states have call predecessors, (75), 75 states have call successors, (75) [2023-02-16 01:39:32,881 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 216 states to 216 states and 288 transitions. [2023-02-16 01:39:32,881 INFO L78 Accepts]: Start accepts. Automaton has 216 states and 288 transitions. Word has length 95 [2023-02-16 01:39:32,882 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-02-16 01:39:32,882 INFO L495 AbstractCegarLoop]: Abstraction has 216 states and 288 transitions. [2023-02-16 01:39:32,882 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 5.4) internal successors, (27), 5 states have internal predecessors, (27), 3 states have call successors, (16), 2 states have call predecessors, (16), 2 states have return successors, (15), 3 states have call predecessors, (15), 3 states have call successors, (15) [2023-02-16 01:39:32,882 INFO L276 IsEmpty]: Start isEmpty. Operand 216 states and 288 transitions. [2023-02-16 01:39:32,883 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 113 [2023-02-16 01:39:32,883 INFO L187 NwaCegarLoop]: Found error trace [2023-02-16 01:39:32,883 INFO L195 NwaCegarLoop]: trace histogram [15, 14, 14, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-02-16 01:39:32,889 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Forceful destruction successful, exit code 0 [2023-02-16 01:39:33,087 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 14 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable12 [2023-02-16 01:39:33,087 INFO L420 AbstractCegarLoop]: === Iteration 14 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-02-16 01:39:33,088 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2023-02-16 01:39:33,088 INFO L85 PathProgramCache]: Analyzing trace with hash 468383399, now seen corresponding path program 2 times [2023-02-16 01:39:33,088 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-02-16 01:39:33,088 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1759553111] [2023-02-16 01:39:33,088 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-16 01:39:33,088 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-02-16 01:39:33,094 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-02-16 01:39:33,095 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1452556356] [2023-02-16 01:39:33,095 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2023-02-16 01:39:33,095 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-02-16 01:39:33,095 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-16 01:39:33,097 INFO L229 MonitoredProcess]: Starting monitored process 15 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-02-16 01:39:33,099 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Waiting until timeout for monitored process [2023-02-16 01:39:33,150 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2023-02-16 01:39:33,150 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-02-16 01:39:33,152 INFO L263 TraceCheckSpWp]: Trace formula consists of 277 conjuncts, 70 conjunts are in the unsatisfiable core [2023-02-16 01:39:33,153 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2023-02-16 01:39:33,713 INFO L134 CoverageAnalysis]: Checked inductivity of 453 backedges. 69 proven. 44 refuted. 0 times theorem prover too weak. 340 trivial. 0 not checked. [2023-02-16 01:39:33,713 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2023-02-16 01:39:34,897 INFO L134 CoverageAnalysis]: Checked inductivity of 453 backedges. 69 proven. 35 refuted. 0 times theorem prover too weak. 349 trivial. 0 not checked. [2023-02-16 01:39:34,898 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-02-16 01:39:34,898 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1759553111] [2023-02-16 01:39:34,898 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-02-16 01:39:34,898 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1452556356] [2023-02-16 01:39:34,898 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1452556356] provided 0 perfect and 2 imperfect interpolant sequences [2023-02-16 01:39:34,898 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-02-16 01:39:34,898 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [18, 14] total 29 [2023-02-16 01:39:34,898 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2046781485] [2023-02-16 01:39:34,898 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-02-16 01:39:34,899 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 29 states [2023-02-16 01:39:34,899 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-02-16 01:39:34,899 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 29 interpolants. [2023-02-16 01:39:34,899 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=143, Invalid=669, Unknown=0, NotChecked=0, Total=812 [2023-02-16 01:39:34,900 INFO L87 Difference]: Start difference. First operand 216 states and 288 transitions. Second operand has 29 states, 27 states have (on average 1.962962962962963) internal successors, (53), 25 states have internal predecessors, (53), 13 states have call successors, (36), 3 states have call predecessors, (36), 3 states have return successors, (35), 14 states have call predecessors, (35), 11 states have call successors, (35) [2023-02-16 01:39:40,281 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.06s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-02-16 01:39:43,065 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-02-16 01:39:43,066 INFO L93 Difference]: Finished difference Result 265 states and 355 transitions. [2023-02-16 01:39:43,066 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 28 states. [2023-02-16 01:39:43,066 INFO L78 Accepts]: Start accepts. Automaton has has 29 states, 27 states have (on average 1.962962962962963) internal successors, (53), 25 states have internal predecessors, (53), 13 states have call successors, (36), 3 states have call predecessors, (36), 3 states have return successors, (35), 14 states have call predecessors, (35), 11 states have call successors, (35) Word has length 112 [2023-02-16 01:39:43,067 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-02-16 01:39:43,068 INFO L225 Difference]: With dead ends: 265 [2023-02-16 01:39:43,069 INFO L226 Difference]: Without dead ends: 263 [2023-02-16 01:39:43,069 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 243 GetRequests, 194 SyntacticMatches, 1 SemanticMatches, 48 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 537 ImplicationChecksByTransitivity, 3.4s TimeCoverageRelationStatistics Valid=472, Invalid=1978, Unknown=0, NotChecked=0, Total=2450 [2023-02-16 01:39:43,070 INFO L413 NwaCegarLoop]: 34 mSDtfsCounter, 94 mSDsluCounter, 211 mSDsCounter, 0 mSdLazyCounter, 1153 mSolverCounterSat, 162 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 5.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 94 SdHoareTripleChecker+Valid, 245 SdHoareTripleChecker+Invalid, 1315 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 162 IncrementalHoareTripleChecker+Valid, 1153 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 5.4s IncrementalHoareTripleChecker+Time [2023-02-16 01:39:43,070 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [94 Valid, 245 Invalid, 1315 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [162 Valid, 1153 Invalid, 0 Unknown, 0 Unchecked, 5.4s Time] [2023-02-16 01:39:43,071 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 263 states. [2023-02-16 01:39:43,175 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 263 to 260. [2023-02-16 01:39:43,176 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 260 states, 144 states have (on average 1.1319444444444444) internal successors, (163), 149 states have internal predecessors, (163), 94 states have call successors, (94), 21 states have call predecessors, (94), 21 states have return successors, (93), 89 states have call predecessors, (93), 93 states have call successors, (93) [2023-02-16 01:39:43,177 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 260 states to 260 states and 350 transitions. [2023-02-16 01:39:43,177 INFO L78 Accepts]: Start accepts. Automaton has 260 states and 350 transitions. Word has length 112 [2023-02-16 01:39:43,177 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-02-16 01:39:43,177 INFO L495 AbstractCegarLoop]: Abstraction has 260 states and 350 transitions. [2023-02-16 01:39:43,178 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 29 states, 27 states have (on average 1.962962962962963) internal successors, (53), 25 states have internal predecessors, (53), 13 states have call successors, (36), 3 states have call predecessors, (36), 3 states have return successors, (35), 14 states have call predecessors, (35), 11 states have call successors, (35) [2023-02-16 01:39:43,178 INFO L276 IsEmpty]: Start isEmpty. Operand 260 states and 350 transitions. [2023-02-16 01:39:43,179 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 124 [2023-02-16 01:39:43,179 INFO L187 NwaCegarLoop]: Found error trace [2023-02-16 01:39:43,179 INFO L195 NwaCegarLoop]: trace histogram [17, 16, 16, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-02-16 01:39:43,184 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Forceful destruction successful, exit code 0 [2023-02-16 01:39:43,384 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable13,15 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-02-16 01:39:43,384 INFO L420 AbstractCegarLoop]: === Iteration 15 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-02-16 01:39:43,384 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2023-02-16 01:39:43,384 INFO L85 PathProgramCache]: Analyzing trace with hash 898620650, now seen corresponding path program 2 times [2023-02-16 01:39:43,385 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-02-16 01:39:43,385 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1180886557] [2023-02-16 01:39:43,385 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-16 01:39:43,385 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-02-16 01:39:43,397 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-02-16 01:39:43,397 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1121104284] [2023-02-16 01:39:43,397 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2023-02-16 01:39:43,397 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-02-16 01:39:43,397 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-16 01:39:43,398 INFO L229 MonitoredProcess]: Starting monitored process 16 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-02-16 01:39:43,399 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Waiting until timeout for monitored process [2023-02-16 01:39:43,463 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2023-02-16 01:39:43,463 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-02-16 01:39:43,464 INFO L263 TraceCheckSpWp]: Trace formula consists of 297 conjuncts, 65 conjunts are in the unsatisfiable core [2023-02-16 01:39:43,466 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2023-02-16 01:39:44,064 INFO L134 CoverageAnalysis]: Checked inductivity of 579 backedges. 35 proven. 49 refuted. 0 times theorem prover too weak. 495 trivial. 0 not checked. [2023-02-16 01:39:44,064 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2023-02-16 01:39:47,479 INFO L134 CoverageAnalysis]: Checked inductivity of 579 backedges. 32 proven. 43 refuted. 0 times theorem prover too weak. 504 trivial. 0 not checked. [2023-02-16 01:39:47,479 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-02-16 01:39:47,480 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1180886557] [2023-02-16 01:39:47,480 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-02-16 01:39:47,480 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1121104284] [2023-02-16 01:39:47,481 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1121104284] provided 0 perfect and 2 imperfect interpolant sequences [2023-02-16 01:39:47,481 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-02-16 01:39:47,481 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [17, 13] total 28 [2023-02-16 01:39:47,481 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1643259453] [2023-02-16 01:39:47,481 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-02-16 01:39:47,481 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 28 states [2023-02-16 01:39:47,481 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-02-16 01:39:47,482 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 28 interpolants. [2023-02-16 01:39:47,482 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=109, Invalid=647, Unknown=0, NotChecked=0, Total=756 [2023-02-16 01:39:47,482 INFO L87 Difference]: Start difference. First operand 260 states and 350 transitions. Second operand has 28 states, 26 states have (on average 1.9230769230769231) internal successors, (50), 25 states have internal predecessors, (50), 13 states have call successors, (40), 3 states have call predecessors, (40), 2 states have return successors, (39), 12 states have call predecessors, (39), 11 states have call successors, (39) [2023-02-16 01:40:25,528 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-02-16 01:40:25,528 INFO L93 Difference]: Finished difference Result 390 states and 548 transitions. [2023-02-16 01:40:25,529 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 51 states. [2023-02-16 01:40:25,529 INFO L78 Accepts]: Start accepts. Automaton has has 28 states, 26 states have (on average 1.9230769230769231) internal successors, (50), 25 states have internal predecessors, (50), 13 states have call successors, (40), 3 states have call predecessors, (40), 2 states have return successors, (39), 12 states have call predecessors, (39), 11 states have call successors, (39) Word has length 123 [2023-02-16 01:40:25,529 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-02-16 01:40:25,531 INFO L225 Difference]: With dead ends: 390 [2023-02-16 01:40:25,531 INFO L226 Difference]: Without dead ends: 382 [2023-02-16 01:40:25,532 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 287 GetRequests, 218 SyntacticMatches, 0 SemanticMatches, 69 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1197 ImplicationChecksByTransitivity, 20.7s TimeCoverageRelationStatistics Valid=853, Invalid=4117, Unknown=0, NotChecked=0, Total=4970 [2023-02-16 01:40:25,532 INFO L413 NwaCegarLoop]: 107 mSDtfsCounter, 175 mSDsluCounter, 590 mSDsCounter, 0 mSdLazyCounter, 2059 mSolverCounterSat, 422 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 19.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 183 SdHoareTripleChecker+Valid, 697 SdHoareTripleChecker+Invalid, 2481 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 422 IncrementalHoareTripleChecker+Valid, 2059 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 19.2s IncrementalHoareTripleChecker+Time [2023-02-16 01:40:25,532 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [183 Valid, 697 Invalid, 2481 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [422 Valid, 2059 Invalid, 0 Unknown, 0 Unchecked, 19.2s Time] [2023-02-16 01:40:25,533 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 382 states. [2023-02-16 01:40:25,740 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 382 to 366. [2023-02-16 01:40:25,741 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 366 states, 194 states have (on average 1.1546391752577319) internal successors, (224), 199 states have internal predecessors, (224), 146 states have call successors, (146), 25 states have call predecessors, (146), 25 states have return successors, (145), 141 states have call predecessors, (145), 145 states have call successors, (145) [2023-02-16 01:40:25,742 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 366 states to 366 states and 515 transitions. [2023-02-16 01:40:25,743 INFO L78 Accepts]: Start accepts. Automaton has 366 states and 515 transitions. Word has length 123 [2023-02-16 01:40:25,743 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-02-16 01:40:25,743 INFO L495 AbstractCegarLoop]: Abstraction has 366 states and 515 transitions. [2023-02-16 01:40:25,743 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 28 states, 26 states have (on average 1.9230769230769231) internal successors, (50), 25 states have internal predecessors, (50), 13 states have call successors, (40), 3 states have call predecessors, (40), 2 states have return successors, (39), 12 states have call predecessors, (39), 11 states have call successors, (39) [2023-02-16 01:40:25,743 INFO L276 IsEmpty]: Start isEmpty. Operand 366 states and 515 transitions. [2023-02-16 01:40:25,745 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 140 [2023-02-16 01:40:25,745 INFO L187 NwaCegarLoop]: Found error trace [2023-02-16 01:40:25,745 INFO L195 NwaCegarLoop]: trace histogram [20, 19, 19, 5, 5, 5, 5, 5, 5, 5, 5, 4, 4, 4, 4, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-02-16 01:40:25,750 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Forceful destruction successful, exit code 0 [2023-02-16 01:40:25,950 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 16 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable14 [2023-02-16 01:40:25,950 INFO L420 AbstractCegarLoop]: === Iteration 16 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-02-16 01:40:25,950 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2023-02-16 01:40:25,950 INFO L85 PathProgramCache]: Analyzing trace with hash 1501327478, now seen corresponding path program 3 times [2023-02-16 01:40:25,950 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-02-16 01:40:25,951 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1592844374] [2023-02-16 01:40:25,951 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-16 01:40:25,951 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-02-16 01:40:25,957 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-02-16 01:40:25,957 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [565661036] [2023-02-16 01:40:25,957 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2023-02-16 01:40:25,957 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-02-16 01:40:25,958 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-16 01:40:25,958 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) [2023-02-16 01:40:25,960 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Waiting until timeout for monitored process [2023-02-16 01:40:26,337 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2023-02-16 01:40:26,337 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-02-16 01:40:26,340 INFO L263 TraceCheckSpWp]: Trace formula consists of 196 conjuncts, 66 conjunts are in the unsatisfiable core [2023-02-16 01:40:26,342 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2023-02-16 01:40:32,631 INFO L134 CoverageAnalysis]: Checked inductivity of 809 backedges. 112 proven. 46 refuted. 0 times theorem prover too weak. 651 trivial. 0 not checked. [2023-02-16 01:40:32,631 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2023-02-16 01:40:35,003 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-02-16 01:40:35,004 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1592844374] [2023-02-16 01:40:35,004 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-02-16 01:40:35,004 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [565661036] [2023-02-16 01:40:35,004 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [565661036] provided 0 perfect and 1 imperfect interpolant sequences [2023-02-16 01:40:35,004 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2023-02-16 01:40:35,004 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [18] total 18 [2023-02-16 01:40:35,004 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1951448698] [2023-02-16 01:40:35,004 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2023-02-16 01:40:35,004 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 18 states [2023-02-16 01:40:35,005 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-02-16 01:40:35,005 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 18 interpolants. [2023-02-16 01:40:35,005 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=121, Invalid=529, Unknown=0, NotChecked=0, Total=650 [2023-02-16 01:40:35,006 INFO L87 Difference]: Start difference. First operand 366 states and 515 transitions. Second operand has 18 states, 16 states have (on average 2.125) internal successors, (34), 16 states have internal predecessors, (34), 7 states have call successors, (20), 2 states have call predecessors, (20), 3 states have return successors, (19), 8 states have call predecessors, (19), 6 states have call successors, (19) [2023-02-16 01:40:37,018 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-02-16 01:40:37,018 INFO L93 Difference]: Finished difference Result 407 states and 568 transitions. [2023-02-16 01:40:37,018 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 18 states. [2023-02-16 01:40:37,018 INFO L78 Accepts]: Start accepts. Automaton has has 18 states, 16 states have (on average 2.125) internal successors, (34), 16 states have internal predecessors, (34), 7 states have call successors, (20), 2 states have call predecessors, (20), 3 states have return successors, (19), 8 states have call predecessors, (19), 6 states have call successors, (19) Word has length 139 [2023-02-16 01:40:37,019 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-02-16 01:40:37,020 INFO L225 Difference]: With dead ends: 407 [2023-02-16 01:40:37,020 INFO L226 Difference]: Without dead ends: 405 [2023-02-16 01:40:37,021 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 191 GetRequests, 160 SyntacticMatches, 1 SemanticMatches, 30 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 185 ImplicationChecksByTransitivity, 5.0s TimeCoverageRelationStatistics Valid=175, Invalid=817, Unknown=0, NotChecked=0, Total=992 [2023-02-16 01:40:37,021 INFO L413 NwaCegarLoop]: 41 mSDtfsCounter, 26 mSDsluCounter, 188 mSDsCounter, 0 mSdLazyCounter, 1016 mSolverCounterSat, 25 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 33 SdHoareTripleChecker+Valid, 229 SdHoareTripleChecker+Invalid, 1041 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 25 IncrementalHoareTripleChecker+Valid, 1016 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.3s IncrementalHoareTripleChecker+Time [2023-02-16 01:40:37,021 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [33 Valid, 229 Invalid, 1041 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [25 Valid, 1016 Invalid, 0 Unknown, 0 Unchecked, 1.3s Time] [2023-02-16 01:40:37,022 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 405 states. [2023-02-16 01:40:37,241 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 405 to 402. [2023-02-16 01:40:37,242 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 402 states, 215 states have (on average 1.1534883720930234) internal successors, (248), 220 states have internal predecessors, (248), 158 states have call successors, (158), 28 states have call predecessors, (158), 28 states have return successors, (157), 153 states have call predecessors, (157), 157 states have call successors, (157) [2023-02-16 01:40:37,243 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 402 states to 402 states and 563 transitions. [2023-02-16 01:40:37,243 INFO L78 Accepts]: Start accepts. Automaton has 402 states and 563 transitions. Word has length 139 [2023-02-16 01:40:37,244 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-02-16 01:40:37,244 INFO L495 AbstractCegarLoop]: Abstraction has 402 states and 563 transitions. [2023-02-16 01:40:37,244 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 18 states, 16 states have (on average 2.125) internal successors, (34), 16 states have internal predecessors, (34), 7 states have call successors, (20), 2 states have call predecessors, (20), 3 states have return successors, (19), 8 states have call predecessors, (19), 6 states have call successors, (19) [2023-02-16 01:40:37,244 INFO L276 IsEmpty]: Start isEmpty. Operand 402 states and 563 transitions. [2023-02-16 01:40:37,245 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 143 [2023-02-16 01:40:37,245 INFO L187 NwaCegarLoop]: Found error trace [2023-02-16 01:40:37,245 INFO L195 NwaCegarLoop]: trace histogram [21, 20, 20, 5, 5, 5, 5, 5, 5, 5, 5, 5, 4, 4, 4, 4, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-02-16 01:40:37,251 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Forceful destruction successful, exit code 0 [2023-02-16 01:40:37,451 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 17 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable15 [2023-02-16 01:40:37,451 INFO L420 AbstractCegarLoop]: === Iteration 17 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-02-16 01:40:37,451 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2023-02-16 01:40:37,452 INFO L85 PathProgramCache]: Analyzing trace with hash -1673937813, now seen corresponding path program 3 times [2023-02-16 01:40:37,452 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-02-16 01:40:37,452 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1984162807] [2023-02-16 01:40:37,452 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-16 01:40:37,452 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-02-16 01:40:37,458 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-02-16 01:40:37,458 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1313017013] [2023-02-16 01:40:37,458 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2023-02-16 01:40:37,458 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-02-16 01:40:37,458 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-16 01:40:37,459 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) [2023-02-16 01:40:37,460 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (18)] Waiting until timeout for monitored process [2023-02-16 01:40:37,514 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2023-02-16 01:40:37,514 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-02-16 01:40:37,515 INFO L263 TraceCheckSpWp]: Trace formula consists of 185 conjuncts, 38 conjunts are in the unsatisfiable core [2023-02-16 01:40:37,517 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2023-02-16 01:40:37,857 INFO L134 CoverageAnalysis]: Checked inductivity of 886 backedges. 93 proven. 31 refuted. 0 times theorem prover too weak. 762 trivial. 0 not checked. [2023-02-16 01:40:37,857 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2023-02-16 01:40:38,010 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-02-16 01:40:38,010 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1984162807] [2023-02-16 01:40:38,010 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-02-16 01:40:38,010 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1313017013] [2023-02-16 01:40:38,010 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1313017013] provided 0 perfect and 1 imperfect interpolant sequences [2023-02-16 01:40:38,010 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2023-02-16 01:40:38,010 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12] total 12 [2023-02-16 01:40:38,011 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [325840805] [2023-02-16 01:40:38,011 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2023-02-16 01:40:38,011 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2023-02-16 01:40:38,012 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-02-16 01:40:38,012 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2023-02-16 01:40:38,012 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=40, Invalid=232, Unknown=0, NotChecked=0, Total=272 [2023-02-16 01:40:38,012 INFO L87 Difference]: Start difference. First operand 402 states and 563 transitions. Second operand has 12 states, 11 states have (on average 2.3636363636363638) internal successors, (26), 11 states have internal predecessors, (26), 4 states have call successors, (12), 2 states have call predecessors, (12), 3 states have return successors, (12), 3 states have call predecessors, (12), 3 states have call successors, (12) [2023-02-16 01:40:38,536 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-02-16 01:40:38,536 INFO L93 Difference]: Finished difference Result 429 states and 599 transitions. [2023-02-16 01:40:38,537 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2023-02-16 01:40:38,537 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 11 states have (on average 2.3636363636363638) internal successors, (26), 11 states have internal predecessors, (26), 4 states have call successors, (12), 2 states have call predecessors, (12), 3 states have return successors, (12), 3 states have call predecessors, (12), 3 states have call successors, (12) Word has length 142 [2023-02-16 01:40:38,537 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-02-16 01:40:38,538 INFO L225 Difference]: With dead ends: 429 [2023-02-16 01:40:38,539 INFO L226 Difference]: Without dead ends: 422 [2023-02-16 01:40:38,539 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 170 GetRequests, 150 SyntacticMatches, 0 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 28 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=70, Invalid=392, Unknown=0, NotChecked=0, Total=462 [2023-02-16 01:40:38,539 INFO L413 NwaCegarLoop]: 24 mSDtfsCounter, 20 mSDsluCounter, 115 mSDsCounter, 0 mSdLazyCounter, 396 mSolverCounterSat, 6 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 24 SdHoareTripleChecker+Valid, 139 SdHoareTripleChecker+Invalid, 402 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 6 IncrementalHoareTripleChecker+Valid, 396 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2023-02-16 01:40:38,540 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [24 Valid, 139 Invalid, 402 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [6 Valid, 396 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2023-02-16 01:40:38,540 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 422 states. [2023-02-16 01:40:38,773 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 422 to 405. [2023-02-16 01:40:38,774 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 405 states, 216 states have (on average 1.1481481481481481) internal successors, (248), 220 states have internal predecessors, (248), 159 states have call successors, (159), 29 states have call predecessors, (159), 29 states have return successors, (158), 155 states have call predecessors, (158), 158 states have call successors, (158) [2023-02-16 01:40:38,775 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 405 states to 405 states and 565 transitions. [2023-02-16 01:40:38,775 INFO L78 Accepts]: Start accepts. Automaton has 405 states and 565 transitions. Word has length 142 [2023-02-16 01:40:38,775 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-02-16 01:40:38,776 INFO L495 AbstractCegarLoop]: Abstraction has 405 states and 565 transitions. [2023-02-16 01:40:38,776 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 11 states have (on average 2.3636363636363638) internal successors, (26), 11 states have internal predecessors, (26), 4 states have call successors, (12), 2 states have call predecessors, (12), 3 states have return successors, (12), 3 states have call predecessors, (12), 3 states have call successors, (12) [2023-02-16 01:40:38,776 INFO L276 IsEmpty]: Start isEmpty. Operand 405 states and 565 transitions. [2023-02-16 01:40:38,777 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 157 [2023-02-16 01:40:38,777 INFO L187 NwaCegarLoop]: Found error trace [2023-02-16 01:40:38,777 INFO L195 NwaCegarLoop]: trace histogram [23, 22, 22, 6, 6, 6, 6, 6, 6, 5, 5, 5, 4, 4, 4, 3, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-02-16 01:40:38,783 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (18)] Ended with exit code 0 [2023-02-16 01:40:38,982 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 18 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable16 [2023-02-16 01:40:38,982 INFO L420 AbstractCegarLoop]: === Iteration 18 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-02-16 01:40:38,983 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2023-02-16 01:40:38,983 INFO L85 PathProgramCache]: Analyzing trace with hash -428170169, now seen corresponding path program 4 times [2023-02-16 01:40:38,983 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-02-16 01:40:38,983 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [123593548] [2023-02-16 01:40:38,983 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-16 01:40:38,983 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-02-16 01:40:38,989 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-02-16 01:40:38,989 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [230697963] [2023-02-16 01:40:38,989 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2023-02-16 01:40:38,989 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-02-16 01:40:38,990 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-16 01:40:38,990 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) [2023-02-16 01:40:38,991 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (19)] Waiting until timeout for monitored process [2023-02-16 01:40:39,054 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2023-02-16 01:40:39,054 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-02-16 01:40:39,056 INFO L263 TraceCheckSpWp]: Trace formula consists of 326 conjuncts, 81 conjunts are in the unsatisfiable core [2023-02-16 01:40:39,058 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2023-02-16 01:40:40,389 INFO L134 CoverageAnalysis]: Checked inductivity of 1079 backedges. 150 proven. 110 refuted. 0 times theorem prover too weak. 819 trivial. 0 not checked. [2023-02-16 01:40:40,389 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2023-02-16 01:40:40,854 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-02-16 01:40:40,854 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [123593548] [2023-02-16 01:40:40,854 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-02-16 01:40:40,854 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [230697963] [2023-02-16 01:40:40,854 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [230697963] provided 0 perfect and 1 imperfect interpolant sequences [2023-02-16 01:40:40,854 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2023-02-16 01:40:40,854 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [20] total 20 [2023-02-16 01:40:40,854 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2028996672] [2023-02-16 01:40:40,855 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2023-02-16 01:40:40,855 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 20 states [2023-02-16 01:40:40,855 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-02-16 01:40:40,855 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 20 interpolants. [2023-02-16 01:40:40,856 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=99, Invalid=501, Unknown=0, NotChecked=0, Total=600 [2023-02-16 01:40:40,856 INFO L87 Difference]: Start difference. First operand 405 states and 565 transitions. Second operand has 20 states, 20 states have (on average 1.85) internal successors, (37), 17 states have internal predecessors, (37), 9 states have call successors, (27), 2 states have call predecessors, (27), 3 states have return successors, (26), 9 states have call predecessors, (26), 9 states have call successors, (26) [2023-02-16 01:40:43,179 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.48s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [0] [2023-02-16 01:40:45,602 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-02-16 01:40:45,602 INFO L93 Difference]: Finished difference Result 443 states and 613 transitions. [2023-02-16 01:40:45,602 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 19 states. [2023-02-16 01:40:45,603 INFO L78 Accepts]: Start accepts. Automaton has has 20 states, 20 states have (on average 1.85) internal successors, (37), 17 states have internal predecessors, (37), 9 states have call successors, (27), 2 states have call predecessors, (27), 3 states have return successors, (26), 9 states have call predecessors, (26), 9 states have call successors, (26) Word has length 156 [2023-02-16 01:40:45,603 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-02-16 01:40:45,604 INFO L225 Difference]: With dead ends: 443 [2023-02-16 01:40:45,604 INFO L226 Difference]: Without dead ends: 441 [2023-02-16 01:40:45,605 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 186 GetRequests, 153 SyntacticMatches, 0 SemanticMatches, 33 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 211 ImplicationChecksByTransitivity, 1.4s TimeCoverageRelationStatistics Valid=185, Invalid=1005, Unknown=0, NotChecked=0, Total=1190 [2023-02-16 01:40:45,605 INFO L413 NwaCegarLoop]: 45 mSDtfsCounter, 50 mSDsluCounter, 175 mSDsCounter, 0 mSdLazyCounter, 1102 mSolverCounterSat, 88 mSolverCounterUnsat, 3 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 4.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 64 SdHoareTripleChecker+Valid, 220 SdHoareTripleChecker+Invalid, 1193 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 88 IncrementalHoareTripleChecker+Valid, 1102 IncrementalHoareTripleChecker+Invalid, 3 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 4.2s IncrementalHoareTripleChecker+Time [2023-02-16 01:40:45,605 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [64 Valid, 220 Invalid, 1193 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [88 Valid, 1102 Invalid, 3 Unknown, 0 Unchecked, 4.2s Time] [2023-02-16 01:40:45,606 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 441 states. [2023-02-16 01:40:45,843 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 441 to 410. [2023-02-16 01:40:45,844 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 410 states, 219 states have (on average 1.1461187214611872) internal successors, (251), 223 states have internal predecessors, (251), 159 states have call successors, (159), 31 states have call predecessors, (159), 31 states have return successors, (158), 155 states have call predecessors, (158), 158 states have call successors, (158) [2023-02-16 01:40:45,846 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 410 states to 410 states and 568 transitions. [2023-02-16 01:40:45,846 INFO L78 Accepts]: Start accepts. Automaton has 410 states and 568 transitions. Word has length 156 [2023-02-16 01:40:45,846 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-02-16 01:40:45,846 INFO L495 AbstractCegarLoop]: Abstraction has 410 states and 568 transitions. [2023-02-16 01:40:45,846 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 20 states, 20 states have (on average 1.85) internal successors, (37), 17 states have internal predecessors, (37), 9 states have call successors, (27), 2 states have call predecessors, (27), 3 states have return successors, (26), 9 states have call predecessors, (26), 9 states have call successors, (26) [2023-02-16 01:40:45,846 INFO L276 IsEmpty]: Start isEmpty. Operand 410 states and 568 transitions. [2023-02-16 01:40:45,848 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 165 [2023-02-16 01:40:45,848 INFO L187 NwaCegarLoop]: Found error trace [2023-02-16 01:40:45,848 INFO L195 NwaCegarLoop]: trace histogram [24, 23, 23, 6, 6, 6, 6, 6, 6, 6, 6, 5, 4, 4, 4, 4, 4, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-02-16 01:40:45,859 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (19)] Forceful destruction successful, exit code 0 [2023-02-16 01:40:46,053 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 19 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable17 [2023-02-16 01:40:46,054 INFO L420 AbstractCegarLoop]: === Iteration 19 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-02-16 01:40:46,054 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2023-02-16 01:40:46,054 INFO L85 PathProgramCache]: Analyzing trace with hash 194788219, now seen corresponding path program 5 times [2023-02-16 01:40:46,054 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-02-16 01:40:46,054 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1281672601] [2023-02-16 01:40:46,054 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-16 01:40:46,055 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-02-16 01:40:46,061 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-02-16 01:40:46,061 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1313146275] [2023-02-16 01:40:46,061 INFO L93 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2023-02-16 01:40:46,061 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-02-16 01:40:46,061 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-16 01:40:46,062 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) [2023-02-16 01:40:46,064 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (20)] Waiting until timeout for monitored process [2023-02-16 01:40:46,400 INFO L228 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 8 check-sat command(s) [2023-02-16 01:40:46,400 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-02-16 01:40:46,403 INFO L263 TraceCheckSpWp]: Trace formula consists of 386 conjuncts, 110 conjunts are in the unsatisfiable core [2023-02-16 01:40:46,406 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2023-02-16 01:40:47,584 INFO L134 CoverageAnalysis]: Checked inductivity of 1182 backedges. 188 proven. 228 refuted. 0 times theorem prover too weak. 766 trivial. 0 not checked. [2023-02-16 01:40:47,584 INFO L328 TraceCheckSpWp]: Computing backward predicates...