./Ultimate.py --spec ../sv-benchmarks/c/properties/unreach-call.prp --file ../sv-benchmarks/c/nla-digbench-scaling/egcd2-ll_valuebound20.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version 35987657 Calling Ultimate with: /usr/bin/java -Dosgi.configuration.area=/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/config -Xmx15G -Xms4m -jar /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data -tc /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/AutomizerReach.xml -i ../sv-benchmarks/c/nla-digbench-scaling/egcd2-ll_valuebound20.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 e587d407128aaafd417211e5ccf66790913a0bc1afeba03ae0cdb578f5831614 --- Real Ultimate output --- This is Ultimate 0.2.2-?-3598765 [2022-07-21 03:25:59,213 INFO L177 SettingsManager]: Resetting all preferences to default values... [2022-07-21 03:25:59,216 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2022-07-21 03:25:59,250 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2022-07-21 03:25:59,250 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2022-07-21 03:25:59,252 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2022-07-21 03:25:59,255 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2022-07-21 03:25:59,257 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2022-07-21 03:25:59,259 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2022-07-21 03:25:59,262 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2022-07-21 03:25:59,263 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2022-07-21 03:25:59,267 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2022-07-21 03:25:59,267 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2022-07-21 03:25:59,269 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2022-07-21 03:25:59,270 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2022-07-21 03:25:59,275 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2022-07-21 03:25:59,276 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2022-07-21 03:25:59,276 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2022-07-21 03:25:59,278 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2022-07-21 03:25:59,282 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2022-07-21 03:25:59,283 INFO L181 SettingsManager]: Resetting HornVerifier preferences to default values [2022-07-21 03:25:59,288 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2022-07-21 03:25:59,290 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2022-07-21 03:25:59,290 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2022-07-21 03:25:59,291 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2022-07-21 03:25:59,296 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2022-07-21 03:25:59,297 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2022-07-21 03:25:59,297 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2022-07-21 03:25:59,297 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2022-07-21 03:25:59,298 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2022-07-21 03:25:59,298 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2022-07-21 03:25:59,299 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2022-07-21 03:25:59,300 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2022-07-21 03:25:59,300 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2022-07-21 03:25:59,301 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2022-07-21 03:25:59,302 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2022-07-21 03:25:59,302 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2022-07-21 03:25:59,303 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2022-07-21 03:25:59,303 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2022-07-21 03:25:59,303 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2022-07-21 03:25:59,304 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2022-07-21 03:25:59,305 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2022-07-21 03:25:59,309 INFO L101 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf [2022-07-21 03:25:59,333 INFO L113 SettingsManager]: Loading preferences was successful [2022-07-21 03:25:59,334 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2022-07-21 03:25:59,334 INFO L136 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2022-07-21 03:25:59,334 INFO L138 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2022-07-21 03:25:59,334 INFO L136 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2022-07-21 03:25:59,335 INFO L138 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2022-07-21 03:25:59,335 INFO L136 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2022-07-21 03:25:59,335 INFO L138 SettingsManager]: * Create parallel compositions if possible=false [2022-07-21 03:25:59,335 INFO L138 SettingsManager]: * Use SBE=true [2022-07-21 03:25:59,336 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2022-07-21 03:25:59,336 INFO L138 SettingsManager]: * sizeof long=4 [2022-07-21 03:25:59,336 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2022-07-21 03:25:59,336 INFO L138 SettingsManager]: * sizeof POINTER=4 [2022-07-21 03:25:59,337 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2022-07-21 03:25:59,337 INFO L138 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2022-07-21 03:25:59,342 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2022-07-21 03:25:59,342 INFO L138 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2022-07-21 03:25:59,342 INFO L138 SettingsManager]: * sizeof long double=12 [2022-07-21 03:25:59,342 INFO L138 SettingsManager]: * Check if freed pointer was valid=false [2022-07-21 03:25:59,342 INFO L138 SettingsManager]: * Use constant arrays=true [2022-07-21 03:25:59,343 INFO L138 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2022-07-21 03:25:59,343 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2022-07-21 03:25:59,343 INFO L138 SettingsManager]: * Size of a code block=SequenceOfStatements [2022-07-21 03:25:59,343 INFO L138 SettingsManager]: * SMT solver=External_DefaultMode [2022-07-21 03:25:59,343 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-07-21 03:25:59,343 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2022-07-21 03:25:59,344 INFO L138 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2022-07-21 03:25:59,344 INFO L138 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2022-07-21 03:25:59,344 INFO L138 SettingsManager]: * Trace refinement strategy=CAMEL [2022-07-21 03:25:59,344 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2022-07-21 03:25:59,344 INFO L138 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2022-07-21 03:25:59,344 INFO L138 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2022-07-21 03:25:59,345 INFO L138 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2022-07-21 03:25:59,345 INFO L138 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode WARNING: An illegal reflective access operation has occurred WARNING: Illegal reflective access by com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 (file:/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/com.sun.xml.bind_2.2.0.v201505121915.jar) to method java.lang.ClassLoader.defineClass(java.lang.String,byte[],int,int) WARNING: Please consider reporting this to the maintainers of com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 WARNING: Use --illegal-access=warn to enable warnings of further illegal reflective access operations WARNING: All illegal access operations will be denied in a future release Applying setting for plugin de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator: Entry function -> main Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Witness directory -> /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Witness filename -> witness.graphml Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Write witness besides input file -> false Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data specification -> CHECK( init(main()), LTL(G ! call(reach_error())) ) Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data producer -> Automizer Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data architecture -> 32bit Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data programhash -> e587d407128aaafd417211e5ccf66790913a0bc1afeba03ae0cdb578f5831614 [2022-07-21 03:25:59,640 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2022-07-21 03:25:59,655 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2022-07-21 03:25:59,656 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2022-07-21 03:25:59,657 INFO L271 PluginConnector]: Initializing CDTParser... [2022-07-21 03:25:59,658 INFO L275 PluginConnector]: CDTParser initialized [2022-07-21 03:25:59,658 INFO L432 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/nla-digbench-scaling/egcd2-ll_valuebound20.c [2022-07-21 03:25:59,706 INFO L220 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/70c1fb2c2/e07ebd91a68d4717b53716776ef16811/FLAG4be79e17f [2022-07-21 03:26:00,024 INFO L306 CDTParser]: Found 1 translation units. [2022-07-21 03:26:00,025 INFO L160 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/egcd2-ll_valuebound20.c [2022-07-21 03:26:00,033 INFO L349 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/70c1fb2c2/e07ebd91a68d4717b53716776ef16811/FLAG4be79e17f [2022-07-21 03:26:00,049 INFO L357 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/70c1fb2c2/e07ebd91a68d4717b53716776ef16811 [2022-07-21 03:26:00,051 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2022-07-21 03:26:00,052 INFO L131 ToolchainWalker]: Walking toolchain with 6 elements. [2022-07-21 03:26:00,055 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2022-07-21 03:26:00,055 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2022-07-21 03:26:00,058 INFO L275 PluginConnector]: CACSL2BoogieTranslator initialized [2022-07-21 03:26:00,059 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 21.07 03:26:00" (1/1) ... [2022-07-21 03:26:00,060 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@5a285f3e and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.07 03:26:00, skipping insertion in model container [2022-07-21 03:26:00,060 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 21.07 03:26:00" (1/1) ... [2022-07-21 03:26:00,065 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2022-07-21 03:26:00,079 INFO L178 MainTranslator]: Built tables and reachable declarations [2022-07-21 03:26:00,207 WARN L230 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/egcd2-ll_valuebound20.c[490,503] [2022-07-21 03:26:00,239 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-07-21 03:26:00,251 INFO L203 MainTranslator]: Completed pre-run [2022-07-21 03:26:00,266 WARN L230 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/egcd2-ll_valuebound20.c[490,503] [2022-07-21 03:26:00,299 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-07-21 03:26:00,309 INFO L208 MainTranslator]: Completed translation [2022-07-21 03:26:00,309 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.07 03:26:00 WrapperNode [2022-07-21 03:26:00,309 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2022-07-21 03:26:00,310 INFO L113 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2022-07-21 03:26:00,310 INFO L271 PluginConnector]: Initializing Boogie Procedure Inliner... [2022-07-21 03:26:00,310 INFO L275 PluginConnector]: Boogie Procedure Inliner initialized [2022-07-21 03:26:00,316 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.07 03:26:00" (1/1) ... [2022-07-21 03:26:00,327 INFO L185 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.07 03:26:00" (1/1) ... [2022-07-21 03:26:00,347 INFO L137 Inliner]: procedures = 14, calls = 19, calls flagged for inlining = 2, calls inlined = 2, statements flattened = 77 [2022-07-21 03:26:00,347 INFO L132 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2022-07-21 03:26:00,348 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2022-07-21 03:26:00,349 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2022-07-21 03:26:00,349 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2022-07-21 03:26:00,354 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.07 03:26:00" (1/1) ... [2022-07-21 03:26:00,355 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.07 03:26:00" (1/1) ... [2022-07-21 03:26:00,358 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.07 03:26:00" (1/1) ... [2022-07-21 03:26:00,359 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.07 03:26:00" (1/1) ... [2022-07-21 03:26:00,371 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.07 03:26:00" (1/1) ... [2022-07-21 03:26:00,374 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.07 03:26:00" (1/1) ... [2022-07-21 03:26:00,379 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.07 03:26:00" (1/1) ... [2022-07-21 03:26:00,381 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2022-07-21 03:26:00,383 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2022-07-21 03:26:00,383 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2022-07-21 03:26:00,383 INFO L275 PluginConnector]: RCFGBuilder initialized [2022-07-21 03:26:00,384 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.07 03:26:00" (1/1) ... [2022-07-21 03:26:00,389 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-07-21 03:26:00,398 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-21 03:26:00,449 INFO L229 MonitoredProcess]: Starting monitored process 1 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) [2022-07-21 03:26:00,457 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Waiting until timeout for monitored process [2022-07-21 03:26:00,478 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2022-07-21 03:26:00,478 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2022-07-21 03:26:00,478 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2022-07-21 03:26:00,479 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2022-07-21 03:26:00,479 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2022-07-21 03:26:00,479 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2022-07-21 03:26:00,479 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2022-07-21 03:26:00,479 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2022-07-21 03:26:00,529 INFO L234 CfgBuilder]: Building ICFG [2022-07-21 03:26:00,531 INFO L260 CfgBuilder]: Building CFG for each procedure with an implementation [2022-07-21 03:26:00,643 INFO L275 CfgBuilder]: Performing block encoding [2022-07-21 03:26:00,647 INFO L294 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2022-07-21 03:26:00,647 INFO L299 CfgBuilder]: Removed 2 assume(true) statements. [2022-07-21 03:26:00,649 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 21.07 03:26:00 BoogieIcfgContainer [2022-07-21 03:26:00,649 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2022-07-21 03:26:00,650 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2022-07-21 03:26:00,650 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2022-07-21 03:26:00,652 INFO L275 PluginConnector]: TraceAbstraction initialized [2022-07-21 03:26:00,652 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 21.07 03:26:00" (1/3) ... [2022-07-21 03:26:00,653 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@471f0c8d and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 21.07 03:26:00, skipping insertion in model container [2022-07-21 03:26:00,653 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.07 03:26:00" (2/3) ... [2022-07-21 03:26:00,653 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@471f0c8d and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 21.07 03:26:00, skipping insertion in model container [2022-07-21 03:26:00,653 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 21.07 03:26:00" (3/3) ... [2022-07-21 03:26:00,654 INFO L111 eAbstractionObserver]: Analyzing ICFG egcd2-ll_valuebound20.c [2022-07-21 03:26:00,691 INFO L201 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2022-07-21 03:26:00,692 INFO L160 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2022-07-21 03:26:00,744 INFO L356 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2022-07-21 03:26:00,756 INFO L357 AbstractCegarLoop]: Settings: SEPARATE_VIOLATION_CHECK=true, mInterprocedural=true, mMaxIterations=1000000, mWatchIteration=1000000, mArtifact=RCFG, mInterpolation=FPandBP, mInterpolantAutomaton=STRAIGHT_LINE, mDumpAutomata=false, mAutomataFormat=ATS_NUMERATE, mDumpPath=., mDeterminiation=PREDICATE_ABSTRACTION, mMinimize=MINIMIZE_SEVPA, mHoare=true, mAutomataTypeConcurrency=PETRI_NET, mHoareTripleChecks=INCREMENTAL, mHoareAnnotationPositions=LoopsAndPotentialCycles, mDumpOnlyReuseAutomata=false, mLimitTraceHistogram=0, mErrorLocTimeLimit=0, mLimitPathProgramCount=0, mCollectInterpolantStatistics=true, mHeuristicEmptinessCheck=false, mHeuristicEmptinessCheckAStarHeuristic=ZERO, mHeuristicEmptinessCheckAStarHeuristicRandomSeed=1337, mHeuristicEmptinessCheckSmtFeatureScoringMethod=DAGSIZE, mSMTFeatureExtraction=false, mSMTFeatureExtractionDumpPath=., mOverrideInterpolantAutomaton=false, mMcrInterpolantMethod=WP, mPorIndependenceSettings=de.uni_freiburg.informatik.ultimate.lib.tracecheckerutils.partialorder.independence.IndependenceSettings@b740785, mLbeIndependenceSettings=de.uni_freiburg.informatik.ultimate.lib.tracecheckerutils.partialorder.independence.IndependenceSettings@bf0549e [2022-07-21 03:26:00,756 INFO L358 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2022-07-21 03:26:00,760 INFO L276 IsEmpty]: Start isEmpty. Operand has 35 states, 19 states have (on average 1.4736842105263157) internal successors, (28), 21 states have internal predecessors, (28), 12 states have call successors, (12), 2 states have call predecessors, (12), 2 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) [2022-07-21 03:26:00,765 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 40 [2022-07-21 03:26:00,765 INFO L187 NwaCegarLoop]: Found error trace [2022-07-21 03:26:00,766 INFO L195 NwaCegarLoop]: trace histogram [6, 6, 6, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-21 03:26:00,766 INFO L420 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-21 03:26:00,772 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-21 03:26:00,773 INFO L85 PathProgramCache]: Analyzing trace with hash -1146169762, now seen corresponding path program 1 times [2022-07-21 03:26:00,779 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-21 03:26:00,780 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [123206084] [2022-07-21 03:26:00,780 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-21 03:26:00,781 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-21 03:26:00,882 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-21 03:26:00,923 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2022-07-21 03:26:00,928 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-21 03:26:00,933 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 8 [2022-07-21 03:26:00,937 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-21 03:26:00,941 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 13 [2022-07-21 03:26:00,946 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-21 03:26:00,949 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 18 [2022-07-21 03:26:00,954 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-21 03:26:00,958 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 24 [2022-07-21 03:26:00,965 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-21 03:26:00,970 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 29 [2022-07-21 03:26:00,973 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-21 03:26:00,976 INFO L134 CoverageAnalysis]: Checked inductivity of 60 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 60 trivial. 0 not checked. [2022-07-21 03:26:00,977 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-21 03:26:00,978 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [123206084] [2022-07-21 03:26:00,978 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [123206084] provided 1 perfect and 0 imperfect interpolant sequences [2022-07-21 03:26:00,979 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-07-21 03:26:00,979 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2022-07-21 03:26:00,980 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1560950350] [2022-07-21 03:26:00,981 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-07-21 03:26:00,985 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2022-07-21 03:26:00,985 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-21 03:26:01,008 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2022-07-21 03:26:01,010 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2022-07-21 03:26:01,011 INFO L87 Difference]: Start difference. First operand has 35 states, 19 states have (on average 1.4736842105263157) internal successors, (28), 21 states have internal predecessors, (28), 12 states have call successors, (12), 2 states have call predecessors, (12), 2 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) Second operand has 2 states, 2 states have (on average 5.5) internal successors, (11), 2 states have internal predecessors, (11), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 1 states have call predecessors, (6), 2 states have call successors, (6) [2022-07-21 03:26:01,032 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-21 03:26:01,033 INFO L93 Difference]: Finished difference Result 67 states and 112 transitions. [2022-07-21 03:26:01,033 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2022-07-21 03:26:01,034 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 5.5) internal successors, (11), 2 states have internal predecessors, (11), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 1 states have call predecessors, (6), 2 states have call successors, (6) Word has length 39 [2022-07-21 03:26:01,034 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-21 03:26:01,039 INFO L225 Difference]: With dead ends: 67 [2022-07-21 03:26:01,039 INFO L226 Difference]: Without dead ends: 31 [2022-07-21 03:26:01,045 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 20 GetRequests, 20 SyntacticMatches, 0 SemanticMatches, 0 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2022-07-21 03:26:01,049 INFO L413 NwaCegarLoop]: 46 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, 46 SdHoareTripleChecker+Invalid, 0 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 0 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-07-21 03:26:01,050 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 46 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 0 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-07-21 03:26:01,066 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 31 states. [2022-07-21 03:26:01,084 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 31 to 31. [2022-07-21 03:26:01,086 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 31 states, 16 states have (on average 1.1875) internal successors, (19), 18 states have internal predecessors, (19), 12 states have call successors, (12), 2 states have call predecessors, (12), 2 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2022-07-21 03:26:01,088 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 31 states to 31 states and 42 transitions. [2022-07-21 03:26:01,089 INFO L78 Accepts]: Start accepts. Automaton has 31 states and 42 transitions. Word has length 39 [2022-07-21 03:26:01,090 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-21 03:26:01,090 INFO L495 AbstractCegarLoop]: Abstraction has 31 states and 42 transitions. [2022-07-21 03:26:01,090 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 2 states have (on average 5.5) internal successors, (11), 2 states have internal predecessors, (11), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 1 states have call predecessors, (6), 2 states have call successors, (6) [2022-07-21 03:26:01,091 INFO L276 IsEmpty]: Start isEmpty. Operand 31 states and 42 transitions. [2022-07-21 03:26:01,094 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 41 [2022-07-21 03:26:01,094 INFO L187 NwaCegarLoop]: Found error trace [2022-07-21 03:26:01,094 INFO L195 NwaCegarLoop]: trace histogram [6, 6, 6, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-21 03:26:01,095 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2022-07-21 03:26:01,095 INFO L420 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-21 03:26:01,096 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-21 03:26:01,096 INFO L85 PathProgramCache]: Analyzing trace with hash 846808023, now seen corresponding path program 1 times [2022-07-21 03:26:01,097 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-21 03:26:01,097 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [311968106] [2022-07-21 03:26:01,097 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-21 03:26:01,097 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-21 03:26:01,132 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-07-21 03:26:01,134 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [78086982] [2022-07-21 03:26:01,134 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-21 03:26:01,134 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-21 03:26:01,134 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-21 03:26:01,136 INFO L229 MonitoredProcess]: Starting monitored process 2 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-07-21 03:26:01,137 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2022-07-21 03:26:01,206 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-21 03:26:01,208 INFO L263 TraceCheckSpWp]: Trace formula consists of 117 conjuncts, 7 conjunts are in the unsatisfiable core [2022-07-21 03:26:01,212 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-21 03:26:01,307 INFO L134 CoverageAnalysis]: Checked inductivity of 60 backedges. 9 proven. 6 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2022-07-21 03:26:01,310 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-21 03:26:01,423 INFO L134 CoverageAnalysis]: Checked inductivity of 60 backedges. 9 proven. 6 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2022-07-21 03:26:01,423 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-21 03:26:01,423 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [311968106] [2022-07-21 03:26:01,424 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-07-21 03:26:01,424 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [78086982] [2022-07-21 03:26:01,424 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [78086982] provided 0 perfect and 2 imperfect interpolant sequences [2022-07-21 03:26:01,424 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-07-21 03:26:01,424 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 7 [2022-07-21 03:26:01,425 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [56344529] [2022-07-21 03:26:01,425 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-07-21 03:26:01,426 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2022-07-21 03:26:01,426 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-21 03:26:01,426 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2022-07-21 03:26:01,426 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=29, Unknown=0, NotChecked=0, Total=42 [2022-07-21 03:26:01,427 INFO L87 Difference]: Start difference. First operand 31 states and 42 transitions. Second operand has 7 states, 7 states have (on average 2.4285714285714284) internal successors, (17), 6 states have internal predecessors, (17), 3 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (6), 3 states have call predecessors, (6), 2 states have call successors, (6) [2022-07-21 03:26:01,568 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-21 03:26:01,568 INFO L93 Difference]: Finished difference Result 48 states and 65 transitions. [2022-07-21 03:26:01,569 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2022-07-21 03:26:01,569 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 7 states have (on average 2.4285714285714284) internal successors, (17), 6 states have internal predecessors, (17), 3 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (6), 3 states have call predecessors, (6), 2 states have call successors, (6) Word has length 40 [2022-07-21 03:26:01,569 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-21 03:26:01,570 INFO L225 Difference]: With dead ends: 48 [2022-07-21 03:26:01,570 INFO L226 Difference]: Without dead ends: 40 [2022-07-21 03:26:01,570 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 80 GetRequests, 72 SyntacticMatches, 1 SemanticMatches, 7 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=22, Invalid=50, Unknown=0, NotChecked=0, Total=72 [2022-07-21 03:26:01,571 INFO L413 NwaCegarLoop]: 34 mSDtfsCounter, 21 mSDsluCounter, 74 mSDsCounter, 0 mSdLazyCounter, 90 mSolverCounterSat, 11 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 26 SdHoareTripleChecker+Valid, 108 SdHoareTripleChecker+Invalid, 101 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 11 IncrementalHoareTripleChecker+Valid, 90 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-07-21 03:26:01,571 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [26 Valid, 108 Invalid, 101 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [11 Valid, 90 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-07-21 03:26:01,572 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 40 states. [2022-07-21 03:26:01,577 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 40 to 33. [2022-07-21 03:26:01,577 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 33 states, 18 states have (on average 1.1666666666666667) internal successors, (21), 19 states have internal predecessors, (21), 12 states have call successors, (12), 2 states have call predecessors, (12), 2 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2022-07-21 03:26:01,578 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 33 states to 33 states and 44 transitions. [2022-07-21 03:26:01,578 INFO L78 Accepts]: Start accepts. Automaton has 33 states and 44 transitions. Word has length 40 [2022-07-21 03:26:01,578 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-21 03:26:01,579 INFO L495 AbstractCegarLoop]: Abstraction has 33 states and 44 transitions. [2022-07-21 03:26:01,579 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 7 states have (on average 2.4285714285714284) internal successors, (17), 6 states have internal predecessors, (17), 3 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (6), 3 states have call predecessors, (6), 2 states have call successors, (6) [2022-07-21 03:26:01,579 INFO L276 IsEmpty]: Start isEmpty. Operand 33 states and 44 transitions. [2022-07-21 03:26:01,579 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 42 [2022-07-21 03:26:01,580 INFO L187 NwaCegarLoop]: Found error trace [2022-07-21 03:26:01,580 INFO L195 NwaCegarLoop]: trace histogram [6, 6, 6, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-21 03:26:01,602 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Forceful destruction successful, exit code 0 [2022-07-21 03:26:01,780 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1,2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-21 03:26:01,781 INFO L420 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-21 03:26:01,781 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-21 03:26:01,781 INFO L85 PathProgramCache]: Analyzing trace with hash 481927254, now seen corresponding path program 1 times [2022-07-21 03:26:01,782 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-21 03:26:01,782 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [950276454] [2022-07-21 03:26:01,782 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-21 03:26:01,782 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-21 03:26:01,802 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-07-21 03:26:01,802 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [461172876] [2022-07-21 03:26:01,803 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-21 03:26:01,803 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-21 03:26:01,803 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-21 03:26:01,804 INFO L229 MonitoredProcess]: Starting monitored process 3 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-07-21 03:26:01,805 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2022-07-21 03:26:01,856 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-21 03:26:01,857 INFO L263 TraceCheckSpWp]: Trace formula consists of 121 conjuncts, 14 conjunts are in the unsatisfiable core [2022-07-21 03:26:01,859 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-21 03:26:01,958 INFO L134 CoverageAnalysis]: Checked inductivity of 60 backedges. 9 proven. 6 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2022-07-21 03:26:01,959 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-21 03:26:02,015 INFO L134 CoverageAnalysis]: Checked inductivity of 60 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 60 trivial. 0 not checked. [2022-07-21 03:26:02,016 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-21 03:26:02,016 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [950276454] [2022-07-21 03:26:02,016 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-07-21 03:26:02,017 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [461172876] [2022-07-21 03:26:02,017 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [461172876] provided 1 perfect and 1 imperfect interpolant sequences [2022-07-21 03:26:02,017 INFO L184 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2022-07-21 03:26:02,017 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [9] total 10 [2022-07-21 03:26:02,018 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2025483458] [2022-07-21 03:26:02,018 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-07-21 03:26:02,019 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-07-21 03:26:02,019 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-21 03:26:02,019 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-07-21 03:26:02,020 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=19, Invalid=71, Unknown=0, NotChecked=0, Total=90 [2022-07-21 03:26:02,020 INFO L87 Difference]: Start difference. First operand 33 states and 44 transitions. Second operand has 5 states, 5 states have (on average 2.6) internal successors, (13), 4 states have internal predecessors, (13), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 1 states have call predecessors, (6), 1 states have call successors, (6) [2022-07-21 03:26:02,064 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-21 03:26:02,064 INFO L93 Difference]: Finished difference Result 39 states and 49 transitions. [2022-07-21 03:26:02,065 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-07-21 03:26:02,065 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.6) internal successors, (13), 4 states have internal predecessors, (13), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 1 states have call predecessors, (6), 1 states have call successors, (6) Word has length 41 [2022-07-21 03:26:02,066 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-21 03:26:02,069 INFO L225 Difference]: With dead ends: 39 [2022-07-21 03:26:02,069 INFO L226 Difference]: Without dead ends: 37 [2022-07-21 03:26:02,070 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 81 GetRequests, 71 SyntacticMatches, 1 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 5 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=23, Invalid=87, Unknown=0, NotChecked=0, Total=110 [2022-07-21 03:26:02,071 INFO L413 NwaCegarLoop]: 36 mSDtfsCounter, 6 mSDsluCounter, 85 mSDsCounter, 0 mSdLazyCounter, 38 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 10 SdHoareTripleChecker+Valid, 121 SdHoareTripleChecker+Invalid, 39 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 38 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-07-21 03:26:02,073 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [10 Valid, 121 Invalid, 39 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 38 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-07-21 03:26:02,074 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 37 states. [2022-07-21 03:26:02,087 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 37 to 37. [2022-07-21 03:26:02,087 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 37 states, 21 states have (on average 1.1428571428571428) internal successors, (24), 22 states have internal predecessors, (24), 12 states have call successors, (12), 3 states have call predecessors, (12), 3 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2022-07-21 03:26:02,088 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 37 states to 37 states and 47 transitions. [2022-07-21 03:26:02,088 INFO L78 Accepts]: Start accepts. Automaton has 37 states and 47 transitions. Word has length 41 [2022-07-21 03:26:02,088 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-21 03:26:02,091 INFO L495 AbstractCegarLoop]: Abstraction has 37 states and 47 transitions. [2022-07-21 03:26:02,092 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.6) internal successors, (13), 4 states have internal predecessors, (13), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 1 states have call predecessors, (6), 1 states have call successors, (6) [2022-07-21 03:26:02,092 INFO L276 IsEmpty]: Start isEmpty. Operand 37 states and 47 transitions. [2022-07-21 03:26:02,092 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 47 [2022-07-21 03:26:02,093 INFO L187 NwaCegarLoop]: Found error trace [2022-07-21 03:26:02,093 INFO L195 NwaCegarLoop]: trace histogram [6, 6, 6, 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] [2022-07-21 03:26:02,113 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2022-07-21 03:26:02,310 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 3 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable2 [2022-07-21 03:26:02,311 INFO L420 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-21 03:26:02,311 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-21 03:26:02,311 INFO L85 PathProgramCache]: Analyzing trace with hash -1626076469, now seen corresponding path program 1 times [2022-07-21 03:26:02,311 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-21 03:26:02,312 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [948759337] [2022-07-21 03:26:02,312 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-21 03:26:02,312 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-21 03:26:02,324 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-07-21 03:26:02,324 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1491718916] [2022-07-21 03:26:02,324 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-21 03:26:02,324 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-21 03:26:02,325 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-21 03:26:02,326 INFO L229 MonitoredProcess]: Starting monitored process 4 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-07-21 03:26:02,327 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2022-07-21 03:26:02,371 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-21 03:26:02,372 INFO L263 TraceCheckSpWp]: Trace formula consists of 130 conjuncts, 9 conjunts are in the unsatisfiable core [2022-07-21 03:26:02,374 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-21 03:26:02,425 INFO L134 CoverageAnalysis]: Checked inductivity of 62 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 60 trivial. 0 not checked. [2022-07-21 03:26:02,425 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-07-21 03:26:02,425 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-21 03:26:02,426 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [948759337] [2022-07-21 03:26:02,426 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-07-21 03:26:02,426 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1491718916] [2022-07-21 03:26:02,426 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1491718916] provided 1 perfect and 0 imperfect interpolant sequences [2022-07-21 03:26:02,426 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-07-21 03:26:02,426 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-07-21 03:26:02,426 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1502077788] [2022-07-21 03:26:02,427 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-07-21 03:26:02,427 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-07-21 03:26:02,427 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-21 03:26:02,427 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-07-21 03:26:02,428 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-07-21 03:26:02,428 INFO L87 Difference]: Start difference. First operand 37 states and 47 transitions. Second operand has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 2 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2022-07-21 03:26:02,460 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-21 03:26:02,461 INFO L93 Difference]: Finished difference Result 50 states and 64 transitions. [2022-07-21 03:26:02,461 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-07-21 03:26:02,461 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 2 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) Word has length 46 [2022-07-21 03:26:02,462 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-21 03:26:02,462 INFO L225 Difference]: With dead ends: 50 [2022-07-21 03:26:02,462 INFO L226 Difference]: Without dead ends: 48 [2022-07-21 03:26:02,463 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 46 GetRequests, 42 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2022-07-21 03:26:02,465 INFO L413 NwaCegarLoop]: 44 mSDtfsCounter, 7 mSDsluCounter, 101 mSDsCounter, 0 mSdLazyCounter, 38 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 10 SdHoareTripleChecker+Valid, 145 SdHoareTripleChecker+Invalid, 38 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 38 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-07-21 03:26:02,465 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [10 Valid, 145 Invalid, 38 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 38 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-07-21 03:26:02,466 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 48 states. [2022-07-21 03:26:02,471 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 48 to 47. [2022-07-21 03:26:02,471 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 47 states, 26 states have (on average 1.1538461538461537) internal successors, (30), 27 states have internal predecessors, (30), 16 states have call successors, (16), 4 states have call predecessors, (16), 4 states have return successors, (15), 15 states have call predecessors, (15), 15 states have call successors, (15) [2022-07-21 03:26:02,472 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 47 states to 47 states and 61 transitions. [2022-07-21 03:26:02,472 INFO L78 Accepts]: Start accepts. Automaton has 47 states and 61 transitions. Word has length 46 [2022-07-21 03:26:02,472 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-21 03:26:02,472 INFO L495 AbstractCegarLoop]: Abstraction has 47 states and 61 transitions. [2022-07-21 03:26:02,473 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 2 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2022-07-21 03:26:02,473 INFO L276 IsEmpty]: Start isEmpty. Operand 47 states and 61 transitions. [2022-07-21 03:26:02,474 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 52 [2022-07-21 03:26:02,474 INFO L187 NwaCegarLoop]: Found error trace [2022-07-21 03:26:02,474 INFO L195 NwaCegarLoop]: trace histogram [6, 6, 6, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-21 03:26:02,492 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Forceful destruction successful, exit code 0 [2022-07-21 03:26:02,679 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-21 03:26:02,680 INFO L420 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-21 03:26:02,680 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-21 03:26:02,680 INFO L85 PathProgramCache]: Analyzing trace with hash 779090230, now seen corresponding path program 1 times [2022-07-21 03:26:02,680 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-21 03:26:02,680 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1844817114] [2022-07-21 03:26:02,681 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-21 03:26:02,681 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-21 03:26:02,691 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-07-21 03:26:02,692 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [521981937] [2022-07-21 03:26:02,692 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-21 03:26:02,692 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-21 03:26:02,692 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-21 03:26:02,693 INFO L229 MonitoredProcess]: Starting monitored process 5 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-07-21 03:26:02,694 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2022-07-21 03:26:02,739 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-21 03:26:02,741 INFO L263 TraceCheckSpWp]: Trace formula consists of 139 conjuncts, 19 conjunts are in the unsatisfiable core [2022-07-21 03:26:02,746 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-21 03:26:02,892 INFO L134 CoverageAnalysis]: Checked inductivity of 68 backedges. 7 proven. 21 refuted. 0 times theorem prover too weak. 40 trivial. 0 not checked. [2022-07-21 03:26:02,892 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-21 03:26:02,982 INFO L134 CoverageAnalysis]: Checked inductivity of 68 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 64 trivial. 0 not checked. [2022-07-21 03:26:02,982 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-21 03:26:02,982 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1844817114] [2022-07-21 03:26:02,982 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-07-21 03:26:02,982 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [521981937] [2022-07-21 03:26:02,983 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [521981937] provided 1 perfect and 1 imperfect interpolant sequences [2022-07-21 03:26:02,983 INFO L184 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2022-07-21 03:26:02,983 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [9] total 10 [2022-07-21 03:26:02,983 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1310709668] [2022-07-21 03:26:02,983 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-07-21 03:26:02,984 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-07-21 03:26:02,984 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-21 03:26:02,985 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-07-21 03:26:02,985 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=21, Invalid=69, Unknown=0, NotChecked=0, Total=90 [2022-07-21 03:26:02,986 INFO L87 Difference]: Start difference. First operand 47 states and 61 transitions. Second operand has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 2 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (8), 2 states have call predecessors, (8), 2 states have call successors, (8) [2022-07-21 03:26:03,039 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-21 03:26:03,039 INFO L93 Difference]: Finished difference Result 54 states and 67 transitions. [2022-07-21 03:26:03,040 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-07-21 03:26:03,040 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 2 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (8), 2 states have call predecessors, (8), 2 states have call successors, (8) Word has length 51 [2022-07-21 03:26:03,041 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-21 03:26:03,043 INFO L225 Difference]: With dead ends: 54 [2022-07-21 03:26:03,043 INFO L226 Difference]: Without dead ends: 52 [2022-07-21 03:26:03,043 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 101 GetRequests, 91 SyntacticMatches, 1 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 10 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=25, Invalid=85, Unknown=0, NotChecked=0, Total=110 [2022-07-21 03:26:03,044 INFO L413 NwaCegarLoop]: 42 mSDtfsCounter, 7 mSDsluCounter, 91 mSDsCounter, 0 mSdLazyCounter, 50 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 9 SdHoareTripleChecker+Valid, 133 SdHoareTripleChecker+Invalid, 50 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 50 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-07-21 03:26:03,044 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [9 Valid, 133 Invalid, 50 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 50 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-07-21 03:26:03,046 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 52 states. [2022-07-21 03:26:03,061 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 52 to 51. [2022-07-21 03:26:03,062 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 51 states, 29 states have (on average 1.1379310344827587) internal successors, (33), 30 states have internal predecessors, (33), 16 states have call successors, (16), 5 states have call predecessors, (16), 5 states have return successors, (15), 15 states have call predecessors, (15), 15 states have call successors, (15) [2022-07-21 03:26:03,063 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 51 states to 51 states and 64 transitions. [2022-07-21 03:26:03,063 INFO L78 Accepts]: Start accepts. Automaton has 51 states and 64 transitions. Word has length 51 [2022-07-21 03:26:03,065 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-21 03:26:03,065 INFO L495 AbstractCegarLoop]: Abstraction has 51 states and 64 transitions. [2022-07-21 03:26:03,066 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 2 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (8), 2 states have call predecessors, (8), 2 states have call successors, (8) [2022-07-21 03:26:03,067 INFO L276 IsEmpty]: Start isEmpty. Operand 51 states and 64 transitions. [2022-07-21 03:26:03,068 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 57 [2022-07-21 03:26:03,069 INFO L187 NwaCegarLoop]: Found error trace [2022-07-21 03:26:03,070 INFO L195 NwaCegarLoop]: trace histogram [6, 6, 6, 4, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-21 03:26:03,099 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Forceful destruction successful, exit code 0 [2022-07-21 03:26:03,283 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-21 03:26:03,283 INFO L420 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-21 03:26:03,284 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-21 03:26:03,284 INFO L85 PathProgramCache]: Analyzing trace with hash -670274197, now seen corresponding path program 1 times [2022-07-21 03:26:03,284 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-21 03:26:03,286 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [76315569] [2022-07-21 03:26:03,287 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-21 03:26:03,287 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-21 03:26:03,295 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-07-21 03:26:03,296 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [595954463] [2022-07-21 03:26:03,296 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-21 03:26:03,296 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-21 03:26:03,296 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-21 03:26:03,299 INFO L229 MonitoredProcess]: Starting monitored process 6 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-07-21 03:26:03,301 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2022-07-21 03:26:03,343 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-21 03:26:03,344 INFO L263 TraceCheckSpWp]: Trace formula consists of 148 conjuncts, 22 conjunts are in the unsatisfiable core [2022-07-21 03:26:03,346 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-21 03:26:03,599 INFO L134 CoverageAnalysis]: Checked inductivity of 78 backedges. 14 proven. 13 refuted. 0 times theorem prover too weak. 51 trivial. 0 not checked. [2022-07-21 03:26:03,600 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-21 03:26:03,766 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-21 03:26:03,766 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [76315569] [2022-07-21 03:26:03,766 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-07-21 03:26:03,766 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [595954463] [2022-07-21 03:26:03,766 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [595954463] provided 0 perfect and 1 imperfect interpolant sequences [2022-07-21 03:26:03,766 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-07-21 03:26:03,766 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11] total 11 [2022-07-21 03:26:03,767 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [16642634] [2022-07-21 03:26:03,767 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2022-07-21 03:26:03,767 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 11 states [2022-07-21 03:26:03,767 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-21 03:26:03,767 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2022-07-21 03:26:03,767 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=32, Invalid=124, Unknown=0, NotChecked=0, Total=156 [2022-07-21 03:26:03,768 INFO L87 Difference]: Start difference. First operand 51 states and 64 transitions. Second operand has 11 states, 11 states have (on average 2.0) internal successors, (22), 9 states have internal predecessors, (22), 4 states have call successors, (10), 2 states have call predecessors, (10), 3 states have return successors, (9), 4 states have call predecessors, (9), 4 states have call successors, (9) [2022-07-21 03:26:03,977 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-21 03:26:03,977 INFO L93 Difference]: Finished difference Result 60 states and 72 transitions. [2022-07-21 03:26:03,977 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2022-07-21 03:26:03,978 INFO L78 Accepts]: Start accepts. Automaton has has 11 states, 11 states have (on average 2.0) internal successors, (22), 9 states have internal predecessors, (22), 4 states have call successors, (10), 2 states have call predecessors, (10), 3 states have return successors, (9), 4 states have call predecessors, (9), 4 states have call successors, (9) Word has length 56 [2022-07-21 03:26:03,978 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-21 03:26:03,978 INFO L225 Difference]: With dead ends: 60 [2022-07-21 03:26:03,978 INFO L226 Difference]: Without dead ends: 58 [2022-07-21 03:26:03,979 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 63 GetRequests, 47 SyntacticMatches, 2 SemanticMatches, 14 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 29 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=47, Invalid=193, Unknown=0, NotChecked=0, Total=240 [2022-07-21 03:26:03,979 INFO L413 NwaCegarLoop]: 24 mSDtfsCounter, 27 mSDsluCounter, 96 mSDsCounter, 0 mSdLazyCounter, 285 mSolverCounterSat, 10 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 33 SdHoareTripleChecker+Valid, 120 SdHoareTripleChecker+Invalid, 295 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 10 IncrementalHoareTripleChecker+Valid, 285 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2022-07-21 03:26:03,979 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [33 Valid, 120 Invalid, 295 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [10 Valid, 285 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2022-07-21 03:26:03,980 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 58 states. [2022-07-21 03:26:03,991 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 58 to 55. [2022-07-21 03:26:03,993 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 55 states, 32 states have (on average 1.125) internal successors, (36), 33 states have internal predecessors, (36), 16 states have call successors, (16), 6 states have call predecessors, (16), 6 states have return successors, (15), 15 states have call predecessors, (15), 15 states have call successors, (15) [2022-07-21 03:26:03,995 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 55 states to 55 states and 67 transitions. [2022-07-21 03:26:03,995 INFO L78 Accepts]: Start accepts. Automaton has 55 states and 67 transitions. Word has length 56 [2022-07-21 03:26:03,995 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-21 03:26:03,995 INFO L495 AbstractCegarLoop]: Abstraction has 55 states and 67 transitions. [2022-07-21 03:26:03,996 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 11 states, 11 states have (on average 2.0) internal successors, (22), 9 states have internal predecessors, (22), 4 states have call successors, (10), 2 states have call predecessors, (10), 3 states have return successors, (9), 4 states have call predecessors, (9), 4 states have call successors, (9) [2022-07-21 03:26:03,996 INFO L276 IsEmpty]: Start isEmpty. Operand 55 states and 67 transitions. [2022-07-21 03:26:03,998 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 66 [2022-07-21 03:26:03,998 INFO L187 NwaCegarLoop]: Found error trace [2022-07-21 03:26:03,999 INFO L195 NwaCegarLoop]: trace histogram [6, 6, 6, 5, 4, 4, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-21 03:26:04,018 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Forceful destruction successful, exit code 0 [2022-07-21 03:26:04,218 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-21 03:26:04,219 INFO L420 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-21 03:26:04,219 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-21 03:26:04,219 INFO L85 PathProgramCache]: Analyzing trace with hash -759965185, now seen corresponding path program 1 times [2022-07-21 03:26:04,219 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-21 03:26:04,219 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [651757338] [2022-07-21 03:26:04,219 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-21 03:26:04,220 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-21 03:26:04,228 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-07-21 03:26:04,229 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1761811763] [2022-07-21 03:26:04,229 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-21 03:26:04,229 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-21 03:26:04,229 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-21 03:26:04,232 INFO L229 MonitoredProcess]: Starting monitored process 7 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-07-21 03:26:04,233 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2022-07-21 03:26:04,272 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-21 03:26:04,273 INFO L263 TraceCheckSpWp]: Trace formula consists of 175 conjuncts, 9 conjunts are in the unsatisfiable core [2022-07-21 03:26:04,275 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-21 03:26:04,322 INFO L134 CoverageAnalysis]: Checked inductivity of 94 backedges. 14 proven. 11 refuted. 0 times theorem prover too weak. 69 trivial. 0 not checked. [2022-07-21 03:26:04,322 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-21 03:26:04,393 INFO L134 CoverageAnalysis]: Checked inductivity of 94 backedges. 14 proven. 11 refuted. 0 times theorem prover too weak. 69 trivial. 0 not checked. [2022-07-21 03:26:04,393 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-21 03:26:04,393 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [651757338] [2022-07-21 03:26:04,393 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-07-21 03:26:04,393 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1761811763] [2022-07-21 03:26:04,394 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1761811763] provided 0 perfect and 2 imperfect interpolant sequences [2022-07-21 03:26:04,394 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-07-21 03:26:04,394 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 9 [2022-07-21 03:26:04,395 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [835030981] [2022-07-21 03:26:04,395 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-07-21 03:26:04,396 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2022-07-21 03:26:04,397 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-21 03:26:04,399 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2022-07-21 03:26:04,400 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=17, Invalid=55, Unknown=0, NotChecked=0, Total=72 [2022-07-21 03:26:04,400 INFO L87 Difference]: Start difference. First operand 55 states and 67 transitions. Second operand has 9 states, 9 states have (on average 2.7777777777777777) internal successors, (25), 8 states have internal predecessors, (25), 5 states have call successors, (11), 2 states have call predecessors, (11), 2 states have return successors, (10), 4 states have call predecessors, (10), 4 states have call successors, (10) [2022-07-21 03:26:04,561 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-21 03:26:04,561 INFO L93 Difference]: Finished difference Result 102 states and 142 transitions. [2022-07-21 03:26:04,561 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2022-07-21 03:26:04,561 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 9 states have (on average 2.7777777777777777) internal successors, (25), 8 states have internal predecessors, (25), 5 states have call successors, (11), 2 states have call predecessors, (11), 2 states have return successors, (10), 4 states have call predecessors, (10), 4 states have call successors, (10) Word has length 65 [2022-07-21 03:26:04,562 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-21 03:26:04,564 INFO L225 Difference]: With dead ends: 102 [2022-07-21 03:26:04,565 INFO L226 Difference]: Without dead ends: 94 [2022-07-21 03:26:04,565 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 133 GetRequests, 120 SyntacticMatches, 1 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 6 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=47, Invalid=135, Unknown=0, NotChecked=0, Total=182 [2022-07-21 03:26:04,566 INFO L413 NwaCegarLoop]: 56 mSDtfsCounter, 32 mSDsluCounter, 139 mSDsCounter, 0 mSdLazyCounter, 142 mSolverCounterSat, 53 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 37 SdHoareTripleChecker+Valid, 195 SdHoareTripleChecker+Invalid, 195 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 53 IncrementalHoareTripleChecker+Valid, 142 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-07-21 03:26:04,566 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [37 Valid, 195 Invalid, 195 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [53 Valid, 142 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-07-21 03:26:04,567 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 94 states. [2022-07-21 03:26:04,590 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 94 to 85. [2022-07-21 03:26:04,590 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 85 states, 46 states have (on average 1.1956521739130435) internal successors, (55), 47 states have internal predecessors, (55), 32 states have call successors, (32), 6 states have call predecessors, (32), 6 states have return successors, (31), 31 states have call predecessors, (31), 31 states have call successors, (31) [2022-07-21 03:26:04,591 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 85 states to 85 states and 118 transitions. [2022-07-21 03:26:04,591 INFO L78 Accepts]: Start accepts. Automaton has 85 states and 118 transitions. Word has length 65 [2022-07-21 03:26:04,592 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-21 03:26:04,592 INFO L495 AbstractCegarLoop]: Abstraction has 85 states and 118 transitions. [2022-07-21 03:26:04,592 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 9 states have (on average 2.7777777777777777) internal successors, (25), 8 states have internal predecessors, (25), 5 states have call successors, (11), 2 states have call predecessors, (11), 2 states have return successors, (10), 4 states have call predecessors, (10), 4 states have call successors, (10) [2022-07-21 03:26:04,592 INFO L276 IsEmpty]: Start isEmpty. Operand 85 states and 118 transitions. [2022-07-21 03:26:04,593 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 72 [2022-07-21 03:26:04,593 INFO L187 NwaCegarLoop]: Found error trace [2022-07-21 03:26:04,593 INFO L195 NwaCegarLoop]: trace histogram [6, 6, 6, 6, 5, 5, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-21 03:26:04,612 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Forceful destruction successful, exit code 0 [2022-07-21 03:26:04,795 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-21 03:26:04,796 INFO L420 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-21 03:26:04,796 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-21 03:26:04,796 INFO L85 PathProgramCache]: Analyzing trace with hash -696294669, now seen corresponding path program 1 times [2022-07-21 03:26:04,796 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-21 03:26:04,796 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1877447164] [2022-07-21 03:26:04,796 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-21 03:26:04,797 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-21 03:26:04,805 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-07-21 03:26:04,805 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1511676135] [2022-07-21 03:26:04,805 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-21 03:26:04,806 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-21 03:26:04,806 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-21 03:26:04,807 INFO L229 MonitoredProcess]: Starting monitored process 8 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-07-21 03:26:04,808 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2022-07-21 03:26:04,849 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-21 03:26:04,851 INFO L263 TraceCheckSpWp]: Trace formula consists of 188 conjuncts, 26 conjunts are in the unsatisfiable core [2022-07-21 03:26:04,853 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-21 03:26:04,966 INFO L134 CoverageAnalysis]: Checked inductivity of 115 backedges. 15 proven. 12 refuted. 0 times theorem prover too weak. 88 trivial. 0 not checked. [2022-07-21 03:26:04,967 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-21 03:26:05,052 INFO L134 CoverageAnalysis]: Checked inductivity of 115 backedges. 20 proven. 7 refuted. 0 times theorem prover too weak. 88 trivial. 0 not checked. [2022-07-21 03:26:05,052 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-21 03:26:05,052 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1877447164] [2022-07-21 03:26:05,052 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-07-21 03:26:05,052 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1511676135] [2022-07-21 03:26:05,053 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1511676135] provided 0 perfect and 2 imperfect interpolant sequences [2022-07-21 03:26:05,053 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-07-21 03:26:05,053 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 8] total 12 [2022-07-21 03:26:05,053 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [66706303] [2022-07-21 03:26:05,053 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-07-21 03:26:05,054 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2022-07-21 03:26:05,054 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-21 03:26:05,054 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2022-07-21 03:26:05,055 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=28, Invalid=104, Unknown=0, NotChecked=0, Total=132 [2022-07-21 03:26:05,055 INFO L87 Difference]: Start difference. First operand 85 states and 118 transitions. Second operand has 12 states, 12 states have (on average 2.9166666666666665) internal successors, (35), 11 states have internal predecessors, (35), 6 states have call successors, (20), 2 states have call predecessors, (20), 2 states have return successors, (18), 6 states have call predecessors, (18), 6 states have call successors, (18) [2022-07-21 03:26:05,341 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-21 03:26:05,341 INFO L93 Difference]: Finished difference Result 128 states and 183 transitions. [2022-07-21 03:26:05,342 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2022-07-21 03:26:05,342 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 12 states have (on average 2.9166666666666665) internal successors, (35), 11 states have internal predecessors, (35), 6 states have call successors, (20), 2 states have call predecessors, (20), 2 states have return successors, (18), 6 states have call predecessors, (18), 6 states have call successors, (18) Word has length 71 [2022-07-21 03:26:05,342 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-21 03:26:05,344 INFO L225 Difference]: With dead ends: 128 [2022-07-21 03:26:05,344 INFO L226 Difference]: Without dead ends: 124 [2022-07-21 03:26:05,344 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 150 GetRequests, 132 SyntacticMatches, 2 SemanticMatches, 16 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 27 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=65, Invalid=241, Unknown=0, NotChecked=0, Total=306 [2022-07-21 03:26:05,345 INFO L413 NwaCegarLoop]: 42 mSDtfsCounter, 37 mSDsluCounter, 123 mSDsCounter, 0 mSdLazyCounter, 310 mSolverCounterSat, 65 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 43 SdHoareTripleChecker+Valid, 165 SdHoareTripleChecker+Invalid, 375 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 65 IncrementalHoareTripleChecker+Valid, 310 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2022-07-21 03:26:05,345 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [43 Valid, 165 Invalid, 375 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [65 Valid, 310 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2022-07-21 03:26:05,346 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 124 states. [2022-07-21 03:26:05,356 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 124 to 92. [2022-07-21 03:26:05,356 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 92 states, 50 states have (on average 1.18) internal successors, (59), 52 states have internal predecessors, (59), 34 states have call successors, (34), 7 states have call predecessors, (34), 7 states have return successors, (33), 32 states have call predecessors, (33), 33 states have call successors, (33) [2022-07-21 03:26:05,357 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 92 states to 92 states and 126 transitions. [2022-07-21 03:26:05,357 INFO L78 Accepts]: Start accepts. Automaton has 92 states and 126 transitions. Word has length 71 [2022-07-21 03:26:05,357 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-21 03:26:05,357 INFO L495 AbstractCegarLoop]: Abstraction has 92 states and 126 transitions. [2022-07-21 03:26:05,358 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 12 states have (on average 2.9166666666666665) internal successors, (35), 11 states have internal predecessors, (35), 6 states have call successors, (20), 2 states have call predecessors, (20), 2 states have return successors, (18), 6 states have call predecessors, (18), 6 states have call successors, (18) [2022-07-21 03:26:05,358 INFO L276 IsEmpty]: Start isEmpty. Operand 92 states and 126 transitions. [2022-07-21 03:26:05,359 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 77 [2022-07-21 03:26:05,359 INFO L187 NwaCegarLoop]: Found error trace [2022-07-21 03:26:05,359 INFO L195 NwaCegarLoop]: trace histogram [7, 6, 6, 6, 6, 6, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-21 03:26:05,382 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Forceful destruction successful, exit code 0 [2022-07-21 03:26:05,580 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-21 03:26:05,580 INFO L420 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-21 03:26:05,580 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-21 03:26:05,580 INFO L85 PathProgramCache]: Analyzing trace with hash 1352497678, now seen corresponding path program 2 times [2022-07-21 03:26:05,581 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-21 03:26:05,581 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1727680311] [2022-07-21 03:26:05,581 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-21 03:26:05,581 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-21 03:26:05,589 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-07-21 03:26:05,590 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1892238581] [2022-07-21 03:26:05,590 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-07-21 03:26:05,590 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-21 03:26:05,590 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-21 03:26:05,593 INFO L229 MonitoredProcess]: Starting monitored process 9 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-07-21 03:26:05,595 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2022-07-21 03:26:05,645 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-07-21 03:26:05,646 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-07-21 03:26:05,650 INFO L263 TraceCheckSpWp]: Trace formula consists of 197 conjuncts, 39 conjunts are in the unsatisfiable core [2022-07-21 03:26:05,652 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-21 03:26:05,925 INFO L134 CoverageAnalysis]: Checked inductivity of 138 backedges. 24 proven. 18 refuted. 0 times theorem prover too weak. 96 trivial. 0 not checked. [2022-07-21 03:26:05,925 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-21 03:26:06,084 INFO L134 CoverageAnalysis]: Checked inductivity of 138 backedges. 12 proven. 6 refuted. 0 times theorem prover too weak. 120 trivial. 0 not checked. [2022-07-21 03:26:06,084 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-21 03:26:06,084 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1727680311] [2022-07-21 03:26:06,084 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-07-21 03:26:06,084 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1892238581] [2022-07-21 03:26:06,084 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1892238581] provided 0 perfect and 2 imperfect interpolant sequences [2022-07-21 03:26:06,084 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-07-21 03:26:06,084 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 7] total 14 [2022-07-21 03:26:06,084 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2070782760] [2022-07-21 03:26:06,084 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-07-21 03:26:06,085 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2022-07-21 03:26:06,085 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-21 03:26:06,085 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2022-07-21 03:26:06,085 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=35, Invalid=147, Unknown=0, NotChecked=0, Total=182 [2022-07-21 03:26:06,086 INFO L87 Difference]: Start difference. First operand 92 states and 126 transitions. Second operand has 14 states, 13 states have (on average 2.5384615384615383) internal successors, (33), 11 states have internal predecessors, (33), 8 states have call successors, (23), 2 states have call predecessors, (23), 2 states have return successors, (22), 9 states have call predecessors, (22), 8 states have call successors, (22) [2022-07-21 03:26:09,636 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-07-21 03:26:11,949 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-07-21 03:26:12,796 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-21 03:26:12,796 INFO L93 Difference]: Finished difference Result 236 states and 350 transitions. [2022-07-21 03:26:12,796 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 18 states. [2022-07-21 03:26:12,797 INFO L78 Accepts]: Start accepts. Automaton has has 14 states, 13 states have (on average 2.5384615384615383) internal successors, (33), 11 states have internal predecessors, (33), 8 states have call successors, (23), 2 states have call predecessors, (23), 2 states have return successors, (22), 9 states have call predecessors, (22), 8 states have call successors, (22) Word has length 76 [2022-07-21 03:26:12,797 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-21 03:26:12,798 INFO L225 Difference]: With dead ends: 236 [2022-07-21 03:26:12,798 INFO L226 Difference]: Without dead ends: 234 [2022-07-21 03:26:12,799 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 162 GetRequests, 137 SyntacticMatches, 1 SemanticMatches, 24 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 109 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=145, Invalid=505, Unknown=0, NotChecked=0, Total=650 [2022-07-21 03:26:12,799 INFO L413 NwaCegarLoop]: 46 mSDtfsCounter, 83 mSDsluCounter, 191 mSDsCounter, 0 mSdLazyCounter, 496 mSolverCounterSat, 129 mSolverCounterUnsat, 2 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 6.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 88 SdHoareTripleChecker+Valid, 237 SdHoareTripleChecker+Invalid, 627 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 129 IncrementalHoareTripleChecker+Valid, 496 IncrementalHoareTripleChecker+Invalid, 2 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 6.3s IncrementalHoareTripleChecker+Time [2022-07-21 03:26:12,799 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [88 Valid, 237 Invalid, 627 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [129 Valid, 496 Invalid, 2 Unknown, 0 Unchecked, 6.3s Time] [2022-07-21 03:26:12,800 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 234 states. [2022-07-21 03:26:12,844 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 234 to 225. [2022-07-21 03:26:12,845 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 225 states, 117 states have (on average 1.2478632478632479) internal successors, (146), 120 states have internal predecessors, (146), 97 states have call successors, (97), 10 states have call predecessors, (97), 10 states have return successors, (96), 94 states have call predecessors, (96), 96 states have call successors, (96) [2022-07-21 03:26:12,847 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 225 states to 225 states and 339 transitions. [2022-07-21 03:26:12,847 INFO L78 Accepts]: Start accepts. Automaton has 225 states and 339 transitions. Word has length 76 [2022-07-21 03:26:12,847 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-21 03:26:12,847 INFO L495 AbstractCegarLoop]: Abstraction has 225 states and 339 transitions. [2022-07-21 03:26:12,848 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 14 states, 13 states have (on average 2.5384615384615383) internal successors, (33), 11 states have internal predecessors, (33), 8 states have call successors, (23), 2 states have call predecessors, (23), 2 states have return successors, (22), 9 states have call predecessors, (22), 8 states have call successors, (22) [2022-07-21 03:26:12,848 INFO L276 IsEmpty]: Start isEmpty. Operand 225 states and 339 transitions. [2022-07-21 03:26:12,848 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 82 [2022-07-21 03:26:12,849 INFO L187 NwaCegarLoop]: Found error trace [2022-07-21 03:26:12,849 INFO L195 NwaCegarLoop]: trace histogram [8, 7, 7, 6, 6, 6, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-21 03:26:12,872 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Forceful destruction successful, exit code 0 [2022-07-21 03:26:13,069 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 9 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable8 [2022-07-21 03:26:13,070 INFO L420 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-21 03:26:13,070 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-21 03:26:13,070 INFO L85 PathProgramCache]: Analyzing trace with hash -421153901, now seen corresponding path program 3 times [2022-07-21 03:26:13,070 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-21 03:26:13,070 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1002108435] [2022-07-21 03:26:13,070 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-21 03:26:13,070 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-21 03:26:13,088 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-07-21 03:26:13,088 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [992417001] [2022-07-21 03:26:13,088 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2022-07-21 03:26:13,089 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-21 03:26:13,089 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-21 03:26:13,092 INFO L229 MonitoredProcess]: Starting monitored process 10 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-07-21 03:26:13,093 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Waiting until timeout for monitored process [2022-07-21 03:26:13,132 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2022-07-21 03:26:13,132 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-07-21 03:26:13,133 INFO L263 TraceCheckSpWp]: Trace formula consists of 148 conjuncts, 43 conjunts are in the unsatisfiable core [2022-07-21 03:26:13,135 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-21 03:26:13,899 INFO L134 CoverageAnalysis]: Checked inductivity of 165 backedges. 31 proven. 23 refuted. 0 times theorem prover too weak. 111 trivial. 0 not checked. [2022-07-21 03:26:13,899 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-21 03:26:13,988 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-21 03:26:13,989 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1002108435] [2022-07-21 03:26:13,989 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-07-21 03:26:13,989 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [992417001] [2022-07-21 03:26:13,989 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [992417001] provided 0 perfect and 1 imperfect interpolant sequences [2022-07-21 03:26:13,989 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-07-21 03:26:13,989 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [15] total 15 [2022-07-21 03:26:13,990 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [306183430] [2022-07-21 03:26:13,990 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2022-07-21 03:26:13,991 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 15 states [2022-07-21 03:26:13,991 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-21 03:26:13,991 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2022-07-21 03:26:13,991 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=46, Invalid=226, Unknown=0, NotChecked=0, Total=272 [2022-07-21 03:26:13,992 INFO L87 Difference]: Start difference. First operand 225 states and 339 transitions. Second operand has 15 states, 14 states have (on average 1.9285714285714286) internal successors, (27), 13 states have internal predecessors, (27), 6 states have call successors, (14), 2 states have call predecessors, (14), 3 states have return successors, (13), 5 states have call predecessors, (13), 5 states have call successors, (13) [2022-07-21 03:26:14,655 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-21 03:26:14,656 INFO L93 Difference]: Finished difference Result 241 states and 352 transitions. [2022-07-21 03:26:14,656 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2022-07-21 03:26:14,656 INFO L78 Accepts]: Start accepts. Automaton has has 15 states, 14 states have (on average 1.9285714285714286) internal successors, (27), 13 states have internal predecessors, (27), 6 states have call successors, (14), 2 states have call predecessors, (14), 3 states have return successors, (13), 5 states have call predecessors, (13), 5 states have call successors, (13) Word has length 81 [2022-07-21 03:26:14,656 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-21 03:26:14,658 INFO L225 Difference]: With dead ends: 241 [2022-07-21 03:26:14,658 INFO L226 Difference]: Without dead ends: 239 [2022-07-21 03:26:14,659 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 91 GetRequests, 69 SyntacticMatches, 1 SemanticMatches, 21 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 94 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=81, Invalid=425, Unknown=0, NotChecked=0, Total=506 [2022-07-21 03:26:14,659 INFO L413 NwaCegarLoop]: 31 mSDtfsCounter, 38 mSDsluCounter, 118 mSDsCounter, 0 mSdLazyCounter, 521 mSolverCounterSat, 26 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 49 SdHoareTripleChecker+Valid, 149 SdHoareTripleChecker+Invalid, 547 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 26 IncrementalHoareTripleChecker+Valid, 521 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.5s IncrementalHoareTripleChecker+Time [2022-07-21 03:26:14,659 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [49 Valid, 149 Invalid, 547 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [26 Valid, 521 Invalid, 0 Unknown, 0 Unchecked, 0.5s Time] [2022-07-21 03:26:14,660 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 239 states. [2022-07-21 03:26:14,689 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 239 to 237. [2022-07-21 03:26:14,689 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 237 states, 126 states have (on average 1.2301587301587302) internal successors, (155), 129 states have internal predecessors, (155), 97 states have call successors, (97), 13 states have call predecessors, (97), 13 states have return successors, (96), 94 states have call predecessors, (96), 96 states have call successors, (96) [2022-07-21 03:26:14,691 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 237 states to 237 states and 348 transitions. [2022-07-21 03:26:14,691 INFO L78 Accepts]: Start accepts. Automaton has 237 states and 348 transitions. Word has length 81 [2022-07-21 03:26:14,693 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-21 03:26:14,693 INFO L495 AbstractCegarLoop]: Abstraction has 237 states and 348 transitions. [2022-07-21 03:26:14,693 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 15 states, 14 states have (on average 1.9285714285714286) internal successors, (27), 13 states have internal predecessors, (27), 6 states have call successors, (14), 2 states have call predecessors, (14), 3 states have return successors, (13), 5 states have call predecessors, (13), 5 states have call successors, (13) [2022-07-21 03:26:14,693 INFO L276 IsEmpty]: Start isEmpty. Operand 237 states and 348 transitions. [2022-07-21 03:26:14,694 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 88 [2022-07-21 03:26:14,695 INFO L187 NwaCegarLoop]: Found error trace [2022-07-21 03:26:14,695 INFO L195 NwaCegarLoop]: trace histogram [9, 8, 8, 6, 6, 6, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-21 03:26:14,714 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Ended with exit code 0 [2022-07-21 03:26:14,911 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 10 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable9 [2022-07-21 03:26:14,911 INFO L420 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-21 03:26:14,912 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-21 03:26:14,912 INFO L85 PathProgramCache]: Analyzing trace with hash -1712962370, now seen corresponding path program 1 times [2022-07-21 03:26:14,912 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-21 03:26:14,912 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1600984031] [2022-07-21 03:26:14,912 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-21 03:26:14,912 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-21 03:26:14,919 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-07-21 03:26:14,919 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [938670537] [2022-07-21 03:26:14,919 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-21 03:26:14,919 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-21 03:26:14,920 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-21 03:26:14,922 INFO L229 MonitoredProcess]: Starting monitored process 11 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-07-21 03:26:14,923 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Waiting until timeout for monitored process [2022-07-21 03:26:14,966 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-21 03:26:14,968 INFO L263 TraceCheckSpWp]: Trace formula consists of 217 conjuncts, 38 conjunts are in the unsatisfiable core [2022-07-21 03:26:14,969 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-21 03:26:15,214 INFO L134 CoverageAnalysis]: Checked inductivity of 196 backedges. 30 proven. 15 refuted. 0 times theorem prover too weak. 151 trivial. 0 not checked. [2022-07-21 03:26:15,214 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-21 03:26:15,474 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-21 03:26:15,474 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1600984031] [2022-07-21 03:26:15,474 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-07-21 03:26:15,474 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [938670537] [2022-07-21 03:26:15,474 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [938670537] provided 0 perfect and 1 imperfect interpolant sequences [2022-07-21 03:26:15,475 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-07-21 03:26:15,475 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12] total 12 [2022-07-21 03:26:15,475 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1835815477] [2022-07-21 03:26:15,475 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2022-07-21 03:26:15,475 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2022-07-21 03:26:15,475 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-21 03:26:15,476 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2022-07-21 03:26:15,476 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=40, Invalid=200, Unknown=0, NotChecked=0, Total=240 [2022-07-21 03:26:15,476 INFO L87 Difference]: Start difference. First operand 237 states and 348 transitions. Second operand has 12 states, 11 states have (on average 2.272727272727273) internal successors, (25), 11 states have internal predecessors, (25), 6 states have call successors, (15), 2 states have call predecessors, (15), 2 states have return successors, (14), 5 states have call predecessors, (14), 5 states have call successors, (14) [2022-07-21 03:26:15,915 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-21 03:26:15,916 INFO L93 Difference]: Finished difference Result 280 states and 403 transitions. [2022-07-21 03:26:15,916 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2022-07-21 03:26:15,916 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 11 states have (on average 2.272727272727273) internal successors, (25), 11 states have internal predecessors, (25), 6 states have call successors, (15), 2 states have call predecessors, (15), 2 states have return successors, (14), 5 states have call predecessors, (14), 5 states have call successors, (14) Word has length 87 [2022-07-21 03:26:15,917 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-21 03:26:15,920 INFO L225 Difference]: With dead ends: 280 [2022-07-21 03:26:15,920 INFO L226 Difference]: Without dead ends: 273 [2022-07-21 03:26:15,921 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 110 GetRequests, 90 SyntacticMatches, 1 SemanticMatches, 19 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 40 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=72, Invalid=348, Unknown=0, NotChecked=0, Total=420 [2022-07-21 03:26:15,921 INFO L413 NwaCegarLoop]: 39 mSDtfsCounter, 25 mSDsluCounter, 205 mSDsCounter, 0 mSdLazyCounter, 516 mSolverCounterSat, 20 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 33 SdHoareTripleChecker+Valid, 244 SdHoareTripleChecker+Invalid, 536 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 20 IncrementalHoareTripleChecker+Valid, 516 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2022-07-21 03:26:15,922 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [33 Valid, 244 Invalid, 536 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [20 Valid, 516 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2022-07-21 03:26:15,922 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 273 states. [2022-07-21 03:26:15,958 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 273 to 270. [2022-07-21 03:26:15,959 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 270 states, 144 states have (on average 1.2222222222222223) internal successors, (176), 147 states have internal predecessors, (176), 109 states have call successors, (109), 16 states have call predecessors, (109), 16 states have return successors, (108), 106 states have call predecessors, (108), 108 states have call successors, (108) [2022-07-21 03:26:15,962 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 270 states to 270 states and 393 transitions. [2022-07-21 03:26:15,962 INFO L78 Accepts]: Start accepts. Automaton has 270 states and 393 transitions. Word has length 87 [2022-07-21 03:26:15,962 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-21 03:26:15,962 INFO L495 AbstractCegarLoop]: Abstraction has 270 states and 393 transitions. [2022-07-21 03:26:15,962 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 11 states have (on average 2.272727272727273) internal successors, (25), 11 states have internal predecessors, (25), 6 states have call successors, (15), 2 states have call predecessors, (15), 2 states have return successors, (14), 5 states have call predecessors, (14), 5 states have call successors, (14) [2022-07-21 03:26:15,962 INFO L276 IsEmpty]: Start isEmpty. Operand 270 states and 393 transitions. [2022-07-21 03:26:15,963 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 104 [2022-07-21 03:26:15,963 INFO L187 NwaCegarLoop]: Found error trace [2022-07-21 03:26:15,964 INFO L195 NwaCegarLoop]: trace histogram [12, 11, 11, 6, 6, 6, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-21 03:26:15,980 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Forceful destruction successful, exit code 0 [2022-07-21 03:26:16,174 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 11 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable10 [2022-07-21 03:26:16,175 INFO L420 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-21 03:26:16,175 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-21 03:26:16,175 INFO L85 PathProgramCache]: Analyzing trace with hash -1899970478, now seen corresponding path program 1 times [2022-07-21 03:26:16,175 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-21 03:26:16,175 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1132316145] [2022-07-21 03:26:16,176 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-21 03:26:16,176 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-21 03:26:16,194 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-07-21 03:26:16,198 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1097777863] [2022-07-21 03:26:16,198 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-21 03:26:16,198 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-21 03:26:16,198 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-21 03:26:16,200 INFO L229 MonitoredProcess]: Starting monitored process 12 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-07-21 03:26:16,201 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Waiting until timeout for monitored process [2022-07-21 03:26:16,258 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-21 03:26:16,259 INFO L263 TraceCheckSpWp]: Trace formula consists of 248 conjuncts, 40 conjunts are in the unsatisfiable core [2022-07-21 03:26:16,261 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-21 03:26:16,690 INFO L134 CoverageAnalysis]: Checked inductivity of 320 backedges. 51 proven. 19 refuted. 0 times theorem prover too weak. 250 trivial. 0 not checked. [2022-07-21 03:26:16,691 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-21 03:26:17,064 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-21 03:26:17,064 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1132316145] [2022-07-21 03:26:17,065 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-07-21 03:26:17,065 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1097777863] [2022-07-21 03:26:17,065 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1097777863] provided 0 perfect and 1 imperfect interpolant sequences [2022-07-21 03:26:17,065 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-07-21 03:26:17,065 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11] total 11 [2022-07-21 03:26:17,065 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [495904461] [2022-07-21 03:26:17,065 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2022-07-21 03:26:17,065 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 11 states [2022-07-21 03:26:17,065 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-21 03:26:17,065 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2022-07-21 03:26:17,066 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=46, Invalid=164, Unknown=0, NotChecked=0, Total=210 [2022-07-21 03:26:17,066 INFO L87 Difference]: Start difference. First operand 270 states and 393 transitions. Second operand has 11 states, 10 states have (on average 2.6) internal successors, (26), 9 states have internal predecessors, (26), 6 states have call successors, (18), 2 states have call predecessors, (18), 2 states have return successors, (17), 6 states have call predecessors, (17), 5 states have call successors, (17) [2022-07-21 03:26:17,571 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-21 03:26:17,571 INFO L93 Difference]: Finished difference Result 279 states and 401 transitions. [2022-07-21 03:26:17,572 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2022-07-21 03:26:17,572 INFO L78 Accepts]: Start accepts. Automaton has has 11 states, 10 states have (on average 2.6) internal successors, (26), 9 states have internal predecessors, (26), 6 states have call successors, (18), 2 states have call predecessors, (18), 2 states have return successors, (17), 6 states have call predecessors, (17), 5 states have call successors, (17) Word has length 103 [2022-07-21 03:26:17,572 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-21 03:26:17,574 INFO L225 Difference]: With dead ends: 279 [2022-07-21 03:26:17,575 INFO L226 Difference]: Without dead ends: 277 [2022-07-21 03:26:17,575 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 131 GetRequests, 113 SyntacticMatches, 1 SemanticMatches, 17 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 31 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=73, Invalid=269, Unknown=0, NotChecked=0, Total=342 [2022-07-21 03:26:17,576 INFO L413 NwaCegarLoop]: 46 mSDtfsCounter, 23 mSDsluCounter, 171 mSDsCounter, 0 mSdLazyCounter, 473 mSolverCounterSat, 23 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 31 SdHoareTripleChecker+Valid, 217 SdHoareTripleChecker+Invalid, 496 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 23 IncrementalHoareTripleChecker+Valid, 473 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2022-07-21 03:26:17,576 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [31 Valid, 217 Invalid, 496 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [23 Valid, 473 Invalid, 0 Unknown, 0 Unchecked, 0.4s Time] [2022-07-21 03:26:17,577 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 277 states. [2022-07-21 03:26:17,615 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 277 to 274. [2022-07-21 03:26:17,616 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 274 states, 147 states have (on average 1.217687074829932) internal successors, (179), 150 states have internal predecessors, (179), 109 states have call successors, (109), 17 states have call predecessors, (109), 17 states have return successors, (108), 106 states have call predecessors, (108), 108 states have call successors, (108) [2022-07-21 03:26:17,618 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 274 states to 274 states and 396 transitions. [2022-07-21 03:26:17,619 INFO L78 Accepts]: Start accepts. Automaton has 274 states and 396 transitions. Word has length 103 [2022-07-21 03:26:17,619 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-21 03:26:17,619 INFO L495 AbstractCegarLoop]: Abstraction has 274 states and 396 transitions. [2022-07-21 03:26:17,619 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 11 states, 10 states have (on average 2.6) internal successors, (26), 9 states have internal predecessors, (26), 6 states have call successors, (18), 2 states have call predecessors, (18), 2 states have return successors, (17), 6 states have call predecessors, (17), 5 states have call successors, (17) [2022-07-21 03:26:17,619 INFO L276 IsEmpty]: Start isEmpty. Operand 274 states and 396 transitions. [2022-07-21 03:26:17,621 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 107 [2022-07-21 03:26:17,621 INFO L187 NwaCegarLoop]: Found error trace [2022-07-21 03:26:17,621 INFO L195 NwaCegarLoop]: trace histogram [12, 11, 11, 6, 6, 6, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-21 03:26:17,639 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Forceful destruction successful, exit code 0 [2022-07-21 03:26:17,838 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 12 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable11 [2022-07-21 03:26:17,838 INFO L420 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-21 03:26:17,839 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-21 03:26:17,839 INFO L85 PathProgramCache]: Analyzing trace with hash -992204181, now seen corresponding path program 4 times [2022-07-21 03:26:17,839 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-21 03:26:17,839 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1930635176] [2022-07-21 03:26:17,839 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-21 03:26:17,839 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-21 03:26:17,849 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-07-21 03:26:17,857 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1359398558] [2022-07-21 03:26:17,857 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2022-07-21 03:26:17,857 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-21 03:26:17,858 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-21 03:26:17,859 INFO L229 MonitoredProcess]: Starting monitored process 13 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-07-21 03:26:17,860 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Waiting until timeout for monitored process [2022-07-21 03:26:17,910 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2022-07-21 03:26:17,910 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-07-21 03:26:17,911 INFO L263 TraceCheckSpWp]: Trace formula consists of 219 conjuncts, 5 conjunts are in the unsatisfiable core [2022-07-21 03:26:17,914 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-21 03:26:17,932 INFO L134 CoverageAnalysis]: Checked inductivity of 325 backedges. 135 proven. 0 refuted. 0 times theorem prover too weak. 190 trivial. 0 not checked. [2022-07-21 03:26:17,932 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-07-21 03:26:17,932 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-21 03:26:17,932 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1930635176] [2022-07-21 03:26:17,932 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-07-21 03:26:17,933 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1359398558] [2022-07-21 03:26:17,933 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1359398558] provided 1 perfect and 0 imperfect interpolant sequences [2022-07-21 03:26:17,933 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-07-21 03:26:17,933 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-07-21 03:26:17,933 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1120898005] [2022-07-21 03:26:17,933 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-07-21 03:26:17,934 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-07-21 03:26:17,934 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-21 03:26:17,934 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-07-21 03:26:17,934 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-07-21 03:26:17,934 INFO L87 Difference]: Start difference. First operand 274 states and 396 transitions. Second operand has 5 states, 5 states have (on average 5.6) internal successors, (28), 5 states have internal predecessors, (28), 3 states have call successors, (18), 2 states have call predecessors, (18), 2 states have return successors, (17), 3 states have call predecessors, (17), 3 states have call successors, (17) [2022-07-21 03:26:18,013 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-21 03:26:18,013 INFO L93 Difference]: Finished difference Result 346 states and 495 transitions. [2022-07-21 03:26:18,014 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2022-07-21 03:26:18,014 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 5.6) internal successors, (28), 5 states have internal predecessors, (28), 3 states have call successors, (18), 2 states have call predecessors, (18), 2 states have return successors, (17), 3 states have call predecessors, (17), 3 states have call successors, (17) Word has length 106 [2022-07-21 03:26:18,014 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-21 03:26:18,015 INFO L225 Difference]: With dead ends: 346 [2022-07-21 03:26:18,015 INFO L226 Difference]: Without dead ends: 185 [2022-07-21 03:26:18,018 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 107 GetRequests, 102 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=15, Invalid=27, Unknown=0, NotChecked=0, Total=42 [2022-07-21 03:26:18,019 INFO L413 NwaCegarLoop]: 52 mSDtfsCounter, 6 mSDsluCounter, 93 mSDsCounter, 0 mSdLazyCounter, 64 mSolverCounterSat, 5 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 10 SdHoareTripleChecker+Valid, 145 SdHoareTripleChecker+Invalid, 69 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 5 IncrementalHoareTripleChecker+Valid, 64 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-07-21 03:26:18,019 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [10 Valid, 145 Invalid, 69 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [5 Valid, 64 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-07-21 03:26:18,020 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 185 states. [2022-07-21 03:26:18,045 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 185 to 176. [2022-07-21 03:26:18,046 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 176 states, 99 states have (on average 1.121212121212121) internal successors, (111), 100 states have internal predecessors, (111), 59 states have call successors, (59), 17 states have call predecessors, (59), 17 states have return successors, (58), 58 states have call predecessors, (58), 58 states have call successors, (58) [2022-07-21 03:26:18,047 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 176 states to 176 states and 228 transitions. [2022-07-21 03:26:18,047 INFO L78 Accepts]: Start accepts. Automaton has 176 states and 228 transitions. Word has length 106 [2022-07-21 03:26:18,047 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-21 03:26:18,048 INFO L495 AbstractCegarLoop]: Abstraction has 176 states and 228 transitions. [2022-07-21 03:26:18,048 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 5.6) internal successors, (28), 5 states have internal predecessors, (28), 3 states have call successors, (18), 2 states have call predecessors, (18), 2 states have return successors, (17), 3 states have call predecessors, (17), 3 states have call successors, (17) [2022-07-21 03:26:18,048 INFO L276 IsEmpty]: Start isEmpty. Operand 176 states and 228 transitions. [2022-07-21 03:26:18,050 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 110 [2022-07-21 03:26:18,050 INFO L187 NwaCegarLoop]: Found error trace [2022-07-21 03:26:18,050 INFO L195 NwaCegarLoop]: trace histogram [13, 12, 12, 6, 6, 6, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-21 03:26:18,075 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Forceful destruction successful, exit code 0 [2022-07-21 03:26:18,270 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 13 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable12 [2022-07-21 03:26:18,271 INFO L420 AbstractCegarLoop]: === Iteration 14 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-21 03:26:18,271 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-21 03:26:18,271 INFO L85 PathProgramCache]: Analyzing trace with hash -200374723, now seen corresponding path program 2 times [2022-07-21 03:26:18,271 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-21 03:26:18,271 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1056004688] [2022-07-21 03:26:18,271 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-21 03:26:18,272 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-21 03:26:18,280 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-07-21 03:26:18,281 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2025332392] [2022-07-21 03:26:18,281 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-07-21 03:26:18,281 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-21 03:26:18,281 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-21 03:26:18,282 INFO L229 MonitoredProcess]: Starting monitored process 14 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-07-21 03:26:18,283 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Waiting until timeout for monitored process [2022-07-21 03:26:18,330 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-07-21 03:26:18,330 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-07-21 03:26:18,332 INFO L263 TraceCheckSpWp]: Trace formula consists of 259 conjuncts, 40 conjunts are in the unsatisfiable core [2022-07-21 03:26:18,334 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-21 03:26:18,742 INFO L134 CoverageAnalysis]: Checked inductivity of 368 backedges. 47 proven. 30 refuted. 0 times theorem prover too weak. 291 trivial. 0 not checked. [2022-07-21 03:26:18,743 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-21 03:26:18,944 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-21 03:26:18,944 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1056004688] [2022-07-21 03:26:18,944 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-07-21 03:26:18,944 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2025332392] [2022-07-21 03:26:18,944 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2025332392] provided 0 perfect and 1 imperfect interpolant sequences [2022-07-21 03:26:18,944 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-07-21 03:26:18,944 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13] total 13 [2022-07-21 03:26:18,944 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [503949727] [2022-07-21 03:26:18,944 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2022-07-21 03:26:18,945 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 13 states [2022-07-21 03:26:18,945 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-21 03:26:18,945 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2022-07-21 03:26:18,945 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=48, Invalid=224, Unknown=0, NotChecked=0, Total=272 [2022-07-21 03:26:18,945 INFO L87 Difference]: Start difference. First operand 176 states and 228 transitions. Second operand has 13 states, 12 states have (on average 2.25) internal successors, (27), 12 states have internal predecessors, (27), 7 states have call successors, (19), 2 states have call predecessors, (19), 2 states have return successors, (18), 5 states have call predecessors, (18), 6 states have call successors, (18) [2022-07-21 03:26:19,964 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-21 03:26:19,965 INFO L93 Difference]: Finished difference Result 214 states and 278 transitions. [2022-07-21 03:26:19,965 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2022-07-21 03:26:19,965 INFO L78 Accepts]: Start accepts. Automaton has has 13 states, 12 states have (on average 2.25) internal successors, (27), 12 states have internal predecessors, (27), 7 states have call successors, (19), 2 states have call predecessors, (19), 2 states have return successors, (18), 5 states have call predecessors, (18), 6 states have call successors, (18) Word has length 109 [2022-07-21 03:26:19,966 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-21 03:26:19,966 INFO L225 Difference]: With dead ends: 214 [2022-07-21 03:26:19,967 INFO L226 Difference]: Without dead ends: 207 [2022-07-21 03:26:19,967 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 136 GetRequests, 116 SyntacticMatches, 1 SemanticMatches, 19 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 69 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=73, Invalid=347, Unknown=0, NotChecked=0, Total=420 [2022-07-21 03:26:19,967 INFO L413 NwaCegarLoop]: 48 mSDtfsCounter, 26 mSDsluCounter, 202 mSDsCounter, 0 mSdLazyCounter, 608 mSolverCounterSat, 33 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 35 SdHoareTripleChecker+Valid, 250 SdHoareTripleChecker+Invalid, 641 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 33 IncrementalHoareTripleChecker+Valid, 608 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.5s IncrementalHoareTripleChecker+Time [2022-07-21 03:26:19,967 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [35 Valid, 250 Invalid, 641 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [33 Valid, 608 Invalid, 0 Unknown, 0 Unchecked, 0.5s Time] [2022-07-21 03:26:19,968 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 207 states. [2022-07-21 03:26:19,996 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 207 to 205. [2022-07-21 03:26:19,997 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 205 states, 114 states have (on average 1.1228070175438596) internal successors, (128), 115 states have internal predecessors, (128), 71 states have call successors, (71), 19 states have call predecessors, (71), 19 states have return successors, (70), 70 states have call predecessors, (70), 70 states have call successors, (70) [2022-07-21 03:26:19,998 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 205 states to 205 states and 269 transitions. [2022-07-21 03:26:19,998 INFO L78 Accepts]: Start accepts. Automaton has 205 states and 269 transitions. Word has length 109 [2022-07-21 03:26:19,998 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-21 03:26:19,998 INFO L495 AbstractCegarLoop]: Abstraction has 205 states and 269 transitions. [2022-07-21 03:26:19,998 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 13 states, 12 states have (on average 2.25) internal successors, (27), 12 states have internal predecessors, (27), 7 states have call successors, (19), 2 states have call predecessors, (19), 2 states have return successors, (18), 5 states have call predecessors, (18), 6 states have call successors, (18) [2022-07-21 03:26:19,998 INFO L276 IsEmpty]: Start isEmpty. Operand 205 states and 269 transitions. [2022-07-21 03:26:20,000 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 113 [2022-07-21 03:26:20,001 INFO L187 NwaCegarLoop]: Found error trace [2022-07-21 03:26:20,001 INFO L195 NwaCegarLoop]: trace histogram [13, 12, 12, 6, 6, 6, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-21 03:26:20,020 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Ended with exit code 0 [2022-07-21 03:26:20,215 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 14 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable13 [2022-07-21 03:26:20,215 INFO L420 AbstractCegarLoop]: === Iteration 15 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-21 03:26:20,216 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-21 03:26:20,216 INFO L85 PathProgramCache]: Analyzing trace with hash 1760442774, now seen corresponding path program 3 times [2022-07-21 03:26:20,216 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-21 03:26:20,216 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1474127347] [2022-07-21 03:26:20,216 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-21 03:26:20,216 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-21 03:26:20,223 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-07-21 03:26:20,223 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [523097085] [2022-07-21 03:26:20,223 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2022-07-21 03:26:20,223 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-21 03:26:20,224 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-21 03:26:20,225 INFO L229 MonitoredProcess]: Starting monitored process 15 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-07-21 03:26:20,226 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Waiting until timeout for monitored process [2022-07-21 03:26:20,266 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2022-07-21 03:26:20,266 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-07-21 03:26:20,267 INFO L263 TraceCheckSpWp]: Trace formula consists of 172 conjuncts, 7 conjunts are in the unsatisfiable core [2022-07-21 03:26:20,268 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-21 03:26:20,309 INFO L134 CoverageAnalysis]: Checked inductivity of 373 backedges. 40 proven. 9 refuted. 0 times theorem prover too weak. 324 trivial. 0 not checked. [2022-07-21 03:26:20,309 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-21 03:26:20,368 INFO L134 CoverageAnalysis]: Checked inductivity of 373 backedges. 40 proven. 9 refuted. 0 times theorem prover too weak. 324 trivial. 0 not checked. [2022-07-21 03:26:20,369 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-21 03:26:20,369 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1474127347] [2022-07-21 03:26:20,369 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-07-21 03:26:20,369 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [523097085] [2022-07-21 03:26:20,369 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [523097085] provided 0 perfect and 2 imperfect interpolant sequences [2022-07-21 03:26:20,369 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-07-21 03:26:20,369 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7] total 7 [2022-07-21 03:26:20,369 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [875674581] [2022-07-21 03:26:20,369 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-07-21 03:26:20,369 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2022-07-21 03:26:20,370 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-21 03:26:20,370 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2022-07-21 03:26:20,370 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=11, Invalid=31, Unknown=0, NotChecked=0, Total=42 [2022-07-21 03:26:20,370 INFO L87 Difference]: Start difference. First operand 205 states and 269 transitions. Second operand has 7 states, 7 states have (on average 3.857142857142857) internal successors, (27), 7 states have internal predecessors, (27), 4 states have call successors, (19), 2 states have call predecessors, (19), 1 states have return successors, (18), 3 states have call predecessors, (18), 3 states have call successors, (18) [2022-07-21 03:26:20,589 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-21 03:26:20,589 INFO L93 Difference]: Finished difference Result 314 states and 452 transitions. [2022-07-21 03:26:20,589 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2022-07-21 03:26:20,590 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 7 states have (on average 3.857142857142857) internal successors, (27), 7 states have internal predecessors, (27), 4 states have call successors, (19), 2 states have call predecessors, (19), 1 states have return successors, (18), 3 states have call predecessors, (18), 3 states have call successors, (18) Word has length 112 [2022-07-21 03:26:20,590 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-21 03:26:20,591 INFO L225 Difference]: With dead ends: 314 [2022-07-21 03:26:20,591 INFO L226 Difference]: Without dead ends: 307 [2022-07-21 03:26:20,592 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 233 GetRequests, 218 SyntacticMatches, 2 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 22 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=62, Invalid=148, Unknown=0, NotChecked=0, Total=210 [2022-07-21 03:26:20,592 INFO L413 NwaCegarLoop]: 79 mSDtfsCounter, 14 mSDsluCounter, 174 mSDsCounter, 0 mSdLazyCounter, 197 mSolverCounterSat, 40 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 18 SdHoareTripleChecker+Valid, 253 SdHoareTripleChecker+Invalid, 237 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 40 IncrementalHoareTripleChecker+Valid, 197 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-07-21 03:26:20,592 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [18 Valid, 253 Invalid, 237 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [40 Valid, 197 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-07-21 03:26:20,593 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 307 states. [2022-07-21 03:26:20,620 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 307 to 250. [2022-07-21 03:26:20,621 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 250 states, 135 states have (on average 1.1481481481481481) internal successors, (155), 136 states have internal predecessors, (155), 95 states have call successors, (95), 19 states have call predecessors, (95), 19 states have return successors, (94), 94 states have call predecessors, (94), 94 states have call successors, (94) [2022-07-21 03:26:20,622 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 250 states to 250 states and 344 transitions. [2022-07-21 03:26:20,622 INFO L78 Accepts]: Start accepts. Automaton has 250 states and 344 transitions. Word has length 112 [2022-07-21 03:26:20,622 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-21 03:26:20,622 INFO L495 AbstractCegarLoop]: Abstraction has 250 states and 344 transitions. [2022-07-21 03:26:20,622 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 7 states have (on average 3.857142857142857) internal successors, (27), 7 states have internal predecessors, (27), 4 states have call successors, (19), 2 states have call predecessors, (19), 1 states have return successors, (18), 3 states have call predecessors, (18), 3 states have call successors, (18) [2022-07-21 03:26:20,622 INFO L276 IsEmpty]: Start isEmpty. Operand 250 states and 344 transitions. [2022-07-21 03:26:20,623 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 126 [2022-07-21 03:26:20,623 INFO L187 NwaCegarLoop]: Found error trace [2022-07-21 03:26:20,623 INFO L195 NwaCegarLoop]: trace histogram [16, 15, 15, 6, 6, 6, 4, 4, 4, 4, 4, 4, 4, 4, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-21 03:26:20,642 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Forceful destruction successful, exit code 0 [2022-07-21 03:26:20,842 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable14,15 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-21 03:26:20,842 INFO L420 AbstractCegarLoop]: === Iteration 16 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-21 03:26:20,843 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-21 03:26:20,843 INFO L85 PathProgramCache]: Analyzing trace with hash -1098112047, now seen corresponding path program 2 times [2022-07-21 03:26:20,843 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-21 03:26:20,843 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [467108435] [2022-07-21 03:26:20,843 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-21 03:26:20,843 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-21 03:26:20,851 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-07-21 03:26:20,851 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1391956410] [2022-07-21 03:26:20,852 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-07-21 03:26:20,852 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-21 03:26:20,852 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-21 03:26:20,858 INFO L229 MonitoredProcess]: Starting monitored process 16 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-07-21 03:26:20,859 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Waiting until timeout for monitored process [2022-07-21 03:26:20,932 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-07-21 03:26:20,932 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-07-21 03:26:20,934 INFO L263 TraceCheckSpWp]: Trace formula consists of 290 conjuncts, 60 conjunts are in the unsatisfiable core [2022-07-21 03:26:20,936 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-21 03:26:21,527 INFO L134 CoverageAnalysis]: Checked inductivity of 545 backedges. 123 proven. 50 refuted. 0 times theorem prover too weak. 372 trivial. 0 not checked. [2022-07-21 03:26:21,528 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-21 03:26:29,251 INFO L134 CoverageAnalysis]: Checked inductivity of 545 backedges. 127 proven. 32 refuted. 0 times theorem prover too weak. 386 trivial. 0 not checked. [2022-07-21 03:26:29,252 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-21 03:26:29,252 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [467108435] [2022-07-21 03:26:29,252 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-07-21 03:26:29,252 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1391956410] [2022-07-21 03:26:29,252 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1391956410] provided 0 perfect and 2 imperfect interpolant sequences [2022-07-21 03:26:29,252 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-07-21 03:26:29,259 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 12] total 19 [2022-07-21 03:26:29,259 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [368531059] [2022-07-21 03:26:29,260 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-07-21 03:26:29,260 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 19 states [2022-07-21 03:26:29,260 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-21 03:26:29,260 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 19 interpolants. [2022-07-21 03:26:29,261 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=80, Invalid=262, Unknown=0, NotChecked=0, Total=342 [2022-07-21 03:26:29,261 INFO L87 Difference]: Start difference. First operand 250 states and 344 transitions. Second operand has 19 states, 17 states have (on average 2.3529411764705883) internal successors, (40), 16 states have internal predecessors, (40), 11 states have call successors, (33), 2 states have call predecessors, (33), 2 states have return successors, (32), 12 states have call predecessors, (32), 10 states have call successors, (32) [2022-07-21 03:26:33,371 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.14s for a HTC check with result VALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-07-21 03:26:34,218 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-21 03:26:34,218 INFO L93 Difference]: Finished difference Result 270 states and 364 transitions. [2022-07-21 03:26:34,219 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2022-07-21 03:26:34,219 INFO L78 Accepts]: Start accepts. Automaton has has 19 states, 17 states have (on average 2.3529411764705883) internal successors, (40), 16 states have internal predecessors, (40), 11 states have call successors, (33), 2 states have call predecessors, (33), 2 states have return successors, (32), 12 states have call predecessors, (32), 10 states have call successors, (32) Word has length 125 [2022-07-21 03:26:34,219 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-21 03:26:34,220 INFO L225 Difference]: With dead ends: 270 [2022-07-21 03:26:34,220 INFO L226 Difference]: Without dead ends: 268 [2022-07-21 03:26:34,221 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 258 GetRequests, 225 SyntacticMatches, 6 SemanticMatches, 27 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 93 ImplicationChecksByTransitivity, 2.8s TimeCoverageRelationStatistics Valid=207, Invalid=605, Unknown=0, NotChecked=0, Total=812 [2022-07-21 03:26:34,221 INFO L413 NwaCegarLoop]: 45 mSDtfsCounter, 54 mSDsluCounter, 215 mSDsCounter, 0 mSdLazyCounter, 739 mSolverCounterSat, 95 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 4.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 62 SdHoareTripleChecker+Valid, 260 SdHoareTripleChecker+Invalid, 834 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 95 IncrementalHoareTripleChecker+Valid, 739 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 4.1s IncrementalHoareTripleChecker+Time [2022-07-21 03:26:34,221 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [62 Valid, 260 Invalid, 834 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [95 Valid, 739 Invalid, 0 Unknown, 0 Unchecked, 4.1s Time] [2022-07-21 03:26:34,222 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 268 states. [2022-07-21 03:26:34,260 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 268 to 258. [2022-07-21 03:26:34,261 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 258 states, 141 states have (on average 1.1418439716312057) internal successors, (161), 142 states have internal predecessors, (161), 95 states have call successors, (95), 21 states have call predecessors, (95), 21 states have return successors, (94), 94 states have call predecessors, (94), 94 states have call successors, (94) [2022-07-21 03:26:34,262 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 258 states to 258 states and 350 transitions. [2022-07-21 03:26:34,262 INFO L78 Accepts]: Start accepts. Automaton has 258 states and 350 transitions. Word has length 125 [2022-07-21 03:26:34,262 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-21 03:26:34,262 INFO L495 AbstractCegarLoop]: Abstraction has 258 states and 350 transitions. [2022-07-21 03:26:34,262 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 19 states, 17 states have (on average 2.3529411764705883) internal successors, (40), 16 states have internal predecessors, (40), 11 states have call successors, (33), 2 states have call predecessors, (33), 2 states have return successors, (32), 12 states have call predecessors, (32), 10 states have call successors, (32) [2022-07-21 03:26:34,263 INFO L276 IsEmpty]: Start isEmpty. Operand 258 states and 350 transitions. [2022-07-21 03:26:34,265 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 132 [2022-07-21 03:26:34,265 INFO L187 NwaCegarLoop]: Found error trace [2022-07-21 03:26:34,265 INFO L195 NwaCegarLoop]: trace histogram [17, 16, 16, 6, 6, 6, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-21 03:26:34,285 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Forceful destruction successful, exit code 0 [2022-07-21 03:26:34,475 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 16 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable15 [2022-07-21 03:26:34,475 INFO L420 AbstractCegarLoop]: === Iteration 17 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-21 03:26:34,475 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-21 03:26:34,476 INFO L85 PathProgramCache]: Analyzing trace with hash 649793148, now seen corresponding path program 4 times [2022-07-21 03:26:34,476 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-21 03:26:34,476 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [850167815] [2022-07-21 03:26:34,476 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-21 03:26:34,476 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-21 03:26:34,483 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-07-21 03:26:34,483 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [755298590] [2022-07-21 03:26:34,484 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2022-07-21 03:26:34,484 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-21 03:26:34,484 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-21 03:26:34,485 INFO L229 MonitoredProcess]: Starting monitored process 17 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-07-21 03:26:34,486 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Waiting until timeout for monitored process [2022-07-21 03:26:34,536 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2022-07-21 03:26:34,537 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-07-21 03:26:34,538 INFO L263 TraceCheckSpWp]: Trace formula consists of 256 conjuncts, 57 conjunts are in the unsatisfiable core [2022-07-21 03:26:34,540 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-21 03:26:35,110 INFO L134 CoverageAnalysis]: Checked inductivity of 610 backedges. 121 proven. 93 refuted. 0 times theorem prover too weak. 396 trivial. 0 not checked. [2022-07-21 03:26:35,110 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-21 03:26:35,593 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-21 03:26:35,593 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [850167815] [2022-07-21 03:26:35,593 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-07-21 03:26:35,593 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [755298590] [2022-07-21 03:26:35,593 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [755298590] provided 0 perfect and 1 imperfect interpolant sequences [2022-07-21 03:26:35,593 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-07-21 03:26:35,594 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [16] total 16 [2022-07-21 03:26:35,594 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1963054919] [2022-07-21 03:26:35,594 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2022-07-21 03:26:35,594 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2022-07-21 03:26:35,594 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-21 03:26:35,594 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2022-07-21 03:26:35,595 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=78, Invalid=384, Unknown=0, NotChecked=0, Total=462 [2022-07-21 03:26:35,595 INFO L87 Difference]: Start difference. First operand 258 states and 350 transitions. Second operand has 16 states, 14 states have (on average 2.0714285714285716) internal successors, (29), 13 states have internal predecessors, (29), 10 states have call successors, (23), 2 states have call predecessors, (23), 2 states have return successors, (22), 7 states have call predecessors, (22), 9 states have call successors, (22) [2022-07-21 03:26:36,789 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-21 03:26:36,789 INFO L93 Difference]: Finished difference Result 303 states and 412 transitions. [2022-07-21 03:26:36,789 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2022-07-21 03:26:36,789 INFO L78 Accepts]: Start accepts. Automaton has has 16 states, 14 states have (on average 2.0714285714285716) internal successors, (29), 13 states have internal predecessors, (29), 10 states have call successors, (23), 2 states have call predecessors, (23), 2 states have return successors, (22), 7 states have call predecessors, (22), 9 states have call successors, (22) Word has length 131 [2022-07-21 03:26:36,790 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-21 03:26:36,791 INFO L225 Difference]: With dead ends: 303 [2022-07-21 03:26:36,791 INFO L226 Difference]: Without dead ends: 296 [2022-07-21 03:26:36,791 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 158 GetRequests, 132 SyntacticMatches, 2 SemanticMatches, 24 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 145 ImplicationChecksByTransitivity, 0.9s TimeCoverageRelationStatistics Valid=108, Invalid=542, Unknown=0, NotChecked=0, Total=650 [2022-07-21 03:26:36,792 INFO L413 NwaCegarLoop]: 51 mSDtfsCounter, 33 mSDsluCounter, 207 mSDsCounter, 0 mSdLazyCounter, 756 mSolverCounterSat, 51 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.6s Time, 0 mProtectedPredicate, 0 mProtectedAction, 46 SdHoareTripleChecker+Valid, 258 SdHoareTripleChecker+Invalid, 807 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 51 IncrementalHoareTripleChecker+Valid, 756 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.7s IncrementalHoareTripleChecker+Time [2022-07-21 03:26:36,792 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [46 Valid, 258 Invalid, 807 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [51 Valid, 756 Invalid, 0 Unknown, 0 Unchecked, 0.7s Time] [2022-07-21 03:26:36,792 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 296 states. [2022-07-21 03:26:36,839 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 296 to 264. [2022-07-21 03:26:36,840 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 264 states, 143 states have (on average 1.1468531468531469) internal successors, (164), 144 states have internal predecessors, (164), 99 states have call successors, (99), 21 states have call predecessors, (99), 21 states have return successors, (98), 98 states have call predecessors, (98), 98 states have call successors, (98) [2022-07-21 03:26:36,841 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 264 states to 264 states and 361 transitions. [2022-07-21 03:26:36,841 INFO L78 Accepts]: Start accepts. Automaton has 264 states and 361 transitions. Word has length 131 [2022-07-21 03:26:36,842 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-21 03:26:36,842 INFO L495 AbstractCegarLoop]: Abstraction has 264 states and 361 transitions. [2022-07-21 03:26:36,842 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 16 states, 14 states have (on average 2.0714285714285716) internal successors, (29), 13 states have internal predecessors, (29), 10 states have call successors, (23), 2 states have call predecessors, (23), 2 states have return successors, (22), 7 states have call predecessors, (22), 9 states have call successors, (22) [2022-07-21 03:26:36,842 INFO L276 IsEmpty]: Start isEmpty. Operand 264 states and 361 transitions. [2022-07-21 03:26:36,843 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 135 [2022-07-21 03:26:36,843 INFO L187 NwaCegarLoop]: Found error trace [2022-07-21 03:26:36,843 INFO L195 NwaCegarLoop]: trace histogram [17, 16, 16, 6, 6, 6, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-21 03:26:36,864 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Forceful destruction successful, exit code 0 [2022-07-21 03:26:37,059 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 17 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable16 [2022-07-21 03:26:37,059 INFO L420 AbstractCegarLoop]: === Iteration 18 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-21 03:26:37,060 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-21 03:26:37,060 INFO L85 PathProgramCache]: Analyzing trace with hash -1816082155, now seen corresponding path program 5 times [2022-07-21 03:26:37,060 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-21 03:26:37,060 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [18909018] [2022-07-21 03:26:37,060 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-21 03:26:37,060 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-21 03:26:37,067 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-07-21 03:26:37,067 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1446755312] [2022-07-21 03:26:37,067 INFO L93 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2022-07-21 03:26:37,071 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-21 03:26:37,071 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-21 03:26:37,072 INFO L229 MonitoredProcess]: Starting monitored process 18 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-07-21 03:26:37,073 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (18)] Waiting until timeout for monitored process [2022-07-21 03:26:37,174 INFO L228 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 7 check-sat command(s) [2022-07-21 03:26:37,174 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-07-21 03:26:37,176 INFO L263 TraceCheckSpWp]: Trace formula consists of 317 conjuncts, 87 conjunts are in the unsatisfiable core [2022-07-21 03:26:37,179 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-21 03:26:37,971 INFO L134 CoverageAnalysis]: Checked inductivity of 615 backedges. 80 proven. 175 refuted. 0 times theorem prover too weak. 360 trivial. 0 not checked. [2022-07-21 03:26:37,971 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-21 03:26:38,438 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-21 03:26:38,439 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [18909018] [2022-07-21 03:26:38,439 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-07-21 03:26:38,439 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1446755312] [2022-07-21 03:26:38,439 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1446755312] provided 0 perfect and 1 imperfect interpolant sequences [2022-07-21 03:26:38,439 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-07-21 03:26:38,439 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [17] total 17 [2022-07-21 03:26:38,439 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [326024397] [2022-07-21 03:26:38,439 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2022-07-21 03:26:38,439 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 17 states [2022-07-21 03:26:38,439 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-21 03:26:38,440 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2022-07-21 03:26:38,440 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=85, Invalid=421, Unknown=0, NotChecked=0, Total=506 [2022-07-21 03:26:38,440 INFO L87 Difference]: Start difference. First operand 264 states and 361 transitions. Second operand has 17 states, 16 states have (on average 2.0) internal successors, (32), 15 states have internal predecessors, (32), 9 states have call successors, (23), 2 states have call predecessors, (23), 2 states have return successors, (22), 8 states have call predecessors, (22), 8 states have call successors, (22) [2022-07-21 03:26:39,712 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-21 03:26:39,713 INFO L93 Difference]: Finished difference Result 313 states and 426 transitions. [2022-07-21 03:26:39,721 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2022-07-21 03:26:39,721 INFO L78 Accepts]: Start accepts. Automaton has has 17 states, 16 states have (on average 2.0) internal successors, (32), 15 states have internal predecessors, (32), 9 states have call successors, (23), 2 states have call predecessors, (23), 2 states have return successors, (22), 8 states have call predecessors, (22), 8 states have call successors, (22) Word has length 134 [2022-07-21 03:26:39,721 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-21 03:26:39,723 INFO L225 Difference]: With dead ends: 313 [2022-07-21 03:26:39,723 INFO L226 Difference]: Without dead ends: 306 [2022-07-21 03:26:39,724 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 170 GetRequests, 140 SyntacticMatches, 3 SemanticMatches, 27 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 116 ImplicationChecksByTransitivity, 0.9s TimeCoverageRelationStatistics Valid=128, Invalid=684, Unknown=0, NotChecked=0, Total=812 [2022-07-21 03:26:39,724 INFO L413 NwaCegarLoop]: 50 mSDtfsCounter, 37 mSDsluCounter, 261 mSDsCounter, 0 mSdLazyCounter, 1013 mSolverCounterSat, 68 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.7s Time, 0 mProtectedPredicate, 0 mProtectedAction, 53 SdHoareTripleChecker+Valid, 311 SdHoareTripleChecker+Invalid, 1081 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 68 IncrementalHoareTripleChecker+Valid, 1013 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.8s IncrementalHoareTripleChecker+Time [2022-07-21 03:26:39,725 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [53 Valid, 311 Invalid, 1081 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [68 Valid, 1013 Invalid, 0 Unknown, 0 Unchecked, 0.8s Time] [2022-07-21 03:26:39,725 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 306 states. [2022-07-21 03:26:39,784 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 306 to 303. [2022-07-21 03:26:39,785 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 303 states, 163 states have (on average 1.147239263803681) internal successors, (187), 164 states have internal predecessors, (187), 115 states have call successors, (115), 24 states have call predecessors, (115), 24 states have return successors, (114), 114 states have call predecessors, (114), 114 states have call successors, (114) [2022-07-21 03:26:39,786 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 303 states to 303 states and 416 transitions. [2022-07-21 03:26:39,786 INFO L78 Accepts]: Start accepts. Automaton has 303 states and 416 transitions. Word has length 134 [2022-07-21 03:26:39,786 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-21 03:26:39,787 INFO L495 AbstractCegarLoop]: Abstraction has 303 states and 416 transitions. [2022-07-21 03:26:39,787 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 17 states, 16 states have (on average 2.0) internal successors, (32), 15 states have internal predecessors, (32), 9 states have call successors, (23), 2 states have call predecessors, (23), 2 states have return successors, (22), 8 states have call predecessors, (22), 8 states have call successors, (22) [2022-07-21 03:26:39,787 INFO L276 IsEmpty]: Start isEmpty. Operand 303 states and 416 transitions. [2022-07-21 03:26:39,788 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 146 [2022-07-21 03:26:39,789 INFO L187 NwaCegarLoop]: Found error trace [2022-07-21 03:26:39,789 INFO L195 NwaCegarLoop]: trace histogram [19, 18, 18, 6, 6, 6, 5, 5, 5, 5, 5, 5, 4, 4, 4, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-21 03:26:39,821 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (18)] Forceful destruction successful, exit code 0 [2022-07-21 03:26:40,011 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 18 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable17 [2022-07-21 03:26:40,012 INFO L420 AbstractCegarLoop]: === Iteration 19 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-21 03:26:40,012 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-21 03:26:40,012 INFO L85 PathProgramCache]: Analyzing trace with hash -1419250666, now seen corresponding path program 3 times [2022-07-21 03:26:40,012 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-21 03:26:40,012 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1030915916] [2022-07-21 03:26:40,012 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-21 03:26:40,012 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-21 03:26:40,022 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-07-21 03:26:40,022 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1608016602] [2022-07-21 03:26:40,022 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2022-07-21 03:26:40,023 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-21 03:26:40,023 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-21 03:26:40,024 INFO L229 MonitoredProcess]: Starting monitored process 19 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-07-21 03:26:40,043 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (19)] Waiting until timeout for monitored process [2022-07-21 03:26:40,111 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2022-07-21 03:26:40,111 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-07-21 03:26:40,113 INFO L263 TraceCheckSpWp]: Trace formula consists of 194 conjuncts, 67 conjunts are in the unsatisfiable core [2022-07-21 03:26:40,119 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-21 03:26:40,788 INFO L134 CoverageAnalysis]: Checked inductivity of 767 backedges. 86 proven. 69 refuted. 0 times theorem prover too weak. 612 trivial. 0 not checked. [2022-07-21 03:26:40,788 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-21 03:26:42,236 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-21 03:26:42,236 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1030915916] [2022-07-21 03:26:42,236 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-07-21 03:26:42,236 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1608016602] [2022-07-21 03:26:42,236 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1608016602] provided 0 perfect and 1 imperfect interpolant sequences [2022-07-21 03:26:42,236 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-07-21 03:26:42,236 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [18] total 18 [2022-07-21 03:26:42,237 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1704876216] [2022-07-21 03:26:42,237 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2022-07-21 03:26:42,237 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 18 states [2022-07-21 03:26:42,237 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-21 03:26:42,237 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 18 interpolants. [2022-07-21 03:26:42,238 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=101, Invalid=601, Unknown=0, NotChecked=0, Total=702 [2022-07-21 03:26:42,238 INFO L87 Difference]: Start difference. First operand 303 states and 416 transitions. Second operand has 18 states, 17 states have (on average 2.0588235294117645) internal successors, (35), 16 states have internal predecessors, (35), 8 states have call successors, (21), 2 states have call predecessors, (21), 3 states have return successors, (20), 7 states have call predecessors, (20), 7 states have call successors, (20) [2022-07-21 03:26:43,099 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-21 03:26:43,099 INFO L93 Difference]: Finished difference Result 399 states and 548 transitions. [2022-07-21 03:26:43,100 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 17 states. [2022-07-21 03:26:43,100 INFO L78 Accepts]: Start accepts. Automaton has has 18 states, 17 states have (on average 2.0588235294117645) internal successors, (35), 16 states have internal predecessors, (35), 8 states have call successors, (21), 2 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 145 [2022-07-21 03:26:43,100 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-21 03:26:43,102 INFO L225 Difference]: With dead ends: 399 [2022-07-21 03:26:43,102 INFO L226 Difference]: Without dead ends: 397 [2022-07-21 03:26:43,102 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 219 GetRequests, 184 SyntacticMatches, 2 SemanticMatches, 33 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 265 ImplicationChecksByTransitivity, 1.5s TimeCoverageRelationStatistics Valid=168, Invalid=1022, Unknown=0, NotChecked=0, Total=1190 [2022-07-21 03:26:43,103 INFO L413 NwaCegarLoop]: 44 mSDtfsCounter, 46 mSDsluCounter, 214 mSDsCounter, 0 mSdLazyCounter, 949 mSolverCounterSat, 45 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 59 SdHoareTripleChecker+Valid, 258 SdHoareTripleChecker+Invalid, 994 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 45 IncrementalHoareTripleChecker+Valid, 949 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.6s IncrementalHoareTripleChecker+Time [2022-07-21 03:26:43,103 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [59 Valid, 258 Invalid, 994 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [45 Valid, 949 Invalid, 0 Unknown, 0 Unchecked, 0.6s Time] [2022-07-21 03:26:43,105 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 397 states. [2022-07-21 03:26:43,178 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 397 to 391. [2022-07-21 03:26:43,179 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 391 states, 208 states have (on average 1.1490384615384615) internal successors, (239), 209 states have internal predecessors, (239), 151 states have call successors, (151), 31 states have call predecessors, (151), 31 states have return successors, (150), 150 states have call predecessors, (150), 150 states have call successors, (150) [2022-07-21 03:26:43,180 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 391 states to 391 states and 540 transitions. [2022-07-21 03:26:43,180 INFO L78 Accepts]: Start accepts. Automaton has 391 states and 540 transitions. Word has length 145 [2022-07-21 03:26:43,181 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-21 03:26:43,182 INFO L495 AbstractCegarLoop]: Abstraction has 391 states and 540 transitions. [2022-07-21 03:26:43,182 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 18 states, 17 states have (on average 2.0588235294117645) internal successors, (35), 16 states have internal predecessors, (35), 8 states have call successors, (21), 2 states have call predecessors, (21), 3 states have return successors, (20), 7 states have call predecessors, (20), 7 states have call successors, (20) [2022-07-21 03:26:43,182 INFO L276 IsEmpty]: Start isEmpty. Operand 391 states and 540 transitions. [2022-07-21 03:26:43,183 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 154 [2022-07-21 03:26:43,183 INFO L187 NwaCegarLoop]: Found error trace [2022-07-21 03:26:43,183 INFO L195 NwaCegarLoop]: trace histogram [21, 20, 20, 6, 6, 6, 5, 5, 5, 5, 5, 5, 5, 5, 5, 4, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-21 03:26:43,201 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (19)] Forceful destruction successful, exit code 0 [2022-07-21 03:26:43,398 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable18,19 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-21 03:26:43,398 INFO L420 AbstractCegarLoop]: === Iteration 20 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-21 03:26:43,398 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-21 03:26:43,398 INFO L85 PathProgramCache]: Analyzing trace with hash 1812352379, now seen corresponding path program 6 times [2022-07-21 03:26:43,398 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-21 03:26:43,399 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [192589056] [2022-07-21 03:26:43,399 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-21 03:26:43,399 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-21 03:26:43,408 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-07-21 03:26:43,409 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [781808788] [2022-07-21 03:26:43,409 INFO L93 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2022-07-21 03:26:43,409 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-21 03:26:43,409 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-21 03:26:43,410 INFO L229 MonitoredProcess]: Starting monitored process 20 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-07-21 03:26:43,450 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (20)] Waiting until timeout for monitored process [2022-07-21 03:26:43,491 INFO L228 tOrderPrioritization]: Assert order MIX_INSIDE_OUTSIDE issued 7 check-sat command(s) [2022-07-21 03:26:43,491 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-07-21 03:26:43,492 INFO L263 TraceCheckSpWp]: Trace formula consists of 234 conjuncts, 41 conjunts are in the unsatisfiable core [2022-07-21 03:26:43,494 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-21 03:26:43,881 INFO L134 CoverageAnalysis]: Checked inductivity of 922 backedges. 89 proven. 77 refuted. 0 times theorem prover too weak. 756 trivial. 0 not checked. [2022-07-21 03:26:43,882 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-21 03:26:44,061 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-21 03:26:44,062 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [192589056] [2022-07-21 03:26:44,062 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-07-21 03:26:44,062 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [781808788] [2022-07-21 03:26:44,062 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [781808788] provided 0 perfect and 1 imperfect interpolant sequences [2022-07-21 03:26:44,062 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-07-21 03:26:44,062 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10] total 10 [2022-07-21 03:26:44,062 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [997982144] [2022-07-21 03:26:44,062 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2022-07-21 03:26:44,062 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2022-07-21 03:26:44,062 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-21 03:26:44,063 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2022-07-21 03:26:44,063 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=34, Invalid=148, Unknown=0, NotChecked=0, Total=182 [2022-07-21 03:26:44,063 INFO L87 Difference]: Start difference. First operand 391 states and 540 transitions. Second operand has 10 states, 9 states have (on average 2.6666666666666665) internal successors, (24), 9 states have internal predecessors, (24), 4 states have call successors, (14), 2 states have call predecessors, (14), 2 states have return successors, (15), 3 states have call predecessors, (15), 3 states have call successors, (15) [2022-07-21 03:26:44,333 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-21 03:26:44,334 INFO L93 Difference]: Finished difference Result 415 states and 559 transitions. [2022-07-21 03:26:44,334 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2022-07-21 03:26:44,334 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 9 states have (on average 2.6666666666666665) internal successors, (24), 9 states have internal predecessors, (24), 4 states have call successors, (14), 2 states have call predecessors, (14), 2 states have return successors, (15), 3 states have call predecessors, (15), 3 states have call successors, (15) Word has length 153 [2022-07-21 03:26:44,334 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-21 03:26:44,336 INFO L225 Difference]: With dead ends: 415 [2022-07-21 03:26:44,336 INFO L226 Difference]: Without dead ends: 408 [2022-07-21 03:26:44,336 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 180 GetRequests, 162 SyntacticMatches, 2 SemanticMatches, 16 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 19 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=58, Invalid=248, Unknown=0, NotChecked=0, Total=306 [2022-07-21 03:26:44,337 INFO L413 NwaCegarLoop]: 36 mSDtfsCounter, 19 mSDsluCounter, 137 mSDsCounter, 0 mSdLazyCounter, 266 mSolverCounterSat, 11 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 23 SdHoareTripleChecker+Valid, 173 SdHoareTripleChecker+Invalid, 277 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 11 IncrementalHoareTripleChecker+Valid, 266 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2022-07-21 03:26:44,337 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [23 Valid, 173 Invalid, 277 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [11 Valid, 266 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2022-07-21 03:26:44,337 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 408 states. [2022-07-21 03:26:44,405 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 408 to 362. [2022-07-21 03:26:44,406 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 362 states, 198 states have (on average 1.1313131313131313) internal successors, (224), 199 states have internal predecessors, (224), 131 states have call successors, (131), 32 states have call predecessors, (131), 32 states have return successors, (130), 130 states have call predecessors, (130), 130 states have call successors, (130) [2022-07-21 03:26:44,407 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 362 states to 362 states and 485 transitions. [2022-07-21 03:26:44,407 INFO L78 Accepts]: Start accepts. Automaton has 362 states and 485 transitions. Word has length 153 [2022-07-21 03:26:44,407 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-21 03:26:44,408 INFO L495 AbstractCegarLoop]: Abstraction has 362 states and 485 transitions. [2022-07-21 03:26:44,408 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 9 states have (on average 2.6666666666666665) internal successors, (24), 9 states have internal predecessors, (24), 4 states have call successors, (14), 2 states have call predecessors, (14), 2 states have return successors, (15), 3 states have call predecessors, (15), 3 states have call successors, (15) [2022-07-21 03:26:44,408 INFO L276 IsEmpty]: Start isEmpty. Operand 362 states and 485 transitions. [2022-07-21 03:26:44,409 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 157 [2022-07-21 03:26:44,409 INFO L187 NwaCegarLoop]: Found error trace [2022-07-21 03:26:44,409 INFO L195 NwaCegarLoop]: trace histogram [21, 20, 20, 6, 6, 6, 5, 5, 5, 5, 5, 5, 5, 5, 5, 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] [2022-07-21 03:26:44,426 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (20)] Forceful destruction successful, exit code 0 [2022-07-21 03:26:44,612 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable19,20 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-21 03:26:44,613 INFO L420 AbstractCegarLoop]: === Iteration 21 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-21 03:26:44,613 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-21 03:26:44,613 INFO L85 PathProgramCache]: Analyzing trace with hash 2018058068, now seen corresponding path program 7 times [2022-07-21 03:26:44,613 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-21 03:26:44,613 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [231357606] [2022-07-21 03:26:44,613 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-21 03:26:44,614 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-21 03:26:44,621 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-07-21 03:26:44,634 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2069313850] [2022-07-21 03:26:44,635 INFO L93 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2022-07-21 03:26:44,635 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-21 03:26:44,635 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-21 03:26:44,636 INFO L229 MonitoredProcess]: Starting monitored process 21 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-07-21 03:26:44,639 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (21)] Waiting until timeout for monitored process [2022-07-21 03:26:44,714 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-21 03:26:44,717 INFO L263 TraceCheckSpWp]: Trace formula consists of 359 conjuncts, 95 conjunts are in the unsatisfiable core [2022-07-21 03:26:44,719 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-21 03:26:45,748 INFO L134 CoverageAnalysis]: Checked inductivity of 927 backedges. 176 proven. 171 refuted. 0 times theorem prover too weak. 580 trivial. 0 not checked. [2022-07-21 03:26:45,748 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-21 03:26:52,997 INFO L134 CoverageAnalysis]: Checked inductivity of 927 backedges. 134 proven. 81 refuted. 0 times theorem prover too weak. 712 trivial. 0 not checked. [2022-07-21 03:26:52,997 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-21 03:26:52,997 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [231357606] [2022-07-21 03:26:52,997 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-07-21 03:26:52,998 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2069313850] [2022-07-21 03:26:52,998 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2069313850] provided 0 perfect and 2 imperfect interpolant sequences [2022-07-21 03:26:52,998 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-07-21 03:26:52,998 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [20, 18] total 33 [2022-07-21 03:26:52,998 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [506819892] [2022-07-21 03:26:52,998 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-07-21 03:26:52,998 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 33 states [2022-07-21 03:26:52,998 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-21 03:26:52,999 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 33 interpolants. [2022-07-21 03:26:52,999 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=188, Invalid=868, Unknown=0, NotChecked=0, Total=1056 [2022-07-21 03:26:52,999 INFO L87 Difference]: Start difference. First operand 362 states and 485 transitions. Second operand has 33 states, 30 states have (on average 1.9333333333333333) internal successors, (58), 28 states have internal predecessors, (58), 19 states have call successors, (51), 2 states have call predecessors, (51), 3 states have return successors, (50), 16 states have call predecessors, (50), 17 states have call successors, (50) [2022-07-21 03:27:34,244 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.62s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-07-21 03:27:48,081 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-21 03:27:48,081 INFO L93 Difference]: Finished difference Result 426 states and 570 transitions. [2022-07-21 03:27:48,082 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 43 states. [2022-07-21 03:27:48,082 INFO L78 Accepts]: Start accepts. Automaton has has 33 states, 30 states have (on average 1.9333333333333333) internal successors, (58), 28 states have internal predecessors, (58), 19 states have call successors, (51), 2 states have call predecessors, (51), 3 states have return successors, (50), 16 states have call predecessors, (50), 17 states have call successors, (50) Word has length 156 [2022-07-21 03:27:48,082 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-21 03:27:48,083 INFO L225 Difference]: With dead ends: 426 [2022-07-21 03:27:48,084 INFO L226 Difference]: Without dead ends: 418 [2022-07-21 03:27:48,085 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 341 GetRequests, 272 SyntacticMatches, 7 SemanticMatches, 62 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 961 ImplicationChecksByTransitivity, 42.3s TimeCoverageRelationStatistics Valid=814, Invalid=3218, Unknown=0, NotChecked=0, Total=4032 [2022-07-21 03:27:48,085 INFO L413 NwaCegarLoop]: 48 mSDtfsCounter, 142 mSDsluCounter, 269 mSDsCounter, 0 mSdLazyCounter, 1756 mSolverCounterSat, 449 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 16.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 147 SdHoareTripleChecker+Valid, 317 SdHoareTripleChecker+Invalid, 2205 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 449 IncrementalHoareTripleChecker+Valid, 1756 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 16.5s IncrementalHoareTripleChecker+Time [2022-07-21 03:27:48,085 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [147 Valid, 317 Invalid, 2205 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [449 Valid, 1756 Invalid, 0 Unknown, 0 Unchecked, 16.5s Time] [2022-07-21 03:27:48,086 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 418 states. [2022-07-21 03:27:48,173 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 418 to 333. [2022-07-21 03:27:48,174 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 333 states, 188 states have (on average 1.0957446808510638) internal successors, (206), 188 states have internal predecessors, (206), 110 states have call successors, (110), 34 states have call predecessors, (110), 34 states have return successors, (110), 110 states have call predecessors, (110), 110 states have call successors, (110) [2022-07-21 03:27:48,175 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 333 states to 333 states and 426 transitions. [2022-07-21 03:27:48,175 INFO L78 Accepts]: Start accepts. Automaton has 333 states and 426 transitions. Word has length 156 [2022-07-21 03:27:48,175 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-21 03:27:48,175 INFO L495 AbstractCegarLoop]: Abstraction has 333 states and 426 transitions. [2022-07-21 03:27:48,176 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 33 states, 30 states have (on average 1.9333333333333333) internal successors, (58), 28 states have internal predecessors, (58), 19 states have call successors, (51), 2 states have call predecessors, (51), 3 states have return successors, (50), 16 states have call predecessors, (50), 17 states have call successors, (50) [2022-07-21 03:27:48,176 INFO L276 IsEmpty]: Start isEmpty. Operand 333 states and 426 transitions. [2022-07-21 03:27:48,177 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 168 [2022-07-21 03:27:48,177 INFO L187 NwaCegarLoop]: Found error trace [2022-07-21 03:27:48,177 INFO L195 NwaCegarLoop]: trace histogram [23, 22, 22, 6, 6, 6, 6, 6, 6, 6, 6, 6, 5, 5, 5, 3, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-21 03:27:48,195 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (21)] Forceful destruction successful, exit code 0 [2022-07-21 03:27:48,385 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 21 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable20 [2022-07-21 03:27:48,385 INFO L420 AbstractCegarLoop]: === Iteration 22 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-21 03:27:48,386 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-21 03:27:48,386 INFO L85 PathProgramCache]: Analyzing trace with hash 2114909687, now seen corresponding path program 4 times [2022-07-21 03:27:48,386 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-21 03:27:48,386 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1032562043] [2022-07-21 03:27:48,386 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-21 03:27:48,386 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-21 03:27:48,395 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-07-21 03:27:48,395 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [330119564] [2022-07-21 03:27:48,395 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2022-07-21 03:27:48,395 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-21 03:27:48,395 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-21 03:27:48,400 INFO L229 MonitoredProcess]: Starting monitored process 22 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-07-21 03:27:48,402 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (22)] Waiting until timeout for monitored process [2022-07-21 03:27:48,489 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2022-07-21 03:27:48,489 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-07-21 03:27:48,491 INFO L263 TraceCheckSpWp]: Trace formula consists of 336 conjuncts, 89 conjunts are in the unsatisfiable core [2022-07-21 03:27:48,496 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-21 03:27:49,412 INFO L134 CoverageAnalysis]: Checked inductivity of 1115 backedges. 196 proven. 151 refuted. 0 times theorem prover too weak. 768 trivial. 0 not checked. [2022-07-21 03:27:49,412 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-21 03:27:50,641 INFO L134 CoverageAnalysis]: Checked inductivity of 1115 backedges. 202 proven. 41 refuted. 0 times theorem prover too weak. 872 trivial. 0 not checked. [2022-07-21 03:27:50,641 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-21 03:27:50,641 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1032562043] [2022-07-21 03:27:50,642 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-07-21 03:27:50,642 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [330119564] [2022-07-21 03:27:50,642 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [330119564] provided 0 perfect and 2 imperfect interpolant sequences [2022-07-21 03:27:50,642 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-07-21 03:27:50,642 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [18, 13] total 26 [2022-07-21 03:27:50,642 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [8749833] [2022-07-21 03:27:50,642 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-07-21 03:27:50,642 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 26 states [2022-07-21 03:27:50,642 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-21 03:27:50,643 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 26 interpolants. [2022-07-21 03:27:50,643 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=130, Invalid=520, Unknown=0, NotChecked=0, Total=650 [2022-07-21 03:27:50,643 INFO L87 Difference]: Start difference. First operand 333 states and 426 transitions. Second operand has 26 states, 24 states have (on average 2.2916666666666665) internal successors, (55), 21 states have internal predecessors, (55), 16 states have call successors, (50), 2 states have call predecessors, (50), 2 states have return successors, (48), 16 states have call predecessors, (48), 14 states have call successors, (48) [2022-07-21 03:27:53,506 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.15s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-07-21 03:27:58,171 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-21 03:27:58,171 INFO L93 Difference]: Finished difference Result 381 states and 482 transitions. [2022-07-21 03:27:58,172 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 24 states. [2022-07-21 03:27:58,172 INFO L78 Accepts]: Start accepts. Automaton has has 26 states, 24 states have (on average 2.2916666666666665) internal successors, (55), 21 states have internal predecessors, (55), 16 states have call successors, (50), 2 states have call predecessors, (50), 2 states have return successors, (48), 16 states have call predecessors, (48), 14 states have call successors, (48) Word has length 167 [2022-07-21 03:27:58,172 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-21 03:27:58,172 INFO L225 Difference]: With dead ends: 381 [2022-07-21 03:27:58,173 INFO L226 Difference]: Without dead ends: 0 [2022-07-21 03:27:58,174 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 348 GetRequests, 302 SyntacticMatches, 6 SemanticMatches, 40 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 365 ImplicationChecksByTransitivity, 3.4s TimeCoverageRelationStatistics Valid=371, Invalid=1351, Unknown=0, NotChecked=0, Total=1722 [2022-07-21 03:27:58,174 INFO L413 NwaCegarLoop]: 54 mSDtfsCounter, 57 mSDsluCounter, 260 mSDsCounter, 0 mSdLazyCounter, 1119 mSolverCounterSat, 195 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 5.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 60 SdHoareTripleChecker+Valid, 314 SdHoareTripleChecker+Invalid, 1314 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 195 IncrementalHoareTripleChecker+Valid, 1119 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 5.1s IncrementalHoareTripleChecker+Time [2022-07-21 03:27:58,174 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [60 Valid, 314 Invalid, 1314 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [195 Valid, 1119 Invalid, 0 Unknown, 0 Unchecked, 5.1s Time] [2022-07-21 03:27:58,174 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 0 states. [2022-07-21 03:27:58,174 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 0 to 0. [2022-07-21 03:27:58,174 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 0 states, 0 states have (on average 0.0) internal successors, (0), 0 states have internal predecessors, (0), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-07-21 03:27:58,175 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 0 states to 0 states and 0 transitions. [2022-07-21 03:27:58,175 INFO L78 Accepts]: Start accepts. Automaton has 0 states and 0 transitions. Word has length 167 [2022-07-21 03:27:58,175 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-21 03:27:58,175 INFO L495 AbstractCegarLoop]: Abstraction has 0 states and 0 transitions. [2022-07-21 03:27:58,175 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 26 states, 24 states have (on average 2.2916666666666665) internal successors, (55), 21 states have internal predecessors, (55), 16 states have call successors, (50), 2 states have call predecessors, (50), 2 states have return successors, (48), 16 states have call predecessors, (48), 14 states have call successors, (48) [2022-07-21 03:27:58,175 INFO L276 IsEmpty]: Start isEmpty. Operand 0 states and 0 transitions. [2022-07-21 03:27:58,175 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-07-21 03:27:58,177 INFO L805 garLoopResultBuilder]: Registering result SAFE for location __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION (0 of 1 remaining) [2022-07-21 03:27:58,196 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (22)] Forceful destruction successful, exit code 0 [2022-07-21 03:27:58,383 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 22 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable21 [2022-07-21 03:27:58,385 INFO L343 DoubleDeckerVisitor]: Before removal of dead ends 0 states and 0 transitions. [2022-07-21 03:29:12,138 WARN L233 SmtUtils]: Spent 1.17m on a formula simplification. DAG size of input: 392 DAG size of output: 60 (called from [L 149] de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.HoareAnnotationComposer.combineInter) [2022-07-21 03:29:37,916 WARN L233 SmtUtils]: Spent 25.78s on a formula simplification. DAG size of input: 276 DAG size of output: 73 (called from [L 149] de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.HoareAnnotationComposer.combineInter) [2022-07-21 03:30:18,045 WARN L233 SmtUtils]: Spent 40.12s on a formula simplification. DAG size of input: 397 DAG size of output: 60 (called from [L 149] de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.HoareAnnotationComposer.combineInter)