/usr/bin/java -Xmx8000000000 -Xss4m -jar ./plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata ./data --core.log.level.for.class de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=WARN -tc ../../../trunk/examples/toolchains/AutomizerCTransformed.xml -s ../../../trunk/examples/settings/loopacceleration/qvasr/qvasr_64.epf -i ../../../trunk/examples/svcomp/nla-digbench-scaling/hard2_unwindbound5.c -------------------------------------------------------------------------------- This is Ultimate 0.2.2-dev-34549b5 [2022-04-06 12:29:03,395 INFO L177 SettingsManager]: Resetting all preferences to default values... [2022-04-06 12:29:03,398 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2022-04-06 12:29:03,435 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2022-04-06 12:29:03,435 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2022-04-06 12:29:03,436 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2022-04-06 12:29:03,438 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2022-04-06 12:29:03,441 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2022-04-06 12:29:03,442 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2022-04-06 12:29:03,446 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2022-04-06 12:29:03,446 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2022-04-06 12:29:03,447 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2022-04-06 12:29:03,447 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2022-04-06 12:29:03,449 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2022-04-06 12:29:03,450 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2022-04-06 12:29:03,452 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2022-04-06 12:29:03,452 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2022-04-06 12:29:03,453 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2022-04-06 12:29:03,454 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2022-04-06 12:29:03,459 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2022-04-06 12:29:03,461 INFO L181 SettingsManager]: Resetting HornVerifier preferences to default values [2022-04-06 12:29:03,461 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2022-04-06 12:29:03,462 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2022-04-06 12:29:03,462 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2022-04-06 12:29:03,464 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2022-04-06 12:29:03,468 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2022-04-06 12:29:03,468 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2022-04-06 12:29:03,469 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2022-04-06 12:29:03,469 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2022-04-06 12:29:03,469 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2022-04-06 12:29:03,471 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2022-04-06 12:29:03,471 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2022-04-06 12:29:03,472 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2022-04-06 12:29:03,472 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2022-04-06 12:29:03,473 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2022-04-06 12:29:03,473 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2022-04-06 12:29:03,473 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2022-04-06 12:29:03,474 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2022-04-06 12:29:03,474 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2022-04-06 12:29:03,474 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2022-04-06 12:29:03,474 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2022-04-06 12:29:03,476 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2022-04-06 12:29:03,476 INFO L101 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/loopacceleration/qvasr/qvasr_64.epf [2022-04-06 12:29:03,497 INFO L113 SettingsManager]: Loading preferences was successful [2022-04-06 12:29:03,497 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2022-04-06 12:29:03,498 INFO L136 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2022-04-06 12:29:03,498 INFO L138 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2022-04-06 12:29:03,499 INFO L136 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2022-04-06 12:29:03,499 INFO L138 SettingsManager]: * Create parallel compositions if possible=false [2022-04-06 12:29:03,499 INFO L138 SettingsManager]: * Use SBE=true [2022-04-06 12:29:03,499 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2022-04-06 12:29:03,499 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2022-04-06 12:29:03,500 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2022-04-06 12:29:03,500 INFO L138 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2022-04-06 12:29:03,500 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2022-04-06 12:29:03,500 INFO L138 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2022-04-06 12:29:03,500 INFO L138 SettingsManager]: * Check if freed pointer was valid=false [2022-04-06 12:29:03,500 INFO L138 SettingsManager]: * Use constant arrays=true [2022-04-06 12:29:03,500 INFO L138 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2022-04-06 12:29:03,500 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2022-04-06 12:29:03,500 INFO L138 SettingsManager]: * Size of a code block=SequenceOfStatements [2022-04-06 12:29:03,501 INFO L138 SettingsManager]: * SMT solver=External_DefaultMode [2022-04-06 12:29:03,501 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-04-06 12:29:03,501 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2022-04-06 12:29:03,501 INFO L138 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2022-04-06 12:29:03,501 INFO L138 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2022-04-06 12:29:03,501 INFO L138 SettingsManager]: * Trace refinement strategy=CAMEL [2022-04-06 12:29:03,501 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2022-04-06 12:29:03,501 INFO L138 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2022-04-06 12:29:03,502 INFO L138 SettingsManager]: * Trace refinement exception blacklist=NONE [2022-04-06 12:29:03,502 INFO L138 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2022-04-06 12:29:03,503 INFO L136 SettingsManager]: Preferences of IcfgTransformer differ from their defaults: [2022-04-06 12:29:03,503 INFO L138 SettingsManager]: * TransformationType=LOOP_ACCELERATION_QVASR 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.core: Log level for class -> de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=WARN; [2022-04-06 12:29:03,670 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2022-04-06 12:29:03,686 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2022-04-06 12:29:03,688 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2022-04-06 12:29:03,688 INFO L271 PluginConnector]: Initializing CDTParser... [2022-04-06 12:29:03,689 INFO L275 PluginConnector]: CDTParser initialized [2022-04-06 12:29:03,690 INFO L432 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/svcomp/nla-digbench-scaling/hard2_unwindbound5.c [2022-04-06 12:29:03,730 INFO L220 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/0abc1af35/422e74abc39046bfaf97ecac049f5ac8/FLAG1bdae4036 [2022-04-06 12:29:04,096 INFO L306 CDTParser]: Found 1 translation units. [2022-04-06 12:29:04,096 INFO L160 CDTParser]: Scanning /storage/repos/ultimate/trunk/examples/svcomp/nla-digbench-scaling/hard2_unwindbound5.c [2022-04-06 12:29:04,101 INFO L349 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/0abc1af35/422e74abc39046bfaf97ecac049f5ac8/FLAG1bdae4036 [2022-04-06 12:29:04,117 INFO L357 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/0abc1af35/422e74abc39046bfaf97ecac049f5ac8 [2022-04-06 12:29:04,118 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2022-04-06 12:29:04,120 INFO L131 ToolchainWalker]: Walking toolchain with 5 elements. [2022-04-06 12:29:04,122 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2022-04-06 12:29:04,122 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2022-04-06 12:29:04,125 INFO L275 PluginConnector]: CACSL2BoogieTranslator initialized [2022-04-06 12:29:04,125 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 06.04 12:29:04" (1/1) ... [2022-04-06 12:29:04,127 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@2f6aa1fb and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 12:29:04, skipping insertion in model container [2022-04-06 12:29:04,127 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 06.04 12:29:04" (1/1) ... [2022-04-06 12:29:04,132 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2022-04-06 12:29:04,143 INFO L178 MainTranslator]: Built tables and reachable declarations [2022-04-06 12:29:04,253 WARN L230 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/trunk/examples/svcomp/nla-digbench-scaling/hard2_unwindbound5.c[526,539] [2022-04-06 12:29:04,273 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-04-06 12:29:04,278 INFO L203 MainTranslator]: Completed pre-run [2022-04-06 12:29:04,286 WARN L230 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/trunk/examples/svcomp/nla-digbench-scaling/hard2_unwindbound5.c[526,539] [2022-04-06 12:29:04,290 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-04-06 12:29:04,299 INFO L208 MainTranslator]: Completed translation [2022-04-06 12:29:04,299 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 12:29:04 WrapperNode [2022-04-06 12:29:04,299 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2022-04-06 12:29:04,300 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2022-04-06 12:29:04,300 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2022-04-06 12:29:04,300 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2022-04-06 12:29:04,307 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 12:29:04" (1/1) ... [2022-04-06 12:29:04,307 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 12:29:04" (1/1) ... [2022-04-06 12:29:04,311 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 12:29:04" (1/1) ... [2022-04-06 12:29:04,312 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 12:29:04" (1/1) ... [2022-04-06 12:29:04,315 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 12:29:04" (1/1) ... [2022-04-06 12:29:04,318 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 12:29:04" (1/1) ... [2022-04-06 12:29:04,319 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 12:29:04" (1/1) ... [2022-04-06 12:29:04,320 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2022-04-06 12:29:04,320 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2022-04-06 12:29:04,320 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2022-04-06 12:29:04,320 INFO L275 PluginConnector]: RCFGBuilder initialized [2022-04-06 12:29:04,321 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 12:29:04" (1/1) ... [2022-04-06 12:29:04,326 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-04-06 12:29:04,332 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 12:29:04,341 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-04-06 12:29:04,357 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-04-06 12:29:04,370 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.init [2022-04-06 12:29:04,371 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2022-04-06 12:29:04,371 INFO L138 BoogieDeclarations]: Found implementation of procedure reach_error [2022-04-06 12:29:04,371 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2022-04-06 12:29:04,371 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2022-04-06 12:29:04,371 INFO L138 BoogieDeclarations]: Found implementation of procedure main [2022-04-06 12:29:04,371 INFO L130 BoogieDeclarations]: Found specification of procedure abort [2022-04-06 12:29:04,372 INFO L130 BoogieDeclarations]: Found specification of procedure __assert_fail [2022-04-06 12:29:04,373 INFO L130 BoogieDeclarations]: Found specification of procedure reach_error [2022-04-06 12:29:04,373 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2022-04-06 12:29:04,373 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_nondet_int [2022-04-06 12:29:04,374 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2022-04-06 12:29:04,374 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2022-04-06 12:29:04,374 INFO L130 BoogieDeclarations]: Found specification of procedure main [2022-04-06 12:29:04,374 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.init [2022-04-06 12:29:04,374 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2022-04-06 12:29:04,374 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2022-04-06 12:29:04,374 INFO L130 BoogieDeclarations]: Found specification of procedure write~int [2022-04-06 12:29:04,374 INFO L130 BoogieDeclarations]: Found specification of procedure read~int [2022-04-06 12:29:04,374 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2022-04-06 12:29:04,419 INFO L234 CfgBuilder]: Building ICFG [2022-04-06 12:29:04,421 INFO L260 CfgBuilder]: Building CFG for each procedure with an implementation [2022-04-06 12:29:04,555 INFO L275 CfgBuilder]: Performing block encoding [2022-04-06 12:29:04,559 INFO L294 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2022-04-06 12:29:04,559 INFO L299 CfgBuilder]: Removed 2 assume(true) statements. [2022-04-06 12:29:04,561 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 06.04 12:29:04 BoogieIcfgContainer [2022-04-06 12:29:04,561 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2022-04-06 12:29:04,561 INFO L113 PluginConnector]: ------------------------IcfgTransformer---------------------------- [2022-04-06 12:29:04,561 INFO L271 PluginConnector]: Initializing IcfgTransformer... [2022-04-06 12:29:04,562 INFO L275 PluginConnector]: IcfgTransformer initialized [2022-04-06 12:29:04,564 INFO L185 PluginConnector]: Executing the observer IcfgTransformationObserver from plugin IcfgTransformer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 06.04 12:29:04" (1/1) ... [2022-04-06 12:29:04,565 INFO L168 ansformationObserver]: Applying ICFG transformation LOOP_ACCELERATION_QVASR [2022-04-06 12:29:04,577 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.icfgtransformation CFG 06.04 12:29:04 BasicIcfg [2022-04-06 12:29:04,577 INFO L132 PluginConnector]: ------------------------ END IcfgTransformer---------------------------- [2022-04-06 12:29:04,578 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2022-04-06 12:29:04,578 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2022-04-06 12:29:04,581 INFO L275 PluginConnector]: TraceAbstraction initialized [2022-04-06 12:29:04,581 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 06.04 12:29:04" (1/4) ... [2022-04-06 12:29:04,582 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@7481cccc and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 06.04 12:29:04, skipping insertion in model container [2022-04-06 12:29:04,582 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 12:29:04" (2/4) ... [2022-04-06 12:29:04,582 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@7481cccc and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 06.04 12:29:04, skipping insertion in model container [2022-04-06 12:29:04,582 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 06.04 12:29:04" (3/4) ... [2022-04-06 12:29:04,582 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@7481cccc and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 06.04 12:29:04, skipping insertion in model container [2022-04-06 12:29:04,582 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.icfgtransformation CFG 06.04 12:29:04" (4/4) ... [2022-04-06 12:29:04,583 INFO L111 eAbstractionObserver]: Analyzing ICFG hard2_unwindbound5.cqvasr [2022-04-06 12:29:04,587 INFO L203 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2022-04-06 12:29:04,587 INFO L162 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2022-04-06 12:29:04,638 INFO L339 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2022-04-06 12:29:04,643 INFO L340 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=FINITE_AUTOMATA, 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 [2022-04-06 12:29:04,643 INFO L341 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2022-04-06 12:29:04,677 INFO L276 IsEmpty]: Start isEmpty. Operand has 31 states, 17 states have (on average 1.5294117647058822) internal successors, (26), 18 states have internal predecessors, (26), 9 states have call successors, (9), 3 states have call predecessors, (9), 3 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2022-04-06 12:29:04,681 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 13 [2022-04-06 12:29:04,681 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 12:29:04,681 INFO L499 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 12:29:04,687 INFO L403 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 12:29:04,691 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 12:29:04,691 INFO L85 PathProgramCache]: Analyzing trace with hash 121155216, now seen corresponding path program 1 times [2022-04-06 12:29:04,701 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 12:29:04,703 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [587139595] [2022-04-06 12:29:04,703 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 12:29:04,704 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 12:29:04,786 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 12:29:04,849 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-04-06 12:29:04,856 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 12:29:04,866 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-04-06 12:29:04,866 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 12:29:04,868 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [587139595] [2022-04-06 12:29:04,868 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [587139595] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 12:29:04,868 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 12:29:04,868 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2022-04-06 12:29:04,869 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [562952028] [2022-04-06 12:29:04,870 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 12:29:04,874 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2022-04-06 12:29:04,874 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-06 12:29:04,898 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2022-04-06 12:29:04,899 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2022-04-06 12:29:04,900 INFO L87 Difference]: Start difference. First operand has 31 states, 17 states have (on average 1.5294117647058822) internal successors, (26), 18 states have internal predecessors, (26), 9 states have call successors, (9), 3 states have call predecessors, (9), 3 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) Second operand has 3 states, 3 states have (on average 2.6666666666666665) internal successors, (8), 2 states have internal predecessors, (8), 2 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-04-06 12:29:04,995 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 12:29:04,995 INFO L93 Difference]: Finished difference Result 57 states and 91 transitions. [2022-04-06 12:29:04,998 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2022-04-06 12:29:04,999 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 2.6666666666666665) internal successors, (8), 2 states have internal predecessors, (8), 2 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 12 [2022-04-06 12:29:05,000 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 12:29:05,008 INFO L225 Difference]: With dead ends: 57 [2022-04-06 12:29:05,008 INFO L226 Difference]: Without dead ends: 27 [2022-04-06 12:29:05,012 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 4 GetRequests, 3 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2022-04-06 12:29:05,015 INFO L913 BasicCegarLoop]: 40 mSDtfsCounter, 6 mSDsluCounter, 4 mSDsCounter, 0 mSdLazyCounter, 23 mSolverCounterSat, 8 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 6 SdHoareTripleChecker+Valid, 44 SdHoareTripleChecker+Invalid, 31 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 8 IncrementalHoareTripleChecker+Valid, 23 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-04-06 12:29:05,016 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [6 Valid, 44 Invalid, 31 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [8 Valid, 23 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-06 12:29:05,028 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 27 states. [2022-04-06 12:29:05,053 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 27 to 26. [2022-04-06 12:29:05,054 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 26 states, 14 states have (on average 1.4285714285714286) internal successors, (20), 15 states have internal predecessors, (20), 9 states have call successors, (9), 3 states have call predecessors, (9), 2 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2022-04-06 12:29:05,056 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 26 states to 26 states and 36 transitions. [2022-04-06 12:29:05,057 INFO L78 Accepts]: Start accepts. Automaton has 26 states and 36 transitions. Word has length 12 [2022-04-06 12:29:05,057 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 12:29:05,057 INFO L478 AbstractCegarLoop]: Abstraction has 26 states and 36 transitions. [2022-04-06 12:29:05,058 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 2.6666666666666665) internal successors, (8), 2 states have internal predecessors, (8), 2 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-04-06 12:29:05,058 INFO L276 IsEmpty]: Start isEmpty. Operand 26 states and 36 transitions. [2022-04-06 12:29:05,058 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 13 [2022-04-06 12:29:05,059 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 12:29:05,059 INFO L499 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 12:29:05,059 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2022-04-06 12:29:05,059 INFO L403 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 12:29:05,061 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 12:29:05,061 INFO L85 PathProgramCache]: Analyzing trace with hash 152644303, now seen corresponding path program 1 times [2022-04-06 12:29:05,062 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 12:29:05,062 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1901569182] [2022-04-06 12:29:05,062 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 12:29:05,062 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 12:29:05,099 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 12:29:05,173 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-04-06 12:29:05,177 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 12:29:05,193 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-04-06 12:29:05,194 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 12:29:05,194 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1901569182] [2022-04-06 12:29:05,194 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1901569182] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 12:29:05,194 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 12:29:05,195 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2022-04-06 12:29:05,195 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2109057701] [2022-04-06 12:29:05,195 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 12:29:05,196 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2022-04-06 12:29:05,196 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-06 12:29:05,197 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2022-04-06 12:29:05,197 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2022-04-06 12:29:05,198 INFO L87 Difference]: Start difference. First operand 26 states and 36 transitions. Second operand has 6 states, 6 states have (on average 1.3333333333333333) internal successors, (8), 4 states have internal predecessors, (8), 2 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-04-06 12:29:05,347 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 12:29:05,347 INFO L93 Difference]: Finished difference Result 41 states and 56 transitions. [2022-04-06 12:29:05,348 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2022-04-06 12:29:05,348 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 1.3333333333333333) internal successors, (8), 4 states have internal predecessors, (8), 2 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 12 [2022-04-06 12:29:05,348 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 12:29:05,350 INFO L225 Difference]: With dead ends: 41 [2022-04-06 12:29:05,350 INFO L226 Difference]: Without dead ends: 39 [2022-04-06 12:29:05,353 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 11 GetRequests, 3 SyntacticMatches, 0 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 5 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=28, Invalid=62, Unknown=0, NotChecked=0, Total=90 [2022-04-06 12:29:05,354 INFO L913 BasicCegarLoop]: 34 mSDtfsCounter, 24 mSDsluCounter, 51 mSDsCounter, 0 mSdLazyCounter, 80 mSolverCounterSat, 13 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 30 SdHoareTripleChecker+Valid, 85 SdHoareTripleChecker+Invalid, 93 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 13 IncrementalHoareTripleChecker+Valid, 80 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-04-06 12:29:05,355 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [30 Valid, 85 Invalid, 93 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [13 Valid, 80 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-06 12:29:05,357 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 39 states. [2022-04-06 12:29:05,369 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 39 to 30. [2022-04-06 12:29:05,369 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 30 states, 17 states have (on average 1.3529411764705883) internal successors, (23), 18 states have internal predecessors, (23), 9 states have call successors, (9), 4 states have call predecessors, (9), 3 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2022-04-06 12:29:05,376 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 30 states to 30 states and 39 transitions. [2022-04-06 12:29:05,376 INFO L78 Accepts]: Start accepts. Automaton has 30 states and 39 transitions. Word has length 12 [2022-04-06 12:29:05,376 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 12:29:05,376 INFO L478 AbstractCegarLoop]: Abstraction has 30 states and 39 transitions. [2022-04-06 12:29:05,376 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 1.3333333333333333) internal successors, (8), 4 states have internal predecessors, (8), 2 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-04-06 12:29:05,377 INFO L276 IsEmpty]: Start isEmpty. Operand 30 states and 39 transitions. [2022-04-06 12:29:05,377 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 15 [2022-04-06 12:29:05,377 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 12:29:05,377 INFO L499 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 12:29:05,378 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2022-04-06 12:29:05,378 INFO L403 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 12:29:05,383 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 12:29:05,383 INFO L85 PathProgramCache]: Analyzing trace with hash -400958603, now seen corresponding path program 1 times [2022-04-06 12:29:05,384 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 12:29:05,384 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1510808106] [2022-04-06 12:29:05,384 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 12:29:05,384 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 12:29:05,408 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 12:29:05,443 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-04-06 12:29:05,446 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 12:29:05,455 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-04-06 12:29:05,455 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 12:29:05,455 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1510808106] [2022-04-06 12:29:05,456 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1510808106] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 12:29:05,456 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 12:29:05,456 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2022-04-06 12:29:05,456 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1654963627] [2022-04-06 12:29:05,456 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 12:29:05,457 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-04-06 12:29:05,457 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-06 12:29:05,457 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-04-06 12:29:05,457 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-04-06 12:29:05,458 INFO L87 Difference]: Start difference. First operand 30 states and 39 transitions. Second operand has 5 states, 4 states have (on average 2.5) internal successors, (10), 3 states have internal predecessors, (10), 3 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-04-06 12:29:05,523 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 12:29:05,523 INFO L93 Difference]: Finished difference Result 46 states and 61 transitions. [2022-04-06 12:29:05,524 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2022-04-06 12:29:05,524 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 4 states have (on average 2.5) internal successors, (10), 3 states have internal predecessors, (10), 3 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 14 [2022-04-06 12:29:05,524 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 12:29:05,525 INFO L225 Difference]: With dead ends: 46 [2022-04-06 12:29:05,525 INFO L226 Difference]: Without dead ends: 32 [2022-04-06 12:29:05,528 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 7 GetRequests, 3 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-04-06 12:29:05,531 INFO L913 BasicCegarLoop]: 34 mSDtfsCounter, 6 mSDsluCounter, 39 mSDsCounter, 0 mSdLazyCounter, 51 mSolverCounterSat, 8 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 6 SdHoareTripleChecker+Valid, 73 SdHoareTripleChecker+Invalid, 59 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 8 IncrementalHoareTripleChecker+Valid, 51 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-06 12:29:05,532 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [6 Valid, 73 Invalid, 59 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [8 Valid, 51 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-06 12:29:05,532 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 32 states. [2022-04-06 12:29:05,537 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 32 to 32. [2022-04-06 12:29:05,538 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 32 states, 19 states have (on average 1.3157894736842106) internal successors, (25), 20 states have internal predecessors, (25), 9 states have call successors, (9), 4 states have call predecessors, (9), 3 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2022-04-06 12:29:05,539 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 32 states to 32 states and 41 transitions. [2022-04-06 12:29:05,539 INFO L78 Accepts]: Start accepts. Automaton has 32 states and 41 transitions. Word has length 14 [2022-04-06 12:29:05,539 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 12:29:05,540 INFO L478 AbstractCegarLoop]: Abstraction has 32 states and 41 transitions. [2022-04-06 12:29:05,540 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 4 states have (on average 2.5) internal successors, (10), 3 states have internal predecessors, (10), 3 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-04-06 12:29:05,540 INFO L276 IsEmpty]: Start isEmpty. Operand 32 states and 41 transitions. [2022-04-06 12:29:05,540 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 18 [2022-04-06 12:29:05,540 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 12:29:05,540 INFO L499 BasicCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 12:29:05,541 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2 [2022-04-06 12:29:05,541 INFO L403 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 12:29:05,541 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 12:29:05,541 INFO L85 PathProgramCache]: Analyzing trace with hash 185978583, now seen corresponding path program 1 times [2022-04-06 12:29:05,542 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 12:29:05,542 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1052645089] [2022-04-06 12:29:05,542 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 12:29:05,542 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 12:29:05,554 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 12:29:05,586 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-04-06 12:29:05,592 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 12:29:05,611 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 8 [2022-04-06 12:29:05,613 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 12:29:05,616 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-04-06 12:29:05,616 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 12:29:05,617 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1052645089] [2022-04-06 12:29:05,617 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1052645089] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 12:29:05,617 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 12:29:05,617 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2022-04-06 12:29:05,617 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1602722021] [2022-04-06 12:29:05,617 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 12:29:05,617 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2022-04-06 12:29:05,617 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-06 12:29:05,618 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2022-04-06 12:29:05,618 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2022-04-06 12:29:05,618 INFO L87 Difference]: Start difference. First operand 32 states and 41 transitions. Second operand has 6 states, 6 states have (on average 1.8333333333333333) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2022-04-06 12:29:05,730 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 12:29:05,730 INFO L93 Difference]: Finished difference Result 46 states and 60 transitions. [2022-04-06 12:29:05,730 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2022-04-06 12:29:05,731 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 1.8333333333333333) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) Word has length 17 [2022-04-06 12:29:05,731 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 12:29:05,732 INFO L225 Difference]: With dead ends: 46 [2022-04-06 12:29:05,732 INFO L226 Difference]: Without dead ends: 44 [2022-04-06 12:29:05,733 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 13 GetRequests, 5 SyntacticMatches, 0 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=28, Invalid=62, Unknown=0, NotChecked=0, Total=90 [2022-04-06 12:29:05,734 INFO L913 BasicCegarLoop]: 34 mSDtfsCounter, 19 mSDsluCounter, 44 mSDsCounter, 0 mSdLazyCounter, 93 mSolverCounterSat, 13 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 24 SdHoareTripleChecker+Valid, 78 SdHoareTripleChecker+Invalid, 106 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 13 IncrementalHoareTripleChecker+Valid, 93 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-04-06 12:29:05,734 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [24 Valid, 78 Invalid, 106 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [13 Valid, 93 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-06 12:29:05,735 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 44 states. [2022-04-06 12:29:05,740 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 44 to 36. [2022-04-06 12:29:05,740 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 36 states, 22 states have (on average 1.2727272727272727) internal successors, (28), 23 states have internal predecessors, (28), 9 states have call successors, (9), 5 states have call predecessors, (9), 4 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2022-04-06 12:29:05,742 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 36 states to 36 states and 44 transitions. [2022-04-06 12:29:05,742 INFO L78 Accepts]: Start accepts. Automaton has 36 states and 44 transitions. Word has length 17 [2022-04-06 12:29:05,743 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 12:29:05,743 INFO L478 AbstractCegarLoop]: Abstraction has 36 states and 44 transitions. [2022-04-06 12:29:05,745 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 1.8333333333333333) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2022-04-06 12:29:05,745 INFO L276 IsEmpty]: Start isEmpty. Operand 36 states and 44 transitions. [2022-04-06 12:29:05,746 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 23 [2022-04-06 12:29:05,746 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 12:29:05,746 INFO L499 BasicCegarLoop]: trace histogram [3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 12:29:05,746 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3 [2022-04-06 12:29:05,746 INFO L403 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 12:29:05,746 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 12:29:05,746 INFO L85 PathProgramCache]: Analyzing trace with hash -820589269, now seen corresponding path program 1 times [2022-04-06 12:29:05,747 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 12:29:05,747 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1412710917] [2022-04-06 12:29:05,747 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 12:29:05,747 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 12:29:05,760 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 12:29:05,760 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1364503863] [2022-04-06 12:29:05,761 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 12:29:05,761 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 12:29:05,761 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 12:29:05,771 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-04-06 12:29:05,782 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-04-06 12:29:05,809 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 12:29:05,816 INFO L263 TraceCheckSpWp]: Trace formula consists of 93 conjuncts, 9 conjunts are in the unsatisfiable core [2022-04-06 12:29:05,820 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 12:29:05,981 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2022-04-06 12:29:05,981 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-04-06 12:29:05,981 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 12:29:05,982 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1412710917] [2022-04-06 12:29:05,982 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 12:29:05,982 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1364503863] [2022-04-06 12:29:05,982 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1364503863] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 12:29:05,982 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 12:29:05,982 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-06 12:29:05,982 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1475735427] [2022-04-06 12:29:05,982 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 12:29:05,983 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-04-06 12:29:05,983 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-06 12:29:05,983 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-04-06 12:29:05,983 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-04-06 12:29:05,983 INFO L87 Difference]: Start difference. First operand 36 states and 44 transitions. Second operand has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2022-04-06 12:29:06,031 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 12:29:06,031 INFO L93 Difference]: Finished difference Result 65 states and 87 transitions. [2022-04-06 12:29:06,032 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-04-06 12:29:06,032 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) Word has length 22 [2022-04-06 12:29:06,032 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 12:29:06,033 INFO L225 Difference]: With dead ends: 65 [2022-04-06 12:29:06,033 INFO L226 Difference]: Without dead ends: 50 [2022-04-06 12:29:06,034 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 22 GetRequests, 18 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-04-06 12:29:06,034 INFO L913 BasicCegarLoop]: 38 mSDtfsCounter, 10 mSDsluCounter, 83 mSDsCounter, 0 mSdLazyCounter, 46 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 14 SdHoareTripleChecker+Valid, 121 SdHoareTripleChecker+Invalid, 49 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 46 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-06 12:29:06,035 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [14 Valid, 121 Invalid, 49 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 46 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-06 12:29:06,035 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 50 states. [2022-04-06 12:29:06,041 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 50 to 50. [2022-04-06 12:29:06,041 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 50 states, 29 states have (on average 1.2758620689655173) internal successors, (37), 31 states have internal predecessors, (37), 15 states have call successors, (15), 6 states have call predecessors, (15), 5 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) [2022-04-06 12:29:06,042 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 50 states to 50 states and 64 transitions. [2022-04-06 12:29:06,042 INFO L78 Accepts]: Start accepts. Automaton has 50 states and 64 transitions. Word has length 22 [2022-04-06 12:29:06,042 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 12:29:06,042 INFO L478 AbstractCegarLoop]: Abstraction has 50 states and 64 transitions. [2022-04-06 12:29:06,042 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2022-04-06 12:29:06,042 INFO L276 IsEmpty]: Start isEmpty. Operand 50 states and 64 transitions. [2022-04-06 12:29:06,043 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 31 [2022-04-06 12:29:06,043 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 12:29:06,043 INFO L499 BasicCegarLoop]: trace histogram [4, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 12:29:06,066 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-04-06 12:29:06,253 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 12:29:06,254 INFO L403 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 12:29:06,254 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 12:29:06,254 INFO L85 PathProgramCache]: Analyzing trace with hash 1259710898, now seen corresponding path program 1 times [2022-04-06 12:29:06,254 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 12:29:06,254 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1650064350] [2022-04-06 12:29:06,255 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 12:29:06,255 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 12:29:06,261 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 12:29:06,262 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1622041090] [2022-04-06 12:29:06,262 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 12:29:06,262 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 12:29:06,262 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 12:29:06,263 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-04-06 12:29:06,265 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-04-06 12:29:06,301 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 12:29:06,302 INFO L263 TraceCheckSpWp]: Trace formula consists of 108 conjuncts, 7 conjunts are in the unsatisfiable core [2022-04-06 12:29:06,304 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 12:29:06,394 INFO L134 CoverageAnalysis]: Checked inductivity of 18 backedges. 6 proven. 0 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2022-04-06 12:29:06,394 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-04-06 12:29:06,394 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 12:29:06,394 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1650064350] [2022-04-06 12:29:06,394 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 12:29:06,394 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1622041090] [2022-04-06 12:29:06,394 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1622041090] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 12:29:06,394 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 12:29:06,395 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-06 12:29:06,395 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1363337061] [2022-04-06 12:29:06,395 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 12:29:06,395 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-04-06 12:29:06,395 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-06 12:29:06,395 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-04-06 12:29:06,395 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2022-04-06 12:29:06,396 INFO L87 Difference]: Start difference. First operand 50 states and 64 transitions. Second operand has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 4 states have call successors, (6), 4 states have call predecessors, (6), 2 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2022-04-06 12:29:06,420 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 12:29:06,420 INFO L93 Difference]: Finished difference Result 70 states and 80 transitions. [2022-04-06 12:29:06,420 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-04-06 12:29:06,420 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 4 states have call successors, (6), 4 states have call predecessors, (6), 2 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) Word has length 30 [2022-04-06 12:29:06,421 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 12:29:06,421 INFO L225 Difference]: With dead ends: 70 [2022-04-06 12:29:06,421 INFO L226 Difference]: Without dead ends: 63 [2022-04-06 12:29:06,421 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 29 GetRequests, 26 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2022-04-06 12:29:06,422 INFO L913 BasicCegarLoop]: 36 mSDtfsCounter, 3 mSDsluCounter, 88 mSDsCounter, 0 mSdLazyCounter, 19 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 3 SdHoareTripleChecker+Valid, 124 SdHoareTripleChecker+Invalid, 22 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 19 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-06 12:29:06,422 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [3 Valid, 124 Invalid, 22 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 19 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-06 12:29:06,422 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 63 states. [2022-04-06 12:29:06,427 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 63 to 62. [2022-04-06 12:29:06,427 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 62 states, 38 states have (on average 1.1842105263157894) internal successors, (45), 40 states have internal predecessors, (45), 15 states have call successors, (15), 9 states have call predecessors, (15), 8 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) [2022-04-06 12:29:06,428 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 62 states to 62 states and 72 transitions. [2022-04-06 12:29:06,428 INFO L78 Accepts]: Start accepts. Automaton has 62 states and 72 transitions. Word has length 30 [2022-04-06 12:29:06,428 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 12:29:06,428 INFO L478 AbstractCegarLoop]: Abstraction has 62 states and 72 transitions. [2022-04-06 12:29:06,428 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 4 states have call successors, (6), 4 states have call predecessors, (6), 2 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2022-04-06 12:29:06,428 INFO L276 IsEmpty]: Start isEmpty. Operand 62 states and 72 transitions. [2022-04-06 12:29:06,428 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 31 [2022-04-06 12:29:06,429 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 12:29:06,429 INFO L499 BasicCegarLoop]: trace histogram [4, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 12:29:06,456 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Ended with exit code 0 [2022-04-06 12:29:06,629 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 3 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable5 [2022-04-06 12:29:06,629 INFO L403 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 12:29:06,630 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 12:29:06,630 INFO L85 PathProgramCache]: Analyzing trace with hash 1260813165, now seen corresponding path program 1 times [2022-04-06 12:29:06,630 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 12:29:06,630 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1337299698] [2022-04-06 12:29:06,630 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 12:29:06,630 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 12:29:06,644 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 12:29:06,645 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1556688360] [2022-04-06 12:29:06,645 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 12:29:06,645 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 12:29:06,645 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 12:29:06,650 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-04-06 12:29:06,655 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-04-06 12:29:06,687 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 12:29:06,688 INFO L263 TraceCheckSpWp]: Trace formula consists of 108 conjuncts, 7 conjunts are in the unsatisfiable core [2022-04-06 12:29:06,689 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 12:29:06,788 INFO L134 CoverageAnalysis]: Checked inductivity of 18 backedges. 6 proven. 0 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2022-04-06 12:29:06,788 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-04-06 12:29:06,788 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 12:29:06,788 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1337299698] [2022-04-06 12:29:06,788 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 12:29:06,788 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1556688360] [2022-04-06 12:29:06,788 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1556688360] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 12:29:06,789 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 12:29:06,789 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-06 12:29:06,789 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1263057970] [2022-04-06 12:29:06,789 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 12:29:06,789 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-04-06 12:29:06,789 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-06 12:29:06,789 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-04-06 12:29:06,790 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-04-06 12:29:06,790 INFO L87 Difference]: Start difference. First operand 62 states and 72 transitions. Second operand has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2022-04-06 12:29:06,831 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 12:29:06,831 INFO L93 Difference]: Finished difference Result 76 states and 91 transitions. [2022-04-06 12:29:06,834 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-04-06 12:29:06,834 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) Word has length 30 [2022-04-06 12:29:06,836 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 12:29:06,838 INFO L225 Difference]: With dead ends: 76 [2022-04-06 12:29:06,838 INFO L226 Difference]: Without dead ends: 64 [2022-04-06 12:29:06,838 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 30 GetRequests, 26 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-04-06 12:29:06,839 INFO L913 BasicCegarLoop]: 29 mSDtfsCounter, 11 mSDsluCounter, 66 mSDsCounter, 0 mSdLazyCounter, 47 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 14 SdHoareTripleChecker+Valid, 95 SdHoareTripleChecker+Invalid, 50 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 47 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-06 12:29:06,839 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [14 Valid, 95 Invalid, 50 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 47 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-06 12:29:06,840 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 64 states. [2022-04-06 12:29:06,861 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 64 to 63. [2022-04-06 12:29:06,861 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 63 states, 39 states have (on average 1.2307692307692308) internal successors, (48), 41 states have internal predecessors, (48), 15 states have call successors, (15), 9 states have call predecessors, (15), 8 states have return successors, (13), 12 states have call predecessors, (13), 13 states have call successors, (13) [2022-04-06 12:29:06,862 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 63 states to 63 states and 76 transitions. [2022-04-06 12:29:06,862 INFO L78 Accepts]: Start accepts. Automaton has 63 states and 76 transitions. Word has length 30 [2022-04-06 12:29:06,862 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 12:29:06,862 INFO L478 AbstractCegarLoop]: Abstraction has 63 states and 76 transitions. [2022-04-06 12:29:06,862 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2022-04-06 12:29:06,862 INFO L276 IsEmpty]: Start isEmpty. Operand 63 states and 76 transitions. [2022-04-06 12:29:06,863 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 38 [2022-04-06 12:29:06,863 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 12:29:06,863 INFO L499 BasicCegarLoop]: trace histogram [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] [2022-04-06 12:29:06,883 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-04-06 12:29:07,063 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 12:29:07,064 INFO L403 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 12:29:07,064 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 12:29:07,064 INFO L85 PathProgramCache]: Analyzing trace with hash 1811137592, now seen corresponding path program 1 times [2022-04-06 12:29:07,064 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 12:29:07,064 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1173593527] [2022-04-06 12:29:07,065 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 12:29:07,065 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 12:29:07,071 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 12:29:07,072 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [834611272] [2022-04-06 12:29:07,072 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 12:29:07,072 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 12:29:07,072 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 12:29:07,073 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-04-06 12:29:07,074 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-04-06 12:29:07,108 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 12:29:07,109 INFO L263 TraceCheckSpWp]: Trace formula consists of 126 conjuncts, 7 conjunts are in the unsatisfiable core [2022-04-06 12:29:07,111 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 12:29:07,195 INFO L134 CoverageAnalysis]: Checked inductivity of 34 backedges. 18 proven. 2 refuted. 0 times theorem prover too weak. 14 trivial. 0 not checked. [2022-04-06 12:29:07,195 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 12:29:07,292 INFO L134 CoverageAnalysis]: Checked inductivity of 34 backedges. 8 proven. 2 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2022-04-06 12:29:07,293 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 12:29:07,293 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1173593527] [2022-04-06 12:29:07,293 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 12:29:07,293 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [834611272] [2022-04-06 12:29:07,293 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [834611272] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-06 12:29:07,293 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-06 12:29:07,293 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 5] total 8 [2022-04-06 12:29:07,293 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1207976442] [2022-04-06 12:29:07,293 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-04-06 12:29:07,294 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2022-04-06 12:29:07,294 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-06 12:29:07,294 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2022-04-06 12:29:07,294 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=20, Invalid=36, Unknown=0, NotChecked=0, Total=56 [2022-04-06 12:29:07,294 INFO L87 Difference]: Start difference. First operand 63 states and 76 transitions. Second operand has 8 states, 8 states have (on average 3.625) internal successors, (29), 8 states have internal predecessors, (29), 6 states have call successors, (12), 5 states have call predecessors, (12), 5 states have return successors, (10), 5 states have call predecessors, (10), 4 states have call successors, (10) [2022-04-06 12:29:07,373 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 12:29:07,374 INFO L93 Difference]: Finished difference Result 144 states and 177 transitions. [2022-04-06 12:29:07,374 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2022-04-06 12:29:07,374 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 8 states have (on average 3.625) internal successors, (29), 8 states have internal predecessors, (29), 6 states have call successors, (12), 5 states have call predecessors, (12), 5 states have return successors, (10), 5 states have call predecessors, (10), 4 states have call successors, (10) Word has length 37 [2022-04-06 12:29:07,374 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 12:29:07,376 INFO L225 Difference]: With dead ends: 144 [2022-04-06 12:29:07,376 INFO L226 Difference]: Without dead ends: 119 [2022-04-06 12:29:07,376 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 76 GetRequests, 67 SyntacticMatches, 0 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 7 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=40, Invalid=70, Unknown=0, NotChecked=0, Total=110 [2022-04-06 12:29:07,377 INFO L913 BasicCegarLoop]: 45 mSDtfsCounter, 41 mSDsluCounter, 162 mSDsCounter, 0 mSdLazyCounter, 57 mSolverCounterSat, 14 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 41 SdHoareTripleChecker+Valid, 207 SdHoareTripleChecker+Invalid, 71 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 14 IncrementalHoareTripleChecker+Valid, 57 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-04-06 12:29:07,377 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [41 Valid, 207 Invalid, 71 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [14 Valid, 57 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-06 12:29:07,377 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 119 states. [2022-04-06 12:29:07,385 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 119 to 112. [2022-04-06 12:29:07,385 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 112 states, 71 states have (on average 1.2112676056338028) internal successors, (86), 74 states have internal predecessors, (86), 25 states have call successors, (25), 16 states have call predecessors, (25), 15 states have return successors, (22), 21 states have call predecessors, (22), 22 states have call successors, (22) [2022-04-06 12:29:07,386 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 112 states to 112 states and 133 transitions. [2022-04-06 12:29:07,386 INFO L78 Accepts]: Start accepts. Automaton has 112 states and 133 transitions. Word has length 37 [2022-04-06 12:29:07,386 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 12:29:07,386 INFO L478 AbstractCegarLoop]: Abstraction has 112 states and 133 transitions. [2022-04-06 12:29:07,387 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 8 states have (on average 3.625) internal successors, (29), 8 states have internal predecessors, (29), 6 states have call successors, (12), 5 states have call predecessors, (12), 5 states have return successors, (10), 5 states have call predecessors, (10), 4 states have call successors, (10) [2022-04-06 12:29:07,387 INFO L276 IsEmpty]: Start isEmpty. Operand 112 states and 133 transitions. [2022-04-06 12:29:07,387 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 41 [2022-04-06 12:29:07,387 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 12:29:07,387 INFO L499 BasicCegarLoop]: trace histogram [6, 5, 5, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 12:29:07,404 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-04-06 12:29:07,588 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 12:29:07,588 INFO L403 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 12:29:07,588 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 12:29:07,588 INFO L85 PathProgramCache]: Analyzing trace with hash -599722260, now seen corresponding path program 1 times [2022-04-06 12:29:07,588 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 12:29:07,588 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1535677257] [2022-04-06 12:29:07,589 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 12:29:07,589 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 12:29:07,594 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 12:29:07,595 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [722225934] [2022-04-06 12:29:07,595 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 12:29:07,595 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 12:29:07,595 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 12:29:07,596 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-04-06 12:29:07,597 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-04-06 12:29:07,636 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 12:29:07,637 INFO L263 TraceCheckSpWp]: Trace formula consists of 130 conjuncts, 13 conjunts are in the unsatisfiable core [2022-04-06 12:29:07,638 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 12:29:07,770 INFO L134 CoverageAnalysis]: Checked inductivity of 55 backedges. 10 proven. 5 refuted. 0 times theorem prover too weak. 40 trivial. 0 not checked. [2022-04-06 12:29:07,770 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 12:29:07,883 INFO L134 CoverageAnalysis]: Checked inductivity of 55 backedges. 10 proven. 0 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2022-04-06 12:29:07,884 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 12:29:07,884 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1535677257] [2022-04-06 12:29:07,884 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 12:29:07,884 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [722225934] [2022-04-06 12:29:07,884 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [722225934] provided 1 perfect and 1 imperfect interpolant sequences [2022-04-06 12:29:07,884 INFO L184 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2022-04-06 12:29:07,884 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [6] total 7 [2022-04-06 12:29:07,884 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [136416173] [2022-04-06 12:29:07,884 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 12:29:07,885 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-04-06 12:29:07,885 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-06 12:29:07,885 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-04-06 12:29:07,885 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=29, Unknown=0, NotChecked=0, Total=42 [2022-04-06 12:29:07,885 INFO L87 Difference]: Start difference. First operand 112 states and 133 transitions. Second operand has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2022-04-06 12:29:07,932 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 12:29:07,932 INFO L93 Difference]: Finished difference Result 129 states and 154 transitions. [2022-04-06 12:29:07,932 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-04-06 12:29:07,932 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) Word has length 40 [2022-04-06 12:29:07,932 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 12:29:07,933 INFO L225 Difference]: With dead ends: 129 [2022-04-06 12:29:07,933 INFO L226 Difference]: Without dead ends: 125 [2022-04-06 12:29:07,933 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 80 GetRequests, 72 SyntacticMatches, 2 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=17, Invalid=39, Unknown=0, NotChecked=0, Total=56 [2022-04-06 12:29:07,934 INFO L913 BasicCegarLoop]: 34 mSDtfsCounter, 11 mSDsluCounter, 69 mSDsCounter, 0 mSdLazyCounter, 46 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 14 SdHoareTripleChecker+Valid, 103 SdHoareTripleChecker+Invalid, 47 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 46 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-06 12:29:07,934 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [14 Valid, 103 Invalid, 47 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 46 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-06 12:29:07,934 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 125 states. [2022-04-06 12:29:07,942 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 125 to 122. [2022-04-06 12:29:07,942 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 122 states, 78 states have (on average 1.1794871794871795) internal successors, (92), 81 states have internal predecessors, (92), 27 states have call successors, (27), 18 states have call predecessors, (27), 16 states have return successors, (24), 22 states have call predecessors, (24), 24 states have call successors, (24) [2022-04-06 12:29:07,943 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 122 states to 122 states and 143 transitions. [2022-04-06 12:29:07,943 INFO L78 Accepts]: Start accepts. Automaton has 122 states and 143 transitions. Word has length 40 [2022-04-06 12:29:07,943 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 12:29:07,943 INFO L478 AbstractCegarLoop]: Abstraction has 122 states and 143 transitions. [2022-04-06 12:29:07,944 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2022-04-06 12:29:07,944 INFO L276 IsEmpty]: Start isEmpty. Operand 122 states and 143 transitions. [2022-04-06 12:29:07,945 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 54 [2022-04-06 12:29:07,945 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 12:29:07,945 INFO L499 BasicCegarLoop]: trace histogram [8, 7, 7, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 12:29:07,967 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-04-06 12:29:08,160 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 12:29:08,160 INFO L403 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 12:29:08,160 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 12:29:08,160 INFO L85 PathProgramCache]: Analyzing trace with hash 560903707, now seen corresponding path program 1 times [2022-04-06 12:29:08,161 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 12:29:08,161 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2018610900] [2022-04-06 12:29:08,161 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 12:29:08,161 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 12:29:08,167 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 12:29:08,167 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [977199064] [2022-04-06 12:29:08,167 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 12:29:08,167 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 12:29:08,167 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 12:29:08,168 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-04-06 12:29:08,169 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-04-06 12:29:08,204 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 12:29:08,205 INFO L263 TraceCheckSpWp]: Trace formula consists of 154 conjuncts, 9 conjunts are in the unsatisfiable core [2022-04-06 12:29:08,210 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 12:29:08,296 INFO L134 CoverageAnalysis]: Checked inductivity of 104 backedges. 36 proven. 42 refuted. 0 times theorem prover too weak. 26 trivial. 0 not checked. [2022-04-06 12:29:08,296 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 12:29:08,396 INFO L134 CoverageAnalysis]: Checked inductivity of 104 backedges. 14 proven. 6 refuted. 0 times theorem prover too weak. 84 trivial. 0 not checked. [2022-04-06 12:29:08,396 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 12:29:08,396 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2018610900] [2022-04-06 12:29:08,396 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 12:29:08,396 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [977199064] [2022-04-06 12:29:08,397 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [977199064] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-06 12:29:08,397 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-06 12:29:08,397 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 9 [2022-04-06 12:29:08,397 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1685321356] [2022-04-06 12:29:08,397 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-04-06 12:29:08,397 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2022-04-06 12:29:08,397 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-06 12:29:08,397 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2022-04-06 12:29:08,398 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=26, Invalid=46, Unknown=0, NotChecked=0, Total=72 [2022-04-06 12:29:08,398 INFO L87 Difference]: Start difference. First operand 122 states and 143 transitions. Second operand has 9 states, 9 states have (on average 4.0) internal successors, (36), 9 states have internal predecessors, (36), 7 states have call successors, (18), 5 states have call predecessors, (18), 5 states have return successors, (16), 6 states have call predecessors, (16), 6 states have call successors, (16) [2022-04-06 12:29:08,486 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 12:29:08,487 INFO L93 Difference]: Finished difference Result 198 states and 236 transitions. [2022-04-06 12:29:08,487 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2022-04-06 12:29:08,487 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 9 states have (on average 4.0) internal successors, (36), 9 states have internal predecessors, (36), 7 states have call successors, (18), 5 states have call predecessors, (18), 5 states have return successors, (16), 6 states have call predecessors, (16), 6 states have call successors, (16) Word has length 53 [2022-04-06 12:29:08,487 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 12:29:08,489 INFO L225 Difference]: With dead ends: 198 [2022-04-06 12:29:08,489 INFO L226 Difference]: Without dead ends: 177 [2022-04-06 12:29:08,489 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 107 GetRequests, 97 SyntacticMatches, 1 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 9 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=37, Invalid=73, Unknown=0, NotChecked=0, Total=110 [2022-04-06 12:29:08,490 INFO L913 BasicCegarLoop]: 54 mSDtfsCounter, 52 mSDsluCounter, 214 mSDsCounter, 0 mSdLazyCounter, 84 mSolverCounterSat, 13 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 52 SdHoareTripleChecker+Valid, 268 SdHoareTripleChecker+Invalid, 97 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 13 IncrementalHoareTripleChecker+Valid, 84 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-04-06 12:29:08,490 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [52 Valid, 268 Invalid, 97 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [13 Valid, 84 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-06 12:29:08,491 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 177 states. [2022-04-06 12:29:08,500 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 177 to 172. [2022-04-06 12:29:08,501 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 172 states, 111 states have (on average 1.1801801801801801) internal successors, (131), 117 states have internal predecessors, (131), 39 states have call successors, (39), 23 states have call predecessors, (39), 21 states have return successors, (35), 31 states have call predecessors, (35), 35 states have call successors, (35) [2022-04-06 12:29:08,502 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 172 states to 172 states and 205 transitions. [2022-04-06 12:29:08,502 INFO L78 Accepts]: Start accepts. Automaton has 172 states and 205 transitions. Word has length 53 [2022-04-06 12:29:08,502 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 12:29:08,502 INFO L478 AbstractCegarLoop]: Abstraction has 172 states and 205 transitions. [2022-04-06 12:29:08,502 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 9 states have (on average 4.0) internal successors, (36), 9 states have internal predecessors, (36), 7 states have call successors, (18), 5 states have call predecessors, (18), 5 states have return successors, (16), 6 states have call predecessors, (16), 6 states have call successors, (16) [2022-04-06 12:29:08,502 INFO L276 IsEmpty]: Start isEmpty. Operand 172 states and 205 transitions. [2022-04-06 12:29:08,503 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 63 [2022-04-06 12:29:08,503 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 12:29:08,504 INFO L499 BasicCegarLoop]: trace histogram [9, 8, 8, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 12:29:08,529 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-04-06 12:29:08,711 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable9,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 12:29:08,711 INFO L403 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 12:29:08,712 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 12:29:08,712 INFO L85 PathProgramCache]: Analyzing trace with hash -453219492, now seen corresponding path program 1 times [2022-04-06 12:29:08,712 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 12:29:08,712 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1889449691] [2022-04-06 12:29:08,712 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 12:29:08,712 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 12:29:08,718 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 12:29:08,718 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1734701117] [2022-04-06 12:29:08,719 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 12:29:08,719 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 12:29:08,719 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 12:29:08,724 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-04-06 12:29:08,725 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-04-06 12:29:08,761 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 12:29:08,762 INFO L263 TraceCheckSpWp]: Trace formula consists of 178 conjuncts, 25 conjunts are in the unsatisfiable core [2022-04-06 12:29:08,764 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 12:29:09,062 INFO L134 CoverageAnalysis]: Checked inductivity of 137 backedges. 16 proven. 9 refuted. 0 times theorem prover too weak. 112 trivial. 0 not checked. [2022-04-06 12:29:09,062 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 12:29:09,968 INFO L134 CoverageAnalysis]: Checked inductivity of 137 backedges. 16 proven. 9 refuted. 0 times theorem prover too weak. 112 trivial. 0 not checked. [2022-04-06 12:29:09,969 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 12:29:09,969 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1889449691] [2022-04-06 12:29:09,969 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 12:29:09,969 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1734701117] [2022-04-06 12:29:09,969 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1734701117] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-06 12:29:09,969 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-06 12:29:09,969 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7] total 10 [2022-04-06 12:29:09,971 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [816353513] [2022-04-06 12:29:09,971 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-04-06 12:29:09,971 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2022-04-06 12:29:09,971 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-06 12:29:09,972 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2022-04-06 12:29:09,972 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=24, Invalid=66, Unknown=0, NotChecked=0, Total=90 [2022-04-06 12:29:09,972 INFO L87 Difference]: Start difference. First operand 172 states and 205 transitions. Second operand has 10 states, 10 states have (on average 3.4) internal successors, (34), 9 states have internal predecessors, (34), 7 states have call successors, (20), 2 states have call predecessors, (20), 1 states have return successors, (17), 5 states have call predecessors, (17), 5 states have call successors, (17) [2022-04-06 12:29:14,534 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 12:29:14,534 INFO L93 Difference]: Finished difference Result 270 states and 344 transitions. [2022-04-06 12:29:14,535 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2022-04-06 12:29:14,535 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 10 states have (on average 3.4) internal successors, (34), 9 states have internal predecessors, (34), 7 states have call successors, (20), 2 states have call predecessors, (20), 1 states have return successors, (17), 5 states have call predecessors, (17), 5 states have call successors, (17) Word has length 62 [2022-04-06 12:29:14,535 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 12:29:14,536 INFO L225 Difference]: With dead ends: 270 [2022-04-06 12:29:14,536 INFO L226 Difference]: Without dead ends: 225 [2022-04-06 12:29:14,537 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 127 GetRequests, 112 SyntacticMatches, 3 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 9 ImplicationChecksByTransitivity, 3.9s TimeCoverageRelationStatistics Valid=50, Invalid=132, Unknown=0, NotChecked=0, Total=182 [2022-04-06 12:29:14,537 INFO L913 BasicCegarLoop]: 50 mSDtfsCounter, 53 mSDsluCounter, 150 mSDsCounter, 0 mSdLazyCounter, 316 mSolverCounterSat, 70 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.6s Time, 0 mProtectedPredicate, 0 mProtectedAction, 59 SdHoareTripleChecker+Valid, 200 SdHoareTripleChecker+Invalid, 386 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 70 IncrementalHoareTripleChecker+Valid, 316 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.7s IncrementalHoareTripleChecker+Time [2022-04-06 12:29:14,537 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [59 Valid, 200 Invalid, 386 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [70 Valid, 316 Invalid, 0 Unknown, 0 Unchecked, 0.7s Time] [2022-04-06 12:29:14,538 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 225 states. [2022-04-06 12:29:14,550 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 225 to 212. [2022-04-06 12:29:14,550 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 212 states, 141 states have (on average 1.2198581560283688) internal successors, (172), 147 states have internal predecessors, (172), 45 states have call successors, (45), 26 states have call predecessors, (45), 25 states have return successors, (42), 38 states have call predecessors, (42), 42 states have call successors, (42) [2022-04-06 12:29:14,551 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 212 states to 212 states and 259 transitions. [2022-04-06 12:29:14,551 INFO L78 Accepts]: Start accepts. Automaton has 212 states and 259 transitions. Word has length 62 [2022-04-06 12:29:14,552 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 12:29:14,552 INFO L478 AbstractCegarLoop]: Abstraction has 212 states and 259 transitions. [2022-04-06 12:29:14,552 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 10 states have (on average 3.4) internal successors, (34), 9 states have internal predecessors, (34), 7 states have call successors, (20), 2 states have call predecessors, (20), 1 states have return successors, (17), 5 states have call predecessors, (17), 5 states have call successors, (17) [2022-04-06 12:29:14,552 INFO L276 IsEmpty]: Start isEmpty. Operand 212 states and 259 transitions. [2022-04-06 12:29:14,553 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 74 [2022-04-06 12:29:14,553 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 12:29:14,553 INFO L499 BasicCegarLoop]: trace histogram [11, 10, 10, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 12:29:14,579 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-04-06 12:29:14,771 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable10,8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 12:29:14,772 INFO L403 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 12:29:14,772 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 12:29:14,772 INFO L85 PathProgramCache]: Analyzing trace with hash 929445032, now seen corresponding path program 1 times [2022-04-06 12:29:14,772 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 12:29:14,772 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1597590926] [2022-04-06 12:29:14,772 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 12:29:14,772 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 12:29:14,779 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 12:29:14,779 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1837409087] [2022-04-06 12:29:14,779 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 12:29:14,779 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 12:29:14,779 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 12:29:14,781 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-04-06 12:29:14,782 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-04-06 12:29:14,816 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 12:29:14,817 INFO L263 TraceCheckSpWp]: Trace formula consists of 198 conjuncts, 35 conjunts are in the unsatisfiable core [2022-04-06 12:29:14,819 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 12:29:15,223 INFO L134 CoverageAnalysis]: Checked inductivity of 211 backedges. 66 proven. 13 refuted. 0 times theorem prover too weak. 132 trivial. 0 not checked. [2022-04-06 12:29:15,223 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 12:29:15,440 INFO L134 CoverageAnalysis]: Checked inductivity of 211 backedges. 68 proven. 2 refuted. 0 times theorem prover too weak. 141 trivial. 0 not checked. [2022-04-06 12:29:15,441 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 12:29:15,441 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1597590926] [2022-04-06 12:29:15,441 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 12:29:15,441 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1837409087] [2022-04-06 12:29:15,441 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1837409087] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-06 12:29:15,441 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-06 12:29:15,441 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 9] total 16 [2022-04-06 12:29:15,442 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2006663887] [2022-04-06 12:29:15,442 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-04-06 12:29:15,442 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2022-04-06 12:29:15,442 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-06 12:29:15,443 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2022-04-06 12:29:15,443 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=51, Invalid=189, Unknown=0, NotChecked=0, Total=240 [2022-04-06 12:29:15,443 INFO L87 Difference]: Start difference. First operand 212 states and 259 transitions. Second operand has 16 states, 12 states have (on average 3.0833333333333335) internal successors, (37), 11 states have internal predecessors, (37), 8 states have call successors, (20), 2 states have call predecessors, (20), 2 states have return successors, (18), 7 states have call predecessors, (18), 6 states have call successors, (18) [2022-04-06 12:29:15,807 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 12:29:15,808 INFO L93 Difference]: Finished difference Result 260 states and 320 transitions. [2022-04-06 12:29:15,808 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2022-04-06 12:29:15,808 INFO L78 Accepts]: Start accepts. Automaton has has 16 states, 12 states have (on average 3.0833333333333335) internal successors, (37), 11 states have internal predecessors, (37), 8 states have call successors, (20), 2 states have call predecessors, (20), 2 states have return successors, (18), 7 states have call predecessors, (18), 6 states have call successors, (18) Word has length 73 [2022-04-06 12:29:15,808 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 12:29:15,809 INFO L225 Difference]: With dead ends: 260 [2022-04-06 12:29:15,809 INFO L226 Difference]: Without dead ends: 184 [2022-04-06 12:29:15,810 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 149 GetRequests, 129 SyntacticMatches, 2 SemanticMatches, 18 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 39 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=76, Invalid=304, Unknown=0, NotChecked=0, Total=380 [2022-04-06 12:29:15,810 INFO L913 BasicCegarLoop]: 34 mSDtfsCounter, 46 mSDsluCounter, 136 mSDsCounter, 0 mSdLazyCounter, 395 mSolverCounterSat, 54 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 59 SdHoareTripleChecker+Valid, 170 SdHoareTripleChecker+Invalid, 449 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 54 IncrementalHoareTripleChecker+Valid, 395 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2022-04-06 12:29:15,811 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [59 Valid, 170 Invalid, 449 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [54 Valid, 395 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2022-04-06 12:29:15,811 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 184 states. [2022-04-06 12:29:15,825 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 184 to 173. [2022-04-06 12:29:15,826 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 173 states, 114 states have (on average 1.1842105263157894) internal successors, (135), 118 states have internal predecessors, (135), 36 states have call successors, (36), 24 states have call predecessors, (36), 22 states have return successors, (33), 30 states have call predecessors, (33), 33 states have call successors, (33) [2022-04-06 12:29:15,826 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 173 states to 173 states and 204 transitions. [2022-04-06 12:29:15,826 INFO L78 Accepts]: Start accepts. Automaton has 173 states and 204 transitions. Word has length 73 [2022-04-06 12:29:15,826 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 12:29:15,827 INFO L478 AbstractCegarLoop]: Abstraction has 173 states and 204 transitions. [2022-04-06 12:29:15,827 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 16 states, 12 states have (on average 3.0833333333333335) internal successors, (37), 11 states have internal predecessors, (37), 8 states have call successors, (20), 2 states have call predecessors, (20), 2 states have return successors, (18), 7 states have call predecessors, (18), 6 states have call successors, (18) [2022-04-06 12:29:15,827 INFO L276 IsEmpty]: Start isEmpty. Operand 173 states and 204 transitions. [2022-04-06 12:29:15,827 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 83 [2022-04-06 12:29:15,827 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 12:29:15,827 INFO L499 BasicCegarLoop]: trace histogram [13, 12, 12, 3, 3, 3, 3, 3, 3, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 12:29:15,851 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-04-06 12:29:16,044 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 9 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable11 [2022-04-06 12:29:16,045 INFO L403 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 12:29:16,045 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 12:29:16,045 INFO L85 PathProgramCache]: Analyzing trace with hash -1139963303, now seen corresponding path program 1 times [2022-04-06 12:29:16,045 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 12:29:16,045 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [825894312] [2022-04-06 12:29:16,045 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 12:29:16,045 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 12:29:16,060 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 12:29:16,060 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1279805799] [2022-04-06 12:29:16,060 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 12:29:16,060 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 12:29:16,060 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 12:29:16,061 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-04-06 12:29:16,062 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-04-06 12:29:16,099 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 12:29:16,101 INFO L263 TraceCheckSpWp]: Trace formula consists of 211 conjuncts, 4 conjunts are in the unsatisfiable core [2022-04-06 12:29:16,102 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 12:29:16,262 INFO L134 CoverageAnalysis]: Checked inductivity of 306 backedges. 84 proven. 0 refuted. 0 times theorem prover too weak. 222 trivial. 0 not checked. [2022-04-06 12:29:16,262 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-04-06 12:29:16,263 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 12:29:16,263 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [825894312] [2022-04-06 12:29:16,263 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 12:29:16,263 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1279805799] [2022-04-06 12:29:16,263 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1279805799] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 12:29:16,263 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 12:29:16,263 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-06 12:29:16,263 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [784265794] [2022-04-06 12:29:16,263 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 12:29:16,263 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-04-06 12:29:16,263 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-06 12:29:16,264 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-04-06 12:29:16,264 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=10, Invalid=10, Unknown=0, NotChecked=0, Total=20 [2022-04-06 12:29:16,264 INFO L87 Difference]: Start difference. First operand 173 states and 204 transitions. Second operand has 5 states, 5 states have (on average 4.6) internal successors, (23), 5 states have internal predecessors, (23), 5 states have call successors, (15), 2 states have call predecessors, (15), 2 states have return successors, (13), 5 states have call predecessors, (13), 5 states have call successors, (13) [2022-04-06 12:29:16,315 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 12:29:16,315 INFO L93 Difference]: Finished difference Result 192 states and 227 transitions. [2022-04-06 12:29:16,315 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-04-06 12:29:16,315 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 4.6) internal successors, (23), 5 states have internal predecessors, (23), 5 states have call successors, (15), 2 states have call predecessors, (15), 2 states have return successors, (13), 5 states have call predecessors, (13), 5 states have call successors, (13) Word has length 82 [2022-04-06 12:29:16,316 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 12:29:16,316 INFO L225 Difference]: With dead ends: 192 [2022-04-06 12:29:16,317 INFO L226 Difference]: Without dead ends: 172 [2022-04-06 12:29:16,317 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 81 GetRequests, 78 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=10, Invalid=10, Unknown=0, NotChecked=0, Total=20 [2022-04-06 12:29:16,317 INFO L913 BasicCegarLoop]: 54 mSDtfsCounter, 27 mSDsluCounter, 31 mSDsCounter, 0 mSdLazyCounter, 29 mSolverCounterSat, 15 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 34 SdHoareTripleChecker+Valid, 85 SdHoareTripleChecker+Invalid, 44 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 15 IncrementalHoareTripleChecker+Valid, 29 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-06 12:29:16,317 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [34 Valid, 85 Invalid, 44 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [15 Valid, 29 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-06 12:29:16,318 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 172 states. [2022-04-06 12:29:16,326 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 172 to 167. [2022-04-06 12:29:16,327 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 167 states, 111 states have (on average 1.1711711711711712) internal successors, (130), 113 states have internal predecessors, (130), 34 states have call successors, (34), 22 states have call predecessors, (34), 21 states have return successors, (32), 31 states have call predecessors, (32), 32 states have call successors, (32) [2022-04-06 12:29:16,328 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 167 states to 167 states and 196 transitions. [2022-04-06 12:29:16,328 INFO L78 Accepts]: Start accepts. Automaton has 167 states and 196 transitions. Word has length 82 [2022-04-06 12:29:16,328 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 12:29:16,328 INFO L478 AbstractCegarLoop]: Abstraction has 167 states and 196 transitions. [2022-04-06 12:29:16,328 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 4.6) internal successors, (23), 5 states have internal predecessors, (23), 5 states have call successors, (15), 2 states have call predecessors, (15), 2 states have return successors, (13), 5 states have call predecessors, (13), 5 states have call successors, (13) [2022-04-06 12:29:16,328 INFO L276 IsEmpty]: Start isEmpty. Operand 167 states and 196 transitions. [2022-04-06 12:29:16,329 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 92 [2022-04-06 12:29:16,329 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 12:29:16,329 INFO L499 BasicCegarLoop]: trace histogram [14, 13, 13, 5, 4, 4, 4, 4, 4, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 12:29:16,349 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Ended with exit code 0 [2022-04-06 12:29:16,543 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 10 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable12 [2022-04-06 12:29:16,543 INFO L403 AbstractCegarLoop]: === Iteration 14 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 12:29:16,544 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 12:29:16,544 INFO L85 PathProgramCache]: Analyzing trace with hash -468178091, now seen corresponding path program 2 times [2022-04-06 12:29:16,544 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 12:29:16,544 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [598248632] [2022-04-06 12:29:16,544 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 12:29:16,544 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 12:29:16,550 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 12:29:16,550 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [409562092] [2022-04-06 12:29:16,550 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-06 12:29:16,550 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 12:29:16,550 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 12:29:16,551 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-04-06 12:29:16,579 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Waiting until timeout for monitored process [2022-04-06 12:29:16,595 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-06 12:29:16,595 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-06 12:29:16,596 INFO L263 TraceCheckSpWp]: Trace formula consists of 237 conjuncts, 13 conjunts are in the unsatisfiable core [2022-04-06 12:29:16,598 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 12:29:16,751 INFO L134 CoverageAnalysis]: Checked inductivity of 382 backedges. 72 proven. 260 refuted. 0 times theorem prover too weak. 50 trivial. 0 not checked. [2022-04-06 12:29:16,751 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 12:29:16,898 INFO L134 CoverageAnalysis]: Checked inductivity of 382 backedges. 26 proven. 44 refuted. 0 times theorem prover too weak. 312 trivial. 0 not checked. [2022-04-06 12:29:16,898 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 12:29:16,898 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [598248632] [2022-04-06 12:29:16,898 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 12:29:16,898 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [409562092] [2022-04-06 12:29:16,898 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [409562092] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-06 12:29:16,898 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-06 12:29:16,898 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 8 [2022-04-06 12:29:16,898 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [599396085] [2022-04-06 12:29:16,899 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-04-06 12:29:16,899 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2022-04-06 12:29:16,899 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-06 12:29:16,899 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2022-04-06 12:29:16,899 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=23, Invalid=33, Unknown=0, NotChecked=0, Total=56 [2022-04-06 12:29:16,899 INFO L87 Difference]: Start difference. First operand 167 states and 196 transitions. Second operand has 8 states, 8 states have (on average 4.875) internal successors, (39), 8 states have internal predecessors, (39), 7 states have call successors, (29), 7 states have call predecessors, (29), 7 states have return successors, (27), 6 states have call predecessors, (27), 6 states have call successors, (27) [2022-04-06 12:29:16,979 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 12:29:16,980 INFO L93 Difference]: Finished difference Result 228 states and 280 transitions. [2022-04-06 12:29:16,980 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2022-04-06 12:29:16,980 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 8 states have (on average 4.875) internal successors, (39), 8 states have internal predecessors, (39), 7 states have call successors, (29), 7 states have call predecessors, (29), 7 states have return successors, (27), 6 states have call predecessors, (27), 6 states have call successors, (27) Word has length 91 [2022-04-06 12:29:16,980 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 12:29:16,981 INFO L225 Difference]: With dead ends: 228 [2022-04-06 12:29:16,981 INFO L226 Difference]: Without dead ends: 169 [2022-04-06 12:29:16,981 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 185 GetRequests, 174 SyntacticMatches, 1 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 14 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=51, Invalid=81, Unknown=0, NotChecked=0, Total=132 [2022-04-06 12:29:16,982 INFO L913 BasicCegarLoop]: 47 mSDtfsCounter, 17 mSDsluCounter, 97 mSDsCounter, 0 mSdLazyCounter, 50 mSolverCounterSat, 10 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 17 SdHoareTripleChecker+Valid, 144 SdHoareTripleChecker+Invalid, 60 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 10 IncrementalHoareTripleChecker+Valid, 50 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-06 12:29:16,982 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [17 Valid, 144 Invalid, 60 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [10 Valid, 50 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-06 12:29:16,982 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 169 states. [2022-04-06 12:29:16,996 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 169 to 169. [2022-04-06 12:29:16,996 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 169 states, 113 states have (on average 1.168141592920354) internal successors, (132), 115 states have internal predecessors, (132), 34 states have call successors, (34), 22 states have call predecessors, (34), 21 states have return successors, (32), 31 states have call predecessors, (32), 32 states have call successors, (32) [2022-04-06 12:29:16,997 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 169 states to 169 states and 198 transitions. [2022-04-06 12:29:16,997 INFO L78 Accepts]: Start accepts. Automaton has 169 states and 198 transitions. Word has length 91 [2022-04-06 12:29:16,997 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 12:29:16,997 INFO L478 AbstractCegarLoop]: Abstraction has 169 states and 198 transitions. [2022-04-06 12:29:16,998 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 8 states have (on average 4.875) internal successors, (39), 8 states have internal predecessors, (39), 7 states have call successors, (29), 7 states have call predecessors, (29), 7 states have return successors, (27), 6 states have call predecessors, (27), 6 states have call successors, (27) [2022-04-06 12:29:16,998 INFO L276 IsEmpty]: Start isEmpty. Operand 169 states and 198 transitions. [2022-04-06 12:29:17,001 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 95 [2022-04-06 12:29:17,002 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 12:29:17,002 INFO L499 BasicCegarLoop]: trace histogram [14, 13, 13, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 12:29:17,021 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-04-06 12:29:17,215 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 11 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable13 [2022-04-06 12:29:17,215 INFO L403 AbstractCegarLoop]: === Iteration 15 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 12:29:17,216 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 12:29:17,216 INFO L85 PathProgramCache]: Analyzing trace with hash -2091436208, now seen corresponding path program 1 times [2022-04-06 12:29:17,216 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 12:29:17,216 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [525172513] [2022-04-06 12:29:17,216 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 12:29:17,216 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 12:29:17,222 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 12:29:17,222 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2030462844] [2022-04-06 12:29:17,222 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 12:29:17,222 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 12:29:17,222 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 12:29:17,223 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-04-06 12:29:17,224 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-04-06 12:29:17,277 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 12:29:17,279 INFO L263 TraceCheckSpWp]: Trace formula consists of 248 conjuncts, 39 conjunts are in the unsatisfiable core [2022-04-06 12:29:17,281 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 12:29:17,618 INFO L134 CoverageAnalysis]: Checked inductivity of 366 backedges. 26 proven. 28 refuted. 0 times theorem prover too weak. 312 trivial. 0 not checked. [2022-04-06 12:29:17,618 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 12:29:42,782 INFO L134 CoverageAnalysis]: Checked inductivity of 366 backedges. 26 proven. 28 refuted. 0 times theorem prover too weak. 312 trivial. 0 not checked. [2022-04-06 12:29:42,782 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 12:29:42,789 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [525172513] [2022-04-06 12:29:42,790 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 12:29:42,790 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2030462844] [2022-04-06 12:29:42,790 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2030462844] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-06 12:29:42,790 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-06 12:29:42,790 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10] total 16 [2022-04-06 12:29:42,790 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [919990564] [2022-04-06 12:29:42,790 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-04-06 12:29:42,791 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2022-04-06 12:29:42,791 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-06 12:29:42,791 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2022-04-06 12:29:42,791 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=45, Invalid=195, Unknown=0, NotChecked=0, Total=240 [2022-04-06 12:29:42,792 INFO L87 Difference]: Start difference. First operand 169 states and 198 transitions. Second operand has 16 states, 16 states have (on average 3.0) internal successors, (48), 15 states have internal predecessors, (48), 11 states have call successors, (30), 2 states have call predecessors, (30), 1 states have return successors, (27), 9 states have call predecessors, (27), 9 states have call successors, (27) [2022-04-06 12:29:53,195 WARN L232 SmtUtils]: Spent 7.84s on a formula simplification. DAG size of input: 209 DAG size of output: 30 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-04-06 12:29:55,740 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-04-06 12:29:59,070 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.03s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-04-06 12:30:03,590 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 12:30:03,591 INFO L93 Difference]: Finished difference Result 271 states and 349 transitions. [2022-04-06 12:30:03,591 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2022-04-06 12:30:03,591 INFO L78 Accepts]: Start accepts. Automaton has has 16 states, 16 states have (on average 3.0) internal successors, (48), 15 states have internal predecessors, (48), 11 states have call successors, (30), 2 states have call predecessors, (30), 1 states have return successors, (27), 9 states have call predecessors, (27), 9 states have call successors, (27) Word has length 94 [2022-04-06 12:30:03,592 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 12:30:03,593 INFO L225 Difference]: With dead ends: 271 [2022-04-06 12:30:03,593 INFO L226 Difference]: Without dead ends: 232 [2022-04-06 12:30:03,594 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 192 GetRequests, 171 SyntacticMatches, 3 SemanticMatches, 18 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 25 ImplicationChecksByTransitivity, 12.5s TimeCoverageRelationStatistics Valid=72, Invalid=308, Unknown=0, NotChecked=0, Total=380 [2022-04-06 12:30:03,595 INFO L913 BasicCegarLoop]: 95 mSDtfsCounter, 86 mSDsluCounter, 371 mSDsCounter, 0 mSdLazyCounter, 750 mSolverCounterSat, 113 mSolverCounterUnsat, 2 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 11.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 99 SdHoareTripleChecker+Valid, 466 SdHoareTripleChecker+Invalid, 865 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 113 IncrementalHoareTripleChecker+Valid, 750 IncrementalHoareTripleChecker+Invalid, 2 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 11.5s IncrementalHoareTripleChecker+Time [2022-04-06 12:30:03,595 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [99 Valid, 466 Invalid, 865 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [113 Valid, 750 Invalid, 2 Unknown, 0 Unchecked, 11.5s Time] [2022-04-06 12:30:03,595 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 232 states. [2022-04-06 12:30:03,606 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 232 to 198. [2022-04-06 12:30:03,606 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 198 states, 131 states have (on average 1.2061068702290076) internal successors, (158), 135 states have internal predecessors, (158), 44 states have call successors, (44), 23 states have call predecessors, (44), 22 states have return successors, (42), 39 states have call predecessors, (42), 42 states have call successors, (42) [2022-04-06 12:30:03,607 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 198 states to 198 states and 244 transitions. [2022-04-06 12:30:03,607 INFO L78 Accepts]: Start accepts. Automaton has 198 states and 244 transitions. Word has length 94 [2022-04-06 12:30:03,607 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 12:30:03,607 INFO L478 AbstractCegarLoop]: Abstraction has 198 states and 244 transitions. [2022-04-06 12:30:03,607 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 16 states, 16 states have (on average 3.0) internal successors, (48), 15 states have internal predecessors, (48), 11 states have call successors, (30), 2 states have call predecessors, (30), 1 states have return successors, (27), 9 states have call predecessors, (27), 9 states have call successors, (27) [2022-04-06 12:30:03,607 INFO L276 IsEmpty]: Start isEmpty. Operand 198 states and 244 transitions. [2022-04-06 12:30:03,608 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 95 [2022-04-06 12:30:03,608 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 12:30:03,608 INFO L499 BasicCegarLoop]: trace histogram [14, 13, 13, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 12:30:03,625 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-04-06 12:30:03,814 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 12 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable14 [2022-04-06 12:30:03,814 INFO L403 AbstractCegarLoop]: === Iteration 16 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 12:30:03,814 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 12:30:03,815 INFO L85 PathProgramCache]: Analyzing trace with hash -2090333941, now seen corresponding path program 2 times [2022-04-06 12:30:03,815 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 12:30:03,815 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1511178353] [2022-04-06 12:30:03,815 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 12:30:03,815 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 12:30:03,821 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 12:30:03,821 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1533313474] [2022-04-06 12:30:03,821 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-06 12:30:03,821 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 12:30:03,822 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 12:30:03,828 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-04-06 12:30:03,832 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-04-06 12:30:03,876 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-06 12:30:03,876 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-06 12:30:03,877 INFO L263 TraceCheckSpWp]: Trace formula consists of 248 conjuncts, 15 conjunts are in the unsatisfiable core [2022-04-06 12:30:03,879 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 12:30:04,041 INFO L134 CoverageAnalysis]: Checked inductivity of 368 backedges. 322 proven. 2 refuted. 0 times theorem prover too weak. 44 trivial. 0 not checked. [2022-04-06 12:30:04,041 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 12:30:04,170 INFO L134 CoverageAnalysis]: Checked inductivity of 368 backedges. 54 proven. 2 refuted. 0 times theorem prover too weak. 312 trivial. 0 not checked. [2022-04-06 12:30:04,170 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 12:30:04,170 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1511178353] [2022-04-06 12:30:04,170 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 12:30:04,170 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1533313474] [2022-04-06 12:30:04,171 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1533313474] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-06 12:30:04,171 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-06 12:30:04,171 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9] total 9 [2022-04-06 12:30:04,171 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [879038488] [2022-04-06 12:30:04,171 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-04-06 12:30:04,171 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2022-04-06 12:30:04,171 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-06 12:30:04,171 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2022-04-06 12:30:04,171 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=30, Invalid=42, Unknown=0, NotChecked=0, Total=72 [2022-04-06 12:30:04,172 INFO L87 Difference]: Start difference. First operand 198 states and 244 transitions. Second operand has 9 states, 9 states have (on average 4.777777777777778) internal successors, (43), 9 states have internal predecessors, (43), 8 states have call successors, (29), 8 states have call predecessors, (29), 7 states have return successors, (27), 6 states have call predecessors, (27), 6 states have call successors, (27) [2022-04-06 12:30:04,259 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 12:30:04,260 INFO L93 Difference]: Finished difference Result 237 states and 285 transitions. [2022-04-06 12:30:04,260 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2022-04-06 12:30:04,260 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 9 states have (on average 4.777777777777778) internal successors, (43), 9 states have internal predecessors, (43), 8 states have call successors, (29), 8 states have call predecessors, (29), 7 states have return successors, (27), 6 states have call predecessors, (27), 6 states have call successors, (27) Word has length 94 [2022-04-06 12:30:04,260 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 12:30:04,261 INFO L225 Difference]: With dead ends: 237 [2022-04-06 12:30:04,261 INFO L226 Difference]: Without dead ends: 165 [2022-04-06 12:30:04,261 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 188 GetRequests, 179 SyntacticMatches, 1 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 10 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=39, Invalid=51, Unknown=0, NotChecked=0, Total=90 [2022-04-06 12:30:04,262 INFO L913 BasicCegarLoop]: 86 mSDtfsCounter, 54 mSDsluCounter, 119 mSDsCounter, 0 mSdLazyCounter, 64 mSolverCounterSat, 58 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 54 SdHoareTripleChecker+Valid, 205 SdHoareTripleChecker+Invalid, 122 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 58 IncrementalHoareTripleChecker+Valid, 64 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-04-06 12:30:04,262 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [54 Valid, 205 Invalid, 122 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [58 Valid, 64 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-06 12:30:04,262 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 165 states. [2022-04-06 12:30:04,273 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 165 to 152. [2022-04-06 12:30:04,273 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 152 states, 102 states have (on average 1.0784313725490196) internal successors, (110), 105 states have internal predecessors, (110), 27 states have call successors, (27), 23 states have call predecessors, (27), 22 states have return successors, (25), 23 states have call predecessors, (25), 25 states have call successors, (25) [2022-04-06 12:30:04,274 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 152 states to 152 states and 162 transitions. [2022-04-06 12:30:04,274 INFO L78 Accepts]: Start accepts. Automaton has 152 states and 162 transitions. Word has length 94 [2022-04-06 12:30:04,274 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 12:30:04,274 INFO L478 AbstractCegarLoop]: Abstraction has 152 states and 162 transitions. [2022-04-06 12:30:04,275 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 9 states have (on average 4.777777777777778) internal successors, (43), 9 states have internal predecessors, (43), 8 states have call successors, (29), 8 states have call predecessors, (29), 7 states have return successors, (27), 6 states have call predecessors, (27), 6 states have call successors, (27) [2022-04-06 12:30:04,275 INFO L276 IsEmpty]: Start isEmpty. Operand 152 states and 162 transitions. [2022-04-06 12:30:04,275 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 99 [2022-04-06 12:30:04,275 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 12:30:04,275 INFO L499 BasicCegarLoop]: trace histogram [15, 14, 14, 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] [2022-04-06 12:30:04,292 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Ended with exit code 0 [2022-04-06 12:30:04,491 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 13 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable15 [2022-04-06 12:30:04,491 INFO L403 AbstractCegarLoop]: === Iteration 17 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 12:30:04,492 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 12:30:04,492 INFO L85 PathProgramCache]: Analyzing trace with hash -952273693, now seen corresponding path program 2 times [2022-04-06 12:30:04,492 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 12:30:04,492 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1830594396] [2022-04-06 12:30:04,492 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 12:30:04,492 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 12:30:04,497 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 12:30:04,497 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1759079609] [2022-04-06 12:30:04,497 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-06 12:30:04,497 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 12:30:04,497 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 12:30:04,499 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-04-06 12:30:04,500 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-04-06 12:30:04,543 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-06 12:30:04,543 INFO L229 tOrderPrioritization]: Conjunction of SSA is sat [2022-04-06 12:30:04,543 INFO L352 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2022-04-06 12:30:04,562 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2022-04-06 12:30:04,592 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2022-04-06 12:30:04,592 INFO L618 BasicCegarLoop]: Counterexample is feasible [2022-04-06 12:30:04,593 INFO L788 garLoopResultBuilder]: Registering result UNSAFE for location __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION (0 of 1 remaining) [2022-04-06 12:30:04,631 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Forceful destruction successful, exit code 0 [2022-04-06 12:30:04,803 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 14 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable16 [2022-04-06 12:30:04,806 INFO L719 BasicCegarLoop]: Path program histogram: [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 12:30:04,808 INFO L178 ceAbstractionStarter]: Computing trace abstraction results [2022-04-06 12:30:04,854 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 06.04 12:30:04 BasicIcfg [2022-04-06 12:30:04,854 INFO L132 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2022-04-06 12:30:04,854 INFO L158 Benchmark]: Toolchain (without parser) took 60734.56ms. Allocated memory was 190.8MB in the beginning and 234.9MB in the end (delta: 44.0MB). Free memory was 139.4MB in the beginning and 109.6MB in the end (delta: 29.8MB). Peak memory consumption was 74.4MB. Max. memory is 8.0GB. [2022-04-06 12:30:04,854 INFO L158 Benchmark]: CDTParser took 0.09ms. Allocated memory is still 190.8MB. Free memory was 155.7MB in the beginning and 155.6MB in the end (delta: 136.6kB). There was no memory consumed. Max. memory is 8.0GB. [2022-04-06 12:30:04,855 INFO L158 Benchmark]: CACSL2BoogieTranslator took 177.73ms. Allocated memory is still 190.8MB. Free memory was 139.2MB in the beginning and 166.0MB in the end (delta: -26.7MB). Peak memory consumption was 11.5MB. Max. memory is 8.0GB. [2022-04-06 12:30:04,855 INFO L158 Benchmark]: Boogie Preprocessor took 19.64ms. Allocated memory is still 190.8MB. Free memory was 166.0MB in the beginning and 164.6MB in the end (delta: 1.4MB). Peak memory consumption was 2.1MB. Max. memory is 8.0GB. [2022-04-06 12:30:04,855 INFO L158 Benchmark]: RCFGBuilder took 240.51ms. Allocated memory is still 190.8MB. Free memory was 164.6MB in the beginning and 154.1MB in the end (delta: 10.5MB). Peak memory consumption was 10.5MB. Max. memory is 8.0GB. [2022-04-06 12:30:04,855 INFO L158 Benchmark]: IcfgTransformer took 16.08ms. Allocated memory is still 190.8MB. Free memory was 154.1MB in the beginning and 152.7MB in the end (delta: 1.4MB). Peak memory consumption was 1.0MB. Max. memory is 8.0GB. [2022-04-06 12:30:04,855 INFO L158 Benchmark]: TraceAbstraction took 60275.42ms. Allocated memory was 190.8MB in the beginning and 234.9MB in the end (delta: 44.0MB). Free memory was 152.4MB in the beginning and 109.6MB in the end (delta: 42.8MB). Peak memory consumption was 88.4MB. Max. memory is 8.0GB. [2022-04-06 12:30:04,856 INFO L339 ainManager$Toolchain]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * CDTParser took 0.09ms. Allocated memory is still 190.8MB. Free memory was 155.7MB in the beginning and 155.6MB in the end (delta: 136.6kB). There was no memory consumed. Max. memory is 8.0GB. * CACSL2BoogieTranslator took 177.73ms. Allocated memory is still 190.8MB. Free memory was 139.2MB in the beginning and 166.0MB in the end (delta: -26.7MB). Peak memory consumption was 11.5MB. Max. memory is 8.0GB. * Boogie Preprocessor took 19.64ms. Allocated memory is still 190.8MB. Free memory was 166.0MB in the beginning and 164.6MB in the end (delta: 1.4MB). Peak memory consumption was 2.1MB. Max. memory is 8.0GB. * RCFGBuilder took 240.51ms. Allocated memory is still 190.8MB. Free memory was 164.6MB in the beginning and 154.1MB in the end (delta: 10.5MB). Peak memory consumption was 10.5MB. Max. memory is 8.0GB. * IcfgTransformer took 16.08ms. Allocated memory is still 190.8MB. Free memory was 154.1MB in the beginning and 152.7MB in the end (delta: 1.4MB). Peak memory consumption was 1.0MB. Max. memory is 8.0GB. * TraceAbstraction took 60275.42ms. Allocated memory was 190.8MB in the beginning and 234.9MB in the end (delta: 44.0MB). Free memory was 152.4MB in the beginning and 109.6MB in the end (delta: 42.8MB). Peak memory consumption was 88.4MB. Max. memory is 8.0GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - StatisticsResult: ErrorAutomatonStatistics NumberErrorTraces: 0, NumberStatementsAllTraces: 0, NumberRelevantStatements: 0, 0.0s ErrorAutomatonConstructionTimeTotal, 0.0s FaulLocalizationTime, NumberStatementsFirstTrace: -1, TraceLengthAvg: 0, 0.0s ErrorAutomatonConstructionTimeAvg, 0.0s ErrorAutomatonDifferenceTimeAvg, 0.0s ErrorAutomatonDifferenceTimeTotal, NumberOfNoEnhancement: 0, NumberOfFiniteEnhancement: 0, NumberOfInfiniteEnhancement: 0 - CounterExampleResult [Line: 17]: a call to reach_error is reachable a call to reach_error is reachable We found a FailurePath: [L22] int counter = 0; VAL [\old(counter)=11, counter=0] [L24] int A, B; [L25] int r, d, p, q; [L26] A = __VERIFIER_nondet_int() [L27] B = 1 [L29] r = A [L30] d = B [L31] p = 1 [L32] q = 0 VAL [\old(counter)=0, A=7, B=1, counter=0, d=1, p=1, q=0, r=7] [L34] EXPR counter++ VAL [\old(counter)=0, A=7, B=1, counter=1, counter++=0, d=1, p=1, q=0, r=7] [L34] COND TRUE counter++<5 [L35] CALL __VERIFIER_assert(q == 0) VAL [\old(cond)=1, \old(counter)=0, counter=1] [L15] COND FALSE !(!(cond)) VAL [\old(cond)=1, \old(counter)=0, cond=1, counter=1] [L35] RET __VERIFIER_assert(q == 0) VAL [\old(counter)=0, A=7, B=1, counter=1, d=1, p=1, q=0, r=7] [L36] CALL __VERIFIER_assert(r == A) VAL [\old(cond)=1, \old(counter)=0, counter=1] [L15] COND FALSE !(!(cond)) VAL [\old(cond)=1, \old(counter)=0, cond=1, counter=1] [L36] RET __VERIFIER_assert(r == A) VAL [\old(counter)=0, A=7, B=1, counter=1, d=1, p=1, q=0, r=7] [L37] CALL __VERIFIER_assert(d == B * p) VAL [\old(cond)=1, \old(counter)=0, counter=1] [L15] COND FALSE !(!(cond)) VAL [\old(cond)=1, \old(counter)=0, cond=1, counter=1] [L37] RET __VERIFIER_assert(d == B * p) VAL [\old(counter)=0, A=7, B=1, counter=1, d=1, p=1, q=0, r=7] [L38] COND FALSE !(!(r >= d)) [L40] d = 2 * d [L41] p = 2 * p VAL [\old(counter)=0, A=7, B=1, counter=1, d=2, p=2, q=0, r=7] [L34] EXPR counter++ VAL [\old(counter)=0, A=7, B=1, counter=2, counter++=1, d=2, p=2, q=0, r=7] [L34] COND TRUE counter++<5 [L35] CALL __VERIFIER_assert(q == 0) VAL [\old(cond)=1, \old(counter)=0, counter=2] [L15] COND FALSE !(!(cond)) VAL [\old(cond)=1, \old(counter)=0, cond=1, counter=2] [L35] RET __VERIFIER_assert(q == 0) VAL [\old(counter)=0, A=7, B=1, counter=2, d=2, p=2, q=0, r=7] [L36] CALL __VERIFIER_assert(r == A) VAL [\old(cond)=1, \old(counter)=0, counter=2] [L15] COND FALSE !(!(cond)) VAL [\old(cond)=1, \old(counter)=0, cond=1, counter=2] [L36] RET __VERIFIER_assert(r == A) VAL [\old(counter)=0, A=7, B=1, counter=2, d=2, p=2, q=0, r=7] [L37] CALL __VERIFIER_assert(d == B * p) VAL [\old(cond)=1, \old(counter)=0, counter=2] [L15] COND FALSE !(!(cond)) VAL [\old(cond)=1, \old(counter)=0, cond=1, counter=2] [L37] RET __VERIFIER_assert(d == B * p) VAL [\old(counter)=0, A=7, B=1, counter=2, d=2, p=2, q=0, r=7] [L38] COND FALSE !(!(r >= d)) [L40] d = 2 * d [L41] p = 2 * p VAL [\old(counter)=0, A=7, B=1, counter=2, d=4, p=4, q=0, r=7] [L34] EXPR counter++ VAL [\old(counter)=0, A=7, B=1, counter=3, counter++=2, d=4, p=4, q=0, r=7] [L34] COND TRUE counter++<5 [L35] CALL __VERIFIER_assert(q == 0) VAL [\old(cond)=1, \old(counter)=0, counter=3] [L15] COND FALSE !(!(cond)) VAL [\old(cond)=1, \old(counter)=0, cond=1, counter=3] [L35] RET __VERIFIER_assert(q == 0) VAL [\old(counter)=0, A=7, B=1, counter=3, d=4, p=4, q=0, r=7] [L36] CALL __VERIFIER_assert(r == A) VAL [\old(cond)=1, \old(counter)=0, counter=3] [L15] COND FALSE !(!(cond)) VAL [\old(cond)=1, \old(counter)=0, cond=1, counter=3] [L36] RET __VERIFIER_assert(r == A) VAL [\old(counter)=0, A=7, B=1, counter=3, d=4, p=4, q=0, r=7] [L37] CALL __VERIFIER_assert(d == B * p) VAL [\old(cond)=1, \old(counter)=0, counter=3] [L15] COND FALSE !(!(cond)) VAL [\old(cond)=1, \old(counter)=0, cond=1, counter=3] [L37] RET __VERIFIER_assert(d == B * p) VAL [\old(counter)=0, A=7, B=1, counter=3, d=4, p=4, q=0, r=7] [L38] COND FALSE !(!(r >= d)) [L40] d = 2 * d [L41] p = 2 * p VAL [\old(counter)=0, A=7, B=1, counter=3, d=8, p=8, q=0, r=7] [L34] EXPR counter++ VAL [\old(counter)=0, A=7, B=1, counter=4, counter++=3, d=8, p=8, q=0, r=7] [L34] COND TRUE counter++<5 [L35] CALL __VERIFIER_assert(q == 0) VAL [\old(cond)=1, \old(counter)=0, counter=4] [L15] COND FALSE !(!(cond)) VAL [\old(cond)=1, \old(counter)=0, cond=1, counter=4] [L35] RET __VERIFIER_assert(q == 0) VAL [\old(counter)=0, A=7, B=1, counter=4, d=8, p=8, q=0, r=7] [L36] CALL __VERIFIER_assert(r == A) VAL [\old(cond)=1, \old(counter)=0, counter=4] [L15] COND FALSE !(!(cond)) VAL [\old(cond)=1, \old(counter)=0, cond=1, counter=4] [L36] RET __VERIFIER_assert(r == A) VAL [\old(counter)=0, A=7, B=1, counter=4, d=8, p=8, q=0, r=7] [L37] CALL __VERIFIER_assert(d == B * p) VAL [\old(cond)=1, \old(counter)=0, counter=4] [L15] COND FALSE !(!(cond)) VAL [\old(cond)=1, \old(counter)=0, cond=1, counter=4] [L37] RET __VERIFIER_assert(d == B * p) VAL [\old(counter)=0, A=7, B=1, counter=4, d=8, p=8, q=0, r=7] [L38] COND TRUE !(r >= d) VAL [\old(counter)=0, A=7, B=1, counter=4, d=8, p=8, q=0, r=7] [L44] EXPR counter++ VAL [\old(counter)=0, A=7, B=1, counter=5, counter++=4, d=8, p=8, q=0, r=7] [L44] COND TRUE counter++<5 [L45] CALL __VERIFIER_assert(A == q*B + r) VAL [\old(cond)=1, \old(counter)=0, counter=5] [L15] COND FALSE !(!(cond)) VAL [\old(cond)=1, \old(counter)=0, cond=1, counter=5] [L45] RET __VERIFIER_assert(A == q*B + r) VAL [\old(counter)=0, A=7, B=1, counter=5, d=8, p=8, q=0, r=7] [L46] CALL __VERIFIER_assert(d == B*p) VAL [\old(cond)=1, \old(counter)=0, counter=5] [L15] COND FALSE !(!(cond)) VAL [\old(cond)=1, \old(counter)=0, cond=1, counter=5] [L46] RET __VERIFIER_assert(d == B*p) VAL [\old(counter)=0, A=7, B=1, counter=5, d=8, p=8, q=0, r=7] [L48] COND FALSE !(!(p != 1)) [L50] d = d / 2 [L51] p = p / 2 VAL [\old(counter)=0, A=7, B=1, counter=5, d=4, p=4, q=0, r=7] [L52] COND TRUE r >= d [L53] r = r - d [L54] q = q + p VAL [\old(counter)=0, A=7, B=1, counter=5, d=4, p=4, q=4, r=3] [L44] EXPR counter++ VAL [\old(counter)=0, A=7, B=1, counter=6, counter++=5, d=4, p=4, q=4, r=3] [L44] COND FALSE !(counter++<5) [L58] CALL __VERIFIER_assert(A == d*q + r) VAL [\old(cond)=0, \old(counter)=0, counter=6] [L15] COND TRUE !(cond) VAL [\old(cond)=0, \old(counter)=0, cond=0, counter=6] [L17] reach_error() VAL [\old(cond)=0, \old(counter)=0, cond=0, counter=6] - StatisticsResult: Ultimate Automizer benchmark data CFG has 4 procedures, 31 locations, 1 error locations. Started 1 CEGAR loops. OverallTime: 60.2s, OverallIterations: 17, TraceHistogramMax: 15, PathProgramHistogramMax: 2, EmptinessCheckTime: 0.0s, AutomataDifference: 26.8s, DeadEndRemovalTime: 0.0s, HoareAnnotationTime: 0.0s, InitialAbstractionConstructionTime: 0.0s, PartialOrderReductionTime: 0.0s, HoareTripleCheckerStatistics: 2 mSolverCounterUnknown, 526 SdHoareTripleChecker+Valid, 13.1s IncrementalHoareTripleChecker+Time, 0 mSdLazyCounter, 466 mSDsluCounter, 2468 SdHoareTripleChecker+Invalid, 12.8s Time, 0 mProtectedAction, 0 SdHoareTripleChecker+Unchecked, 0 IncrementalHoareTripleChecker+Unchecked, 1724 mSDsCounter, 399 IncrementalHoareTripleChecker+Valid, 0 mProtectedPredicate, 2150 IncrementalHoareTripleChecker+Invalid, 2551 SdHoareTripleChecker+Unknown, 0 mSolverCounterNotChecked, 399 mSolverCounterUnsat, 744 mSDtfsCounter, 2150 mSolverCounterSat, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Unknown, PredicateUnifierStatistics: 0 DeclaredPredicates, 1301 GetRequests, 1163 SyntacticMatches, 13 SemanticMatches, 125 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 123 ImplicationChecksByTransitivity, 17.0s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=212occurred in iteration=11, InterpolantAutomatonStates: 126, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 0.0s DumpTime, AutomataMinimizationStatistics: 0.2s AutomataMinimizationTime, 16 MinimizatonAttempts, 111 StatesRemovedByMinimization, 13 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TRACE_CHECK: 0.1s SsaConstructionTime, 0.3s SatisfiabilityAnalysisTime, 29.4s InterpolantComputationTime, 861 NumberOfCodeBlocks, 861 NumberOfCodeBlocksAsserted, 20 NumberOfCheckSat, 1283 ConstructedInterpolants, 0 QuantifiedInterpolants, 17951 SizeOfPredicates, 33 NumberOfNonLiveVariables, 2039 ConjunctsInSsa, 183 ConjunctsInUnsatCore, 24 InterpolantComputations, 9 PerfectInterpolantSequences, 3212/3666 InterpolantCoveringCapability, INVARIANT_SYNTHESIS: No data available, INTERPOLANT_CONSOLIDATION: No data available, ABSTRACT_INTERPRETATION: No data available, PDR: No data available, ACCELERATED_INTERPOLATION: No data available, SIFA: No data available, ReuseStatistics: No data available RESULT: Ultimate proved your program to be incorrect! [2022-04-06 12:30:04,895 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Forceful destruction successful, exit code 0 Received shutdown request...