./Ultimate.py --spec ../sv-benchmarks/c/properties/unreach-call.prp --file ../sv-benchmarks/c/nla-digbench/egcd3-ll.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version e8d55036 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/egcd3-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 4ef08007570a64191e0df13d14d3e8d62a8022f43f46779ea6f6701a621376be --- Real Ultimate output --- This is Ultimate 0.2.2-?-e8d5503-m [2023-02-15 20:19:36,369 INFO L177 SettingsManager]: Resetting all preferences to default values... [2023-02-15 20:19:36,371 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2023-02-15 20:19:36,405 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2023-02-15 20:19:36,405 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2023-02-15 20:19:36,408 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2023-02-15 20:19:36,409 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2023-02-15 20:19:36,411 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2023-02-15 20:19:36,413 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2023-02-15 20:19:36,417 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2023-02-15 20:19:36,418 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2023-02-15 20:19:36,419 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2023-02-15 20:19:36,420 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2023-02-15 20:19:36,421 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2023-02-15 20:19:36,422 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2023-02-15 20:19:36,423 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2023-02-15 20:19:36,423 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2023-02-15 20:19:36,424 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2023-02-15 20:19:36,426 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2023-02-15 20:19:36,427 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2023-02-15 20:19:36,430 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2023-02-15 20:19:36,430 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2023-02-15 20:19:36,431 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2023-02-15 20:19:36,432 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2023-02-15 20:19:36,435 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2023-02-15 20:19:36,436 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2023-02-15 20:19:36,436 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2023-02-15 20:19:36,437 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2023-02-15 20:19:36,438 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2023-02-15 20:19:36,438 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2023-02-15 20:19:36,438 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2023-02-15 20:19:36,439 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2023-02-15 20:19:36,440 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2023-02-15 20:19:36,440 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2023-02-15 20:19:36,441 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2023-02-15 20:19:36,441 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2023-02-15 20:19:36,441 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2023-02-15 20:19:36,442 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2023-02-15 20:19:36,442 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2023-02-15 20:19:36,442 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2023-02-15 20:19:36,443 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2023-02-15 20:19:36,443 INFO L101 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf [2023-02-15 20:19:36,467 INFO L113 SettingsManager]: Loading preferences was successful [2023-02-15 20:19:36,467 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2023-02-15 20:19:36,467 INFO L136 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2023-02-15 20:19:36,467 INFO L138 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2023-02-15 20:19:36,468 INFO L136 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2023-02-15 20:19:36,468 INFO L138 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2023-02-15 20:19:36,469 INFO L136 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2023-02-15 20:19:36,469 INFO L138 SettingsManager]: * Create parallel compositions if possible=false [2023-02-15 20:19:36,469 INFO L138 SettingsManager]: * Use SBE=true [2023-02-15 20:19:36,469 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2023-02-15 20:19:36,470 INFO L138 SettingsManager]: * sizeof long=4 [2023-02-15 20:19:36,470 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2023-02-15 20:19:36,470 INFO L138 SettingsManager]: * sizeof POINTER=4 [2023-02-15 20:19:36,470 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2023-02-15 20:19:36,470 INFO L138 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2023-02-15 20:19:36,470 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2023-02-15 20:19:36,471 INFO L138 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2023-02-15 20:19:36,471 INFO L138 SettingsManager]: * sizeof long double=12 [2023-02-15 20:19:36,471 INFO L138 SettingsManager]: * Check if freed pointer was valid=false [2023-02-15 20:19:36,471 INFO L138 SettingsManager]: * Use constant arrays=true [2023-02-15 20:19:36,471 INFO L138 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2023-02-15 20:19:36,471 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2023-02-15 20:19:36,472 INFO L138 SettingsManager]: * Size of a code block=SequenceOfStatements [2023-02-15 20:19:36,472 INFO L138 SettingsManager]: * SMT solver=External_DefaultMode [2023-02-15 20:19:36,472 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2023-02-15 20:19:36,472 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2023-02-15 20:19:36,472 INFO L138 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2023-02-15 20:19:36,472 INFO L138 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2023-02-15 20:19:36,473 INFO L138 SettingsManager]: * Trace refinement strategy=CAMEL [2023-02-15 20:19:36,473 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2023-02-15 20:19:36,473 INFO L138 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2023-02-15 20:19:36,473 INFO L138 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2023-02-15 20:19:36,473 INFO L138 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2023-02-15 20:19:36,473 INFO L138 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2023-02-15 20:19:36,474 INFO L138 SettingsManager]: * Independence relation used for large block encoding in concurrent analysis=SYNTACTIC [2023-02-15 20:19:36,474 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 -> 4ef08007570a64191e0df13d14d3e8d62a8022f43f46779ea6f6701a621376be [2023-02-15 20:19:36,665 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2023-02-15 20:19:36,679 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2023-02-15 20:19:36,681 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2023-02-15 20:19:36,681 INFO L271 PluginConnector]: Initializing CDTParser... [2023-02-15 20:19:36,682 INFO L275 PluginConnector]: CDTParser initialized [2023-02-15 20:19:36,682 INFO L432 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/nla-digbench/egcd3-ll.c [2023-02-15 20:19:37,722 INFO L500 CDTParser]: Created temporary CDT project at NULL [2023-02-15 20:19:37,842 INFO L351 CDTParser]: Found 1 translation units. [2023-02-15 20:19:37,843 INFO L172 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench/egcd3-ll.c [2023-02-15 20:19:37,847 INFO L394 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/0e82e81d5/21e23cf7369346b79267461b1cd3ac02/FLAG96719b574 [2023-02-15 20:19:37,858 INFO L402 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/0e82e81d5/21e23cf7369346b79267461b1cd3ac02 [2023-02-15 20:19:37,860 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2023-02-15 20:19:37,861 INFO L131 ToolchainWalker]: Walking toolchain with 6 elements. [2023-02-15 20:19:37,862 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2023-02-15 20:19:37,862 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2023-02-15 20:19:37,864 INFO L275 PluginConnector]: CACSL2BoogieTranslator initialized [2023-02-15 20:19:37,865 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 15.02 08:19:37" (1/1) ... [2023-02-15 20:19:37,865 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@c27d1b1 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.02 08:19:37, skipping insertion in model container [2023-02-15 20:19:37,865 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 15.02 08:19:37" (1/1) ... [2023-02-15 20:19:37,870 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2023-02-15 20:19:37,883 INFO L178 MainTranslator]: Built tables and reachable declarations [2023-02-15 20:19:37,995 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/egcd3-ll.c[490,503] [2023-02-15 20:19:38,018 INFO L210 PostProcessor]: Analyzing one entry point: main [2023-02-15 20:19:38,025 INFO L203 MainTranslator]: Completed pre-run [2023-02-15 20:19:38,034 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/egcd3-ll.c[490,503] [2023-02-15 20:19:38,050 INFO L210 PostProcessor]: Analyzing one entry point: main [2023-02-15 20:19:38,060 INFO L208 MainTranslator]: Completed translation [2023-02-15 20:19:38,062 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.02 08:19:38 WrapperNode [2023-02-15 20:19:38,062 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2023-02-15 20:19:38,063 INFO L113 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2023-02-15 20:19:38,063 INFO L271 PluginConnector]: Initializing Boogie Procedure Inliner... [2023-02-15 20:19:38,063 INFO L275 PluginConnector]: Boogie Procedure Inliner initialized [2023-02-15 20:19:38,067 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.02 08:19:38" (1/1) ... [2023-02-15 20:19:38,072 INFO L185 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.02 08:19:38" (1/1) ... [2023-02-15 20:19:38,086 INFO L138 Inliner]: procedures = 14, calls = 14, calls flagged for inlining = 2, calls inlined = 2, statements flattened = 78 [2023-02-15 20:19:38,087 INFO L132 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2023-02-15 20:19:38,087 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2023-02-15 20:19:38,087 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2023-02-15 20:19:38,087 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2023-02-15 20:19:38,093 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.02 08:19:38" (1/1) ... [2023-02-15 20:19:38,093 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.02 08:19:38" (1/1) ... [2023-02-15 20:19:38,100 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.02 08:19:38" (1/1) ... [2023-02-15 20:19:38,100 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.02 08:19:38" (1/1) ... [2023-02-15 20:19:38,108 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.02 08:19:38" (1/1) ... [2023-02-15 20:19:38,112 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.02 08:19:38" (1/1) ... [2023-02-15 20:19:38,113 INFO L185 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.02 08:19:38" (1/1) ... [2023-02-15 20:19:38,113 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.02 08:19:38" (1/1) ... [2023-02-15 20:19:38,115 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2023-02-15 20:19:38,116 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2023-02-15 20:19:38,116 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2023-02-15 20:19:38,116 INFO L275 PluginConnector]: RCFGBuilder initialized [2023-02-15 20:19:38,117 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.02 08:19:38" (1/1) ... [2023-02-15 20:19:38,121 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2023-02-15 20:19:38,130 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-15 20:19:38,154 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-15 20:19:38,185 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-15 20:19:38,190 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2023-02-15 20:19:38,190 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2023-02-15 20:19:38,190 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2023-02-15 20:19:38,191 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2023-02-15 20:19:38,191 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2023-02-15 20:19:38,191 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2023-02-15 20:19:38,191 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2023-02-15 20:19:38,192 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2023-02-15 20:19:38,234 INFO L235 CfgBuilder]: Building ICFG [2023-02-15 20:19:38,236 INFO L261 CfgBuilder]: Building CFG for each procedure with an implementation [2023-02-15 20:19:38,379 INFO L276 CfgBuilder]: Performing block encoding [2023-02-15 20:19:38,389 INFO L295 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2023-02-15 20:19:38,389 INFO L300 CfgBuilder]: Removed 3 assume(true) statements. [2023-02-15 20:19:38,390 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 15.02 08:19:38 BoogieIcfgContainer [2023-02-15 20:19:38,390 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2023-02-15 20:19:38,392 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2023-02-15 20:19:38,392 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2023-02-15 20:19:38,394 INFO L275 PluginConnector]: TraceAbstraction initialized [2023-02-15 20:19:38,394 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 15.02 08:19:37" (1/3) ... [2023-02-15 20:19:38,394 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@67d76f56 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 15.02 08:19:38, skipping insertion in model container [2023-02-15 20:19:38,394 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.02 08:19:38" (2/3) ... [2023-02-15 20:19:38,394 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@67d76f56 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 15.02 08:19:38, skipping insertion in model container [2023-02-15 20:19:38,394 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 15.02 08:19:38" (3/3) ... [2023-02-15 20:19:38,395 INFO L112 eAbstractionObserver]: Analyzing ICFG egcd3-ll.c [2023-02-15 20:19:38,423 INFO L203 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2023-02-15 20:19:38,423 INFO L162 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2023-02-15 20:19:38,463 INFO L356 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2023-02-15 20:19:38,468 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;@1995d0c8, mLbeIndependenceSettings=[IndependenceType=SYNTACTIC, AbstractionType=NONE, UseConditional=, UseSemiCommutativity=, Solver=, SolverTimeout=] [2023-02-15 20:19:38,468 INFO L358 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2023-02-15 20:19:38,471 INFO L276 IsEmpty]: Start isEmpty. Operand has 32 states, 21 states have (on average 1.5714285714285714) internal successors, (33), 22 states have internal predecessors, (33), 7 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2023-02-15 20:19:38,475 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 19 [2023-02-15 20:19:38,475 INFO L187 NwaCegarLoop]: Found error trace [2023-02-15 20:19:38,476 INFO L195 NwaCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-02-15 20:19:38,476 INFO L420 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-02-15 20:19:38,481 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2023-02-15 20:19:38,481 INFO L85 PathProgramCache]: Analyzing trace with hash -149497031, now seen corresponding path program 1 times [2023-02-15 20:19:38,486 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-02-15 20:19:38,487 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1484461180] [2023-02-15 20:19:38,487 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-15 20:19:38,487 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-02-15 20:19:38,574 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-02-15 20:19:38,604 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-02-15 20:19:38,604 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1484461180] [2023-02-15 20:19:38,604 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: Unsupported non-linear arithmetic [2023-02-15 20:19:38,605 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [66066032] [2023-02-15 20:19:38,605 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-15 20:19:38,605 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-02-15 20:19:38,605 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-15 20:19:38,616 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-15 20:19:38,655 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-15 20:19:38,683 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-02-15 20:19:38,685 INFO L263 TraceCheckSpWp]: Trace formula consists of 69 conjuncts, 1 conjunts are in the unsatisfiable core [2023-02-15 20:19:38,689 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2023-02-15 20:19:38,708 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2023-02-15 20:19:38,708 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2023-02-15 20:19:38,709 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [66066032] provided 1 perfect and 0 imperfect interpolant sequences [2023-02-15 20:19:38,709 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-02-15 20:19:38,709 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2023-02-15 20:19:38,710 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [237556958] [2023-02-15 20:19:38,711 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-02-15 20:19:38,714 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2023-02-15 20:19:38,714 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-02-15 20:19:38,740 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2023-02-15 20:19:38,741 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2023-02-15 20:19:38,742 INFO L87 Difference]: Start difference. First operand has 32 states, 21 states have (on average 1.5714285714285714) internal successors, (33), 22 states have internal predecessors, (33), 7 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) 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, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) [2023-02-15 20:19:38,765 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-02-15 20:19:38,766 INFO L93 Difference]: Finished difference Result 61 states and 97 transitions. [2023-02-15 20:19:38,766 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2023-02-15 20:19:38,767 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, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) Word has length 18 [2023-02-15 20:19:38,768 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-02-15 20:19:38,772 INFO L225 Difference]: With dead ends: 61 [2023-02-15 20:19:38,772 INFO L226 Difference]: Without dead ends: 28 [2023-02-15 20:19:38,775 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 17 GetRequests, 17 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-15 20:19:38,777 INFO L413 NwaCegarLoop]: 39 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, 39 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-15 20:19:38,778 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 39 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 0 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-02-15 20:19:38,791 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 28 states. [2023-02-15 20:19:38,801 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 28 to 28. [2023-02-15 20:19:38,802 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 28 states, 18 states have (on average 1.2222222222222223) internal successors, (22), 19 states have internal predecessors, (22), 7 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2023-02-15 20:19:38,803 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 28 states to 28 states and 35 transitions. [2023-02-15 20:19:38,804 INFO L78 Accepts]: Start accepts. Automaton has 28 states and 35 transitions. Word has length 18 [2023-02-15 20:19:38,804 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-02-15 20:19:38,804 INFO L495 AbstractCegarLoop]: Abstraction has 28 states and 35 transitions. [2023-02-15 20:19:38,805 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, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) [2023-02-15 20:19:38,805 INFO L276 IsEmpty]: Start isEmpty. Operand 28 states and 35 transitions. [2023-02-15 20:19:38,806 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 20 [2023-02-15 20:19:38,806 INFO L187 NwaCegarLoop]: Found error trace [2023-02-15 20:19:38,806 INFO L195 NwaCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-02-15 20:19:38,817 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-15 20:19:39,023 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-15 20:19:39,023 INFO L420 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-02-15 20:19:39,024 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2023-02-15 20:19:39,024 INFO L85 PathProgramCache]: Analyzing trace with hash -2030119444, now seen corresponding path program 1 times [2023-02-15 20:19:39,024 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-02-15 20:19:39,024 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [503868287] [2023-02-15 20:19:39,024 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-15 20:19:39,024 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-02-15 20:19:39,035 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-02-15 20:19:39,036 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1089863618] [2023-02-15 20:19:39,036 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-15 20:19:39,036 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-02-15 20:19:39,036 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-15 20:19:39,059 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-15 20:19:39,078 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-15 20:19:39,104 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-02-15 20:19:39,105 INFO L263 TraceCheckSpWp]: Trace formula consists of 71 conjuncts, 7 conjunts are in the unsatisfiable core [2023-02-15 20:19:39,107 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2023-02-15 20:19:39,171 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 3 proven. 0 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2023-02-15 20:19:39,171 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2023-02-15 20:19:39,172 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-02-15 20:19:39,173 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [503868287] [2023-02-15 20:19:39,173 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-02-15 20:19:39,174 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1089863618] [2023-02-15 20:19:39,175 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1089863618] provided 1 perfect and 0 imperfect interpolant sequences [2023-02-15 20:19:39,175 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-02-15 20:19:39,177 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2023-02-15 20:19:39,177 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1431305314] [2023-02-15 20:19:39,178 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-02-15 20:19:39,179 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2023-02-15 20:19:39,179 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-02-15 20:19:39,181 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2023-02-15 20:19:39,181 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2023-02-15 20:19:39,181 INFO L87 Difference]: Start difference. First operand 28 states and 35 transitions. Second operand has 6 states, 6 states have (on average 2.3333333333333335) internal successors, (14), 5 states have internal predecessors, (14), 2 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) [2023-02-15 20:19:39,266 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-02-15 20:19:39,267 INFO L93 Difference]: Finished difference Result 47 states and 60 transitions. [2023-02-15 20:19:39,267 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2023-02-15 20:19:39,267 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 2.3333333333333335) internal successors, (14), 5 states have internal predecessors, (14), 2 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) Word has length 19 [2023-02-15 20:19:39,268 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-02-15 20:19:39,268 INFO L225 Difference]: With dead ends: 47 [2023-02-15 20:19:39,268 INFO L226 Difference]: Without dead ends: 40 [2023-02-15 20:19:39,269 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 20 GetRequests, 14 SyntacticMatches, 0 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=17, Invalid=39, Unknown=0, NotChecked=0, Total=56 [2023-02-15 20:19:39,269 INFO L413 NwaCegarLoop]: 31 mSDtfsCounter, 32 mSDsluCounter, 73 mSDsCounter, 0 mSdLazyCounter, 60 mSolverCounterSat, 8 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 36 SdHoareTripleChecker+Valid, 104 SdHoareTripleChecker+Invalid, 68 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 8 IncrementalHoareTripleChecker+Valid, 60 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-02-15 20:19:39,270 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [36 Valid, 104 Invalid, 68 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [8 Valid, 60 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-02-15 20:19:39,270 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 40 states. [2023-02-15 20:19:39,275 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 40 to 30. [2023-02-15 20:19:39,275 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 30 states, 20 states have (on average 1.2) internal successors, (24), 21 states have internal predecessors, (24), 7 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2023-02-15 20:19:39,276 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 30 states to 30 states and 37 transitions. [2023-02-15 20:19:39,276 INFO L78 Accepts]: Start accepts. Automaton has 30 states and 37 transitions. Word has length 19 [2023-02-15 20:19:39,276 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-02-15 20:19:39,277 INFO L495 AbstractCegarLoop]: Abstraction has 30 states and 37 transitions. [2023-02-15 20:19:39,277 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 2.3333333333333335) internal successors, (14), 5 states have internal predecessors, (14), 2 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) [2023-02-15 20:19:39,277 INFO L276 IsEmpty]: Start isEmpty. Operand 30 states and 37 transitions. [2023-02-15 20:19:39,277 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 23 [2023-02-15 20:19:39,277 INFO L187 NwaCegarLoop]: Found error trace [2023-02-15 20:19:39,278 INFO L195 NwaCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-02-15 20:19:39,285 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-15 20:19:39,482 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-15 20:19:39,483 INFO L420 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-02-15 20:19:39,483 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2023-02-15 20:19:39,484 INFO L85 PathProgramCache]: Analyzing trace with hash 1778657237, now seen corresponding path program 1 times [2023-02-15 20:19:39,484 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-02-15 20:19:39,484 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1171269419] [2023-02-15 20:19:39,484 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-15 20:19:39,484 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-02-15 20:19:39,492 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-02-15 20:19:39,493 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1739691559] [2023-02-15 20:19:39,493 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-15 20:19:39,493 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-02-15 20:19:39,493 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-15 20:19:39,510 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-15 20:19:39,537 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-15 20:19:39,570 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-02-15 20:19:39,571 INFO L263 TraceCheckSpWp]: Trace formula consists of 81 conjuncts, 18 conjunts are in the unsatisfiable core [2023-02-15 20:19:39,573 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2023-02-15 20:19:39,671 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 3 proven. 0 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2023-02-15 20:19:39,672 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2023-02-15 20:19:39,672 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-02-15 20:19:39,672 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1171269419] [2023-02-15 20:19:39,672 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-02-15 20:19:39,672 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1739691559] [2023-02-15 20:19:39,672 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1739691559] provided 1 perfect and 0 imperfect interpolant sequences [2023-02-15 20:19:39,672 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-02-15 20:19:39,673 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [9] imperfect sequences [] total 9 [2023-02-15 20:19:39,673 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1036218426] [2023-02-15 20:19:39,673 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-02-15 20:19:39,673 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2023-02-15 20:19:39,673 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-02-15 20:19:39,674 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2023-02-15 20:19:39,674 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=18, Invalid=54, Unknown=0, NotChecked=0, Total=72 [2023-02-15 20:19:39,674 INFO L87 Difference]: Start difference. First operand 30 states and 37 transitions. Second operand has 9 states, 8 states have (on average 2.125) internal successors, (17), 7 states have internal predecessors, (17), 2 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) [2023-02-15 20:19:39,763 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-02-15 20:19:39,763 INFO L93 Difference]: Finished difference Result 46 states and 58 transitions. [2023-02-15 20:19:39,764 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2023-02-15 20:19:39,764 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 8 states have (on average 2.125) internal successors, (17), 7 states have internal predecessors, (17), 2 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) Word has length 22 [2023-02-15 20:19:39,764 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-02-15 20:19:39,765 INFO L225 Difference]: With dead ends: 46 [2023-02-15 20:19:39,765 INFO L226 Difference]: Without dead ends: 44 [2023-02-15 20:19:39,765 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 23 GetRequests, 14 SyntacticMatches, 0 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 9 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=26, Invalid=84, Unknown=0, NotChecked=0, Total=110 [2023-02-15 20:19:39,766 INFO L413 NwaCegarLoop]: 30 mSDtfsCounter, 43 mSDsluCounter, 110 mSDsCounter, 0 mSdLazyCounter, 84 mSolverCounterSat, 12 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 51 SdHoareTripleChecker+Valid, 140 SdHoareTripleChecker+Invalid, 96 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 12 IncrementalHoareTripleChecker+Valid, 84 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-02-15 20:19:39,766 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [51 Valid, 140 Invalid, 96 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [12 Valid, 84 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-02-15 20:19:39,767 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 44 states. [2023-02-15 20:19:39,772 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 44 to 43. [2023-02-15 20:19:39,772 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 43 states, 28 states have (on average 1.2142857142857142) internal successors, (34), 29 states have internal predecessors, (34), 11 states have call successors, (11), 3 states have call predecessors, (11), 3 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2023-02-15 20:19:39,773 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 43 states to 43 states and 55 transitions. [2023-02-15 20:19:39,773 INFO L78 Accepts]: Start accepts. Automaton has 43 states and 55 transitions. Word has length 22 [2023-02-15 20:19:39,773 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-02-15 20:19:39,773 INFO L495 AbstractCegarLoop]: Abstraction has 43 states and 55 transitions. [2023-02-15 20:19:39,773 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 8 states have (on average 2.125) internal successors, (17), 7 states have internal predecessors, (17), 2 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) [2023-02-15 20:19:39,774 INFO L276 IsEmpty]: Start isEmpty. Operand 43 states and 55 transitions. [2023-02-15 20:19:39,774 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 25 [2023-02-15 20:19:39,774 INFO L187 NwaCegarLoop]: Found error trace [2023-02-15 20:19:39,774 INFO L195 NwaCegarLoop]: trace histogram [2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-02-15 20:19:39,781 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-15 20:19:39,979 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-15 20:19:39,979 INFO L420 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-02-15 20:19:39,979 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2023-02-15 20:19:39,979 INFO L85 PathProgramCache]: Analyzing trace with hash 646289443, now seen corresponding path program 1 times [2023-02-15 20:19:39,980 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-02-15 20:19:39,980 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1889713081] [2023-02-15 20:19:39,980 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-15 20:19:39,980 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-02-15 20:19:39,991 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-02-15 20:19:39,992 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1226410329] [2023-02-15 20:19:39,992 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-15 20:19:39,992 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-02-15 20:19:39,992 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-15 20:19:39,993 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-15 20:19:40,001 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-15 20:19:40,055 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-02-15 20:19:40,056 INFO L263 TraceCheckSpWp]: Trace formula consists of 93 conjuncts, 9 conjunts are in the unsatisfiable core [2023-02-15 20:19:40,057 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2023-02-15 20:19:40,110 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 0 proven. 5 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2023-02-15 20:19:40,110 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2023-02-15 20:19:40,175 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 0 proven. 5 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2023-02-15 20:19:40,176 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-02-15 20:19:40,176 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1889713081] [2023-02-15 20:19:40,176 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-02-15 20:19:40,176 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1226410329] [2023-02-15 20:19:40,176 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1226410329] provided 0 perfect and 2 imperfect interpolant sequences [2023-02-15 20:19:40,176 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-02-15 20:19:40,177 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 9 [2023-02-15 20:19:40,177 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1179200934] [2023-02-15 20:19:40,177 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-02-15 20:19:40,177 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2023-02-15 20:19:40,177 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-02-15 20:19:40,178 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2023-02-15 20:19:40,178 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=17, Invalid=55, Unknown=0, NotChecked=0, Total=72 [2023-02-15 20:19:40,178 INFO L87 Difference]: Start difference. First operand 43 states and 55 transitions. Second operand has 9 states, 9 states have (on average 2.3333333333333335) internal successors, (21), 8 states have internal predecessors, (21), 3 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) [2023-02-15 20:19:40,309 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-02-15 20:19:40,310 INFO L93 Difference]: Finished difference Result 96 states and 134 transitions. [2023-02-15 20:19:40,310 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2023-02-15 20:19:40,310 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 9 states have (on average 2.3333333333333335) internal successors, (21), 8 states have internal predecessors, (21), 3 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) Word has length 24 [2023-02-15 20:19:40,310 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-02-15 20:19:40,311 INFO L225 Difference]: With dead ends: 96 [2023-02-15 20:19:40,311 INFO L226 Difference]: Without dead ends: 89 [2023-02-15 20:19:40,312 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 51 GetRequests, 34 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-15 20:19:40,313 INFO L413 NwaCegarLoop]: 45 mSDtfsCounter, 64 mSDsluCounter, 148 mSDsCounter, 0 mSdLazyCounter, 148 mSolverCounterSat, 40 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 68 SdHoareTripleChecker+Valid, 193 SdHoareTripleChecker+Invalid, 188 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 40 IncrementalHoareTripleChecker+Valid, 148 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-02-15 20:19:40,318 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [68 Valid, 193 Invalid, 188 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [40 Valid, 148 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-02-15 20:19:40,319 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 89 states. [2023-02-15 20:19:40,331 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 89 to 64. [2023-02-15 20:19:40,331 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 64 states, 45 states have (on average 1.2666666666666666) internal successors, (57), 46 states have internal predecessors, (57), 15 states have call successors, (15), 3 states have call predecessors, (15), 3 states have return successors, (14), 14 states have call predecessors, (14), 14 states have call successors, (14) [2023-02-15 20:19:40,332 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 64 states to 64 states and 86 transitions. [2023-02-15 20:19:40,332 INFO L78 Accepts]: Start accepts. Automaton has 64 states and 86 transitions. Word has length 24 [2023-02-15 20:19:40,332 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-02-15 20:19:40,332 INFO L495 AbstractCegarLoop]: Abstraction has 64 states and 86 transitions. [2023-02-15 20:19:40,332 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 9 states have (on average 2.3333333333333335) internal successors, (21), 8 states have internal predecessors, (21), 3 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) [2023-02-15 20:19:40,332 INFO L276 IsEmpty]: Start isEmpty. Operand 64 states and 86 transitions. [2023-02-15 20:19:40,333 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 28 [2023-02-15 20:19:40,333 INFO L187 NwaCegarLoop]: Found error trace [2023-02-15 20:19:40,333 INFO L195 NwaCegarLoop]: trace histogram [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-15 20:19:40,352 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-15 20:19:40,533 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-15 20:19:40,534 INFO L420 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-02-15 20:19:40,534 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2023-02-15 20:19:40,534 INFO L85 PathProgramCache]: Analyzing trace with hash 1194834104, now seen corresponding path program 1 times [2023-02-15 20:19:40,534 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-02-15 20:19:40,534 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1404192354] [2023-02-15 20:19:40,534 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-15 20:19:40,534 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-02-15 20:19:40,544 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-02-15 20:19:40,544 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [702704039] [2023-02-15 20:19:40,544 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-15 20:19:40,544 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-02-15 20:19:40,544 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-15 20:19:40,547 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-15 20:19:40,549 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-15 20:19:40,592 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-02-15 20:19:40,593 INFO L263 TraceCheckSpWp]: Trace formula consists of 90 conjuncts, 27 conjunts are in the unsatisfiable core [2023-02-15 20:19:40,594 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2023-02-15 20:19:40,822 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 4 proven. 1 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2023-02-15 20:19:40,822 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2023-02-15 20:19:40,893 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-02-15 20:19:40,893 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1404192354] [2023-02-15 20:19:40,893 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-02-15 20:19:40,893 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [702704039] [2023-02-15 20:19:40,894 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [702704039] provided 0 perfect and 1 imperfect interpolant sequences [2023-02-15 20:19:40,894 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2023-02-15 20:19:40,894 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [14] total 14 [2023-02-15 20:19:40,894 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [124531048] [2023-02-15 20:19:40,894 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2023-02-15 20:19:40,894 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2023-02-15 20:19:40,894 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-02-15 20:19:40,895 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2023-02-15 20:19:40,895 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=54, Invalid=218, Unknown=0, NotChecked=0, Total=272 [2023-02-15 20:19:40,895 INFO L87 Difference]: Start difference. First operand 64 states and 86 transitions. Second operand has 14 states, 12 states have (on average 1.6666666666666667) internal successors, (20), 11 states have internal predecessors, (20), 3 states have call successors, (4), 2 states have call predecessors, (4), 3 states have return successors, (3), 3 states have call predecessors, (3), 2 states have call successors, (3) [2023-02-15 20:19:41,115 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-02-15 20:19:41,115 INFO L93 Difference]: Finished difference Result 79 states and 105 transitions. [2023-02-15 20:19:41,116 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2023-02-15 20:19:41,116 INFO L78 Accepts]: Start accepts. Automaton has has 14 states, 12 states have (on average 1.6666666666666667) internal successors, (20), 11 states have internal predecessors, (20), 3 states have call successors, (4), 2 states have call predecessors, (4), 3 states have return successors, (3), 3 states have call predecessors, (3), 2 states have call successors, (3) Word has length 27 [2023-02-15 20:19:41,116 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-02-15 20:19:41,117 INFO L225 Difference]: With dead ends: 79 [2023-02-15 20:19:41,117 INFO L226 Difference]: Without dead ends: 77 [2023-02-15 20:19:41,117 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 35 GetRequests, 16 SyntacticMatches, 0 SemanticMatches, 19 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 70 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=81, Invalid=339, Unknown=0, NotChecked=0, Total=420 [2023-02-15 20:19:41,118 INFO L413 NwaCegarLoop]: 20 mSDtfsCounter, 43 mSDsluCounter, 115 mSDsCounter, 0 mSdLazyCounter, 340 mSolverCounterSat, 13 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 51 SdHoareTripleChecker+Valid, 135 SdHoareTripleChecker+Invalid, 353 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 13 IncrementalHoareTripleChecker+Valid, 340 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2023-02-15 20:19:41,118 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [51 Valid, 135 Invalid, 353 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [13 Valid, 340 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2023-02-15 20:19:41,118 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 77 states. [2023-02-15 20:19:41,127 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 77 to 68. [2023-02-15 20:19:41,127 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 68 states, 48 states have (on average 1.25) internal successors, (60), 49 states have internal predecessors, (60), 15 states have call successors, (15), 4 states have call predecessors, (15), 4 states have return successors, (14), 14 states have call predecessors, (14), 14 states have call successors, (14) [2023-02-15 20:19:41,128 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 68 states to 68 states and 89 transitions. [2023-02-15 20:19:41,128 INFO L78 Accepts]: Start accepts. Automaton has 68 states and 89 transitions. Word has length 27 [2023-02-15 20:19:41,128 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-02-15 20:19:41,128 INFO L495 AbstractCegarLoop]: Abstraction has 68 states and 89 transitions. [2023-02-15 20:19:41,128 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 14 states, 12 states have (on average 1.6666666666666667) internal successors, (20), 11 states have internal predecessors, (20), 3 states have call successors, (4), 2 states have call predecessors, (4), 3 states have return successors, (3), 3 states have call predecessors, (3), 2 states have call successors, (3) [2023-02-15 20:19:41,129 INFO L276 IsEmpty]: Start isEmpty. Operand 68 states and 89 transitions. [2023-02-15 20:19:41,129 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 28 [2023-02-15 20:19:41,129 INFO L187 NwaCegarLoop]: Found error trace [2023-02-15 20:19:41,129 INFO L195 NwaCegarLoop]: trace histogram [2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-02-15 20:19:41,143 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-15 20:19:41,343 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-15 20:19:41,344 INFO L420 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-02-15 20:19:41,344 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2023-02-15 20:19:41,344 INFO L85 PathProgramCache]: Analyzing trace with hash -1392040386, now seen corresponding path program 1 times [2023-02-15 20:19:41,345 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-02-15 20:19:41,345 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [476219517] [2023-02-15 20:19:41,345 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-15 20:19:41,345 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-02-15 20:19:41,352 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-02-15 20:19:41,352 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1148983925] [2023-02-15 20:19:41,352 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-15 20:19:41,352 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-02-15 20:19:41,353 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-15 20:19:41,373 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-15 20:19:41,392 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-15 20:19:41,420 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-02-15 20:19:41,421 INFO L263 TraceCheckSpWp]: Trace formula consists of 103 conjuncts, 23 conjunts are in the unsatisfiable core [2023-02-15 20:19:41,422 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2023-02-15 20:19:41,512 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 0 proven. 7 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2023-02-15 20:19:41,512 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2023-02-15 20:19:41,572 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2023-02-15 20:19:41,572 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-02-15 20:19:41,572 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [476219517] [2023-02-15 20:19:41,572 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-02-15 20:19:41,573 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1148983925] [2023-02-15 20:19:41,573 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1148983925] provided 0 perfect and 2 imperfect interpolant sequences [2023-02-15 20:19:41,573 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-02-15 20:19:41,573 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 6] total 13 [2023-02-15 20:19:41,573 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [449030536] [2023-02-15 20:19:41,573 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-02-15 20:19:41,574 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 13 states [2023-02-15 20:19:41,574 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-02-15 20:19:41,574 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2023-02-15 20:19:41,574 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=29, Invalid=127, Unknown=0, NotChecked=0, Total=156 [2023-02-15 20:19:41,575 INFO L87 Difference]: Start difference. First operand 68 states and 89 transitions. Second operand has 13 states, 13 states have (on average 2.6923076923076925) internal successors, (35), 10 states have internal predecessors, (35), 4 states have call successors, (5), 3 states have call predecessors, (5), 2 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2023-02-15 20:19:41,714 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-02-15 20:19:41,714 INFO L93 Difference]: Finished difference Result 104 states and 138 transitions. [2023-02-15 20:19:41,714 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2023-02-15 20:19:41,714 INFO L78 Accepts]: Start accepts. Automaton has has 13 states, 13 states have (on average 2.6923076923076925) internal successors, (35), 10 states have internal predecessors, (35), 4 states have call successors, (5), 3 states have call predecessors, (5), 2 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) Word has length 27 [2023-02-15 20:19:41,715 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-02-15 20:19:41,715 INFO L225 Difference]: With dead ends: 104 [2023-02-15 20:19:41,715 INFO L226 Difference]: Without dead ends: 102 [2023-02-15 20:19:41,716 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 55 GetRequests, 41 SyntacticMatches, 0 SemanticMatches, 14 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 25 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=45, Invalid=195, Unknown=0, NotChecked=0, Total=240 [2023-02-15 20:19:41,716 INFO L413 NwaCegarLoop]: 42 mSDtfsCounter, 41 mSDsluCounter, 211 mSDsCounter, 0 mSdLazyCounter, 225 mSolverCounterSat, 16 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 49 SdHoareTripleChecker+Valid, 253 SdHoareTripleChecker+Invalid, 241 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 16 IncrementalHoareTripleChecker+Valid, 225 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-02-15 20:19:41,716 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [49 Valid, 253 Invalid, 241 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [16 Valid, 225 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-02-15 20:19:41,717 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 102 states. [2023-02-15 20:19:41,728 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 102 to 98. [2023-02-15 20:19:41,728 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 98 states, 69 states have (on average 1.2608695652173914) internal successors, (87), 70 states have internal predecessors, (87), 23 states have call successors, (23), 5 states have call predecessors, (23), 5 states have return successors, (22), 22 states have call predecessors, (22), 22 states have call successors, (22) [2023-02-15 20:19:41,729 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 98 states to 98 states and 132 transitions. [2023-02-15 20:19:41,729 INFO L78 Accepts]: Start accepts. Automaton has 98 states and 132 transitions. Word has length 27 [2023-02-15 20:19:41,730 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-02-15 20:19:41,730 INFO L495 AbstractCegarLoop]: Abstraction has 98 states and 132 transitions. [2023-02-15 20:19:41,730 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 13 states, 13 states have (on average 2.6923076923076925) internal successors, (35), 10 states have internal predecessors, (35), 4 states have call successors, (5), 3 states have call predecessors, (5), 2 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2023-02-15 20:19:41,730 INFO L276 IsEmpty]: Start isEmpty. Operand 98 states and 132 transitions. [2023-02-15 20:19:41,731 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 33 [2023-02-15 20:19:41,731 INFO L187 NwaCegarLoop]: Found error trace [2023-02-15 20:19:41,731 INFO L195 NwaCegarLoop]: trace histogram [3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-02-15 20:19:41,742 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Forceful destruction successful, exit code 0 [2023-02-15 20:19:41,935 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-15 20:19:41,936 INFO L420 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-02-15 20:19:41,936 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2023-02-15 20:19:41,936 INFO L85 PathProgramCache]: Analyzing trace with hash -281586315, now seen corresponding path program 1 times [2023-02-15 20:19:41,937 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-02-15 20:19:41,937 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [752382101] [2023-02-15 20:19:41,937 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-15 20:19:41,937 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-02-15 20:19:41,946 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-02-15 20:19:41,947 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [367205784] [2023-02-15 20:19:41,947 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-15 20:19:41,947 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-02-15 20:19:41,947 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-15 20:19:41,964 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-15 20:19:41,978 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-15 20:19:42,000 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-02-15 20:19:42,001 INFO L263 TraceCheckSpWp]: Trace formula consists of 99 conjuncts, 15 conjunts are in the unsatisfiable core [2023-02-15 20:19:42,002 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2023-02-15 20:19:42,050 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 6 proven. 1 refuted. 0 times theorem prover too weak. 5 trivial. 0 not checked. [2023-02-15 20:19:42,050 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2023-02-15 20:19:42,107 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 8 trivial. 0 not checked. [2023-02-15 20:19:42,108 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-02-15 20:19:42,108 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [752382101] [2023-02-15 20:19:42,108 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-02-15 20:19:42,108 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [367205784] [2023-02-15 20:19:42,108 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [367205784] provided 1 perfect and 1 imperfect interpolant sequences [2023-02-15 20:19:42,108 INFO L184 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2023-02-15 20:19:42,108 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [7] total 9 [2023-02-15 20:19:42,109 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1489854039] [2023-02-15 20:19:42,109 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-02-15 20:19:42,109 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2023-02-15 20:19:42,109 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-02-15 20:19:42,109 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2023-02-15 20:19:42,110 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=18, Invalid=54, Unknown=0, NotChecked=0, Total=72 [2023-02-15 20:19:42,110 INFO L87 Difference]: Start difference. First operand 98 states and 132 transitions. Second operand has 6 states, 5 states have (on average 3.4) internal successors, (17), 4 states have internal predecessors, (17), 3 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 3 states have call predecessors, (4), 2 states have call successors, (4) [2023-02-15 20:19:42,166 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-02-15 20:19:42,166 INFO L93 Difference]: Finished difference Result 144 states and 204 transitions. [2023-02-15 20:19:42,166 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2023-02-15 20:19:42,166 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 5 states have (on average 3.4) internal successors, (17), 4 states have internal predecessors, (17), 3 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 3 states have call predecessors, (4), 2 states have call successors, (4) Word has length 32 [2023-02-15 20:19:42,166 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-02-15 20:19:42,167 INFO L225 Difference]: With dead ends: 144 [2023-02-15 20:19:42,167 INFO L226 Difference]: Without dead ends: 142 [2023-02-15 20:19:42,168 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 63 GetRequests, 53 SyntacticMatches, 2 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 5 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=22, Invalid=68, Unknown=0, NotChecked=0, Total=90 [2023-02-15 20:19:42,168 INFO L413 NwaCegarLoop]: 33 mSDtfsCounter, 10 mSDsluCounter, 73 mSDsCounter, 0 mSdLazyCounter, 49 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 13 SdHoareTripleChecker+Valid, 106 SdHoareTripleChecker+Invalid, 52 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 49 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-02-15 20:19:42,168 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [13 Valid, 106 Invalid, 52 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 49 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-02-15 20:19:42,169 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 142 states. [2023-02-15 20:19:42,184 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 142 to 136. [2023-02-15 20:19:42,185 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 136 states, 86 states have (on average 1.2906976744186047) internal successors, (111), 87 states have internal predecessors, (111), 43 states have call successors, (43), 6 states have call predecessors, (43), 6 states have return successors, (42), 42 states have call predecessors, (42), 42 states have call successors, (42) [2023-02-15 20:19:42,186 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 136 states to 136 states and 196 transitions. [2023-02-15 20:19:42,186 INFO L78 Accepts]: Start accepts. Automaton has 136 states and 196 transitions. Word has length 32 [2023-02-15 20:19:42,186 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-02-15 20:19:42,186 INFO L495 AbstractCegarLoop]: Abstraction has 136 states and 196 transitions. [2023-02-15 20:19:42,187 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 5 states have (on average 3.4) internal successors, (17), 4 states have internal predecessors, (17), 3 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 3 states have call predecessors, (4), 2 states have call successors, (4) [2023-02-15 20:19:42,187 INFO L276 IsEmpty]: Start isEmpty. Operand 136 states and 196 transitions. [2023-02-15 20:19:42,187 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 33 [2023-02-15 20:19:42,187 INFO L187 NwaCegarLoop]: Found error trace [2023-02-15 20:19:42,188 INFO L195 NwaCegarLoop]: trace histogram [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-15 20:19:42,205 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Ended with exit code 0 [2023-02-15 20:19:42,392 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-15 20:19:42,392 INFO L420 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-02-15 20:19:42,393 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2023-02-15 20:19:42,393 INFO L85 PathProgramCache]: Analyzing trace with hash -1215278097, now seen corresponding path program 1 times [2023-02-15 20:19:42,393 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-02-15 20:19:42,393 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [328058886] [2023-02-15 20:19:42,393 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-15 20:19:42,393 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-02-15 20:19:42,400 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-02-15 20:19:42,401 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1354142702] [2023-02-15 20:19:42,401 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-15 20:19:42,401 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-02-15 20:19:42,401 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-15 20:19:42,417 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-15 20:19:42,464 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-15 20:19:42,471 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-02-15 20:19:42,472 INFO L263 TraceCheckSpWp]: Trace formula consists of 112 conjuncts, 39 conjunts are in the unsatisfiable core [2023-02-15 20:19:42,473 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2023-02-15 20:19:42,642 INFO L134 CoverageAnalysis]: Checked inductivity of 10 backedges. 1 proven. 8 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2023-02-15 20:19:42,642 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2023-02-15 20:19:42,700 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-02-15 20:19:42,700 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [328058886] [2023-02-15 20:19:42,700 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-02-15 20:19:42,700 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1354142702] [2023-02-15 20:19:42,701 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1354142702] provided 0 perfect and 1 imperfect interpolant sequences [2023-02-15 20:19:42,701 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2023-02-15 20:19:42,701 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13] total 13 [2023-02-15 20:19:42,701 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [150288725] [2023-02-15 20:19:42,701 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2023-02-15 20:19:42,701 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 13 states [2023-02-15 20:19:42,701 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-02-15 20:19:42,702 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2023-02-15 20:19:42,702 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=41, Invalid=199, Unknown=0, NotChecked=0, Total=240 [2023-02-15 20:19:42,702 INFO L87 Difference]: Start difference. First operand 136 states and 196 transitions. Second operand has 13 states, 12 states have (on average 2.0833333333333335) internal successors, (25), 11 states have internal predecessors, (25), 3 states have call successors, (4), 2 states have call predecessors, (4), 3 states have return successors, (3), 2 states have call predecessors, (3), 3 states have call successors, (3) [2023-02-15 20:19:42,886 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-02-15 20:19:42,886 INFO L93 Difference]: Finished difference Result 149 states and 207 transitions. [2023-02-15 20:19:42,886 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2023-02-15 20:19:42,886 INFO L78 Accepts]: Start accepts. Automaton has has 13 states, 12 states have (on average 2.0833333333333335) internal successors, (25), 11 states have internal predecessors, (25), 3 states have call successors, (4), 2 states have call predecessors, (4), 3 states have return successors, (3), 2 states have call predecessors, (3), 3 states have call successors, (3) Word has length 32 [2023-02-15 20:19:42,887 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-02-15 20:19:42,888 INFO L225 Difference]: With dead ends: 149 [2023-02-15 20:19:42,888 INFO L226 Difference]: Without dead ends: 147 [2023-02-15 20:19:42,888 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 40 GetRequests, 22 SyntacticMatches, 0 SemanticMatches, 18 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 58 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=64, Invalid=316, Unknown=0, NotChecked=0, Total=380 [2023-02-15 20:19:42,889 INFO L413 NwaCegarLoop]: 27 mSDtfsCounter, 79 mSDsluCounter, 104 mSDsCounter, 0 mSdLazyCounter, 328 mSolverCounterSat, 40 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 90 SdHoareTripleChecker+Valid, 131 SdHoareTripleChecker+Invalid, 368 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 40 IncrementalHoareTripleChecker+Valid, 328 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-02-15 20:19:42,889 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [90 Valid, 131 Invalid, 368 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [40 Valid, 328 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-02-15 20:19:42,889 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 147 states. [2023-02-15 20:19:42,914 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 147 to 144. [2023-02-15 20:19:42,914 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 144 states, 92 states have (on average 1.2717391304347827) internal successors, (117), 93 states have internal predecessors, (117), 43 states have call successors, (43), 8 states have call predecessors, (43), 8 states have return successors, (42), 42 states have call predecessors, (42), 42 states have call successors, (42) [2023-02-15 20:19:42,915 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 144 states to 144 states and 202 transitions. [2023-02-15 20:19:42,915 INFO L78 Accepts]: Start accepts. Automaton has 144 states and 202 transitions. Word has length 32 [2023-02-15 20:19:42,916 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-02-15 20:19:42,916 INFO L495 AbstractCegarLoop]: Abstraction has 144 states and 202 transitions. [2023-02-15 20:19:42,916 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 13 states, 12 states have (on average 2.0833333333333335) internal successors, (25), 11 states have internal predecessors, (25), 3 states have call successors, (4), 2 states have call predecessors, (4), 3 states have return successors, (3), 2 states have call predecessors, (3), 3 states have call successors, (3) [2023-02-15 20:19:42,916 INFO L276 IsEmpty]: Start isEmpty. Operand 144 states and 202 transitions. [2023-02-15 20:19:42,917 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 33 [2023-02-15 20:19:42,917 INFO L187 NwaCegarLoop]: Found error trace [2023-02-15 20:19:42,917 INFO L195 NwaCegarLoop]: trace histogram [3, 3, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-02-15 20:19:42,929 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Ended with exit code 0 [2023-02-15 20:19:43,122 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-15 20:19:43,122 INFO L420 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-02-15 20:19:43,122 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2023-02-15 20:19:43,122 INFO L85 PathProgramCache]: Analyzing trace with hash 492814709, now seen corresponding path program 2 times [2023-02-15 20:19:43,123 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-02-15 20:19:43,123 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [683449471] [2023-02-15 20:19:43,123 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-15 20:19:43,123 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-02-15 20:19:43,131 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-02-15 20:19:43,131 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [340115648] [2023-02-15 20:19:43,132 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2023-02-15 20:19:43,132 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-02-15 20:19:43,132 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-15 20:19:43,137 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-15 20:19:43,138 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-15 20:19:43,181 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2023-02-15 20:19:43,181 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-02-15 20:19:43,184 INFO L263 TraceCheckSpWp]: Trace formula consists of 125 conjuncts, 5 conjunts are in the unsatisfiable core [2023-02-15 20:19:43,193 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2023-02-15 20:19:43,220 INFO L134 CoverageAnalysis]: Checked inductivity of 17 backedges. 13 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2023-02-15 20:19:43,221 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2023-02-15 20:19:43,221 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-02-15 20:19:43,221 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [683449471] [2023-02-15 20:19:43,221 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-02-15 20:19:43,221 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [340115648] [2023-02-15 20:19:43,221 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [340115648] provided 1 perfect and 0 imperfect interpolant sequences [2023-02-15 20:19:43,221 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-02-15 20:19:43,221 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2023-02-15 20:19:43,221 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [773292709] [2023-02-15 20:19:43,221 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-02-15 20:19:43,221 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2023-02-15 20:19:43,221 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-02-15 20:19:43,222 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2023-02-15 20:19:43,222 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2023-02-15 20:19:43,222 INFO L87 Difference]: Start difference. First operand 144 states and 202 transitions. Second operand has 5 states, 5 states have (on average 4.8) internal successors, (24), 5 states have internal predecessors, (24), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2023-02-15 20:19:43,309 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-02-15 20:19:43,309 INFO L93 Difference]: Finished difference Result 183 states and 254 transitions. [2023-02-15 20:19:43,310 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2023-02-15 20:19:43,310 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 4.8) internal successors, (24), 5 states have internal predecessors, (24), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) Word has length 32 [2023-02-15 20:19:43,310 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-02-15 20:19:43,310 INFO L225 Difference]: With dead ends: 183 [2023-02-15 20:19:43,311 INFO L226 Difference]: Without dead ends: 127 [2023-02-15 20:19:43,313 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 34 GetRequests, 29 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-15 20:19:43,314 INFO L413 NwaCegarLoop]: 48 mSDtfsCounter, 19 mSDsluCounter, 71 mSDsCounter, 0 mSdLazyCounter, 82 mSolverCounterSat, 8 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 23 SdHoareTripleChecker+Valid, 119 SdHoareTripleChecker+Invalid, 90 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 8 IncrementalHoareTripleChecker+Valid, 82 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-02-15 20:19:43,315 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [23 Valid, 119 Invalid, 90 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [8 Valid, 82 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-02-15 20:19:43,315 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 127 states. [2023-02-15 20:19:43,327 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 127 to 119. [2023-02-15 20:19:43,328 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 119 states, 75 states have (on average 1.2133333333333334) internal successors, (91), 76 states have internal predecessors, (91), 35 states have call successors, (35), 8 states have call predecessors, (35), 8 states have return successors, (34), 34 states have call predecessors, (34), 34 states have call successors, (34) [2023-02-15 20:19:43,328 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 119 states to 119 states and 160 transitions. [2023-02-15 20:19:43,329 INFO L78 Accepts]: Start accepts. Automaton has 119 states and 160 transitions. Word has length 32 [2023-02-15 20:19:43,329 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-02-15 20:19:43,329 INFO L495 AbstractCegarLoop]: Abstraction has 119 states and 160 transitions. [2023-02-15 20:19:43,329 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 4.8) internal successors, (24), 5 states have internal predecessors, (24), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2023-02-15 20:19:43,329 INFO L276 IsEmpty]: Start isEmpty. Operand 119 states and 160 transitions. [2023-02-15 20:19:43,343 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 38 [2023-02-15 20:19:43,343 INFO L187 NwaCegarLoop]: Found error trace [2023-02-15 20:19:43,343 INFO L195 NwaCegarLoop]: trace histogram [4, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-02-15 20:19:43,350 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Forceful destruction successful, exit code 0 [2023-02-15 20:19:43,550 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-15 20:19:43,550 INFO L420 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-02-15 20:19:43,550 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2023-02-15 20:19:43,550 INFO L85 PathProgramCache]: Analyzing trace with hash -449167720, now seen corresponding path program 1 times [2023-02-15 20:19:43,550 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-02-15 20:19:43,550 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1504679803] [2023-02-15 20:19:43,550 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-15 20:19:43,551 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-02-15 20:19:43,556 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-02-15 20:19:43,557 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1427501385] [2023-02-15 20:19:43,557 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-15 20:19:43,557 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-02-15 20:19:43,557 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-15 20:19:43,560 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-15 20:19:43,579 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-15 20:19:43,640 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-02-15 20:19:43,641 INFO L263 TraceCheckSpWp]: Trace formula consists of 108 conjuncts, 15 conjunts are in the unsatisfiable core [2023-02-15 20:19:43,641 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2023-02-15 20:19:43,674 INFO L134 CoverageAnalysis]: Checked inductivity of 22 backedges. 11 proven. 1 refuted. 0 times theorem prover too weak. 10 trivial. 0 not checked. [2023-02-15 20:19:43,674 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2023-02-15 20:19:43,710 INFO L134 CoverageAnalysis]: Checked inductivity of 22 backedges. 6 proven. 0 refuted. 0 times theorem prover too weak. 16 trivial. 0 not checked. [2023-02-15 20:19:43,710 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-02-15 20:19:43,710 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1504679803] [2023-02-15 20:19:43,711 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-02-15 20:19:43,711 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1427501385] [2023-02-15 20:19:43,711 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1427501385] provided 1 perfect and 1 imperfect interpolant sequences [2023-02-15 20:19:43,711 INFO L184 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2023-02-15 20:19:43,711 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [7] total 9 [2023-02-15 20:19:43,711 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [89464468] [2023-02-15 20:19:43,711 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-02-15 20:19:43,711 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2023-02-15 20:19:43,711 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-02-15 20:19:43,711 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2023-02-15 20:19:43,712 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=18, Invalid=54, Unknown=0, NotChecked=0, Total=72 [2023-02-15 20:19:43,712 INFO L87 Difference]: Start difference. First operand 119 states and 160 transitions. Second operand has 5 states, 5 states have (on average 3.4) internal successors, (17), 4 states have internal predecessors, (17), 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-15 20:19:43,827 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-02-15 20:19:43,827 INFO L93 Difference]: Finished difference Result 125 states and 165 transitions. [2023-02-15 20:19:43,827 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2023-02-15 20:19:43,827 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.4) internal successors, (17), 4 states have internal predecessors, (17), 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 37 [2023-02-15 20:19:43,827 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-02-15 20:19:43,828 INFO L225 Difference]: With dead ends: 125 [2023-02-15 20:19:43,828 INFO L226 Difference]: Without dead ends: 123 [2023-02-15 20:19:43,828 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 73 GetRequests, 65 SyntacticMatches, 0 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=22, Invalid=68, Unknown=0, NotChecked=0, Total=90 [2023-02-15 20:19:43,828 INFO L413 NwaCegarLoop]: 33 mSDtfsCounter, 8 mSDsluCounter, 69 mSDsCounter, 0 mSdLazyCounter, 45 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 9 SdHoareTripleChecker+Valid, 102 SdHoareTripleChecker+Invalid, 47 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 45 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-02-15 20:19:43,829 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [9 Valid, 102 Invalid, 47 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 45 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-02-15 20:19:43,829 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 123 states. [2023-02-15 20:19:43,855 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 123 to 123. [2023-02-15 20:19:43,855 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 123 states, 78 states have (on average 1.205128205128205) internal successors, (94), 79 states have internal predecessors, (94), 35 states have call successors, (35), 9 states have call predecessors, (35), 9 states have return successors, (34), 34 states have call predecessors, (34), 34 states have call successors, (34) [2023-02-15 20:19:43,856 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 123 states to 123 states and 163 transitions. [2023-02-15 20:19:43,856 INFO L78 Accepts]: Start accepts. Automaton has 123 states and 163 transitions. Word has length 37 [2023-02-15 20:19:43,856 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-02-15 20:19:43,856 INFO L495 AbstractCegarLoop]: Abstraction has 123 states and 163 transitions. [2023-02-15 20:19:43,856 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.4) internal successors, (17), 4 states have internal predecessors, (17), 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-15 20:19:43,857 INFO L276 IsEmpty]: Start isEmpty. Operand 123 states and 163 transitions. [2023-02-15 20:19:43,857 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 50 [2023-02-15 20:19:43,857 INFO L187 NwaCegarLoop]: Found error trace [2023-02-15 20:19:43,857 INFO L195 NwaCegarLoop]: trace histogram [5, 4, 4, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-02-15 20:19:43,877 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-15 20:19:44,061 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-15 20:19:44,062 INFO L420 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-02-15 20:19:44,062 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2023-02-15 20:19:44,062 INFO L85 PathProgramCache]: Analyzing trace with hash 1289603446, now seen corresponding path program 1 times [2023-02-15 20:19:44,062 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-02-15 20:19:44,062 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1339931596] [2023-02-15 20:19:44,062 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-15 20:19:44,062 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-02-15 20:19:44,069 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-02-15 20:19:44,069 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [718036761] [2023-02-15 20:19:44,069 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-15 20:19:44,069 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-02-15 20:19:44,069 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-15 20:19:44,070 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-15 20:19:44,072 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-15 20:19:44,106 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-02-15 20:19:44,107 INFO L263 TraceCheckSpWp]: Trace formula consists of 141 conjuncts, 58 conjunts are in the unsatisfiable core [2023-02-15 20:19:44,109 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2023-02-15 20:19:44,511 INFO L134 CoverageAnalysis]: Checked inductivity of 40 backedges. 10 proven. 14 refuted. 0 times theorem prover too weak. 16 trivial. 0 not checked. [2023-02-15 20:19:44,511 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2023-02-15 20:19:45,361 INFO L134 CoverageAnalysis]: Checked inductivity of 40 backedges. 10 proven. 11 refuted. 0 times theorem prover too weak. 19 trivial. 0 not checked. [2023-02-15 20:19:45,362 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-02-15 20:19:45,362 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1339931596] [2023-02-15 20:19:45,362 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-02-15 20:19:45,362 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [718036761] [2023-02-15 20:19:45,362 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [718036761] provided 0 perfect and 2 imperfect interpolant sequences [2023-02-15 20:19:45,362 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-02-15 20:19:45,362 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 13] total 26 [2023-02-15 20:19:45,362 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [838548662] [2023-02-15 20:19:45,363 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-02-15 20:19:45,364 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 26 states [2023-02-15 20:19:45,364 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-02-15 20:19:45,364 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 26 interpolants. [2023-02-15 20:19:45,364 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=92, Invalid=558, Unknown=0, NotChecked=0, Total=650 [2023-02-15 20:19:45,365 INFO L87 Difference]: Start difference. First operand 123 states and 163 transitions. Second operand has 26 states, 24 states have (on average 1.9583333333333333) internal successors, (47), 23 states have internal predecessors, (47), 7 states have call successors, (13), 3 states have call predecessors, (13), 3 states have return successors, (12), 5 states have call predecessors, (12), 5 states have call successors, (12) [2023-02-15 20:19:53,960 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-02-15 20:19:53,961 INFO L93 Difference]: Finished difference Result 348 states and 494 transitions. [2023-02-15 20:19:53,961 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 36 states. [2023-02-15 20:19:53,962 INFO L78 Accepts]: Start accepts. Automaton has has 26 states, 24 states have (on average 1.9583333333333333) internal successors, (47), 23 states have internal predecessors, (47), 7 states have call successors, (13), 3 states have call predecessors, (13), 3 states have return successors, (12), 5 states have call predecessors, (12), 5 states have call successors, (12) Word has length 49 [2023-02-15 20:19:53,962 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-02-15 20:19:53,965 INFO L225 Difference]: With dead ends: 348 [2023-02-15 20:19:53,965 INFO L226 Difference]: Without dead ends: 270 [2023-02-15 20:19:53,966 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 124 GetRequests, 70 SyntacticMatches, 2 SemanticMatches, 52 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 659 ImplicationChecksByTransitivity, 5.0s TimeCoverageRelationStatistics Valid=497, Invalid=2365, Unknown=0, NotChecked=0, Total=2862 [2023-02-15 20:19:53,966 INFO L413 NwaCegarLoop]: 25 mSDtfsCounter, 190 mSDsluCounter, 183 mSDsCounter, 0 mSdLazyCounter, 1163 mSolverCounterSat, 361 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 4.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 196 SdHoareTripleChecker+Valid, 208 SdHoareTripleChecker+Invalid, 1524 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 361 IncrementalHoareTripleChecker+Valid, 1163 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 4.3s IncrementalHoareTripleChecker+Time [2023-02-15 20:19:53,967 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [196 Valid, 208 Invalid, 1524 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [361 Valid, 1163 Invalid, 0 Unknown, 0 Unchecked, 4.3s Time] [2023-02-15 20:19:53,967 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 270 states. [2023-02-15 20:19:54,014 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 270 to 217. [2023-02-15 20:19:54,015 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 217 states, 141 states have (on average 1.2127659574468086) internal successors, (171), 142 states have internal predecessors, (171), 63 states have call successors, (63), 12 states have call predecessors, (63), 12 states have return successors, (62), 62 states have call predecessors, (62), 62 states have call successors, (62) [2023-02-15 20:19:54,016 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 217 states to 217 states and 296 transitions. [2023-02-15 20:19:54,016 INFO L78 Accepts]: Start accepts. Automaton has 217 states and 296 transitions. Word has length 49 [2023-02-15 20:19:54,016 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-02-15 20:19:54,016 INFO L495 AbstractCegarLoop]: Abstraction has 217 states and 296 transitions. [2023-02-15 20:19:54,017 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 26 states, 24 states have (on average 1.9583333333333333) internal successors, (47), 23 states have internal predecessors, (47), 7 states have call successors, (13), 3 states have call predecessors, (13), 3 states have return successors, (12), 5 states have call predecessors, (12), 5 states have call successors, (12) [2023-02-15 20:19:54,017 INFO L276 IsEmpty]: Start isEmpty. Operand 217 states and 296 transitions. [2023-02-15 20:19:54,017 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 58 [2023-02-15 20:19:54,017 INFO L187 NwaCegarLoop]: Found error trace [2023-02-15 20:19:54,017 INFO L195 NwaCegarLoop]: trace histogram [5, 4, 4, 4, 3, 3, 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-15 20:19:54,025 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-15 20:19:54,222 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-15 20:19:54,222 INFO L420 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-02-15 20:19:54,222 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2023-02-15 20:19:54,222 INFO L85 PathProgramCache]: Analyzing trace with hash -70799180, now seen corresponding path program 1 times [2023-02-15 20:19:54,222 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-02-15 20:19:54,222 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [348398753] [2023-02-15 20:19:54,222 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-15 20:19:54,223 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-02-15 20:19:54,229 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-02-15 20:19:54,229 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1601193295] [2023-02-15 20:19:54,229 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-15 20:19:54,229 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-02-15 20:19:54,229 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-15 20:19:54,233 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-15 20:19:54,235 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-15 20:19:54,282 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-02-15 20:19:54,283 INFO L263 TraceCheckSpWp]: Trace formula consists of 173 conjuncts, 32 conjunts are in the unsatisfiable core [2023-02-15 20:19:54,285 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2023-02-15 20:19:54,795 INFO L134 CoverageAnalysis]: Checked inductivity of 57 backedges. 10 proven. 31 refuted. 0 times theorem prover too weak. 16 trivial. 0 not checked. [2023-02-15 20:19:54,795 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2023-02-15 20:19:55,152 INFO L134 CoverageAnalysis]: Checked inductivity of 57 backedges. 25 proven. 9 refuted. 0 times theorem prover too weak. 23 trivial. 0 not checked. [2023-02-15 20:19:55,153 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-02-15 20:19:55,153 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [348398753] [2023-02-15 20:19:55,153 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-02-15 20:19:55,153 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1601193295] [2023-02-15 20:19:55,153 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1601193295] provided 0 perfect and 2 imperfect interpolant sequences [2023-02-15 20:19:55,153 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-02-15 20:19:55,153 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [18, 8] total 23 [2023-02-15 20:19:55,153 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [513851658] [2023-02-15 20:19:55,153 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-02-15 20:19:55,153 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 23 states [2023-02-15 20:19:55,153 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-02-15 20:19:55,154 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 23 interpolants. [2023-02-15 20:19:55,154 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=67, Invalid=439, Unknown=0, NotChecked=0, Total=506 [2023-02-15 20:19:55,154 INFO L87 Difference]: Start difference. First operand 217 states and 296 transitions. Second operand has 23 states, 23 states have (on average 2.608695652173913) internal successors, (60), 19 states have internal predecessors, (60), 7 states have call successors, (13), 3 states have call predecessors, (13), 3 states have return successors, (12), 5 states have call predecessors, (12), 5 states have call successors, (12) [2023-02-15 20:20:35,256 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-02-15 20:20:35,256 INFO L93 Difference]: Finished difference Result 325 states and 455 transitions. [2023-02-15 20:20:35,256 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 34 states. [2023-02-15 20:20:35,256 INFO L78 Accepts]: Start accepts. Automaton has has 23 states, 23 states have (on average 2.608695652173913) internal successors, (60), 19 states have internal predecessors, (60), 7 states have call successors, (13), 3 states have call predecessors, (13), 3 states have return successors, (12), 5 states have call predecessors, (12), 5 states have call successors, (12) Word has length 57 [2023-02-15 20:20:35,257 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-02-15 20:20:35,260 INFO L225 Difference]: With dead ends: 325 [2023-02-15 20:20:35,260 INFO L226 Difference]: Without dead ends: 323 [2023-02-15 20:20:35,261 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 152 GetRequests, 102 SyntacticMatches, 1 SemanticMatches, 49 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 535 ImplicationChecksByTransitivity, 25.5s TimeCoverageRelationStatistics Valid=424, Invalid=2126, Unknown=0, NotChecked=0, Total=2550 [2023-02-15 20:20:35,261 INFO L413 NwaCegarLoop]: 52 mSDtfsCounter, 152 mSDsluCounter, 296 mSDsCounter, 0 mSdLazyCounter, 1360 mSolverCounterSat, 221 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 14.8s Time, 0 mProtectedPredicate, 0 mProtectedAction, 152 SdHoareTripleChecker+Valid, 348 SdHoareTripleChecker+Invalid, 1581 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 221 IncrementalHoareTripleChecker+Valid, 1360 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 15.0s IncrementalHoareTripleChecker+Time [2023-02-15 20:20:35,262 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [152 Valid, 348 Invalid, 1581 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [221 Valid, 1360 Invalid, 0 Unknown, 0 Unchecked, 15.0s Time] [2023-02-15 20:20:35,262 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 323 states. [2023-02-15 20:20:35,323 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 323 to 232. [2023-02-15 20:20:35,324 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 232 states, 151 states have (on average 1.1986754966887416) internal successors, (181), 153 states have internal predecessors, (181), 65 states have call successors, (65), 15 states have call predecessors, (65), 15 states have return successors, (64), 63 states have call predecessors, (64), 64 states have call successors, (64) [2023-02-15 20:20:35,326 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 232 states to 232 states and 310 transitions. [2023-02-15 20:20:35,326 INFO L78 Accepts]: Start accepts. Automaton has 232 states and 310 transitions. Word has length 57 [2023-02-15 20:20:35,326 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-02-15 20:20:35,326 INFO L495 AbstractCegarLoop]: Abstraction has 232 states and 310 transitions. [2023-02-15 20:20:35,326 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 23 states, 23 states have (on average 2.608695652173913) internal successors, (60), 19 states have internal predecessors, (60), 7 states have call successors, (13), 3 states have call predecessors, (13), 3 states have return successors, (12), 5 states have call predecessors, (12), 5 states have call successors, (12) [2023-02-15 20:20:35,327 INFO L276 IsEmpty]: Start isEmpty. Operand 232 states and 310 transitions. [2023-02-15 20:20:35,328 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 63 [2023-02-15 20:20:35,328 INFO L187 NwaCegarLoop]: Found error trace [2023-02-15 20:20:35,328 INFO L195 NwaCegarLoop]: trace histogram [7, 6, 6, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-02-15 20:20:35,343 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-15 20:20:35,533 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-15 20:20:35,533 INFO L420 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-02-15 20:20:35,533 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2023-02-15 20:20:35,534 INFO L85 PathProgramCache]: Analyzing trace with hash 513336511, now seen corresponding path program 2 times [2023-02-15 20:20:35,534 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-02-15 20:20:35,534 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1805143715] [2023-02-15 20:20:35,534 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-15 20:20:35,534 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-02-15 20:20:35,553 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-02-15 20:20:35,553 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1541532712] [2023-02-15 20:20:35,553 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2023-02-15 20:20:35,554 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-02-15 20:20:35,567 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-15 20:20:35,568 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-15 20:20:35,572 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-15 20:20:35,607 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2023-02-15 20:20:35,607 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-02-15 20:20:35,608 INFO L263 TraceCheckSpWp]: Trace formula consists of 169 conjuncts, 4 conjunts are in the unsatisfiable core [2023-02-15 20:20:35,609 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2023-02-15 20:20:35,628 INFO L134 CoverageAnalysis]: Checked inductivity of 88 backedges. 48 proven. 0 refuted. 0 times theorem prover too weak. 40 trivial. 0 not checked. [2023-02-15 20:20:35,628 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2023-02-15 20:20:35,628 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-02-15 20:20:35,628 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1805143715] [2023-02-15 20:20:35,628 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-02-15 20:20:35,629 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1541532712] [2023-02-15 20:20:35,629 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1541532712] provided 1 perfect and 0 imperfect interpolant sequences [2023-02-15 20:20:35,629 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-02-15 20:20:35,629 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2023-02-15 20:20:35,629 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1546603506] [2023-02-15 20:20:35,629 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-02-15 20:20:35,629 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2023-02-15 20:20:35,630 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-02-15 20:20:35,630 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2023-02-15 20:20:35,630 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2023-02-15 20:20:35,630 INFO L87 Difference]: Start difference. First operand 232 states and 310 transitions. Second operand has 5 states, 5 states have (on average 5.2) internal successors, (26), 5 states have internal predecessors, (26), 3 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (8), 3 states have call predecessors, (8), 3 states have call successors, (8) [2023-02-15 20:20:35,734 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-02-15 20:20:35,734 INFO L93 Difference]: Finished difference Result 422 states and 580 transitions. [2023-02-15 20:20:35,734 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2023-02-15 20:20:35,734 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 5.2) internal successors, (26), 5 states have internal predecessors, (26), 3 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (8), 3 states have call predecessors, (8), 3 states have call successors, (8) Word has length 62 [2023-02-15 20:20:35,747 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-02-15 20:20:35,748 INFO L225 Difference]: With dead ends: 422 [2023-02-15 20:20:35,748 INFO L226 Difference]: Without dead ends: 283 [2023-02-15 20:20:35,749 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 63 GetRequests, 59 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=12, Invalid=18, Unknown=0, NotChecked=0, Total=30 [2023-02-15 20:20:35,749 INFO L413 NwaCegarLoop]: 36 mSDtfsCounter, 3 mSDsluCounter, 67 mSDsCounter, 0 mSdLazyCounter, 55 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 3 SdHoareTripleChecker+Valid, 103 SdHoareTripleChecker+Invalid, 56 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 55 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-02-15 20:20:35,749 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [3 Valid, 103 Invalid, 56 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 55 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-02-15 20:20:35,750 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 283 states. [2023-02-15 20:20:35,818 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 283 to 268. [2023-02-15 20:20:35,819 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 268 states, 165 states have (on average 1.1939393939393939) internal successors, (197), 166 states have internal predecessors, (197), 87 states have call successors, (87), 15 states have call predecessors, (87), 15 states have return successors, (86), 86 states have call predecessors, (86), 86 states have call successors, (86) [2023-02-15 20:20:35,820 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 268 states to 268 states and 370 transitions. [2023-02-15 20:20:35,820 INFO L78 Accepts]: Start accepts. Automaton has 268 states and 370 transitions. Word has length 62 [2023-02-15 20:20:35,820 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-02-15 20:20:35,821 INFO L495 AbstractCegarLoop]: Abstraction has 268 states and 370 transitions. [2023-02-15 20:20:35,821 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 5.2) internal successors, (26), 5 states have internal predecessors, (26), 3 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (8), 3 states have call predecessors, (8), 3 states have call successors, (8) [2023-02-15 20:20:35,821 INFO L276 IsEmpty]: Start isEmpty. Operand 268 states and 370 transitions. [2023-02-15 20:20:35,821 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 63 [2023-02-15 20:20:35,821 INFO L187 NwaCegarLoop]: Found error trace [2023-02-15 20:20:35,822 INFO L195 NwaCegarLoop]: trace histogram [6, 5, 5, 4, 3, 3, 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-15 20:20:35,828 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Ended with exit code 0 [2023-02-15 20:20:36,026 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-15 20:20:36,026 INFO L420 AbstractCegarLoop]: === Iteration 14 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-02-15 20:20:36,027 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2023-02-15 20:20:36,027 INFO L85 PathProgramCache]: Analyzing trace with hash -420355271, now seen corresponding path program 3 times [2023-02-15 20:20:36,027 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-02-15 20:20:36,027 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [324588645] [2023-02-15 20:20:36,027 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-15 20:20:36,027 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-02-15 20:20:36,033 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-02-15 20:20:36,033 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1076629393] [2023-02-15 20:20:36,033 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2023-02-15 20:20:36,033 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-02-15 20:20:36,033 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-15 20:20:36,034 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-15 20:20:36,036 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-15 20:20:36,086 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2023-02-15 20:20:36,086 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-02-15 20:20:36,087 INFO L263 TraceCheckSpWp]: Trace formula consists of 155 conjuncts, 65 conjunts are in the unsatisfiable core [2023-02-15 20:20:36,089 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2023-02-15 20:20:36,534 INFO L134 CoverageAnalysis]: Checked inductivity of 76 backedges. 21 proven. 23 refuted. 0 times theorem prover too weak. 32 trivial. 0 not checked. [2023-02-15 20:20:36,534 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2023-02-15 20:20:37,385 INFO L134 CoverageAnalysis]: Checked inductivity of 76 backedges. 14 proven. 18 refuted. 0 times theorem prover too weak. 44 trivial. 0 not checked. [2023-02-15 20:20:37,385 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-02-15 20:20:37,386 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [324588645] [2023-02-15 20:20:37,386 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-02-15 20:20:37,386 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1076629393] [2023-02-15 20:20:37,386 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1076629393] provided 0 perfect and 2 imperfect interpolant sequences [2023-02-15 20:20:37,386 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-02-15 20:20:37,386 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 13] total 26 [2023-02-15 20:20:37,386 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1572892820] [2023-02-15 20:20:37,386 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-02-15 20:20:37,387 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 26 states [2023-02-15 20:20:37,387 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-02-15 20:20:37,388 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 26 interpolants. [2023-02-15 20:20:37,388 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=99, Invalid=551, Unknown=0, NotChecked=0, Total=650 [2023-02-15 20:20:37,388 INFO L87 Difference]: Start difference. First operand 268 states and 370 transitions. Second operand has 26 states, 25 states have (on average 2.32) internal successors, (58), 24 states have internal predecessors, (58), 6 states have call successors, (14), 3 states have call predecessors, (14), 2 states have return successors, (12), 5 states have call predecessors, (12), 5 states have call successors, (12) [2023-02-15 20:20:48,175 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.44s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-02-15 20:20:49,119 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-02-15 20:20:49,120 INFO L93 Difference]: Finished difference Result 388 states and 527 transitions. [2023-02-15 20:20:49,120 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 36 states. [2023-02-15 20:20:49,120 INFO L78 Accepts]: Start accepts. Automaton has has 26 states, 25 states have (on average 2.32) internal successors, (58), 24 states have internal predecessors, (58), 6 states have call successors, (14), 3 states have call predecessors, (14), 2 states have return successors, (12), 5 states have call predecessors, (12), 5 states have call successors, (12) Word has length 62 [2023-02-15 20:20:49,121 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-02-15 20:20:49,122 INFO L225 Difference]: With dead ends: 388 [2023-02-15 20:20:49,122 INFO L226 Difference]: Without dead ends: 386 [2023-02-15 20:20:49,123 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 152 GetRequests, 98 SyntacticMatches, 0 SemanticMatches, 54 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 678 ImplicationChecksByTransitivity, 5.2s TimeCoverageRelationStatistics Valid=610, Invalid=2470, Unknown=0, NotChecked=0, Total=3080 [2023-02-15 20:20:49,123 INFO L413 NwaCegarLoop]: 35 mSDtfsCounter, 182 mSDsluCounter, 271 mSDsCounter, 0 mSdLazyCounter, 1343 mSolverCounterSat, 329 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 7.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 182 SdHoareTripleChecker+Valid, 306 SdHoareTripleChecker+Invalid, 1672 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 329 IncrementalHoareTripleChecker+Valid, 1343 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 7.2s IncrementalHoareTripleChecker+Time [2023-02-15 20:20:49,123 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [182 Valid, 306 Invalid, 1672 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [329 Valid, 1343 Invalid, 0 Unknown, 0 Unchecked, 7.2s Time] [2023-02-15 20:20:49,127 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 386 states. [2023-02-15 20:20:49,236 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 386 to 316. [2023-02-15 20:20:49,237 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 316 states, 200 states have (on average 1.175) internal successors, (235), 201 states have internal predecessors, (235), 95 states have call successors, (95), 20 states have call predecessors, (95), 20 states have return successors, (94), 94 states have call predecessors, (94), 94 states have call successors, (94) [2023-02-15 20:20:49,238 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 316 states to 316 states and 424 transitions. [2023-02-15 20:20:49,238 INFO L78 Accepts]: Start accepts. Automaton has 316 states and 424 transitions. Word has length 62 [2023-02-15 20:20:49,238 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-02-15 20:20:49,238 INFO L495 AbstractCegarLoop]: Abstraction has 316 states and 424 transitions. [2023-02-15 20:20:49,238 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 26 states, 25 states have (on average 2.32) internal successors, (58), 24 states have internal predecessors, (58), 6 states have call successors, (14), 3 states have call predecessors, (14), 2 states have return successors, (12), 5 states have call predecessors, (12), 5 states have call successors, (12) [2023-02-15 20:20:49,239 INFO L276 IsEmpty]: Start isEmpty. Operand 316 states and 424 transitions. [2023-02-15 20:20:49,239 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 77 [2023-02-15 20:20:49,239 INFO L187 NwaCegarLoop]: Found error trace [2023-02-15 20:20:49,239 INFO L195 NwaCegarLoop]: trace histogram [9, 8, 8, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-02-15 20:20:49,244 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-15 20:20:49,444 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-15 20:20:49,444 INFO L420 AbstractCegarLoop]: === Iteration 15 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-02-15 20:20:49,445 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2023-02-15 20:20:49,445 INFO L85 PathProgramCache]: Analyzing trace with hash -819166674, now seen corresponding path program 1 times [2023-02-15 20:20:49,445 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-02-15 20:20:49,445 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [169008527] [2023-02-15 20:20:49,445 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-15 20:20:49,445 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-02-15 20:20:49,459 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-02-15 20:20:49,459 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1134738309] [2023-02-15 20:20:49,459 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-15 20:20:49,459 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-02-15 20:20:49,459 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-15 20:20:49,485 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-15 20:20:49,487 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-15 20:20:49,527 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-02-15 20:20:49,528 INFO L263 TraceCheckSpWp]: Trace formula consists of 205 conjuncts, 80 conjunts are in the unsatisfiable core [2023-02-15 20:20:49,530 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2023-02-15 20:20:50,172 INFO L134 CoverageAnalysis]: Checked inductivity of 151 backedges. 30 proven. 29 refuted. 0 times theorem prover too weak. 92 trivial. 0 not checked. [2023-02-15 20:20:50,173 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2023-02-15 20:20:57,723 INFO L134 CoverageAnalysis]: Checked inductivity of 151 backedges. 30 proven. 26 refuted. 0 times theorem prover too weak. 95 trivial. 0 not checked. [2023-02-15 20:20:57,723 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-02-15 20:20:57,723 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [169008527] [2023-02-15 20:20:57,723 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-02-15 20:20:57,723 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1134738309] [2023-02-15 20:20:57,724 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1134738309] provided 0 perfect and 2 imperfect interpolant sequences [2023-02-15 20:20:57,724 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-02-15 20:20:57,724 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [20, 16] total 33 [2023-02-15 20:20:57,724 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [625067079] [2023-02-15 20:20:57,724 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-02-15 20:20:57,724 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 33 states [2023-02-15 20:20:57,724 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-02-15 20:20:57,725 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 33 interpolants. [2023-02-15 20:20:57,725 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=151, Invalid=905, Unknown=0, NotChecked=0, Total=1056 [2023-02-15 20:20:57,725 INFO L87 Difference]: Start difference. First operand 316 states and 424 transitions. Second operand has 33 states, 31 states have (on average 1.967741935483871) internal successors, (61), 31 states have internal predecessors, (61), 9 states have call successors, (21), 3 states have call predecessors, (21), 3 states have return successors, (20), 7 states have call predecessors, (20), 7 states have call successors, (20) [2023-02-15 20:21:10,012 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-15 20:21:22,030 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-15 20:21:23,592 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.56s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-02-15 20:21:25,142 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.55s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-02-15 20:21:38,375 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-02-15 20:21:38,376 INFO L93 Difference]: Finished difference Result 503 states and 694 transitions. [2023-02-15 20:21:38,376 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 66 states. [2023-02-15 20:21:38,376 INFO L78 Accepts]: Start accepts. Automaton has has 33 states, 31 states have (on average 1.967741935483871) internal successors, (61), 31 states have internal predecessors, (61), 9 states have call successors, (21), 3 states have call predecessors, (21), 3 states have return successors, (20), 7 states have call predecessors, (20), 7 states have call successors, (20) Word has length 76 [2023-02-15 20:21:38,376 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-02-15 20:21:38,378 INFO L225 Difference]: With dead ends: 503 [2023-02-15 20:21:38,378 INFO L226 Difference]: Without dead ends: 499 [2023-02-15 20:21:38,380 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 209 GetRequests, 117 SyntacticMatches, 2 SemanticMatches, 90 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2362 ImplicationChecksByTransitivity, 22.5s TimeCoverageRelationStatistics Valid=1499, Invalid=6873, Unknown=0, NotChecked=0, Total=8372 [2023-02-15 20:21:38,380 INFO L413 NwaCegarLoop]: 50 mSDtfsCounter, 318 mSDsluCounter, 398 mSDsCounter, 0 mSdLazyCounter, 2620 mSolverCounterSat, 505 mSolverCounterUnsat, 2 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 20.6s Time, 0 mProtectedPredicate, 0 mProtectedAction, 318 SdHoareTripleChecker+Valid, 448 SdHoareTripleChecker+Invalid, 3127 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 505 IncrementalHoareTripleChecker+Valid, 2620 IncrementalHoareTripleChecker+Invalid, 2 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 20.8s IncrementalHoareTripleChecker+Time [2023-02-15 20:21:38,380 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [318 Valid, 448 Invalid, 3127 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [505 Valid, 2620 Invalid, 2 Unknown, 0 Unchecked, 20.8s Time] [2023-02-15 20:21:38,381 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 499 states. [2023-02-15 20:21:38,664 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 499 to 468. [2023-02-15 20:21:38,665 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 468 states, 295 states have (on average 1.193220338983051) internal successors, (352), 296 states have internal predecessors, (352), 147 states have call successors, (147), 25 states have call predecessors, (147), 25 states have return successors, (146), 146 states have call predecessors, (146), 146 states have call successors, (146) [2023-02-15 20:21:38,667 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 468 states to 468 states and 645 transitions. [2023-02-15 20:21:38,667 INFO L78 Accepts]: Start accepts. Automaton has 468 states and 645 transitions. Word has length 76 [2023-02-15 20:21:38,667 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-02-15 20:21:38,667 INFO L495 AbstractCegarLoop]: Abstraction has 468 states and 645 transitions. [2023-02-15 20:21:38,668 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 33 states, 31 states have (on average 1.967741935483871) internal successors, (61), 31 states have internal predecessors, (61), 9 states have call successors, (21), 3 states have call predecessors, (21), 3 states have return successors, (20), 7 states have call predecessors, (20), 7 states have call successors, (20) [2023-02-15 20:21:38,668 INFO L276 IsEmpty]: Start isEmpty. Operand 468 states and 645 transitions. [2023-02-15 20:21:38,668 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 80 [2023-02-15 20:21:38,668 INFO L187 NwaCegarLoop]: Found error trace [2023-02-15 20:21:38,668 INFO L195 NwaCegarLoop]: trace histogram [11, 10, 10, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-02-15 20:21:38,675 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Ended with exit code 0 [2023-02-15 20:21:38,872 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-15 20:21:38,873 INFO L420 AbstractCegarLoop]: === Iteration 16 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-02-15 20:21:38,873 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2023-02-15 20:21:38,873 INFO L85 PathProgramCache]: Analyzing trace with hash 685229769, now seen corresponding path program 1 times [2023-02-15 20:21:38,873 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-02-15 20:21:38,874 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [466091990] [2023-02-15 20:21:38,874 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-15 20:21:38,874 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-02-15 20:21:38,879 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-02-15 20:21:38,879 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [423879226] [2023-02-15 20:21:38,879 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-15 20:21:38,879 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-02-15 20:21:38,879 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-15 20:21:38,880 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-15 20:21:38,882 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-15 20:21:38,922 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-02-15 20:21:38,923 INFO L263 TraceCheckSpWp]: Trace formula consists of 189 conjuncts, 31 conjunts are in the unsatisfiable core [2023-02-15 20:21:38,924 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2023-02-15 20:21:39,114 INFO L134 CoverageAnalysis]: Checked inductivity of 220 backedges. 20 proven. 19 refuted. 0 times theorem prover too weak. 181 trivial. 0 not checked. [2023-02-15 20:21:39,114 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2023-02-15 20:21:39,917 INFO L134 CoverageAnalysis]: Checked inductivity of 220 backedges. 22 proven. 14 refuted. 0 times theorem prover too weak. 184 trivial. 0 not checked. [2023-02-15 20:21:39,918 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-02-15 20:21:39,918 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [466091990] [2023-02-15 20:21:39,918 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-02-15 20:21:39,918 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [423879226] [2023-02-15 20:21:39,918 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [423879226] provided 0 perfect and 2 imperfect interpolant sequences [2023-02-15 20:21:39,918 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-02-15 20:21:39,918 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 10] total 21 [2023-02-15 20:21:39,919 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [657351100] [2023-02-15 20:21:39,919 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-02-15 20:21:39,919 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 21 states [2023-02-15 20:21:39,919 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-02-15 20:21:39,919 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2023-02-15 20:21:39,920 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=81, Invalid=339, Unknown=0, NotChecked=0, Total=420 [2023-02-15 20:21:39,920 INFO L87 Difference]: Start difference. First operand 468 states and 645 transitions. Second operand has 21 states, 21 states have (on average 1.9523809523809523) internal successors, (41), 18 states have internal predecessors, (41), 8 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-15 20:21:42,270 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-02-15 20:21:42,271 INFO L93 Difference]: Finished difference Result 921 states and 1380 transitions. [2023-02-15 20:21:42,271 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 28 states. [2023-02-15 20:21:42,271 INFO L78 Accepts]: Start accepts. Automaton has has 21 states, 21 states have (on average 1.9523809523809523) internal successors, (41), 18 states have internal predecessors, (41), 8 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 79 [2023-02-15 20:21:42,271 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-02-15 20:21:42,275 INFO L225 Difference]: With dead ends: 921 [2023-02-15 20:21:42,275 INFO L226 Difference]: Without dead ends: 919 [2023-02-15 20:21:42,275 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 179 GetRequests, 138 SyntacticMatches, 0 SemanticMatches, 41 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 403 ImplicationChecksByTransitivity, 1.2s TimeCoverageRelationStatistics Valid=392, Invalid=1414, Unknown=0, NotChecked=0, Total=1806 [2023-02-15 20:21:42,276 INFO L413 NwaCegarLoop]: 73 mSDtfsCounter, 135 mSDsluCounter, 432 mSDsCounter, 0 mSdLazyCounter, 701 mSolverCounterSat, 157 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.6s Time, 0 mProtectedPredicate, 0 mProtectedAction, 139 SdHoareTripleChecker+Valid, 505 SdHoareTripleChecker+Invalid, 858 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 157 IncrementalHoareTripleChecker+Valid, 701 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.7s IncrementalHoareTripleChecker+Time [2023-02-15 20:21:42,276 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [139 Valid, 505 Invalid, 858 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [157 Valid, 701 Invalid, 0 Unknown, 0 Unchecked, 0.7s Time] [2023-02-15 20:21:42,277 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 919 states. [2023-02-15 20:21:42,991 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 919 to 838. [2023-02-15 20:21:42,993 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 838 states, 445 states have (on average 1.2719101123595506) internal successors, (566), 446 states have internal predecessors, (566), 363 states have call successors, (363), 29 states have call predecessors, (363), 29 states have return successors, (362), 362 states have call predecessors, (362), 362 states have call successors, (362) [2023-02-15 20:21:43,007 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 838 states to 838 states and 1291 transitions. [2023-02-15 20:21:43,007 INFO L78 Accepts]: Start accepts. Automaton has 838 states and 1291 transitions. Word has length 79 [2023-02-15 20:21:43,008 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-02-15 20:21:43,008 INFO L495 AbstractCegarLoop]: Abstraction has 838 states and 1291 transitions. [2023-02-15 20:21:43,008 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 21 states, 21 states have (on average 1.9523809523809523) internal successors, (41), 18 states have internal predecessors, (41), 8 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-15 20:21:43,008 INFO L276 IsEmpty]: Start isEmpty. Operand 838 states and 1291 transitions. [2023-02-15 20:21:43,009 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 85 [2023-02-15 20:21:43,009 INFO L187 NwaCegarLoop]: Found error trace [2023-02-15 20:21:43,009 INFO L195 NwaCegarLoop]: trace histogram [9, 8, 8, 5, 4, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-02-15 20:21:43,029 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-15 20:21:43,214 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-15 20:21:43,214 INFO L420 AbstractCegarLoop]: === Iteration 17 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-02-15 20:21:43,214 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2023-02-15 20:21:43,214 INFO L85 PathProgramCache]: Analyzing trace with hash -1959088841, now seen corresponding path program 2 times [2023-02-15 20:21:43,214 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-02-15 20:21:43,215 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1045789858] [2023-02-15 20:21:43,215 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-15 20:21:43,215 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-02-15 20:21:43,232 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-02-15 20:21:43,232 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [106682592] [2023-02-15 20:21:43,233 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2023-02-15 20:21:43,233 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-02-15 20:21:43,233 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-15 20:21:43,250 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-15 20:21:43,257 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-15 20:21:43,298 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2023-02-15 20:21:43,299 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-02-15 20:21:43,299 INFO L263 TraceCheckSpWp]: Trace formula consists of 233 conjuncts, 10 conjunts are in the unsatisfiable core [2023-02-15 20:21:43,301 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2023-02-15 20:21:43,365 INFO L134 CoverageAnalysis]: Checked inductivity of 174 backedges. 38 proven. 16 refuted. 0 times theorem prover too weak. 120 trivial. 0 not checked. [2023-02-15 20:21:43,365 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2023-02-15 20:21:43,436 INFO L134 CoverageAnalysis]: Checked inductivity of 174 backedges. 38 proven. 16 refuted. 0 times theorem prover too weak. 120 trivial. 0 not checked. [2023-02-15 20:21:43,437 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-02-15 20:21:43,437 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1045789858] [2023-02-15 20:21:43,437 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-02-15 20:21:43,437 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [106682592] [2023-02-15 20:21:43,437 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [106682592] provided 0 perfect and 2 imperfect interpolant sequences [2023-02-15 20:21:43,437 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-02-15 20:21:43,437 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10] total 11 [2023-02-15 20:21:43,437 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1404120545] [2023-02-15 20:21:43,437 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-02-15 20:21:43,438 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 11 states [2023-02-15 20:21:43,438 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-02-15 20:21:43,438 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2023-02-15 20:21:43,438 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=21, Invalid=89, Unknown=0, NotChecked=0, Total=110 [2023-02-15 20:21:43,439 INFO L87 Difference]: Start difference. First operand 838 states and 1291 transitions. Second operand has 11 states, 11 states have (on average 3.4545454545454546) internal successors, (38), 11 states have internal predecessors, (38), 4 states have call successors, (11), 2 states have call predecessors, (11), 1 states have return successors, (10), 3 states have call predecessors, (10), 3 states have call successors, (10) [2023-02-15 20:21:44,737 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-02-15 20:21:44,737 INFO L93 Difference]: Finished difference Result 1001 states and 1539 transitions. [2023-02-15 20:21:44,738 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 24 states. [2023-02-15 20:21:44,738 INFO L78 Accepts]: Start accepts. Automaton has has 11 states, 11 states have (on average 3.4545454545454546) internal successors, (38), 11 states have internal predecessors, (38), 4 states have call successors, (11), 2 states have call predecessors, (11), 1 states have return successors, (10), 3 states have call predecessors, (10), 3 states have call successors, (10) Word has length 84 [2023-02-15 20:21:44,738 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-02-15 20:21:44,741 INFO L225 Difference]: With dead ends: 1001 [2023-02-15 20:21:44,741 INFO L226 Difference]: Without dead ends: 994 [2023-02-15 20:21:44,742 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 191 GetRequests, 157 SyntacticMatches, 7 SemanticMatches, 27 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 151 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=189, Invalid=623, Unknown=0, NotChecked=0, Total=812 [2023-02-15 20:21:44,742 INFO L413 NwaCegarLoop]: 82 mSDtfsCounter, 81 mSDsluCounter, 234 mSDsCounter, 0 mSdLazyCounter, 455 mSolverCounterSat, 86 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 85 SdHoareTripleChecker+Valid, 316 SdHoareTripleChecker+Invalid, 541 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 86 IncrementalHoareTripleChecker+Valid, 455 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2023-02-15 20:21:44,742 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [85 Valid, 316 Invalid, 541 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [86 Valid, 455 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2023-02-15 20:21:44,743 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 994 states. [2023-02-15 20:21:45,395 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 994 to 801. [2023-02-15 20:21:45,396 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 801 states, 416 states have (on average 1.28125) internal successors, (533), 417 states have internal predecessors, (533), 355 states have call successors, (355), 29 states have call predecessors, (355), 29 states have return successors, (354), 354 states have call predecessors, (354), 354 states have call successors, (354) [2023-02-15 20:21:45,399 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 801 states to 801 states and 1242 transitions. [2023-02-15 20:21:45,399 INFO L78 Accepts]: Start accepts. Automaton has 801 states and 1242 transitions. Word has length 84 [2023-02-15 20:21:45,399 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-02-15 20:21:45,399 INFO L495 AbstractCegarLoop]: Abstraction has 801 states and 1242 transitions. [2023-02-15 20:21:45,399 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 11 states, 11 states have (on average 3.4545454545454546) internal successors, (38), 11 states have internal predecessors, (38), 4 states have call successors, (11), 2 states have call predecessors, (11), 1 states have return successors, (10), 3 states have call predecessors, (10), 3 states have call successors, (10) [2023-02-15 20:21:45,399 INFO L276 IsEmpty]: Start isEmpty. Operand 801 states and 1242 transitions. [2023-02-15 20:21:45,400 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 97 [2023-02-15 20:21:45,400 INFO L187 NwaCegarLoop]: Found error trace [2023-02-15 20:21:45,401 INFO L195 NwaCegarLoop]: trace histogram [13, 12, 12, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-02-15 20:21:45,417 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-15 20:21:45,605 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-15 20:21:45,605 INFO L420 AbstractCegarLoop]: === Iteration 18 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-02-15 20:21:45,606 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2023-02-15 20:21:45,606 INFO L85 PathProgramCache]: Analyzing trace with hash 1810606754, now seen corresponding path program 2 times [2023-02-15 20:21:45,606 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-02-15 20:21:45,606 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2142974006] [2023-02-15 20:21:45,606 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-15 20:21:45,606 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-02-15 20:21:45,617 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-02-15 20:21:45,617 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [702450694] [2023-02-15 20:21:45,617 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2023-02-15 20:21:45,617 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-02-15 20:21:45,617 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-15 20:21:45,640 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-15 20:21:45,652 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-15 20:21:45,701 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2023-02-15 20:21:45,701 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-02-15 20:21:45,702 INFO L263 TraceCheckSpWp]: Trace formula consists of 231 conjuncts, 70 conjunts are in the unsatisfiable core [2023-02-15 20:21:45,704 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2023-02-15 20:21:46,390 INFO L134 CoverageAnalysis]: Checked inductivity of 319 backedges. 29 proven. 58 refuted. 0 times theorem prover too weak. 232 trivial. 0 not checked. [2023-02-15 20:21:46,391 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2023-02-15 20:21:53,400 INFO L134 CoverageAnalysis]: Checked inductivity of 319 backedges. 26 proven. 58 refuted. 0 times theorem prover too weak. 235 trivial. 0 not checked. [2023-02-15 20:21:53,400 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-02-15 20:21:53,400 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2142974006] [2023-02-15 20:21:53,401 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-02-15 20:21:53,401 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [702450694] [2023-02-15 20:21:53,401 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [702450694] provided 0 perfect and 2 imperfect interpolant sequences [2023-02-15 20:21:53,401 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-02-15 20:21:53,401 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [19, 16] total 32 [2023-02-15 20:21:53,401 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [613903610] [2023-02-15 20:21:53,401 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-02-15 20:21:53,402 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 32 states [2023-02-15 20:21:53,402 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-02-15 20:21:53,402 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 32 interpolants. [2023-02-15 20:21:53,403 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=146, Invalid=846, Unknown=0, NotChecked=0, Total=992 [2023-02-15 20:21:53,403 INFO L87 Difference]: Start difference. First operand 801 states and 1242 transitions. Second operand has 32 states, 30 states have (on average 2.033333333333333) internal successors, (61), 29 states have internal predecessors, (61), 10 states have call successors, (28), 3 states have call predecessors, (28), 3 states have return successors, (27), 9 states have call predecessors, (27), 8 states have call successors, (27) [2023-02-15 20:22:51,447 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-15 20:22:57,871 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-02-15 20:22:57,871 INFO L93 Difference]: Finished difference Result 1373 states and 2115 transitions. [2023-02-15 20:22:57,871 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 69 states. [2023-02-15 20:22:57,871 INFO L78 Accepts]: Start accepts. Automaton has has 32 states, 30 states have (on average 2.033333333333333) internal successors, (61), 29 states have internal predecessors, (61), 10 states have call successors, (28), 3 states have call predecessors, (28), 3 states have return successors, (27), 9 states have call predecessors, (27), 8 states have call successors, (27) Word has length 96 [2023-02-15 20:22:57,872 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-02-15 20:22:57,875 INFO L225 Difference]: With dead ends: 1373 [2023-02-15 20:22:57,875 INFO L226 Difference]: Without dead ends: 1046 [2023-02-15 20:22:57,877 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 252 GetRequests, 158 SyntacticMatches, 2 SemanticMatches, 92 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2408 ImplicationChecksByTransitivity, 42.6s TimeCoverageRelationStatistics Valid=1622, Invalid=7120, Unknown=0, NotChecked=0, Total=8742 [2023-02-15 20:22:57,878 INFO L413 NwaCegarLoop]: 38 mSDtfsCounter, 246 mSDsluCounter, 338 mSDsCounter, 0 mSdLazyCounter, 2271 mSolverCounterSat, 423 mSolverCounterUnsat, 1 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 25.9s Time, 0 mProtectedPredicate, 0 mProtectedAction, 246 SdHoareTripleChecker+Valid, 376 SdHoareTripleChecker+Invalid, 2695 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 423 IncrementalHoareTripleChecker+Valid, 2271 IncrementalHoareTripleChecker+Invalid, 1 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 26.1s IncrementalHoareTripleChecker+Time [2023-02-15 20:22:57,878 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [246 Valid, 376 Invalid, 2695 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [423 Valid, 2271 Invalid, 1 Unknown, 0 Unchecked, 26.1s Time] [2023-02-15 20:22:57,879 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1046 states. [2023-02-15 20:22:58,787 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1046 to 984. [2023-02-15 20:22:58,796 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 984 states, 517 states have (on average 1.2707930367504836) internal successors, (657), 518 states have internal predecessors, (657), 431 states have call successors, (431), 35 states have call predecessors, (431), 35 states have return successors, (430), 430 states have call predecessors, (430), 430 states have call successors, (430) [2023-02-15 20:22:58,811 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 984 states to 984 states and 1518 transitions. [2023-02-15 20:22:58,811 INFO L78 Accepts]: Start accepts. Automaton has 984 states and 1518 transitions. Word has length 96 [2023-02-15 20:22:58,811 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-02-15 20:22:58,811 INFO L495 AbstractCegarLoop]: Abstraction has 984 states and 1518 transitions. [2023-02-15 20:22:58,812 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 32 states, 30 states have (on average 2.033333333333333) internal successors, (61), 29 states have internal predecessors, (61), 10 states have call successors, (28), 3 states have call predecessors, (28), 3 states have return successors, (27), 9 states have call predecessors, (27), 8 states have call successors, (27) [2023-02-15 20:22:58,812 INFO L276 IsEmpty]: Start isEmpty. Operand 984 states and 1518 transitions. [2023-02-15 20:22:58,813 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 110 [2023-02-15 20:22:58,828 INFO L187 NwaCegarLoop]: Found error trace [2023-02-15 20:22:58,828 INFO L195 NwaCegarLoop]: trace histogram [14, 13, 13, 5, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-02-15 20:22:58,833 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-15 20:22:59,033 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-15 20:22:59,033 INFO L420 AbstractCegarLoop]: === Iteration 19 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-02-15 20:22:59,034 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2023-02-15 20:22:59,034 INFO L85 PathProgramCache]: Analyzing trace with hash -1865302579, now seen corresponding path program 1 times [2023-02-15 20:22:59,034 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-02-15 20:22:59,034 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [582747973] [2023-02-15 20:22:59,034 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-15 20:22:59,034 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-02-15 20:22:59,040 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-02-15 20:22:59,040 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1232742172] [2023-02-15 20:22:59,040 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-15 20:22:59,040 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-02-15 20:22:59,040 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-15 20:22:59,047 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-15 20:22:59,052 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-15 20:22:59,100 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-02-15 20:22:59,101 INFO L263 TraceCheckSpWp]: Trace formula consists of 272 conjuncts, 86 conjunts are in the unsatisfiable core [2023-02-15 20:22:59,103 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2023-02-15 20:23:00,073 INFO L134 CoverageAnalysis]: Checked inductivity of 397 backedges. 61 proven. 59 refuted. 0 times theorem prover too weak. 277 trivial. 0 not checked. [2023-02-15 20:23:00,074 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2023-02-15 20:23:04,138 INFO L134 CoverageAnalysis]: Checked inductivity of 397 backedges. 62 proven. 53 refuted. 2 times theorem prover too weak. 280 trivial. 0 not checked. [2023-02-15 20:23:04,138 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-02-15 20:23:04,138 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [582747973] [2023-02-15 20:23:04,138 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-02-15 20:23:04,138 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1232742172] [2023-02-15 20:23:04,138 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1232742172] provided 0 perfect and 2 imperfect interpolant sequences [2023-02-15 20:23:04,138 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-02-15 20:23:04,138 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [22, 18] total 37 [2023-02-15 20:23:04,138 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1690805564] [2023-02-15 20:23:04,138 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-02-15 20:23:04,139 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 37 states [2023-02-15 20:23:04,139 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-02-15 20:23:04,139 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 37 interpolants. [2023-02-15 20:23:04,139 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=234, Invalid=1097, Unknown=1, NotChecked=0, Total=1332 [2023-02-15 20:23:04,140 INFO L87 Difference]: Start difference. First operand 984 states and 1518 transitions. Second operand has 37 states, 35 states have (on average 2.2) internal successors, (77), 33 states have internal predecessors, (77), 12 states have call successors, (31), 3 states have call predecessors, (31), 3 states have return successors, (30), 10 states have call predecessors, (30), 10 states have call successors, (30) [2023-02-15 20:23:09,507 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.24s for a HTC check with result VALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-02-15 20:23:11,394 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.33s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-02-15 20:23:17,433 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.41s for a HTC check with result VALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-02-15 20:23:35,703 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-02-15 20:23:35,703 INFO L93 Difference]: Finished difference Result 1184 states and 1793 transitions. [2023-02-15 20:23:35,704 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 52 states. [2023-02-15 20:23:35,704 INFO L78 Accepts]: Start accepts. Automaton has has 37 states, 35 states have (on average 2.2) internal successors, (77), 33 states have internal predecessors, (77), 12 states have call successors, (31), 3 states have call predecessors, (31), 3 states have return successors, (30), 10 states have call predecessors, (30), 10 states have call successors, (30) Word has length 109 [2023-02-15 20:23:35,704 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-02-15 20:23:35,723 INFO L225 Difference]: With dead ends: 1184 [2023-02-15 20:23:35,723 INFO L226 Difference]: Without dead ends: 1182 [2023-02-15 20:23:35,726 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 261 GetRequests, 180 SyntacticMatches, 1 SemanticMatches, 80 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1699 ImplicationChecksByTransitivity, 19.3s TimeCoverageRelationStatistics Valid=1332, Invalid=5309, Unknown=1, NotChecked=0, Total=6642 [2023-02-15 20:23:35,741 INFO L413 NwaCegarLoop]: 46 mSDtfsCounter, 328 mSDsluCounter, 311 mSDsCounter, 0 mSdLazyCounter, 2134 mSolverCounterSat, 784 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 14.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 328 SdHoareTripleChecker+Valid, 357 SdHoareTripleChecker+Invalid, 2918 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 784 IncrementalHoareTripleChecker+Valid, 2134 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 14.3s IncrementalHoareTripleChecker+Time [2023-02-15 20:23:35,741 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [328 Valid, 357 Invalid, 2918 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [784 Valid, 2134 Invalid, 0 Unknown, 0 Unchecked, 14.3s Time] [2023-02-15 20:23:35,742 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1182 states. [2023-02-15 20:23:36,963 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1182 to 1151. [2023-02-15 20:23:36,965 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 1151 states, 613 states have (on average 1.2577487765089723) internal successors, (771), 618 states have internal predecessors, (771), 495 states have call successors, (495), 42 states have call predecessors, (495), 42 states have return successors, (494), 490 states have call predecessors, (494), 494 states have call successors, (494) [2023-02-15 20:23:36,969 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1151 states to 1151 states and 1760 transitions. [2023-02-15 20:23:36,969 INFO L78 Accepts]: Start accepts. Automaton has 1151 states and 1760 transitions. Word has length 109 [2023-02-15 20:23:36,969 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-02-15 20:23:36,969 INFO L495 AbstractCegarLoop]: Abstraction has 1151 states and 1760 transitions. [2023-02-15 20:23:36,970 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 37 states, 35 states have (on average 2.2) internal successors, (77), 33 states have internal predecessors, (77), 12 states have call successors, (31), 3 states have call predecessors, (31), 3 states have return successors, (30), 10 states have call predecessors, (30), 10 states have call successors, (30) [2023-02-15 20:23:36,970 INFO L276 IsEmpty]: Start isEmpty. Operand 1151 states and 1760 transitions. [2023-02-15 20:23:36,971 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 124 [2023-02-15 20:23:36,971 INFO L187 NwaCegarLoop]: Found error trace [2023-02-15 20:23:36,971 INFO L195 NwaCegarLoop]: trace histogram [17, 16, 16, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-02-15 20:23:36,976 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (20)] Ended with exit code 0 [2023-02-15 20:23:37,176 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable18,20 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-02-15 20:23:37,176 INFO L420 AbstractCegarLoop]: === Iteration 20 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-02-15 20:23:37,177 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2023-02-15 20:23:37,177 INFO L85 PathProgramCache]: Analyzing trace with hash 304105922, now seen corresponding path program 3 times [2023-02-15 20:23:37,177 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-02-15 20:23:37,177 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1868800204] [2023-02-15 20:23:37,177 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-02-15 20:23:37,186 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-02-15 20:23:37,192 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-02-15 20:23:37,192 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [826462793] [2023-02-15 20:23:37,192 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2023-02-15 20:23:37,192 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-02-15 20:23:37,192 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-02-15 20:23:37,195 INFO L229 MonitoredProcess]: Starting monitored process 21 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-02-15 20:23:37,195 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (21)] Waiting until timeout for monitored process [2023-02-15 20:23:39,566 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2023-02-15 20:23:39,566 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-02-15 20:23:39,568 INFO L263 TraceCheckSpWp]: Trace formula consists of 181 conjuncts, 85 conjunts are in the unsatisfiable core [2023-02-15 20:23:39,570 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2023-02-15 20:23:57,891 INFO L134 CoverageAnalysis]: Checked inductivity of 572 backedges. 88 proven. 42 refuted. 0 times theorem prover too weak. 442 trivial. 0 not checked. [2023-02-15 20:23:57,891 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2023-02-15 20:23:59,857 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-02-15 20:23:59,857 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1868800204] [2023-02-15 20:23:59,858 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-02-15 20:23:59,858 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [826462793] [2023-02-15 20:23:59,858 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [826462793] provided 0 perfect and 1 imperfect interpolant sequences [2023-02-15 20:23:59,858 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2023-02-15 20:23:59,858 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [22] total 22 [2023-02-15 20:23:59,858 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1094330477] [2023-02-15 20:23:59,858 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2023-02-15 20:23:59,858 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 22 states [2023-02-15 20:23:59,858 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-02-15 20:23:59,859 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 22 interpolants. [2023-02-15 20:23:59,859 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=138, Invalid=792, Unknown=0, NotChecked=0, Total=930 [2023-02-15 20:23:59,859 INFO L87 Difference]: Start difference. First operand 1151 states and 1760 transitions. Second operand has 22 states, 21 states have (on average 2.0476190476190474) internal successors, (43), 20 states have internal predecessors, (43), 6 states have call successors, (15), 2 states have call predecessors, (15), 3 states have return successors, (14), 5 states have call predecessors, (14), 5 states have call successors, (14) [2023-02-15 20:24:21,987 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-02-15 20:24:21,988 INFO L93 Difference]: Finished difference Result 1350 states and 2057 transitions. [2023-02-15 20:24:21,988 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 22 states. [2023-02-15 20:24:21,988 INFO L78 Accepts]: Start accepts. Automaton has has 22 states, 21 states have (on average 2.0476190476190474) internal successors, (43), 20 states have internal predecessors, (43), 6 states have call successors, (15), 2 states have call predecessors, (15), 3 states have return successors, (14), 5 states have call predecessors, (14), 5 states have call successors, (14) Word has length 123 [2023-02-15 20:24:21,989 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-02-15 20:24:21,993 INFO L225 Difference]: With dead ends: 1350 [2023-02-15 20:24:21,993 INFO L226 Difference]: Without dead ends: 1347 [2023-02-15 20:24:21,994 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 169 GetRequests, 125 SyntacticMatches, 2 SemanticMatches, 42 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 445 ImplicationChecksByTransitivity, 21.8s TimeCoverageRelationStatistics Valid=281, Invalid=1611, Unknown=0, NotChecked=0, Total=1892 [2023-02-15 20:24:21,994 INFO L413 NwaCegarLoop]: 46 mSDtfsCounter, 87 mSDsluCounter, 251 mSDsCounter, 0 mSdLazyCounter, 1245 mSolverCounterSat, 94 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 7.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 103 SdHoareTripleChecker+Valid, 297 SdHoareTripleChecker+Invalid, 1339 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 94 IncrementalHoareTripleChecker+Valid, 1245 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 7.7s IncrementalHoareTripleChecker+Time [2023-02-15 20:24:21,994 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [103 Valid, 297 Invalid, 1339 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [94 Valid, 1245 Invalid, 0 Unknown, 0 Unchecked, 7.7s Time] [2023-02-15 20:24:21,995 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1347 states.