/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/egcd2-ll_unwindbound5.c -------------------------------------------------------------------------------- This is Ultimate 0.2.2-dev-7968f31 [2022-03-17 21:20:53,029 INFO L177 SettingsManager]: Resetting all preferences to default values... [2022-03-17 21:20:53,031 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2022-03-17 21:20:53,066 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2022-03-17 21:20:53,066 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2022-03-17 21:20:53,067 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2022-03-17 21:20:53,070 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2022-03-17 21:20:53,072 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2022-03-17 21:20:53,073 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2022-03-17 21:20:53,078 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2022-03-17 21:20:53,078 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2022-03-17 21:20:53,079 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2022-03-17 21:20:53,079 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2022-03-17 21:20:53,081 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2022-03-17 21:20:53,082 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2022-03-17 21:20:53,084 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2022-03-17 21:20:53,084 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2022-03-17 21:20:53,085 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2022-03-17 21:20:53,087 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2022-03-17 21:20:53,091 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2022-03-17 21:20:53,092 INFO L181 SettingsManager]: Resetting HornVerifier preferences to default values [2022-03-17 21:20:53,093 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2022-03-17 21:20:53,093 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2022-03-17 21:20:53,094 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2022-03-17 21:20:53,095 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2022-03-17 21:20:53,100 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2022-03-17 21:20:53,100 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2022-03-17 21:20:53,100 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2022-03-17 21:20:53,101 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2022-03-17 21:20:53,101 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2022-03-17 21:20:53,102 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2022-03-17 21:20:53,102 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2022-03-17 21:20:53,103 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2022-03-17 21:20:53,103 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2022-03-17 21:20:53,104 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2022-03-17 21:20:53,104 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2022-03-17 21:20:53,105 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2022-03-17 21:20:53,105 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2022-03-17 21:20:53,105 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2022-03-17 21:20:53,105 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2022-03-17 21:20:53,106 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2022-03-17 21:20:53,106 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2022-03-17 21:20:53,107 INFO L101 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/loopacceleration/qvasr/qvasr_64.epf [2022-03-17 21:20:53,129 INFO L113 SettingsManager]: Loading preferences was successful [2022-03-17 21:20:53,129 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2022-03-17 21:20:53,130 INFO L136 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2022-03-17 21:20:53,131 INFO L138 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2022-03-17 21:20:53,131 INFO L136 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2022-03-17 21:20:53,131 INFO L138 SettingsManager]: * Create parallel compositions if possible=false [2022-03-17 21:20:53,131 INFO L138 SettingsManager]: * Use SBE=true [2022-03-17 21:20:53,132 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2022-03-17 21:20:53,132 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2022-03-17 21:20:53,132 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2022-03-17 21:20:53,132 INFO L138 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2022-03-17 21:20:53,132 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2022-03-17 21:20:53,133 INFO L138 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2022-03-17 21:20:53,133 INFO L138 SettingsManager]: * Check if freed pointer was valid=false [2022-03-17 21:20:53,133 INFO L138 SettingsManager]: * Use constant arrays=true [2022-03-17 21:20:53,133 INFO L138 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2022-03-17 21:20:53,133 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2022-03-17 21:20:53,133 INFO L138 SettingsManager]: * Size of a code block=SequenceOfStatements [2022-03-17 21:20:53,133 INFO L138 SettingsManager]: * SMT solver=External_DefaultMode [2022-03-17 21:20:53,133 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-03-17 21:20:53,133 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2022-03-17 21:20:53,133 INFO L138 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2022-03-17 21:20:53,134 INFO L138 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2022-03-17 21:20:53,134 INFO L138 SettingsManager]: * Trace refinement strategy=CAMEL [2022-03-17 21:20:53,134 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2022-03-17 21:20:53,134 INFO L138 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2022-03-17 21:20:53,134 INFO L138 SettingsManager]: * Trace refinement exception blacklist=NONE [2022-03-17 21:20:53,134 INFO L138 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2022-03-17 21:20:53,135 INFO L136 SettingsManager]: Preferences of IcfgTransformer differ from their defaults: [2022-03-17 21:20:53,135 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-03-17 21:20:53,339 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2022-03-17 21:20:53,359 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2022-03-17 21:20:53,361 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2022-03-17 21:20:53,361 INFO L271 PluginConnector]: Initializing CDTParser... [2022-03-17 21:20:53,362 INFO L275 PluginConnector]: CDTParser initialized [2022-03-17 21:20:53,363 INFO L432 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/svcomp/nla-digbench-scaling/egcd2-ll_unwindbound5.c [2022-03-17 21:20:53,407 INFO L220 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/281f98ff4/67319a0fa860440bb60cca1cbdfa2d55/FLAGc441b4f60 [2022-03-17 21:20:53,818 INFO L306 CDTParser]: Found 1 translation units. [2022-03-17 21:20:53,819 INFO L160 CDTParser]: Scanning /storage/repos/ultimate/trunk/examples/svcomp/nla-digbench-scaling/egcd2-ll_unwindbound5.c [2022-03-17 21:20:53,827 INFO L349 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/281f98ff4/67319a0fa860440bb60cca1cbdfa2d55/FLAGc441b4f60 [2022-03-17 21:20:54,240 INFO L357 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/281f98ff4/67319a0fa860440bb60cca1cbdfa2d55 [2022-03-17 21:20:54,242 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2022-03-17 21:20:54,243 INFO L131 ToolchainWalker]: Walking toolchain with 5 elements. [2022-03-17 21:20:54,245 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2022-03-17 21:20:54,245 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2022-03-17 21:20:54,248 INFO L275 PluginConnector]: CACSL2BoogieTranslator initialized [2022-03-17 21:20:54,248 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 17.03 09:20:54" (1/1) ... [2022-03-17 21:20:54,249 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@6183453e and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 09:20:54, skipping insertion in model container [2022-03-17 21:20:54,249 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 17.03 09:20:54" (1/1) ... [2022-03-17 21:20:54,254 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2022-03-17 21:20:54,266 INFO L178 MainTranslator]: Built tables and reachable declarations [2022-03-17 21:20:54,363 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/egcd2-ll_unwindbound5.c[490,503] [2022-03-17 21:20:54,394 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-03-17 21:20:54,402 INFO L203 MainTranslator]: Completed pre-run [2022-03-17 21:20:54,410 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/egcd2-ll_unwindbound5.c[490,503] [2022-03-17 21:20:54,420 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-03-17 21:20:54,433 INFO L208 MainTranslator]: Completed translation [2022-03-17 21:20:54,433 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 09:20:54 WrapperNode [2022-03-17 21:20:54,433 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2022-03-17 21:20:54,434 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2022-03-17 21:20:54,434 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2022-03-17 21:20:54,434 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2022-03-17 21:20:54,442 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 09:20:54" (1/1) ... [2022-03-17 21:20:54,442 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 09:20:54" (1/1) ... [2022-03-17 21:20:54,447 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 09:20:54" (1/1) ... [2022-03-17 21:20:54,447 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 09:20:54" (1/1) ... [2022-03-17 21:20:54,450 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 09:20:54" (1/1) ... [2022-03-17 21:20:54,453 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 09:20:54" (1/1) ... [2022-03-17 21:20:54,454 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 09:20:54" (1/1) ... [2022-03-17 21:20:54,455 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2022-03-17 21:20:54,456 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2022-03-17 21:20:54,456 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2022-03-17 21:20:54,456 INFO L275 PluginConnector]: RCFGBuilder initialized [2022-03-17 21:20:54,456 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 09:20:54" (1/1) ... [2022-03-17 21:20:54,461 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-03-17 21:20:54,468 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-17 21:20:54,483 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-03-17 21:20:54,491 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-03-17 21:20:54,516 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.init [2022-03-17 21:20:54,516 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2022-03-17 21:20:54,517 INFO L138 BoogieDeclarations]: Found implementation of procedure reach_error [2022-03-17 21:20:54,517 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2022-03-17 21:20:54,518 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2022-03-17 21:20:54,518 INFO L138 BoogieDeclarations]: Found implementation of procedure main [2022-03-17 21:20:54,518 INFO L130 BoogieDeclarations]: Found specification of procedure abort [2022-03-17 21:20:54,519 INFO L130 BoogieDeclarations]: Found specification of procedure __assert_fail [2022-03-17 21:20:54,519 INFO L130 BoogieDeclarations]: Found specification of procedure reach_error [2022-03-17 21:20:54,520 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2022-03-17 21:20:54,520 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_nondet_int [2022-03-17 21:20:54,520 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2022-03-17 21:20:54,520 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2022-03-17 21:20:54,520 INFO L130 BoogieDeclarations]: Found specification of procedure main [2022-03-17 21:20:54,520 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.init [2022-03-17 21:20:54,521 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2022-03-17 21:20:54,522 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2022-03-17 21:20:54,523 INFO L130 BoogieDeclarations]: Found specification of procedure write~int [2022-03-17 21:20:54,523 INFO L130 BoogieDeclarations]: Found specification of procedure read~int [2022-03-17 21:20:54,523 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2022-03-17 21:20:54,579 INFO L234 CfgBuilder]: Building ICFG [2022-03-17 21:20:54,580 INFO L260 CfgBuilder]: Building CFG for each procedure with an implementation [2022-03-17 21:20:54,731 INFO L275 CfgBuilder]: Performing block encoding [2022-03-17 21:20:54,736 INFO L294 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2022-03-17 21:20:54,736 INFO L299 CfgBuilder]: Removed 2 assume(true) statements. [2022-03-17 21:20:54,737 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 17.03 09:20:54 BoogieIcfgContainer [2022-03-17 21:20:54,737 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2022-03-17 21:20:54,738 INFO L113 PluginConnector]: ------------------------IcfgTransformer---------------------------- [2022-03-17 21:20:54,738 INFO L271 PluginConnector]: Initializing IcfgTransformer... [2022-03-17 21:20:54,741 INFO L275 PluginConnector]: IcfgTransformer initialized [2022-03-17 21:20:54,761 INFO L185 PluginConnector]: Executing the observer IcfgTransformationObserver from plugin IcfgTransformer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 17.03 09:20:54" (1/1) ... [2022-03-17 21:20:54,779 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.icfgtransformation CFG 17.03 09:20:54 BasicIcfg [2022-03-17 21:20:54,779 INFO L132 PluginConnector]: ------------------------ END IcfgTransformer---------------------------- [2022-03-17 21:20:54,780 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2022-03-17 21:20:54,780 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2022-03-17 21:20:54,796 INFO L275 PluginConnector]: TraceAbstraction initialized [2022-03-17 21:20:54,796 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 17.03 09:20:54" (1/4) ... [2022-03-17 21:20:54,797 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@f991894 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 17.03 09:20:54, skipping insertion in model container [2022-03-17 21:20:54,797 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 09:20:54" (2/4) ... [2022-03-17 21:20:54,797 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@f991894 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 17.03 09:20:54, skipping insertion in model container [2022-03-17 21:20:54,797 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 17.03 09:20:54" (3/4) ... [2022-03-17 21:20:54,797 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@f991894 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 17.03 09:20:54, skipping insertion in model container [2022-03-17 21:20:54,797 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.icfgtransformation CFG 17.03 09:20:54" (4/4) ... [2022-03-17 21:20:54,798 INFO L111 eAbstractionObserver]: Analyzing ICFG egcd2-ll_unwindbound5.cqvasr [2022-03-17 21:20:54,801 INFO L205 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2022-03-17 21:20:54,802 INFO L164 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2022-03-17 21:20:54,869 INFO L339 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2022-03-17 21:20:54,873 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-03-17 21:20:54,874 INFO L341 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2022-03-17 21:20:54,888 INFO L276 IsEmpty]: Start isEmpty. Operand has 39 states, 21 states have (on average 1.4285714285714286) internal successors, (30), 23 states have internal predecessors, (30), 12 states have call successors, (12), 4 states have call predecessors, (12), 4 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) [2022-03-17 21:20:54,893 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 33 [2022-03-17 21:20:54,893 INFO L492 BasicCegarLoop]: Found error trace [2022-03-17 21:20:54,893 INFO L500 BasicCegarLoop]: trace histogram [4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-17 21:20:54,894 INFO L403 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-17 21:20:54,898 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-17 21:20:54,899 INFO L85 PathProgramCache]: Analyzing trace with hash -282167495, now seen corresponding path program 1 times [2022-03-17 21:20:54,906 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-17 21:20:54,907 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1321563136] [2022-03-17 21:20:54,907 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 21:20:54,908 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-17 21:20:55,022 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-17 21:20:55,023 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [31807018] [2022-03-17 21:20:55,023 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 21:20:55,024 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-17 21:20:55,024 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-17 21:20:55,035 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-03-17 21:20:55,078 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-03-17 21:20:55,112 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-17 21:20:55,114 INFO L263 TraceCheckSpWp]: Trace formula consists of 121 conjuncts, 1 conjunts are in the unsatisfiable core [2022-03-17 21:20:55,119 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-17 21:20:55,184 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2022-03-17 21:20:55,184 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-03-17 21:20:55,184 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-17 21:20:55,185 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1321563136] [2022-03-17 21:20:55,185 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-17 21:20:55,185 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [31807018] [2022-03-17 21:20:55,185 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [31807018] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-17 21:20:55,185 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-17 21:20:55,186 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2022-03-17 21:20:55,187 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [691064270] [2022-03-17 21:20:55,188 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-17 21:20:55,191 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2022-03-17 21:20:55,191 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-17 21:20:55,209 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2022-03-17 21:20:55,209 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2022-03-17 21:20:55,211 INFO L87 Difference]: Start difference. First operand has 39 states, 21 states have (on average 1.4285714285714286) internal successors, (30), 23 states have internal predecessors, (30), 12 states have call successors, (12), 4 states have call predecessors, (12), 4 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) Second operand has 2 states, 2 states have (on average 5.5) internal successors, (11), 2 states have internal predecessors, (11), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (5), 1 states have call predecessors, (5), 1 states have call successors, (5) [2022-03-17 21:20:55,226 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-17 21:20:55,227 INFO L93 Difference]: Finished difference Result 71 states and 110 transitions. [2022-03-17 21:20:55,228 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2022-03-17 21:20:55,229 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 5.5) internal successors, (11), 2 states have internal predecessors, (11), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (5), 1 states have call predecessors, (5), 1 states have call successors, (5) Word has length 32 [2022-03-17 21:20:55,229 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-17 21:20:55,234 INFO L225 Difference]: With dead ends: 71 [2022-03-17 21:20:55,234 INFO L226 Difference]: Without dead ends: 34 [2022-03-17 21:20:55,236 INFO L911 BasicCegarLoop]: 0 DeclaredPredicates, 31 GetRequests, 31 SyntacticMatches, 0 SemanticMatches, 0 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2022-03-17 21:20:55,238 INFO L912 BasicCegarLoop]: 50 mSDtfsCounter, 0 mSDsluCounter, 0 mSDsCounter, 0 mSdLazyCounter, 0 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 50 SdHoareTripleChecker+Invalid, 0 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 0 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-03-17 21:20:55,239 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [0 Valid, 50 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 0 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-03-17 21:20:55,251 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 34 states. [2022-03-17 21:20:55,264 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 34 to 34. [2022-03-17 21:20:55,265 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 34 states, 18 states have (on average 1.2777777777777777) internal successors, (23), 20 states have internal predecessors, (23), 12 states have call successors, (12), 4 states have call predecessors, (12), 3 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2022-03-17 21:20:55,266 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 34 states to 34 states and 45 transitions. [2022-03-17 21:20:55,267 INFO L78 Accepts]: Start accepts. Automaton has 34 states and 45 transitions. Word has length 32 [2022-03-17 21:20:55,268 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-17 21:20:55,268 INFO L478 AbstractCegarLoop]: Abstraction has 34 states and 45 transitions. [2022-03-17 21:20:55,268 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 2 states have (on average 5.5) internal successors, (11), 2 states have internal predecessors, (11), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (5), 1 states have call predecessors, (5), 1 states have call successors, (5) [2022-03-17 21:20:55,269 INFO L276 IsEmpty]: Start isEmpty. Operand 34 states and 45 transitions. [2022-03-17 21:20:55,269 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 34 [2022-03-17 21:20:55,270 INFO L492 BasicCegarLoop]: Found error trace [2022-03-17 21:20:55,270 INFO L500 BasicCegarLoop]: trace histogram [4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-17 21:20:55,306 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-03-17 21:20:55,488 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable0 [2022-03-17 21:20:55,488 INFO L403 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-17 21:20:55,492 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-17 21:20:55,492 INFO L85 PathProgramCache]: Analyzing trace with hash -127828113, now seen corresponding path program 1 times [2022-03-17 21:20:55,493 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-17 21:20:55,493 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [281511201] [2022-03-17 21:20:55,493 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 21:20:55,493 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-17 21:20:55,511 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-17 21:20:55,512 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [427317287] [2022-03-17 21:20:55,512 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 21:20:55,512 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-17 21:20:55,512 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-17 21:20:55,514 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-03-17 21:20:55,546 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-03-17 21:20:55,591 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-17 21:20:55,592 INFO L263 TraceCheckSpWp]: Trace formula consists of 125 conjuncts, 5 conjunts are in the unsatisfiable core [2022-03-17 21:20:55,594 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-17 21:20:55,693 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2022-03-17 21:20:55,693 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-03-17 21:20:55,693 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-17 21:20:55,694 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [281511201] [2022-03-17 21:20:55,694 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-17 21:20:55,694 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [427317287] [2022-03-17 21:20:55,694 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [427317287] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-17 21:20:55,694 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-17 21:20:55,694 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2022-03-17 21:20:55,694 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1222144673] [2022-03-17 21:20:55,695 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-17 21:20:55,695 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2022-03-17 21:20:55,695 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-17 21:20:55,696 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2022-03-17 21:20:55,696 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2022-03-17 21:20:55,696 INFO L87 Difference]: Start difference. First operand 34 states and 45 transitions. Second operand has 4 states, 4 states have (on average 3.0) internal successors, (12), 3 states have internal predecessors, (12), 3 states have call successors, (7), 3 states have call predecessors, (7), 1 states have return successors, (5), 1 states have call predecessors, (5), 2 states have call successors, (5) [2022-03-17 21:20:55,709 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-17 21:20:55,709 INFO L93 Difference]: Finished difference Result 44 states and 56 transitions. [2022-03-17 21:20:55,709 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2022-03-17 21:20:55,710 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 3.0) internal successors, (12), 3 states have internal predecessors, (12), 3 states have call successors, (7), 3 states have call predecessors, (7), 1 states have return successors, (5), 1 states have call predecessors, (5), 2 states have call successors, (5) Word has length 33 [2022-03-17 21:20:55,710 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-17 21:20:55,710 INFO L225 Difference]: With dead ends: 44 [2022-03-17 21:20:55,710 INFO L226 Difference]: Without dead ends: 36 [2022-03-17 21:20:55,711 INFO L911 BasicCegarLoop]: 0 DeclaredPredicates, 32 GetRequests, 30 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2022-03-17 21:20:55,712 INFO L912 BasicCegarLoop]: 43 mSDtfsCounter, 0 mSDsluCounter, 67 mSDsCounter, 0 mSdLazyCounter, 8 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 110 SdHoareTripleChecker+Invalid, 8 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 8 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-03-17 21:20:55,712 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [0 Valid, 110 Invalid, 8 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 8 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-03-17 21:20:55,713 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 36 states. [2022-03-17 21:20:55,717 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 36 to 36. [2022-03-17 21:20:55,717 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 36 states, 20 states have (on average 1.25) internal successors, (25), 21 states have internal predecessors, (25), 12 states have call successors, (12), 4 states have call predecessors, (12), 3 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2022-03-17 21:20:55,718 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 36 states to 36 states and 47 transitions. [2022-03-17 21:20:55,718 INFO L78 Accepts]: Start accepts. Automaton has 36 states and 47 transitions. Word has length 33 [2022-03-17 21:20:55,718 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-17 21:20:55,718 INFO L478 AbstractCegarLoop]: Abstraction has 36 states and 47 transitions. [2022-03-17 21:20:55,718 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 3.0) internal successors, (12), 3 states have internal predecessors, (12), 3 states have call successors, (7), 3 states have call predecessors, (7), 1 states have return successors, (5), 1 states have call predecessors, (5), 2 states have call successors, (5) [2022-03-17 21:20:55,719 INFO L276 IsEmpty]: Start isEmpty. Operand 36 states and 47 transitions. [2022-03-17 21:20:55,719 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 35 [2022-03-17 21:20:55,719 INFO L492 BasicCegarLoop]: Found error trace [2022-03-17 21:20:55,719 INFO L500 BasicCegarLoop]: trace histogram [4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-17 21:20:55,737 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2022-03-17 21:20:55,937 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,SelfDestructingSolverStorable1 [2022-03-17 21:20:55,937 INFO L403 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-17 21:20:55,938 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-17 21:20:55,938 INFO L85 PathProgramCache]: Analyzing trace with hash 365419517, now seen corresponding path program 1 times [2022-03-17 21:20:55,938 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-17 21:20:55,938 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [742749387] [2022-03-17 21:20:55,938 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 21:20:55,939 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-17 21:20:55,957 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-17 21:20:55,962 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1978916198] [2022-03-17 21:20:55,963 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 21:20:55,963 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-17 21:20:55,963 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-17 21:20:55,964 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-03-17 21:20:55,965 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-03-17 21:20:56,007 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-17 21:20:56,008 INFO L263 TraceCheckSpWp]: Trace formula consists of 127 conjuncts, 7 conjunts are in the unsatisfiable core [2022-03-17 21:20:56,010 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-17 21:20:56,102 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 3 proven. 6 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2022-03-17 21:20:56,103 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-17 21:20:56,223 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 3 proven. 6 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2022-03-17 21:20:56,223 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-17 21:20:56,223 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [742749387] [2022-03-17 21:20:56,224 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-17 21:20:56,224 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1978916198] [2022-03-17 21:20:56,224 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1978916198] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-17 21:20:56,224 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-03-17 21:20:56,224 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 7 [2022-03-17 21:20:56,224 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [233627005] [2022-03-17 21:20:56,224 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-03-17 21:20:56,225 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2022-03-17 21:20:56,226 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-17 21:20:56,227 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2022-03-17 21:20:56,227 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=29, Unknown=0, NotChecked=0, Total=42 [2022-03-17 21:20:56,227 INFO L87 Difference]: Start difference. First operand 36 states and 47 transitions. Second operand has 7 states, 7 states have (on average 2.5714285714285716) internal successors, (18), 6 states have internal predecessors, (18), 3 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (5), 3 states have call predecessors, (5), 2 states have call successors, (5) [2022-03-17 21:20:56,307 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-17 21:20:56,307 INFO L93 Difference]: Finished difference Result 53 states and 71 transitions. [2022-03-17 21:20:56,307 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2022-03-17 21:20:56,307 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 7 states have (on average 2.5714285714285716) internal successors, (18), 6 states have internal predecessors, (18), 3 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (5), 3 states have call predecessors, (5), 2 states have call successors, (5) Word has length 34 [2022-03-17 21:20:56,308 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-17 21:20:56,308 INFO L225 Difference]: With dead ends: 53 [2022-03-17 21:20:56,308 INFO L226 Difference]: Without dead ends: 45 [2022-03-17 21:20:56,309 INFO L911 BasicCegarLoop]: 0 DeclaredPredicates, 69 GetRequests, 61 SyntacticMatches, 1 SemanticMatches, 7 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=22, Invalid=50, Unknown=0, NotChecked=0, Total=72 [2022-03-17 21:20:56,309 INFO L912 BasicCegarLoop]: 39 mSDtfsCounter, 28 mSDsluCounter, 154 mSDsCounter, 0 mSdLazyCounter, 62 mSolverCounterSat, 11 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 33 SdHoareTripleChecker+Valid, 193 SdHoareTripleChecker+Invalid, 73 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 11 IncrementalHoareTripleChecker+Valid, 62 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-03-17 21:20:56,310 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [33 Valid, 193 Invalid, 73 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [11 Valid, 62 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-03-17 21:20:56,310 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 45 states. [2022-03-17 21:20:56,314 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 45 to 37. [2022-03-17 21:20:56,314 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 37 states, 21 states have (on average 1.2380952380952381) internal successors, (26), 22 states have internal predecessors, (26), 12 states have call successors, (12), 4 states have call predecessors, (12), 3 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2022-03-17 21:20:56,315 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 37 states to 37 states and 48 transitions. [2022-03-17 21:20:56,315 INFO L78 Accepts]: Start accepts. Automaton has 37 states and 48 transitions. Word has length 34 [2022-03-17 21:20:56,315 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-17 21:20:56,315 INFO L478 AbstractCegarLoop]: Abstraction has 37 states and 48 transitions. [2022-03-17 21:20:56,316 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 7 states have (on average 2.5714285714285716) internal successors, (18), 6 states have internal predecessors, (18), 3 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (5), 3 states have call predecessors, (5), 2 states have call successors, (5) [2022-03-17 21:20:56,316 INFO L276 IsEmpty]: Start isEmpty. Operand 37 states and 48 transitions. [2022-03-17 21:20:56,316 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 37 [2022-03-17 21:20:56,316 INFO L492 BasicCegarLoop]: Found error trace [2022-03-17 21:20:56,316 INFO L500 BasicCegarLoop]: trace histogram [4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-17 21:20:56,335 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-03-17 21:20:56,533 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-17 21:20:56,533 INFO L403 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-17 21:20:56,534 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-17 21:20:56,534 INFO L85 PathProgramCache]: Analyzing trace with hash 196514290, now seen corresponding path program 1 times [2022-03-17 21:20:56,534 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-17 21:20:56,534 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [589484719] [2022-03-17 21:20:56,534 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 21:20:56,534 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-17 21:20:56,545 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-17 21:20:56,545 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [890764919] [2022-03-17 21:20:56,545 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 21:20:56,545 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-17 21:20:56,546 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-17 21:20:56,548 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-03-17 21:20:56,549 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-03-17 21:20:56,584 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-17 21:20:56,585 INFO L263 TraceCheckSpWp]: Trace formula consists of 135 conjuncts, 14 conjunts are in the unsatisfiable core [2022-03-17 21:20:56,586 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-17 21:20:56,681 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 3 proven. 6 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2022-03-17 21:20:56,682 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-17 21:20:56,774 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2022-03-17 21:20:56,775 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-17 21:20:56,775 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [589484719] [2022-03-17 21:20:56,775 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-17 21:20:56,775 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [890764919] [2022-03-17 21:20:56,775 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [890764919] provided 1 perfect and 1 imperfect interpolant sequences [2022-03-17 21:20:56,775 INFO L184 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2022-03-17 21:20:56,775 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [9] total 10 [2022-03-17 21:20:56,775 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [652663312] [2022-03-17 21:20:56,775 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-17 21:20:56,776 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-03-17 21:20:56,776 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-17 21:20:56,776 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-03-17 21:20:56,776 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=19, Invalid=71, Unknown=0, NotChecked=0, Total=90 [2022-03-17 21:20:56,776 INFO L87 Difference]: Start difference. First operand 37 states and 48 transitions. Second operand has 5 states, 5 states have (on average 3.0) internal successors, (15), 4 states have internal predecessors, (15), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (5), 1 states have call predecessors, (5), 1 states have call successors, (5) [2022-03-17 21:20:56,807 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-17 21:20:56,807 INFO L93 Difference]: Finished difference Result 43 states and 53 transitions. [2022-03-17 21:20:56,807 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-03-17 21:20:56,808 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.0) internal successors, (15), 4 states have internal predecessors, (15), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (5), 1 states have call predecessors, (5), 1 states have call successors, (5) Word has length 36 [2022-03-17 21:20:56,808 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-17 21:20:56,808 INFO L225 Difference]: With dead ends: 43 [2022-03-17 21:20:56,809 INFO L226 Difference]: Without dead ends: 41 [2022-03-17 21:20:56,811 INFO L911 BasicCegarLoop]: 0 DeclaredPredicates, 72 GetRequests, 62 SyntacticMatches, 1 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 5 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=23, Invalid=87, Unknown=0, NotChecked=0, Total=110 [2022-03-17 21:20:56,811 INFO L912 BasicCegarLoop]: 39 mSDtfsCounter, 7 mSDsluCounter, 101 mSDsCounter, 0 mSdLazyCounter, 29 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 11 SdHoareTripleChecker+Valid, 140 SdHoareTripleChecker+Invalid, 30 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 29 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-03-17 21:20:56,812 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [11 Valid, 140 Invalid, 30 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 29 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-03-17 21:20:56,812 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 41 states. [2022-03-17 21:20:56,815 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 41 to 41. [2022-03-17 21:20:56,816 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 41 states, 24 states have (on average 1.2083333333333333) internal successors, (29), 25 states have internal predecessors, (29), 12 states have call successors, (12), 5 states have call predecessors, (12), 4 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2022-03-17 21:20:56,816 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 41 states to 41 states and 51 transitions. [2022-03-17 21:20:56,816 INFO L78 Accepts]: Start accepts. Automaton has 41 states and 51 transitions. Word has length 36 [2022-03-17 21:20:56,816 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-17 21:20:56,816 INFO L478 AbstractCegarLoop]: Abstraction has 41 states and 51 transitions. [2022-03-17 21:20:56,817 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.0) internal successors, (15), 4 states have internal predecessors, (15), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (5), 1 states have call predecessors, (5), 1 states have call successors, (5) [2022-03-17 21:20:56,817 INFO L276 IsEmpty]: Start isEmpty. Operand 41 states and 51 transitions. [2022-03-17 21:20:56,817 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 40 [2022-03-17 21:20:56,817 INFO L492 BasicCegarLoop]: Found error trace [2022-03-17 21:20:56,817 INFO L500 BasicCegarLoop]: trace histogram [4, 4, 4, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-17 21:20:56,849 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-03-17 21:20:57,030 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-17 21:20:57,030 INFO L403 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-17 21:20:57,031 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-17 21:20:57,031 INFO L85 PathProgramCache]: Analyzing trace with hash 56558454, now seen corresponding path program 1 times [2022-03-17 21:20:57,031 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-17 21:20:57,031 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1945678924] [2022-03-17 21:20:57,031 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 21:20:57,031 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-17 21:20:57,042 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-17 21:20:57,043 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2113594381] [2022-03-17 21:20:57,043 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 21:20:57,043 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-17 21:20:57,043 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-17 21:20:57,044 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-03-17 21:20:57,054 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-03-17 21:20:57,086 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-17 21:20:57,087 INFO L263 TraceCheckSpWp]: Trace formula consists of 154 conjuncts, 7 conjunts are in the unsatisfiable core [2022-03-17 21:20:57,088 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-17 21:20:57,167 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2022-03-17 21:20:57,167 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-03-17 21:20:57,167 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-17 21:20:57,168 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1945678924] [2022-03-17 21:20:57,168 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-17 21:20:57,168 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2113594381] [2022-03-17 21:20:57,168 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2113594381] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-17 21:20:57,168 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-17 21:20:57,168 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-03-17 21:20:57,168 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [476590726] [2022-03-17 21:20:57,168 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-17 21:20:57,168 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-03-17 21:20:57,168 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-17 21:20:57,169 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-03-17 21:20:57,169 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2022-03-17 21:20:57,169 INFO L87 Difference]: Start difference. First operand 41 states and 51 transitions. Second operand has 5 states, 5 states have (on average 3.6) internal successors, (18), 4 states have internal predecessors, (18), 3 states have call successors, (7), 3 states have call predecessors, (7), 1 states have return successors, (5), 1 states have call predecessors, (5), 2 states have call successors, (5) [2022-03-17 21:20:57,193 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-17 21:20:57,194 INFO L93 Difference]: Finished difference Result 66 states and 84 transitions. [2022-03-17 21:20:57,196 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-03-17 21:20:57,196 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.6) internal successors, (18), 4 states have internal predecessors, (18), 3 states have call successors, (7), 3 states have call predecessors, (7), 1 states have return successors, (5), 1 states have call predecessors, (5), 2 states have call successors, (5) Word has length 39 [2022-03-17 21:20:57,196 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-17 21:20:57,197 INFO L225 Difference]: With dead ends: 66 [2022-03-17 21:20:57,197 INFO L226 Difference]: Without dead ends: 43 [2022-03-17 21:20:57,197 INFO L911 BasicCegarLoop]: 0 DeclaredPredicates, 38 GetRequests, 35 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-03-17 21:20:57,198 INFO L912 BasicCegarLoop]: 42 mSDtfsCounter, 6 mSDsluCounter, 91 mSDsCounter, 0 mSdLazyCounter, 13 mSolverCounterSat, 11 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 6 SdHoareTripleChecker+Valid, 133 SdHoareTripleChecker+Invalid, 24 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 11 IncrementalHoareTripleChecker+Valid, 13 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-03-17 21:20:57,198 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [6 Valid, 133 Invalid, 24 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [11 Valid, 13 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-03-17 21:20:57,198 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 43 states. [2022-03-17 21:20:57,215 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 43 to 43. [2022-03-17 21:20:57,216 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 43 states, 26 states have (on average 1.1923076923076923) internal successors, (31), 27 states have internal predecessors, (31), 12 states have call successors, (12), 5 states have call predecessors, (12), 4 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2022-03-17 21:20:57,216 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 43 states to 43 states and 53 transitions. [2022-03-17 21:20:57,216 INFO L78 Accepts]: Start accepts. Automaton has 43 states and 53 transitions. Word has length 39 [2022-03-17 21:20:57,217 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-17 21:20:57,217 INFO L478 AbstractCegarLoop]: Abstraction has 43 states and 53 transitions. [2022-03-17 21:20:57,217 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.6) internal successors, (18), 4 states have internal predecessors, (18), 3 states have call successors, (7), 3 states have call predecessors, (7), 1 states have return successors, (5), 1 states have call predecessors, (5), 2 states have call successors, (5) [2022-03-17 21:20:57,217 INFO L276 IsEmpty]: Start isEmpty. Operand 43 states and 53 transitions. [2022-03-17 21:20:57,217 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 42 [2022-03-17 21:20:57,217 INFO L492 BasicCegarLoop]: Found error trace [2022-03-17 21:20:57,217 INFO L500 BasicCegarLoop]: trace histogram [4, 4, 4, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-17 21:20:57,234 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-03-17 21:20:57,434 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-17 21:20:57,434 INFO L403 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-17 21:20:57,435 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-17 21:20:57,435 INFO L85 PathProgramCache]: Analyzing trace with hash 578094295, now seen corresponding path program 1 times [2022-03-17 21:20:57,435 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-17 21:20:57,435 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [50747386] [2022-03-17 21:20:57,435 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 21:20:57,435 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-17 21:20:57,443 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-17 21:20:57,443 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1805754582] [2022-03-17 21:20:57,443 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 21:20:57,443 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-17 21:20:57,443 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-17 21:20:57,453 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-03-17 21:20:57,455 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-03-17 21:20:57,489 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-17 21:20:57,490 INFO L263 TraceCheckSpWp]: Trace formula consists of 144 conjuncts, 14 conjunts are in the unsatisfiable core [2022-03-17 21:20:57,491 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-17 21:20:57,624 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 5 proven. 6 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2022-03-17 21:20:57,624 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-17 21:20:57,711 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2022-03-17 21:20:57,711 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-17 21:20:57,711 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [50747386] [2022-03-17 21:20:57,711 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-17 21:20:57,711 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1805754582] [2022-03-17 21:20:57,711 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1805754582] provided 1 perfect and 1 imperfect interpolant sequences [2022-03-17 21:20:57,711 INFO L184 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2022-03-17 21:20:57,711 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [8] total 9 [2022-03-17 21:20:57,712 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1994740819] [2022-03-17 21:20:57,712 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-17 21:20:57,712 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-03-17 21:20:57,712 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-17 21:20:57,712 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-03-17 21:20:57,712 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=17, Invalid=55, Unknown=0, NotChecked=0, Total=72 [2022-03-17 21:20:57,712 INFO L87 Difference]: Start difference. First operand 43 states and 53 transitions. Second operand has 5 states, 5 states have (on average 3.6) internal successors, (18), 4 states have internal predecessors, (18), 2 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) [2022-03-17 21:20:57,744 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-17 21:20:57,744 INFO L93 Difference]: Finished difference Result 57 states and 72 transitions. [2022-03-17 21:20:57,745 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-03-17 21:20:57,745 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.6) internal successors, (18), 4 states have internal predecessors, (18), 2 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) Word has length 41 [2022-03-17 21:20:57,745 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-17 21:20:57,746 INFO L225 Difference]: With dead ends: 57 [2022-03-17 21:20:57,746 INFO L226 Difference]: Without dead ends: 55 [2022-03-17 21:20:57,746 INFO L911 BasicCegarLoop]: 0 DeclaredPredicates, 82 GetRequests, 73 SyntacticMatches, 1 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 5 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=21, Invalid=69, Unknown=0, NotChecked=0, Total=90 [2022-03-17 21:20:57,746 INFO L912 BasicCegarLoop]: 47 mSDtfsCounter, 8 mSDsluCounter, 122 mSDsCounter, 0 mSdLazyCounter, 26 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 11 SdHoareTripleChecker+Valid, 169 SdHoareTripleChecker+Invalid, 26 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 26 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-03-17 21:20:57,747 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [11 Valid, 169 Invalid, 26 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 26 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-03-17 21:20:57,747 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 55 states. [2022-03-17 21:20:57,751 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 55 to 54. [2022-03-17 21:20:57,752 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 54 states, 32 states have (on average 1.21875) internal successors, (39), 33 states have internal predecessors, (39), 16 states have call successors, (16), 6 states have call predecessors, (16), 5 states have return successors, (14), 14 states have call predecessors, (14), 14 states have call successors, (14) [2022-03-17 21:20:57,752 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 54 states to 54 states and 69 transitions. [2022-03-17 21:20:57,752 INFO L78 Accepts]: Start accepts. Automaton has 54 states and 69 transitions. Word has length 41 [2022-03-17 21:20:57,752 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-17 21:20:57,752 INFO L478 AbstractCegarLoop]: Abstraction has 54 states and 69 transitions. [2022-03-17 21:20:57,753 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.6) internal successors, (18), 4 states have internal predecessors, (18), 2 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) [2022-03-17 21:20:57,753 INFO L276 IsEmpty]: Start isEmpty. Operand 54 states and 69 transitions. [2022-03-17 21:20:57,753 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 47 [2022-03-17 21:20:57,753 INFO L492 BasicCegarLoop]: Found error trace [2022-03-17 21:20:57,753 INFO L500 BasicCegarLoop]: trace histogram [4, 4, 4, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-17 21:20:57,772 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Ended with exit code 0 [2022-03-17 21:20:57,970 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-17 21:20:57,970 INFO L403 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-17 21:20:57,971 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-17 21:20:57,971 INFO L85 PathProgramCache]: Analyzing trace with hash -1581112078, now seen corresponding path program 1 times [2022-03-17 21:20:57,971 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-17 21:20:57,971 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1484236953] [2022-03-17 21:20:57,971 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 21:20:57,971 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-17 21:20:57,981 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-17 21:20:57,981 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1681642025] [2022-03-17 21:20:57,981 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 21:20:57,981 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-17 21:20:57,981 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-17 21:20:57,993 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-03-17 21:20:57,998 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-03-17 21:20:58,032 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-17 21:20:58,033 INFO L263 TraceCheckSpWp]: Trace formula consists of 153 conjuncts, 14 conjunts are in the unsatisfiable core [2022-03-17 21:20:58,035 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-17 21:20:58,192 INFO L134 CoverageAnalysis]: Checked inductivity of 32 backedges. 4 proven. 9 refuted. 0 times theorem prover too weak. 19 trivial. 0 not checked. [2022-03-17 21:20:58,193 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-17 21:20:58,303 INFO L134 CoverageAnalysis]: Checked inductivity of 32 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2022-03-17 21:20:58,303 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-17 21:20:58,304 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1484236953] [2022-03-17 21:20:58,304 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-17 21:20:58,304 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1681642025] [2022-03-17 21:20:58,304 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1681642025] provided 1 perfect and 1 imperfect interpolant sequences [2022-03-17 21:20:58,304 INFO L184 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2022-03-17 21:20:58,304 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [8] total 9 [2022-03-17 21:20:58,304 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [933475954] [2022-03-17 21:20:58,304 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-17 21:20:58,304 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-03-17 21:20:58,304 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-17 21:20:58,305 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-03-17 21:20:58,305 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=17, Invalid=55, Unknown=0, NotChecked=0, Total=72 [2022-03-17 21:20:58,305 INFO L87 Difference]: Start difference. First operand 54 states and 69 transitions. Second operand has 5 states, 5 states have (on average 3.6) internal successors, (18), 4 states have internal predecessors, (18), 2 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2022-03-17 21:20:58,341 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-17 21:20:58,342 INFO L93 Difference]: Finished difference Result 61 states and 75 transitions. [2022-03-17 21:20:58,342 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-03-17 21:20:58,342 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.6) internal successors, (18), 4 states have internal predecessors, (18), 2 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) Word has length 46 [2022-03-17 21:20:58,342 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-17 21:20:58,343 INFO L225 Difference]: With dead ends: 61 [2022-03-17 21:20:58,343 INFO L226 Difference]: Without dead ends: 59 [2022-03-17 21:20:58,343 INFO L911 BasicCegarLoop]: 0 DeclaredPredicates, 92 GetRequests, 83 SyntacticMatches, 1 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 5 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=21, Invalid=69, Unknown=0, NotChecked=0, Total=90 [2022-03-17 21:20:58,344 INFO L912 BasicCegarLoop]: 45 mSDtfsCounter, 8 mSDsluCounter, 115 mSDsCounter, 0 mSdLazyCounter, 35 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 10 SdHoareTripleChecker+Valid, 160 SdHoareTripleChecker+Invalid, 35 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 35 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-03-17 21:20:58,344 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [10 Valid, 160 Invalid, 35 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 35 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-03-17 21:20:58,344 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 59 states. [2022-03-17 21:20:58,349 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 59 to 58. [2022-03-17 21:20:58,349 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 58 states, 35 states have (on average 1.2) internal successors, (42), 36 states have internal predecessors, (42), 16 states have call successors, (16), 7 states have call predecessors, (16), 6 states have return successors, (14), 14 states have call predecessors, (14), 14 states have call successors, (14) [2022-03-17 21:20:58,349 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 58 states to 58 states and 72 transitions. [2022-03-17 21:20:58,350 INFO L78 Accepts]: Start accepts. Automaton has 58 states and 72 transitions. Word has length 46 [2022-03-17 21:20:58,350 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-17 21:20:58,350 INFO L478 AbstractCegarLoop]: Abstraction has 58 states and 72 transitions. [2022-03-17 21:20:58,350 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.6) internal successors, (18), 4 states have internal predecessors, (18), 2 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2022-03-17 21:20:58,350 INFO L276 IsEmpty]: Start isEmpty. Operand 58 states and 72 transitions. [2022-03-17 21:20:58,350 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 52 [2022-03-17 21:20:58,350 INFO L492 BasicCegarLoop]: Found error trace [2022-03-17 21:20:58,351 INFO L500 BasicCegarLoop]: trace histogram [4, 4, 4, 4, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-17 21:20:58,370 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Ended with exit code 0 [2022-03-17 21:20:58,570 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-17 21:20:58,570 INFO L403 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-17 21:20:58,570 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-17 21:20:58,570 INFO L85 PathProgramCache]: Analyzing trace with hash 1942645143, now seen corresponding path program 1 times [2022-03-17 21:20:58,571 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-17 21:20:58,571 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1295287396] [2022-03-17 21:20:58,571 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 21:20:58,571 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-17 21:20:58,579 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-17 21:20:58,579 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1319412745] [2022-03-17 21:20:58,579 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 21:20:58,579 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-17 21:20:58,579 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-17 21:20:58,580 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-03-17 21:20:58,581 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-03-17 21:20:58,632 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-17 21:20:58,634 INFO L263 TraceCheckSpWp]: Trace formula consists of 162 conjuncts, 28 conjunts are in the unsatisfiable core [2022-03-17 21:20:58,635 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-17 21:20:58,875 INFO L134 CoverageAnalysis]: Checked inductivity of 42 backedges. 13 proven. 8 refuted. 0 times theorem prover too weak. 21 trivial. 0 not checked. [2022-03-17 21:20:58,876 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-17 21:20:58,973 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-17 21:20:58,974 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1295287396] [2022-03-17 21:20:58,974 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-17 21:20:58,974 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1319412745] [2022-03-17 21:20:58,974 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1319412745] provided 0 perfect and 1 imperfect interpolant sequences [2022-03-17 21:20:58,974 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-03-17 21:20:58,974 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10] total 10 [2022-03-17 21:20:58,974 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1824431868] [2022-03-17 21:20:58,974 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2022-03-17 21:20:58,974 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2022-03-17 21:20:58,975 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-17 21:20:58,975 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2022-03-17 21:20:58,975 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=26, Invalid=106, Unknown=0, NotChecked=0, Total=132 [2022-03-17 21:20:58,975 INFO L87 Difference]: Start difference. First operand 58 states and 72 transitions. Second operand has 10 states, 10 states have (on average 2.4) internal successors, (24), 8 states have internal predecessors, (24), 2 states have call successors, (10), 2 states have call predecessors, (10), 3 states have return successors, (8), 3 states have call predecessors, (8), 2 states have call successors, (8) [2022-03-17 21:20:59,136 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-17 21:20:59,136 INFO L93 Difference]: Finished difference Result 65 states and 78 transitions. [2022-03-17 21:20:59,136 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2022-03-17 21:20:59,136 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 10 states have (on average 2.4) internal successors, (24), 8 states have internal predecessors, (24), 2 states have call successors, (10), 2 states have call predecessors, (10), 3 states have return successors, (8), 3 states have call predecessors, (8), 2 states have call successors, (8) Word has length 51 [2022-03-17 21:20:59,138 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-17 21:20:59,138 INFO L225 Difference]: With dead ends: 65 [2022-03-17 21:20:59,138 INFO L226 Difference]: Without dead ends: 63 [2022-03-17 21:20:59,139 INFO L911 BasicCegarLoop]: 0 DeclaredPredicates, 58 GetRequests, 44 SyntacticMatches, 1 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 17 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=41, Invalid=169, Unknown=0, NotChecked=0, Total=210 [2022-03-17 21:20:59,139 INFO L912 BasicCegarLoop]: 29 mSDtfsCounter, 35 mSDsluCounter, 140 mSDsCounter, 0 mSdLazyCounter, 169 mSolverCounterSat, 10 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 41 SdHoareTripleChecker+Valid, 169 SdHoareTripleChecker+Invalid, 179 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 10 IncrementalHoareTripleChecker+Valid, 169 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-03-17 21:20:59,139 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [41 Valid, 169 Invalid, 179 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [10 Valid, 169 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-03-17 21:20:59,140 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 63 states. [2022-03-17 21:20:59,146 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 63 to 62. [2022-03-17 21:20:59,146 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 62 states, 38 states have (on average 1.1842105263157894) internal successors, (45), 39 states have internal predecessors, (45), 16 states have call successors, (16), 8 states have call predecessors, (16), 7 states have return successors, (14), 14 states have call predecessors, (14), 14 states have call successors, (14) [2022-03-17 21:20:59,146 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 62 states to 62 states and 75 transitions. [2022-03-17 21:20:59,147 INFO L78 Accepts]: Start accepts. Automaton has 62 states and 75 transitions. Word has length 51 [2022-03-17 21:20:59,147 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-17 21:20:59,147 INFO L478 AbstractCegarLoop]: Abstraction has 62 states and 75 transitions. [2022-03-17 21:20:59,147 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 10 states have (on average 2.4) internal successors, (24), 8 states have internal predecessors, (24), 2 states have call successors, (10), 2 states have call predecessors, (10), 3 states have return successors, (8), 3 states have call predecessors, (8), 2 states have call successors, (8) [2022-03-17 21:20:59,147 INFO L276 IsEmpty]: Start isEmpty. Operand 62 states and 75 transitions. [2022-03-17 21:20:59,148 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 61 [2022-03-17 21:20:59,148 INFO L492 BasicCegarLoop]: Found error trace [2022-03-17 21:20:59,148 INFO L500 BasicCegarLoop]: trace histogram [5, 4, 4, 4, 4, 4, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-17 21:20:59,180 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-03-17 21:20:59,366 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,SelfDestructingSolverStorable7 [2022-03-17 21:20:59,366 INFO L403 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-17 21:20:59,366 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-17 21:20:59,366 INFO L85 PathProgramCache]: Analyzing trace with hash -1573186588, now seen corresponding path program 1 times [2022-03-17 21:20:59,367 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-17 21:20:59,367 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1759372765] [2022-03-17 21:20:59,367 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 21:20:59,367 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-17 21:20:59,374 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-17 21:20:59,374 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [68472417] [2022-03-17 21:20:59,374 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 21:20:59,374 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-17 21:20:59,375 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-17 21:20:59,376 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-03-17 21:20:59,377 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-03-17 21:20:59,416 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-17 21:20:59,417 INFO L263 TraceCheckSpWp]: Trace formula consists of 191 conjuncts, 9 conjunts are in the unsatisfiable core [2022-03-17 21:20:59,418 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-17 21:20:59,526 INFO L134 CoverageAnalysis]: Checked inductivity of 58 backedges. 8 proven. 2 refuted. 0 times theorem prover too weak. 48 trivial. 0 not checked. [2022-03-17 21:20:59,527 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-17 21:20:59,622 INFO L134 CoverageAnalysis]: Checked inductivity of 58 backedges. 8 proven. 2 refuted. 0 times theorem prover too weak. 48 trivial. 0 not checked. [2022-03-17 21:20:59,622 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-17 21:20:59,622 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1759372765] [2022-03-17 21:20:59,622 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-17 21:20:59,622 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [68472417] [2022-03-17 21:20:59,622 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [68472417] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-17 21:20:59,622 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-03-17 21:20:59,623 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 9 [2022-03-17 21:20:59,623 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1136167460] [2022-03-17 21:20:59,623 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-03-17 21:20:59,623 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2022-03-17 21:20:59,623 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-17 21:20:59,623 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2022-03-17 21:20:59,623 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=26, Invalid=46, Unknown=0, NotChecked=0, Total=72 [2022-03-17 21:20:59,624 INFO L87 Difference]: Start difference. First operand 62 states and 75 transitions. Second operand has 9 states, 9 states have (on average 4.555555555555555) internal successors, (41), 9 states have internal predecessors, (41), 5 states have call successors, (20), 4 states have call predecessors, (20), 3 states have return successors, (18), 3 states have call predecessors, (18), 4 states have call successors, (18) [2022-03-17 21:20:59,716 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-17 21:20:59,717 INFO L93 Difference]: Finished difference Result 173 states and 202 transitions. [2022-03-17 21:20:59,717 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2022-03-17 21:20:59,717 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 9 states have (on average 4.555555555555555) internal successors, (41), 9 states have internal predecessors, (41), 5 states have call successors, (20), 4 states have call predecessors, (20), 3 states have return successors, (18), 3 states have call predecessors, (18), 4 states have call successors, (18) Word has length 60 [2022-03-17 21:20:59,717 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-17 21:20:59,719 INFO L225 Difference]: With dead ends: 173 [2022-03-17 21:20:59,719 INFO L226 Difference]: Without dead ends: 165 [2022-03-17 21:20:59,719 INFO L911 BasicCegarLoop]: 0 DeclaredPredicates, 122 GetRequests, 111 SyntacticMatches, 1 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 11 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=47, Invalid=85, Unknown=0, NotChecked=0, Total=132 [2022-03-17 21:20:59,719 INFO L912 BasicCegarLoop]: 56 mSDtfsCounter, 82 mSDsluCounter, 123 mSDsCounter, 0 mSdLazyCounter, 66 mSolverCounterSat, 66 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 82 SdHoareTripleChecker+Valid, 179 SdHoareTripleChecker+Invalid, 132 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 66 IncrementalHoareTripleChecker+Valid, 66 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-03-17 21:20:59,720 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [82 Valid, 179 Invalid, 132 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [66 Valid, 66 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-03-17 21:20:59,720 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 165 states. [2022-03-17 21:20:59,731 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 165 to 159. [2022-03-17 21:20:59,732 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 159 states, 101 states have (on average 1.1782178217821782) internal successors, (119), 104 states have internal predecessors, (119), 36 states have call successors, (36), 22 states have call predecessors, (36), 21 states have return successors, (32), 32 states have call predecessors, (32), 32 states have call successors, (32) [2022-03-17 21:20:59,732 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 159 states to 159 states and 187 transitions. [2022-03-17 21:20:59,733 INFO L78 Accepts]: Start accepts. Automaton has 159 states and 187 transitions. Word has length 60 [2022-03-17 21:20:59,733 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-17 21:20:59,733 INFO L478 AbstractCegarLoop]: Abstraction has 159 states and 187 transitions. [2022-03-17 21:20:59,733 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 9 states have (on average 4.555555555555555) internal successors, (41), 9 states have internal predecessors, (41), 5 states have call successors, (20), 4 states have call predecessors, (20), 3 states have return successors, (18), 3 states have call predecessors, (18), 4 states have call successors, (18) [2022-03-17 21:20:59,733 INFO L276 IsEmpty]: Start isEmpty. Operand 159 states and 187 transitions. [2022-03-17 21:20:59,736 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 62 [2022-03-17 21:20:59,736 INFO L492 BasicCegarLoop]: Found error trace [2022-03-17 21:20:59,736 INFO L500 BasicCegarLoop]: trace histogram [5, 4, 4, 4, 4, 4, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-17 21:20:59,754 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Forceful destruction successful, exit code 0 [2022-03-17 21:20:59,939 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,10 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-17 21:20:59,939 INFO L403 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-17 21:20:59,940 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-17 21:20:59,940 INFO L85 PathProgramCache]: Analyzing trace with hash -1491020248, now seen corresponding path program 1 times [2022-03-17 21:20:59,940 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-17 21:20:59,940 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [305183156] [2022-03-17 21:20:59,940 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 21:20:59,940 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-17 21:20:59,947 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-17 21:20:59,947 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1356719807] [2022-03-17 21:20:59,947 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 21:20:59,947 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-17 21:20:59,948 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-17 21:20:59,964 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-03-17 21:20:59,993 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-03-17 21:21:00,005 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-17 21:21:00,006 INFO L263 TraceCheckSpWp]: Trace formula consists of 193 conjuncts, 9 conjunts are in the unsatisfiable core [2022-03-17 21:21:00,007 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-17 21:21:00,098 INFO L134 CoverageAnalysis]: Checked inductivity of 59 backedges. 8 proven. 12 refuted. 0 times theorem prover too weak. 39 trivial. 0 not checked. [2022-03-17 21:21:00,098 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-17 21:21:00,210 INFO L134 CoverageAnalysis]: Checked inductivity of 59 backedges. 8 proven. 12 refuted. 0 times theorem prover too weak. 39 trivial. 0 not checked. [2022-03-17 21:21:00,211 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-17 21:21:00,211 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [305183156] [2022-03-17 21:21:00,211 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-17 21:21:00,211 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1356719807] [2022-03-17 21:21:00,211 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1356719807] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-17 21:21:00,211 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-03-17 21:21:00,211 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 9 [2022-03-17 21:21:00,211 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1055806728] [2022-03-17 21:21:00,211 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-03-17 21:21:00,211 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2022-03-17 21:21:00,212 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-17 21:21:00,212 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2022-03-17 21:21:00,212 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=17, Invalid=55, Unknown=0, NotChecked=0, Total=72 [2022-03-17 21:21:00,212 INFO L87 Difference]: Start difference. First operand 159 states and 187 transitions. Second operand has 9 states, 9 states have (on average 3.111111111111111) internal successors, (28), 8 states have internal predecessors, (28), 5 states have call successors, (11), 2 states have call predecessors, (11), 2 states have return successors, (9), 4 states have call predecessors, (9), 4 states have call successors, (9) [2022-03-17 21:21:00,338 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-17 21:21:00,338 INFO L93 Difference]: Finished difference Result 225 states and 292 transitions. [2022-03-17 21:21:00,338 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2022-03-17 21:21:00,339 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 9 states have (on average 3.111111111111111) internal successors, (28), 8 states have internal predecessors, (28), 5 states have call successors, (11), 2 states have call predecessors, (11), 2 states have return successors, (9), 4 states have call predecessors, (9), 4 states have call successors, (9) Word has length 61 [2022-03-17 21:21:00,339 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-17 21:21:00,340 INFO L225 Difference]: With dead ends: 225 [2022-03-17 21:21:00,340 INFO L226 Difference]: Without dead ends: 211 [2022-03-17 21:21:00,340 INFO L911 BasicCegarLoop]: 0 DeclaredPredicates, 128 GetRequests, 113 SyntacticMatches, 1 SemanticMatches, 14 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 17 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=60, Invalid=180, Unknown=0, NotChecked=0, Total=240 [2022-03-17 21:21:00,341 INFO L912 BasicCegarLoop]: 71 mSDtfsCounter, 61 mSDsluCounter, 254 mSDsCounter, 0 mSdLazyCounter, 72 mSolverCounterSat, 71 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 66 SdHoareTripleChecker+Valid, 325 SdHoareTripleChecker+Invalid, 143 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 71 IncrementalHoareTripleChecker+Valid, 72 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-03-17 21:21:00,341 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [66 Valid, 325 Invalid, 143 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [71 Valid, 72 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-03-17 21:21:00,341 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 211 states. [2022-03-17 21:21:00,375 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 211 to 189. [2022-03-17 21:21:00,376 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 189 states, 122 states have (on average 1.2131147540983607) internal successors, (148), 124 states have internal predecessors, (148), 46 states have call successors, (46), 21 states have call predecessors, (46), 20 states have return successors, (43), 43 states have call predecessors, (43), 43 states have call successors, (43) [2022-03-17 21:21:00,376 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 189 states to 189 states and 237 transitions. [2022-03-17 21:21:00,377 INFO L78 Accepts]: Start accepts. Automaton has 189 states and 237 transitions. Word has length 61 [2022-03-17 21:21:00,377 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-17 21:21:00,377 INFO L478 AbstractCegarLoop]: Abstraction has 189 states and 237 transitions. [2022-03-17 21:21:00,377 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 9 states have (on average 3.111111111111111) internal successors, (28), 8 states have internal predecessors, (28), 5 states have call successors, (11), 2 states have call predecessors, (11), 2 states have return successors, (9), 4 states have call predecessors, (9), 4 states have call successors, (9) [2022-03-17 21:21:00,377 INFO L276 IsEmpty]: Start isEmpty. Operand 189 states and 237 transitions. [2022-03-17 21:21:00,378 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 64 [2022-03-17 21:21:00,378 INFO L492 BasicCegarLoop]: Found error trace [2022-03-17 21:21:00,378 INFO L500 BasicCegarLoop]: trace histogram [5, 4, 4, 4, 4, 4, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-17 21:21:00,397 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-03-17 21:21:00,594 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,SelfDestructingSolverStorable9 [2022-03-17 21:21:00,594 INFO L403 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-17 21:21:00,594 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-17 21:21:00,594 INFO L85 PathProgramCache]: Analyzing trace with hash 317217743, now seen corresponding path program 1 times [2022-03-17 21:21:00,595 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-17 21:21:00,595 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [784938211] [2022-03-17 21:21:00,595 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 21:21:00,595 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-17 21:21:00,601 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-17 21:21:00,601 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [988319672] [2022-03-17 21:21:00,601 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 21:21:00,601 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-17 21:21:00,601 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-17 21:21:00,603 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-03-17 21:21:00,604 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-03-17 21:21:00,650 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-17 21:21:00,651 INFO L263 TraceCheckSpWp]: Trace formula consists of 202 conjuncts, 9 conjunts are in the unsatisfiable core [2022-03-17 21:21:00,652 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-17 21:21:00,753 INFO L134 CoverageAnalysis]: Checked inductivity of 61 backedges. 11 proven. 2 refuted. 0 times theorem prover too weak. 48 trivial. 0 not checked. [2022-03-17 21:21:00,753 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-17 21:21:00,854 INFO L134 CoverageAnalysis]: Checked inductivity of 61 backedges. 11 proven. 2 refuted. 0 times theorem prover too weak. 48 trivial. 0 not checked. [2022-03-17 21:21:00,854 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-17 21:21:00,855 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [784938211] [2022-03-17 21:21:00,855 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-17 21:21:00,855 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [988319672] [2022-03-17 21:21:00,855 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [988319672] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-17 21:21:00,855 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-03-17 21:21:00,855 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 9 [2022-03-17 21:21:00,855 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [333170136] [2022-03-17 21:21:00,855 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-03-17 21:21:00,856 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2022-03-17 21:21:00,856 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-17 21:21:00,856 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2022-03-17 21:21:00,856 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=26, Invalid=46, Unknown=0, NotChecked=0, Total=72 [2022-03-17 21:21:00,857 INFO L87 Difference]: Start difference. First operand 189 states and 237 transitions. Second operand has 9 states, 9 states have (on average 4.777777777777778) internal successors, (43), 9 states have internal predecessors, (43), 5 states have call successors, (20), 4 states have call predecessors, (20), 3 states have return successors, (18), 3 states have call predecessors, (18), 4 states have call successors, (18) [2022-03-17 21:21:00,942 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-17 21:21:00,943 INFO L93 Difference]: Finished difference Result 269 states and 350 transitions. [2022-03-17 21:21:00,943 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2022-03-17 21:21:00,943 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), 5 states have call successors, (20), 4 states have call predecessors, (20), 3 states have return successors, (18), 3 states have call predecessors, (18), 4 states have call successors, (18) Word has length 63 [2022-03-17 21:21:00,944 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-17 21:21:00,946 INFO L225 Difference]: With dead ends: 269 [2022-03-17 21:21:00,946 INFO L226 Difference]: Without dead ends: 197 [2022-03-17 21:21:00,949 INFO L911 BasicCegarLoop]: 0 DeclaredPredicates, 128 GetRequests, 117 SyntacticMatches, 1 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 11 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=46, Invalid=86, Unknown=0, NotChecked=0, Total=132 [2022-03-17 21:21:00,950 INFO L912 BasicCegarLoop]: 55 mSDtfsCounter, 49 mSDsluCounter, 127 mSDsCounter, 0 mSdLazyCounter, 59 mSolverCounterSat, 26 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 49 SdHoareTripleChecker+Valid, 182 SdHoareTripleChecker+Invalid, 85 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 26 IncrementalHoareTripleChecker+Valid, 59 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-03-17 21:21:00,950 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [49 Valid, 182 Invalid, 85 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [26 Valid, 59 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-03-17 21:21:00,950 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 197 states. [2022-03-17 21:21:00,966 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 197 to 195. [2022-03-17 21:21:00,966 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 195 states, 128 states have (on average 1.1796875) internal successors, (151), 130 states have internal predecessors, (151), 46 states have call successors, (46), 21 states have call predecessors, (46), 20 states have return successors, (43), 43 states have call predecessors, (43), 43 states have call successors, (43) [2022-03-17 21:21:00,968 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 195 states to 195 states and 240 transitions. [2022-03-17 21:21:00,969 INFO L78 Accepts]: Start accepts. Automaton has 195 states and 240 transitions. Word has length 63 [2022-03-17 21:21:00,969 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-17 21:21:00,969 INFO L478 AbstractCegarLoop]: Abstraction has 195 states and 240 transitions. [2022-03-17 21:21:00,969 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), 5 states have call successors, (20), 4 states have call predecessors, (20), 3 states have return successors, (18), 3 states have call predecessors, (18), 4 states have call successors, (18) [2022-03-17 21:21:00,969 INFO L276 IsEmpty]: Start isEmpty. Operand 195 states and 240 transitions. [2022-03-17 21:21:00,973 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 69 [2022-03-17 21:21:00,973 INFO L492 BasicCegarLoop]: Found error trace [2022-03-17 21:21:00,973 INFO L500 BasicCegarLoop]: trace histogram [6, 5, 5, 4, 4, 4, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-17 21:21:00,999 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-03-17 21:21:01,200 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,SelfDestructingSolverStorable10 [2022-03-17 21:21:01,200 INFO L403 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-17 21:21:01,200 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-17 21:21:01,200 INFO L85 PathProgramCache]: Analyzing trace with hash 918639692, now seen corresponding path program 1 times [2022-03-17 21:21:01,200 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-17 21:21:01,200 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1381997972] [2022-03-17 21:21:01,201 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 21:21:01,201 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-17 21:21:01,208 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-17 21:21:01,208 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [765331173] [2022-03-17 21:21:01,208 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 21:21:01,208 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-17 21:21:01,208 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-17 21:21:01,209 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-03-17 21:21:01,227 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-03-17 21:21:01,269 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-17 21:21:01,270 INFO L263 TraceCheckSpWp]: Trace formula consists of 210 conjuncts, 32 conjunts are in the unsatisfiable core [2022-03-17 21:21:01,272 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-17 21:21:01,480 INFO L134 CoverageAnalysis]: Checked inductivity of 81 backedges. 15 proven. 14 refuted. 0 times theorem prover too weak. 52 trivial. 0 not checked. [2022-03-17 21:21:01,481 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-17 21:21:01,612 INFO L134 CoverageAnalysis]: Checked inductivity of 81 backedges. 22 proven. 7 refuted. 0 times theorem prover too weak. 52 trivial. 0 not checked. [2022-03-17 21:21:01,612 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-17 21:21:01,613 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1381997972] [2022-03-17 21:21:01,613 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-17 21:21:01,613 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [765331173] [2022-03-17 21:21:01,613 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [765331173] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-17 21:21:01,613 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-03-17 21:21:01,613 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 8] total 12 [2022-03-17 21:21:01,613 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [705687903] [2022-03-17 21:21:01,613 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-03-17 21:21:01,613 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2022-03-17 21:21:01,613 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-17 21:21:01,614 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2022-03-17 21:21:01,614 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=28, Invalid=104, Unknown=0, NotChecked=0, Total=132 [2022-03-17 21:21:01,614 INFO L87 Difference]: Start difference. First operand 195 states and 240 transitions. Second operand has 12 states, 12 states have (on average 3.5833333333333335) internal successors, (43), 11 states have internal predecessors, (43), 6 states have call successors, (20), 2 states have call predecessors, (20), 2 states have return successors, (17), 6 states have call predecessors, (17), 6 states have call successors, (17) [2022-03-17 21:21:01,836 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-17 21:21:01,836 INFO L93 Difference]: Finished difference Result 272 states and 358 transitions. [2022-03-17 21:21:01,836 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2022-03-17 21:21:01,837 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 12 states have (on average 3.5833333333333335) internal successors, (43), 11 states have internal predecessors, (43), 6 states have call successors, (20), 2 states have call predecessors, (20), 2 states have return successors, (17), 6 states have call predecessors, (17), 6 states have call successors, (17) Word has length 68 [2022-03-17 21:21:01,837 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-17 21:21:01,839 INFO L225 Difference]: With dead ends: 272 [2022-03-17 21:21:01,839 INFO L226 Difference]: Without dead ends: 267 [2022-03-17 21:21:01,839 INFO L911 BasicCegarLoop]: 0 DeclaredPredicates, 145 GetRequests, 128 SyntacticMatches, 1 SemanticMatches, 16 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 27 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=65, Invalid=241, Unknown=0, NotChecked=0, Total=306 [2022-03-17 21:21:01,840 INFO L912 BasicCegarLoop]: 53 mSDtfsCounter, 56 mSDsluCounter, 222 mSDsCounter, 0 mSdLazyCounter, 259 mSolverCounterSat, 61 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 62 SdHoareTripleChecker+Valid, 275 SdHoareTripleChecker+Invalid, 320 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 61 IncrementalHoareTripleChecker+Valid, 259 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2022-03-17 21:21:01,840 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [62 Valid, 275 Invalid, 320 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [61 Valid, 259 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2022-03-17 21:21:01,840 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 267 states. [2022-03-17 21:21:01,857 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 267 to 237. [2022-03-17 21:21:01,858 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 237 states, 156 states have (on average 1.2115384615384615) internal successors, (189), 164 states have internal predecessors, (189), 58 states have call successors, (58), 23 states have call predecessors, (58), 22 states have return successors, (54), 49 states have call predecessors, (54), 54 states have call successors, (54) [2022-03-17 21:21:01,859 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 237 states to 237 states and 301 transitions. [2022-03-17 21:21:01,859 INFO L78 Accepts]: Start accepts. Automaton has 237 states and 301 transitions. Word has length 68 [2022-03-17 21:21:01,859 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-17 21:21:01,859 INFO L478 AbstractCegarLoop]: Abstraction has 237 states and 301 transitions. [2022-03-17 21:21:01,860 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 12 states have (on average 3.5833333333333335) internal successors, (43), 11 states have internal predecessors, (43), 6 states have call successors, (20), 2 states have call predecessors, (20), 2 states have return successors, (17), 6 states have call predecessors, (17), 6 states have call successors, (17) [2022-03-17 21:21:01,860 INFO L276 IsEmpty]: Start isEmpty. Operand 237 states and 301 transitions. [2022-03-17 21:21:01,860 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 74 [2022-03-17 21:21:01,860 INFO L492 BasicCegarLoop]: Found error trace [2022-03-17 21:21:01,860 INFO L500 BasicCegarLoop]: trace histogram [7, 6, 6, 4, 4, 4, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-17 21:21:01,880 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Forceful destruction successful, exit code 0 [2022-03-17 21:21:02,078 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,SelfDestructingSolverStorable11 [2022-03-17 21:21:02,078 INFO L403 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-17 21:21:02,078 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-17 21:21:02,078 INFO L85 PathProgramCache]: Analyzing trace with hash -210356579, now seen corresponding path program 2 times [2022-03-17 21:21:02,078 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-17 21:21:02,079 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2007232217] [2022-03-17 21:21:02,079 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 21:21:02,079 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-17 21:21:02,086 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-17 21:21:02,086 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [537460731] [2022-03-17 21:21:02,086 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-03-17 21:21:02,086 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-17 21:21:02,086 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-17 21:21:02,092 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-03-17 21:21:02,093 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-03-17 21:21:02,139 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-03-17 21:21:02,140 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-17 21:21:02,141 INFO L263 TraceCheckSpWp]: Trace formula consists of 219 conjuncts, 36 conjunts are in the unsatisfiable core [2022-03-17 21:21:02,143 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-17 21:21:02,446 INFO L134 CoverageAnalysis]: Checked inductivity of 104 backedges. 17 proven. 18 refuted. 0 times theorem prover too weak. 69 trivial. 0 not checked. [2022-03-17 21:21:02,447 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-17 21:21:02,721 INFO L134 CoverageAnalysis]: Checked inductivity of 104 backedges. 17 proven. 18 refuted. 0 times theorem prover too weak. 69 trivial. 0 not checked. [2022-03-17 21:21:02,721 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-17 21:21:02,721 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2007232217] [2022-03-17 21:21:02,721 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-17 21:21:02,721 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [537460731] [2022-03-17 21:21:02,721 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [537460731] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-17 21:21:02,721 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-03-17 21:21:02,721 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10] total 15 [2022-03-17 21:21:02,721 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1137944558] [2022-03-17 21:21:02,722 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-03-17 21:21:02,722 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 15 states [2022-03-17 21:21:02,722 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-17 21:21:02,722 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2022-03-17 21:21:02,722 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=41, Invalid=169, Unknown=0, NotChecked=0, Total=210 [2022-03-17 21:21:02,722 INFO L87 Difference]: Start difference. First operand 237 states and 301 transitions. Second operand has 15 states, 15 states have (on average 2.8666666666666667) internal successors, (43), 14 states have internal predecessors, (43), 9 states have call successors, (22), 2 states have call predecessors, (22), 2 states have return successors, (19), 9 states have call predecessors, (19), 9 states have call successors, (19) [2022-03-17 21:21:05,279 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-03-17 21:21:05,531 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-17 21:21:05,531 INFO L93 Difference]: Finished difference Result 256 states and 325 transitions. [2022-03-17 21:21:05,531 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2022-03-17 21:21:05,532 INFO L78 Accepts]: Start accepts. Automaton has has 15 states, 15 states have (on average 2.8666666666666667) internal successors, (43), 14 states have internal predecessors, (43), 9 states have call successors, (22), 2 states have call predecessors, (22), 2 states have return successors, (19), 9 states have call predecessors, (19), 9 states have call successors, (19) Word has length 73 [2022-03-17 21:21:05,532 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-17 21:21:05,533 INFO L225 Difference]: With dead ends: 256 [2022-03-17 21:21:05,533 INFO L226 Difference]: Without dead ends: 253 [2022-03-17 21:21:05,533 INFO L911 BasicCegarLoop]: 0 DeclaredPredicates, 154 GetRequests, 131 SyntacticMatches, 2 SemanticMatches, 21 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 65 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=103, Invalid=403, Unknown=0, NotChecked=0, Total=506 [2022-03-17 21:21:05,534 INFO L912 BasicCegarLoop]: 42 mSDtfsCounter, 52 mSDsluCounter, 271 mSDsCounter, 0 mSdLazyCounter, 223 mSolverCounterSat, 93 mSolverCounterUnsat, 1 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 2.6s Time, 0 mProtectedPredicate, 0 mProtectedAction, 52 SdHoareTripleChecker+Valid, 313 SdHoareTripleChecker+Invalid, 317 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 93 IncrementalHoareTripleChecker+Valid, 223 IncrementalHoareTripleChecker+Invalid, 1 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 2.6s IncrementalHoareTripleChecker+Time [2022-03-17 21:21:05,534 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [52 Valid, 313 Invalid, 317 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [93 Valid, 223 Invalid, 1 Unknown, 0 Unchecked, 2.6s Time] [2022-03-17 21:21:05,534 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 253 states. [2022-03-17 21:21:05,566 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 253 to 243. [2022-03-17 21:21:05,566 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 243 states, 162 states have (on average 1.2037037037037037) internal successors, (195), 169 states have internal predecessors, (195), 56 states have call successors, (56), 25 states have call predecessors, (56), 24 states have return successors, (53), 48 states have call predecessors, (53), 53 states have call successors, (53) [2022-03-17 21:21:05,567 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 243 states to 243 states and 304 transitions. [2022-03-17 21:21:05,567 INFO L78 Accepts]: Start accepts. Automaton has 243 states and 304 transitions. Word has length 73 [2022-03-17 21:21:05,567 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-17 21:21:05,568 INFO L478 AbstractCegarLoop]: Abstraction has 243 states and 304 transitions. [2022-03-17 21:21:05,568 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 15 states, 15 states have (on average 2.8666666666666667) internal successors, (43), 14 states have internal predecessors, (43), 9 states have call successors, (22), 2 states have call predecessors, (22), 2 states have return successors, (19), 9 states have call predecessors, (19), 9 states have call successors, (19) [2022-03-17 21:21:05,568 INFO L276 IsEmpty]: Start isEmpty. Operand 243 states and 304 transitions. [2022-03-17 21:21:05,568 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 79 [2022-03-17 21:21:05,568 INFO L492 BasicCegarLoop]: Found error trace [2022-03-17 21:21:05,568 INFO L500 BasicCegarLoop]: trace histogram [8, 7, 7, 4, 4, 4, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-17 21:21:05,594 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-03-17 21:21:05,769 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,SelfDestructingSolverStorable12 [2022-03-17 21:21:05,769 INFO L403 AbstractCegarLoop]: === Iteration 14 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-17 21:21:05,769 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-17 21:21:05,770 INFO L85 PathProgramCache]: Analyzing trace with hash 952478412, now seen corresponding path program 3 times [2022-03-17 21:21:05,770 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-17 21:21:05,770 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [476116337] [2022-03-17 21:21:05,770 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 21:21:05,770 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-17 21:21:05,776 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-17 21:21:05,777 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1512554825] [2022-03-17 21:21:05,777 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2022-03-17 21:21:05,777 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-17 21:21:05,777 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-17 21:21:05,778 INFO L229 MonitoredProcess]: Starting monitored process 15 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-17 21:21:05,779 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Waiting until timeout for monitored process [2022-03-17 21:21:05,825 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2022-03-17 21:21:05,825 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-17 21:21:05,847 INFO L263 TraceCheckSpWp]: Trace formula consists of 192 conjuncts, 40 conjunts are in the unsatisfiable core [2022-03-17 21:21:05,848 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-17 21:21:06,284 INFO L134 CoverageAnalysis]: Checked inductivity of 131 backedges. 31 proven. 10 refuted. 0 times theorem prover too weak. 90 trivial. 0 not checked. [2022-03-17 21:21:06,284 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-17 21:21:06,369 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-17 21:21:06,369 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [476116337] [2022-03-17 21:21:06,369 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-17 21:21:06,369 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1512554825] [2022-03-17 21:21:06,369 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1512554825] provided 0 perfect and 1 imperfect interpolant sequences [2022-03-17 21:21:06,369 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-03-17 21:21:06,369 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9] total 9 [2022-03-17 21:21:06,369 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [981828490] [2022-03-17 21:21:06,369 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2022-03-17 21:21:06,370 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2022-03-17 21:21:06,370 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-17 21:21:06,370 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2022-03-17 21:21:06,370 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=23, Invalid=87, Unknown=0, NotChecked=0, Total=110 [2022-03-17 21:21:06,370 INFO L87 Difference]: Start difference. First operand 243 states and 304 transitions. Second operand has 9 states, 9 states have (on average 3.111111111111111) internal successors, (28), 8 states have internal predecessors, (28), 4 states have call successors, (14), 2 states have call predecessors, (14), 2 states have return successors, (12), 4 states have call predecessors, (12), 4 states have call successors, (12) [2022-03-17 21:21:06,579 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-17 21:21:06,579 INFO L93 Difference]: Finished difference Result 266 states and 331 transitions. [2022-03-17 21:21:06,581 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2022-03-17 21:21:06,582 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 9 states have (on average 3.111111111111111) internal successors, (28), 8 states have internal predecessors, (28), 4 states have call successors, (14), 2 states have call predecessors, (14), 2 states have return successors, (12), 4 states have call predecessors, (12), 4 states have call successors, (12) Word has length 78 [2022-03-17 21:21:06,582 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-17 21:21:06,583 INFO L225 Difference]: With dead ends: 266 [2022-03-17 21:21:06,583 INFO L226 Difference]: Without dead ends: 262 [2022-03-17 21:21:06,584 INFO L911 BasicCegarLoop]: 0 DeclaredPredicates, 85 GetRequests, 72 SyntacticMatches, 1 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 8 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=38, Invalid=144, Unknown=0, NotChecked=0, Total=182 [2022-03-17 21:21:06,584 INFO L912 BasicCegarLoop]: 42 mSDtfsCounter, 24 mSDsluCounter, 207 mSDsCounter, 0 mSdLazyCounter, 190 mSolverCounterSat, 18 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 29 SdHoareTripleChecker+Valid, 249 SdHoareTripleChecker+Invalid, 208 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 18 IncrementalHoareTripleChecker+Valid, 190 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2022-03-17 21:21:06,584 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [29 Valid, 249 Invalid, 208 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [18 Valid, 190 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2022-03-17 21:21:06,585 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 262 states. [2022-03-17 21:21:06,612 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 262 to 260. [2022-03-17 21:21:06,613 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 260 states, 173 states have (on average 1.1965317919075145) internal successors, (207), 179 states have internal predecessors, (207), 60 states have call successors, (60), 28 states have call predecessors, (60), 26 states have return successors, (57), 52 states have call predecessors, (57), 57 states have call successors, (57) [2022-03-17 21:21:06,615 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 260 states to 260 states and 324 transitions. [2022-03-17 21:21:06,616 INFO L78 Accepts]: Start accepts. Automaton has 260 states and 324 transitions. Word has length 78 [2022-03-17 21:21:06,616 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-17 21:21:06,616 INFO L478 AbstractCegarLoop]: Abstraction has 260 states and 324 transitions. [2022-03-17 21:21:06,616 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 9 states have (on average 3.111111111111111) internal successors, (28), 8 states have internal predecessors, (28), 4 states have call successors, (14), 2 states have call predecessors, (14), 2 states have return successors, (12), 4 states have call predecessors, (12), 4 states have call successors, (12) [2022-03-17 21:21:06,616 INFO L276 IsEmpty]: Start isEmpty. Operand 260 states and 324 transitions. [2022-03-17 21:21:06,618 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 85 [2022-03-17 21:21:06,618 INFO L492 BasicCegarLoop]: Found error trace [2022-03-17 21:21:06,618 INFO L500 BasicCegarLoop]: trace histogram [9, 8, 8, 4, 4, 4, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-17 21:21:06,647 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Forceful destruction successful, exit code 0 [2022-03-17 21:21:06,837 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable13,15 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-17 21:21:06,838 INFO L403 AbstractCegarLoop]: === Iteration 15 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-17 21:21:06,838 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-17 21:21:06,838 INFO L85 PathProgramCache]: Analyzing trace with hash 900405455, now seen corresponding path program 1 times [2022-03-17 21:21:06,838 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-17 21:21:06,838 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1137429869] [2022-03-17 21:21:06,839 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 21:21:06,839 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-17 21:21:06,845 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-17 21:21:06,845 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1767820960] [2022-03-17 21:21:06,845 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 21:21:06,845 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-17 21:21:06,845 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-17 21:21:06,846 INFO L229 MonitoredProcess]: Starting monitored process 16 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-17 21:21:06,847 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Waiting until timeout for monitored process [2022-03-17 21:21:06,892 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-17 21:21:06,894 INFO L263 TraceCheckSpWp]: Trace formula consists of 239 conjuncts, 42 conjunts are in the unsatisfiable core [2022-03-17 21:21:06,896 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-17 21:21:07,298 INFO L134 CoverageAnalysis]: Checked inductivity of 162 backedges. 30 proven. 17 refuted. 0 times theorem prover too weak. 115 trivial. 0 not checked. [2022-03-17 21:21:07,298 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-17 21:21:07,810 INFO L134 CoverageAnalysis]: Checked inductivity of 162 backedges. 30 proven. 17 refuted. 0 times theorem prover too weak. 115 trivial. 0 not checked. [2022-03-17 21:21:07,810 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-17 21:21:07,810 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1137429869] [2022-03-17 21:21:07,810 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-17 21:21:07,810 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1767820960] [2022-03-17 21:21:07,811 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1767820960] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-17 21:21:07,811 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-03-17 21:21:07,811 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 12] total 19 [2022-03-17 21:21:07,811 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [397653889] [2022-03-17 21:21:07,811 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-03-17 21:21:07,811 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 19 states [2022-03-17 21:21:07,811 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-17 21:21:07,811 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 19 interpolants. [2022-03-17 21:21:07,812 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=58, Invalid=284, Unknown=0, NotChecked=0, Total=342 [2022-03-17 21:21:07,812 INFO L87 Difference]: Start difference. First operand 260 states and 324 transitions. Second operand has 19 states, 17 states have (on average 2.6470588235294117) internal successors, (45), 18 states have internal predecessors, (45), 11 states have call successors, (26), 2 states have call predecessors, (26), 2 states have return successors, (23), 9 states have call predecessors, (23), 9 states have call successors, (23) [2022-03-17 21:21:10,656 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-03-17 21:21:12,178 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-17 21:21:12,178 INFO L93 Difference]: Finished difference Result 327 states and 422 transitions. [2022-03-17 21:21:12,178 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 26 states. [2022-03-17 21:21:12,179 INFO L78 Accepts]: Start accepts. Automaton has has 19 states, 17 states have (on average 2.6470588235294117) internal successors, (45), 18 states have internal predecessors, (45), 11 states have call successors, (26), 2 states have call predecessors, (26), 2 states have return successors, (23), 9 states have call predecessors, (23), 9 states have call successors, (23) Word has length 84 [2022-03-17 21:21:12,179 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-17 21:21:12,180 INFO L225 Difference]: With dead ends: 327 [2022-03-17 21:21:12,180 INFO L226 Difference]: Without dead ends: 317 [2022-03-17 21:21:12,181 INFO L911 BasicCegarLoop]: 0 DeclaredPredicates, 185 GetRequests, 149 SyntacticMatches, 1 SemanticMatches, 35 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 233 ImplicationChecksByTransitivity, 0.9s TimeCoverageRelationStatistics Valid=248, Invalid=1084, Unknown=0, NotChecked=0, Total=1332 [2022-03-17 21:21:12,181 INFO L912 BasicCegarLoop]: 51 mSDtfsCounter, 101 mSDsluCounter, 367 mSDsCounter, 0 mSdLazyCounter, 487 mSolverCounterSat, 169 mSolverCounterUnsat, 1 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 3.6s Time, 0 mProtectedPredicate, 0 mProtectedAction, 101 SdHoareTripleChecker+Valid, 418 SdHoareTripleChecker+Invalid, 657 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 169 IncrementalHoareTripleChecker+Valid, 487 IncrementalHoareTripleChecker+Invalid, 1 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 3.6s IncrementalHoareTripleChecker+Time [2022-03-17 21:21:12,181 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [101 Valid, 418 Invalid, 657 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [169 Valid, 487 Invalid, 1 Unknown, 0 Unchecked, 3.6s Time] [2022-03-17 21:21:12,181 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 317 states. [2022-03-17 21:21:12,217 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 317 to 301. [2022-03-17 21:21:12,218 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 301 states, 197 states have (on average 1.2233502538071066) internal successors, (241), 202 states have internal predecessors, (241), 76 states have call successors, (76), 28 states have call predecessors, (76), 27 states have return successors, (74), 70 states have call predecessors, (74), 74 states have call successors, (74) [2022-03-17 21:21:12,220 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 301 states to 301 states and 391 transitions. [2022-03-17 21:21:12,220 INFO L78 Accepts]: Start accepts. Automaton has 301 states and 391 transitions. Word has length 84 [2022-03-17 21:21:12,220 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-17 21:21:12,220 INFO L478 AbstractCegarLoop]: Abstraction has 301 states and 391 transitions. [2022-03-17 21:21:12,220 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 19 states, 17 states have (on average 2.6470588235294117) internal successors, (45), 18 states have internal predecessors, (45), 11 states have call successors, (26), 2 states have call predecessors, (26), 2 states have return successors, (23), 9 states have call predecessors, (23), 9 states have call successors, (23) [2022-03-17 21:21:12,220 INFO L276 IsEmpty]: Start isEmpty. Operand 301 states and 391 transitions. [2022-03-17 21:21:12,221 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 94 [2022-03-17 21:21:12,221 INFO L492 BasicCegarLoop]: Found error trace [2022-03-17 21:21:12,221 INFO L500 BasicCegarLoop]: trace histogram [9, 8, 8, 4, 4, 4, 4, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-17 21:21:12,261 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Forceful destruction successful, exit code 0 [2022-03-17 21:21:12,447 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 16 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable14 [2022-03-17 21:21:12,448 INFO L403 AbstractCegarLoop]: === Iteration 16 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-17 21:21:12,448 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-17 21:21:12,448 INFO L85 PathProgramCache]: Analyzing trace with hash 1881160278, now seen corresponding path program 1 times [2022-03-17 21:21:12,448 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-17 21:21:12,448 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1077460243] [2022-03-17 21:21:12,448 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 21:21:12,448 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-17 21:21:12,469 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-17 21:21:12,469 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [454594748] [2022-03-17 21:21:12,469 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 21:21:12,469 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-17 21:21:12,469 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-17 21:21:12,475 INFO L229 MonitoredProcess]: Starting monitored process 17 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-17 21:21:12,476 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Waiting until timeout for monitored process [2022-03-17 21:21:12,521 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-17 21:21:12,522 INFO L263 TraceCheckSpWp]: Trace formula consists of 286 conjuncts, 5 conjunts are in the unsatisfiable core [2022-03-17 21:21:12,523 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-17 21:21:12,613 INFO L134 CoverageAnalysis]: Checked inductivity of 181 backedges. 42 proven. 0 refuted. 0 times theorem prover too weak. 139 trivial. 0 not checked. [2022-03-17 21:21:12,614 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-03-17 21:21:12,614 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-17 21:21:12,614 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1077460243] [2022-03-17 21:21:12,614 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-17 21:21:12,614 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [454594748] [2022-03-17 21:21:12,614 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [454594748] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-17 21:21:12,614 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-17 21:21:12,614 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-03-17 21:21:12,614 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [924785726] [2022-03-17 21:21:12,614 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-17 21:21:12,614 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-03-17 21:21:12,614 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-17 21:21:12,615 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-03-17 21:21:12,615 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-03-17 21:21:12,615 INFO L87 Difference]: Start difference. First operand 301 states and 391 transitions. Second operand has 5 states, 5 states have (on average 6.6) internal successors, (33), 5 states have internal predecessors, (33), 3 states have call successors, (15), 2 states have call predecessors, (15), 1 states have return successors, (13), 2 states have call predecessors, (13), 2 states have call successors, (13) [2022-03-17 21:21:12,678 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-17 21:21:12,678 INFO L93 Difference]: Finished difference Result 470 states and 653 transitions. [2022-03-17 21:21:12,679 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2022-03-17 21:21:12,679 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 6.6) internal successors, (33), 5 states have internal predecessors, (33), 3 states have call successors, (15), 2 states have call predecessors, (15), 1 states have return successors, (13), 2 states have call predecessors, (13), 2 states have call successors, (13) Word has length 93 [2022-03-17 21:21:12,679 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-17 21:21:12,680 INFO L225 Difference]: With dead ends: 470 [2022-03-17 21:21:12,680 INFO L226 Difference]: Without dead ends: 358 [2022-03-17 21:21:12,681 INFO L911 BasicCegarLoop]: 0 DeclaredPredicates, 95 GetRequests, 90 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=15, Invalid=27, Unknown=0, NotChecked=0, Total=42 [2022-03-17 21:21:12,681 INFO L912 BasicCegarLoop]: 59 mSDtfsCounter, 11 mSDsluCounter, 129 mSDsCounter, 0 mSdLazyCounter, 50 mSolverCounterSat, 5 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 15 SdHoareTripleChecker+Valid, 188 SdHoareTripleChecker+Invalid, 55 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 5 IncrementalHoareTripleChecker+Valid, 50 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-03-17 21:21:12,681 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [15 Valid, 188 Invalid, 55 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [5 Valid, 50 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-03-17 21:21:12,682 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 358 states. [2022-03-17 21:21:12,712 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 358 to 327. [2022-03-17 21:21:12,712 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 327 states, 213 states have (on average 1.2300469483568075) internal successors, (262), 217 states have internal predecessors, (262), 86 states have call successors, (86), 28 states have call predecessors, (86), 27 states have return successors, (84), 81 states have call predecessors, (84), 84 states have call successors, (84) [2022-03-17 21:21:12,713 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 327 states to 327 states and 432 transitions. [2022-03-17 21:21:12,714 INFO L78 Accepts]: Start accepts. Automaton has 327 states and 432 transitions. Word has length 93 [2022-03-17 21:21:12,714 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-17 21:21:12,714 INFO L478 AbstractCegarLoop]: Abstraction has 327 states and 432 transitions. [2022-03-17 21:21:12,714 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 6.6) internal successors, (33), 5 states have internal predecessors, (33), 3 states have call successors, (15), 2 states have call predecessors, (15), 1 states have return successors, (13), 2 states have call predecessors, (13), 2 states have call successors, (13) [2022-03-17 21:21:12,714 INFO L276 IsEmpty]: Start isEmpty. Operand 327 states and 432 transitions. [2022-03-17 21:21:12,714 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 102 [2022-03-17 21:21:12,715 INFO L492 BasicCegarLoop]: Found error trace [2022-03-17 21:21:12,715 INFO L500 BasicCegarLoop]: trace histogram [12, 11, 11, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-17 21:21:12,737 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Forceful destruction successful, exit code 0 [2022-03-17 21:21:12,931 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 17 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable15 [2022-03-17 21:21:12,931 INFO L403 AbstractCegarLoop]: === Iteration 17 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-17 21:21:12,932 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-17 21:21:12,932 INFO L85 PathProgramCache]: Analyzing trace with hash 653404933, now seen corresponding path program 1 times [2022-03-17 21:21:12,932 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-17 21:21:12,932 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [841604624] [2022-03-17 21:21:12,932 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 21:21:12,932 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-17 21:21:12,938 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-17 21:21:12,938 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [835132622] [2022-03-17 21:21:12,938 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 21:21:12,938 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-17 21:21:12,938 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-17 21:21:12,939 INFO L229 MonitoredProcess]: Starting monitored process 18 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-17 21:21:12,940 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (18)] Waiting until timeout for monitored process [2022-03-17 21:21:13,003 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-17 21:21:13,005 INFO L263 TraceCheckSpWp]: Trace formula consists of 274 conjuncts, 41 conjunts are in the unsatisfiable core [2022-03-17 21:21:13,006 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-17 21:21:13,689 INFO L134 CoverageAnalysis]: Checked inductivity of 288 backedges. 51 proven. 23 refuted. 0 times theorem prover too weak. 214 trivial. 0 not checked. [2022-03-17 21:21:13,689 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-17 21:21:13,924 WARN L907 QuantifierPusher]: no eliminatee completely removed, nonetheless the elimination was considered successful [2022-03-17 21:21:18,542 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-17 21:21:18,542 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [841604624] [2022-03-17 21:21:18,542 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-17 21:21:18,542 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [835132622] [2022-03-17 21:21:18,542 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [835132622] provided 0 perfect and 1 imperfect interpolant sequences [2022-03-17 21:21:18,542 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-03-17 21:21:18,542 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11] total 11 [2022-03-17 21:21:18,543 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [721771037] [2022-03-17 21:21:18,543 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2022-03-17 21:21:18,543 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 11 states [2022-03-17 21:21:18,543 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-17 21:21:18,543 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2022-03-17 21:21:18,543 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=44, Invalid=164, Unknown=2, NotChecked=0, Total=210 [2022-03-17 21:21:18,543 INFO L87 Difference]: Start difference. First operand 327 states and 432 transitions. Second operand has 11 states, 10 states have (on average 3.1) internal successors, (31), 9 states have internal predecessors, (31), 6 states have call successors, (18), 2 states have call predecessors, (18), 2 states have return successors, (16), 6 states have call predecessors, (16), 5 states have call successors, (16) [2022-03-17 21:21:19,010 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-17 21:21:19,011 INFO L93 Difference]: Finished difference Result 339 states and 442 transitions. [2022-03-17 21:21:19,011 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2022-03-17 21:21:19,011 INFO L78 Accepts]: Start accepts. Automaton has has 11 states, 10 states have (on average 3.1) internal successors, (31), 9 states have internal predecessors, (31), 6 states have call successors, (18), 2 states have call predecessors, (18), 2 states have return successors, (16), 6 states have call predecessors, (16), 5 states have call successors, (16) Word has length 101 [2022-03-17 21:21:19,011 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-17 21:21:19,013 INFO L225 Difference]: With dead ends: 339 [2022-03-17 21:21:19,013 INFO L226 Difference]: Without dead ends: 337 [2022-03-17 21:21:19,013 INFO L911 BasicCegarLoop]: 0 DeclaredPredicates, 131 GetRequests, 113 SyntacticMatches, 1 SemanticMatches, 17 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 31 ImplicationChecksByTransitivity, 4.7s TimeCoverageRelationStatistics Valid=71, Invalid=269, Unknown=2, NotChecked=0, Total=342 [2022-03-17 21:21:19,013 INFO L912 BasicCegarLoop]: 53 mSDtfsCounter, 33 mSDsluCounter, 308 mSDsCounter, 0 mSdLazyCounter, 304 mSolverCounterSat, 29 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 41 SdHoareTripleChecker+Valid, 361 SdHoareTripleChecker+Invalid, 333 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 29 IncrementalHoareTripleChecker+Valid, 304 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2022-03-17 21:21:19,014 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [41 Valid, 361 Invalid, 333 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [29 Valid, 304 Invalid, 0 Unknown, 0 Unchecked, 0.4s Time] [2022-03-17 21:21:19,014 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 337 states. [2022-03-17 21:21:19,045 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 337 to 335. [2022-03-17 21:21:19,046 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 335 states, 219 states have (on average 1.2237442922374429) internal successors, (268), 223 states have internal predecessors, (268), 86 states have call successors, (86), 30 states have call predecessors, (86), 29 states have return successors, (84), 81 states have call predecessors, (84), 84 states have call successors, (84) [2022-03-17 21:21:19,047 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 335 states to 335 states and 438 transitions. [2022-03-17 21:21:19,047 INFO L78 Accepts]: Start accepts. Automaton has 335 states and 438 transitions. Word has length 101 [2022-03-17 21:21:19,048 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-17 21:21:19,048 INFO L478 AbstractCegarLoop]: Abstraction has 335 states and 438 transitions. [2022-03-17 21:21:19,048 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 11 states, 10 states have (on average 3.1) internal successors, (31), 9 states have internal predecessors, (31), 6 states have call successors, (18), 2 states have call predecessors, (18), 2 states have return successors, (16), 6 states have call predecessors, (16), 5 states have call successors, (16) [2022-03-17 21:21:19,048 INFO L276 IsEmpty]: Start isEmpty. Operand 335 states and 438 transitions. [2022-03-17 21:21:19,049 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 111 [2022-03-17 21:21:19,049 INFO L492 BasicCegarLoop]: Found error trace [2022-03-17 21:21:19,049 INFO L500 BasicCegarLoop]: trace histogram [13, 12, 12, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-17 21:21:19,067 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (18)] Ended with exit code 0 [2022-03-17 21:21:19,266 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 18 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable16 [2022-03-17 21:21:19,267 INFO L403 AbstractCegarLoop]: === Iteration 18 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-17 21:21:19,267 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-17 21:21:19,267 INFO L85 PathProgramCache]: Analyzing trace with hash -1392800366, now seen corresponding path program 1 times [2022-03-17 21:21:19,267 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-17 21:21:19,267 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [845404905] [2022-03-17 21:21:19,267 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 21:21:19,267 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-17 21:21:19,277 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-17 21:21:19,277 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2048529366] [2022-03-17 21:21:19,278 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 21:21:19,278 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-17 21:21:19,278 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-17 21:21:19,279 INFO L229 MonitoredProcess]: Starting monitored process 19 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-17 21:21:19,307 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (19)] Waiting until timeout for monitored process [2022-03-17 21:21:19,347 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2022-03-17 21:21:19,347 INFO L352 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2022-03-17 21:21:19,372 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2022-03-17 21:21:19,422 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2022-03-17 21:21:19,422 INFO L614 BasicCegarLoop]: Counterexample is feasible [2022-03-17 21:21:19,422 INFO L788 garLoopResultBuilder]: Registering result UNSAFE for location __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION (0 of 1 remaining) [2022-03-17 21:21:19,443 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (19)] Forceful destruction successful, exit code 0 [2022-03-17 21:21:19,641 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 19 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable17 [2022-03-17 21:21:19,644 INFO L718 BasicCegarLoop]: Path program histogram: [3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-17 21:21:19,646 INFO L180 ceAbstractionStarter]: Computing trace abstraction results [2022-03-17 21:21:19,704 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 17.03 09:21:19 BasicIcfg [2022-03-17 21:21:19,704 INFO L132 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2022-03-17 21:21:19,705 INFO L158 Benchmark]: Toolchain (without parser) took 25462.13ms. Allocated memory was 188.7MB in the beginning and 272.6MB in the end (delta: 83.9MB). Free memory was 138.5MB in the beginning and 157.2MB in the end (delta: -18.7MB). Peak memory consumption was 65.2MB. Max. memory is 8.0GB. [2022-03-17 21:21:19,705 INFO L158 Benchmark]: CDTParser took 0.09ms. Allocated memory is still 188.7MB. Free memory is still 154.4MB. There was no memory consumed. Max. memory is 8.0GB. [2022-03-17 21:21:19,706 INFO L158 Benchmark]: CACSL2BoogieTranslator took 188.14ms. Allocated memory is still 188.7MB. Free memory was 138.4MB in the beginning and 164.9MB in the end (delta: -26.5MB). Peak memory consumption was 9.8MB. Max. memory is 8.0GB. [2022-03-17 21:21:19,706 INFO L158 Benchmark]: Boogie Preprocessor took 20.95ms. Allocated memory is still 188.7MB. Free memory was 164.9MB in the beginning and 163.1MB in the end (delta: 1.8MB). Peak memory consumption was 2.1MB. Max. memory is 8.0GB. [2022-03-17 21:21:19,706 INFO L158 Benchmark]: RCFGBuilder took 281.51ms. Allocated memory is still 188.7MB. Free memory was 163.1MB in the beginning and 152.0MB in the end (delta: 11.2MB). Peak memory consumption was 11.5MB. Max. memory is 8.0GB. [2022-03-17 21:21:19,706 INFO L158 Benchmark]: IcfgTransformer took 41.48ms. Allocated memory is still 188.7MB. Free memory was 152.0MB in the beginning and 150.5MB in the end (delta: 1.4MB). Peak memory consumption was 1.0MB. Max. memory is 8.0GB. [2022-03-17 21:21:19,706 INFO L158 Benchmark]: TraceAbstraction took 24924.43ms. Allocated memory was 188.7MB in the beginning and 272.6MB in the end (delta: 83.9MB). Free memory was 150.2MB in the beginning and 157.2MB in the end (delta: -7.0MB). Peak memory consumption was 78.5MB. Max. memory is 8.0GB. [2022-03-17 21:21:19,712 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 188.7MB. Free memory is still 154.4MB. There was no memory consumed. Max. memory is 8.0GB. * CACSL2BoogieTranslator took 188.14ms. Allocated memory is still 188.7MB. Free memory was 138.4MB in the beginning and 164.9MB in the end (delta: -26.5MB). Peak memory consumption was 9.8MB. Max. memory is 8.0GB. * Boogie Preprocessor took 20.95ms. Allocated memory is still 188.7MB. Free memory was 164.9MB in the beginning and 163.1MB in the end (delta: 1.8MB). Peak memory consumption was 2.1MB. Max. memory is 8.0GB. * RCFGBuilder took 281.51ms. Allocated memory is still 188.7MB. Free memory was 163.1MB in the beginning and 152.0MB in the end (delta: 11.2MB). Peak memory consumption was 11.5MB. Max. memory is 8.0GB. * IcfgTransformer took 41.48ms. Allocated memory is still 188.7MB. Free memory was 152.0MB in the beginning and 150.5MB in the end (delta: 1.4MB). Peak memory consumption was 1.0MB. Max. memory is 8.0GB. * TraceAbstraction took 24924.43ms. Allocated memory was 188.7MB in the beginning and 272.6MB in the end (delta: 83.9MB). Free memory was 150.2MB in the beginning and 157.2MB in the end (delta: -7.0MB). Peak memory consumption was 78.5MB. 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: 13]: a call to reach_error is reachable a call to reach_error is reachable We found a FailurePath: [L18] int counter = 0; VAL [\old(counter)=9, counter=0] [L20] int x, y; [L21] long long a, b, p, q, r, s, c, k, xy, yy; [L22] x = __VERIFIER_nondet_int() [L23] y = __VERIFIER_nondet_int() [L24] CALL assume_abort_if_not(x >= 1) VAL [\old(cond)=1, \old(counter)=0, counter=0] [L8] COND FALSE !(!cond) VAL [\old(cond)=1, \old(counter)=0, cond=1, counter=0] [L24] RET assume_abort_if_not(x >= 1) VAL [\old(counter)=0, counter=0, x=3, y=4] [L25] CALL assume_abort_if_not(y >= 1) VAL [\old(cond)=1, \old(counter)=0, counter=0] [L8] COND FALSE !(!cond) VAL [\old(cond)=1, \old(counter)=0, cond=1, counter=0] [L25] RET assume_abort_if_not(y >= 1) VAL [\old(counter)=0, counter=0, x=3, y=4] [L27] a = x [L28] b = y [L29] p = 1 [L30] q = 0 [L31] r = 0 [L32] s = 1 [L33] c = 0 [L34] k = 0 [L35] xy = (long long) x * y [L36] yy = (long long) y * y VAL [\old(counter)=0, a=3, b=4, c=0, counter=0, k=0, p=1, q=0, r=0, s=1, x=3, xy=12, y=4, yy=16] [L37] CALL assume_abort_if_not(xy < 2147483647) VAL [\old(cond)=1, \old(counter)=0, counter=0] [L8] COND FALSE !(!cond) VAL [\old(cond)=1, \old(counter)=0, cond=1, counter=0] [L37] RET assume_abort_if_not(xy < 2147483647) VAL [\old(counter)=0, a=3, b=4, c=0, counter=0, k=0, p=1, q=0, r=0, s=1, x=3, xy=12, y=4, yy=16] [L38] CALL assume_abort_if_not(yy < 2147483647) VAL [\old(cond)=1, \old(counter)=0, counter=0] [L8] COND FALSE !(!cond) VAL [\old(cond)=1, \old(counter)=0, cond=1, counter=0] [L38] RET assume_abort_if_not(yy < 2147483647) VAL [\old(counter)=0, a=3, b=4, c=0, counter=0, k=0, p=1, q=0, r=0, s=1, x=3, xy=12, y=4, yy=16] [L40] EXPR counter++ VAL [\old(counter)=0, a=3, b=4, c=0, counter=1, counter++=0, k=0, p=1, q=0, r=0, s=1, x=3, xy=12, y=4, yy=16] [L40] COND TRUE counter++<5 [L41] COND FALSE !(!(b != 0)) [L43] c = a [L44] k = 0 VAL [\old(counter)=0, a=3, b=4, c=3, counter=1, k=0, p=1, q=0, r=0, s=1, x=3, xy=12, y=4, yy=16] [L46] EXPR counter++ VAL [\old(counter)=0, a=3, b=4, c=3, counter=2, counter++=1, k=0, p=1, q=0, r=0, s=1, x=3, xy=12, y=4, yy=16] [L46] COND TRUE counter++<5 [L47] CALL __VERIFIER_assert(a == k * b + c) VAL [\old(cond)=1, \old(counter)=0, counter=2] [L11] COND FALSE !(!(cond)) VAL [\old(cond)=1, \old(counter)=0, cond=1, counter=2] [L47] RET __VERIFIER_assert(a == k * b + c) VAL [\old(counter)=0, a=3, b=4, c=3, counter=2, k=0, p=1, q=0, r=0, s=1, x=3, xy=12, y=4, yy=16] [L48] CALL __VERIFIER_assert(a == y*r + x*p) VAL [\old(cond)=1, \old(counter)=0, counter=2] [L11] COND FALSE !(!(cond)) VAL [\old(cond)=1, \old(counter)=0, cond=1, counter=2] [L48] RET __VERIFIER_assert(a == y*r + x*p) VAL [\old(counter)=0, a=3, b=4, c=3, counter=2, k=0, p=1, q=0, r=0, s=1, x=3, xy=12, y=4, yy=16] [L49] CALL __VERIFIER_assert(b == x * q + y * s) VAL [\old(cond)=1, \old(counter)=0, counter=2] [L11] COND FALSE !(!(cond)) VAL [\old(cond)=1, \old(counter)=0, cond=1, counter=2] [L49] RET __VERIFIER_assert(b == x * q + y * s) VAL [\old(counter)=0, a=3, b=4, c=3, counter=2, k=0, p=1, q=0, r=0, s=1, x=3, xy=12, y=4, yy=16] [L50] CALL __VERIFIER_assert(q*xy + s*yy - q*x - b*y - s*y + b == 0) VAL [\old(cond)=1, \old(counter)=0, counter=2] [L11] COND FALSE !(!(cond)) VAL [\old(cond)=1, \old(counter)=0, cond=1, counter=2] [L50] RET __VERIFIER_assert(q*xy + s*yy - q*x - b*y - s*y + b == 0) VAL [\old(counter)=0, a=3, b=4, c=3, counter=2, k=0, p=1, q=0, r=0, s=1, x=3, xy=12, y=4, yy=16] [L51] COND TRUE !(c >= b) VAL [\old(counter)=0, a=3, b=4, c=3, counter=2, k=0, p=1, q=0, r=0, s=1, x=3, xy=12, y=4, yy=16] [L57] a = b [L58] b = c [L60] long long temp; [L61] temp = p [L62] p = q [L63] q = temp - q * k [L64] temp = r [L65] r = s [L66] s = temp - s * k VAL [\old(counter)=0, a=4, b=3, c=3, counter=2, k=0, p=0, q=1, r=1, s=0, temp=0, x=3, xy=12, y=4, yy=16] [L40] EXPR counter++ VAL [\old(counter)=0, a=4, b=3, c=3, counter=3, counter++=2, k=0, p=0, q=1, r=1, s=0, temp=0, x=3, xy=12, y=4, yy=16] [L40] COND TRUE counter++<5 [L41] COND FALSE !(!(b != 0)) [L43] c = a [L44] k = 0 VAL [\old(counter)=0, a=4, b=3, c=4, counter=3, k=0, p=0, q=1, r=1, s=0, temp=0, x=3, xy=12, y=4, yy=16] [L46] EXPR counter++ VAL [\old(counter)=0, a=4, b=3, c=4, counter=4, counter++=3, k=0, p=0, q=1, r=1, s=0, temp=0, x=3, xy=12, y=4, yy=16] [L46] COND TRUE counter++<5 [L47] CALL __VERIFIER_assert(a == k * b + c) VAL [\old(cond)=1, \old(counter)=0, counter=4] [L11] COND FALSE !(!(cond)) VAL [\old(cond)=1, \old(counter)=0, cond=1, counter=4] [L47] RET __VERIFIER_assert(a == k * b + c) VAL [\old(counter)=0, a=4, b=3, c=4, counter=4, k=0, p=0, q=1, r=1, s=0, temp=0, x=3, xy=12, y=4, yy=16] [L48] CALL __VERIFIER_assert(a == y*r + x*p) VAL [\old(cond)=1, \old(counter)=0, counter=4] [L11] COND FALSE !(!(cond)) VAL [\old(cond)=1, \old(counter)=0, cond=1, counter=4] [L48] RET __VERIFIER_assert(a == y*r + x*p) VAL [\old(counter)=0, a=4, b=3, c=4, counter=4, k=0, p=0, q=1, r=1, s=0, temp=0, x=3, xy=12, y=4, yy=16] [L49] CALL __VERIFIER_assert(b == x * q + y * s) VAL [\old(cond)=1, \old(counter)=0, counter=4] [L11] COND FALSE !(!(cond)) VAL [\old(cond)=1, \old(counter)=0, cond=1, counter=4] [L49] RET __VERIFIER_assert(b == x * q + y * s) VAL [\old(counter)=0, a=4, b=3, c=4, counter=4, k=0, p=0, q=1, r=1, s=0, temp=0, x=3, xy=12, y=4, yy=16] [L50] CALL __VERIFIER_assert(q*xy + s*yy - q*x - b*y - s*y + b == 0) VAL [\old(cond)=1, \old(counter)=0, counter=4] [L11] COND FALSE !(!(cond)) VAL [\old(cond)=1, \old(counter)=0, cond=1, counter=4] [L50] RET __VERIFIER_assert(q*xy + s*yy - q*x - b*y - s*y + b == 0) VAL [\old(counter)=0, a=4, b=3, c=4, counter=4, k=0, p=0, q=1, r=1, s=0, temp=0, x=3, xy=12, y=4, yy=16] [L51] COND FALSE !(!(c >= b)) [L53] c = c - b [L54] k = k + 1 VAL [\old(counter)=0, a=4, b=3, c=1, counter=4, k=1, p=0, q=1, r=1, s=0, temp=0, x=3, xy=12, y=4, yy=16] [L46] EXPR counter++ VAL [\old(counter)=0, a=4, b=3, c=1, counter=5, counter++=4, k=1, p=0, q=1, r=1, s=0, temp=0, x=3, xy=12, y=4, yy=16] [L46] COND TRUE counter++<5 [L47] CALL __VERIFIER_assert(a == k * b + c) VAL [\old(cond)=1, \old(counter)=0, counter=5] [L11] COND FALSE !(!(cond)) VAL [\old(cond)=1, \old(counter)=0, cond=1, counter=5] [L47] RET __VERIFIER_assert(a == k * b + c) VAL [\old(counter)=0, a=4, b=3, c=1, counter=5, k=1, p=0, q=1, r=1, s=0, temp=0, x=3, xy=12, y=4, yy=16] [L48] CALL __VERIFIER_assert(a == y*r + x*p) VAL [\old(cond)=1, \old(counter)=0, counter=5] [L11] COND FALSE !(!(cond)) VAL [\old(cond)=1, \old(counter)=0, cond=1, counter=5] [L48] RET __VERIFIER_assert(a == y*r + x*p) VAL [\old(counter)=0, a=4, b=3, c=1, counter=5, k=1, p=0, q=1, r=1, s=0, temp=0, x=3, xy=12, y=4, yy=16] [L49] CALL __VERIFIER_assert(b == x * q + y * s) VAL [\old(cond)=1, \old(counter)=0, counter=5] [L11] COND FALSE !(!(cond)) VAL [\old(cond)=1, \old(counter)=0, cond=1, counter=5] [L49] RET __VERIFIER_assert(b == x * q + y * s) VAL [\old(counter)=0, a=4, b=3, c=1, counter=5, k=1, p=0, q=1, r=1, s=0, temp=0, x=3, xy=12, y=4, yy=16] [L50] CALL __VERIFIER_assert(q*xy + s*yy - q*x - b*y - s*y + b == 0) VAL [\old(cond)=1, \old(counter)=0, counter=5] [L11] COND FALSE !(!(cond)) VAL [\old(cond)=1, \old(counter)=0, cond=1, counter=5] [L50] RET __VERIFIER_assert(q*xy + s*yy - q*x - b*y - s*y + b == 0) VAL [\old(counter)=0, a=4, b=3, c=1, counter=5, k=1, p=0, q=1, r=1, s=0, temp=0, x=3, xy=12, y=4, yy=16] [L51] COND TRUE !(c >= b) VAL [\old(counter)=0, a=4, b=3, c=1, counter=5, k=1, p=0, q=1, r=1, s=0, temp=0, x=3, xy=12, y=4, yy=16] [L57] a = b [L58] b = c [L60] long long temp; [L61] temp = p [L62] p = q [L63] q = temp - q * k [L64] temp = r [L65] r = s [L66] s = temp - s * k VAL [\old(counter)=0, a=3, b=1, c=1, counter=5, k=1, p=1, q=-1, r=0, s=1, temp=1, x=3, xy=12, y=4, yy=16] [L40] EXPR counter++ VAL [\old(counter)=0, a=3, b=1, c=1, counter=6, counter++=5, k=1, p=1, q=-1, r=0, s=1, temp=1, x=3, xy=12, y=4, yy=16] [L40] COND FALSE !(counter++<5) [L70] CALL __VERIFIER_assert(q*x + s*y == 0) VAL [\old(cond)=0, \old(counter)=0, counter=6] [L11] COND TRUE !(cond) VAL [\old(cond)=0, \old(counter)=0, cond=0, counter=6] [L13] reach_error() VAL [\old(cond)=0, \old(counter)=0, cond=0, counter=6] - StatisticsResult: Ultimate Automizer benchmark data CFG has 5 procedures, 39 locations, 1 error locations. Started 1 CEGAR loops. OverallTime: 24.8s, OverallIterations: 18, TraceHistogramMax: 13, PathProgramHistogramMax: 3, EmptinessCheckTime: 0.0s, AutomataDifference: 8.9s, DeadEndRemovalTime: 0.0s, HoareAnnotationTime: 0.0s, InitialAbstractionConstructionTime: 0.0s, PartialOrderReductionTime: 0.0s, HoareTripleCheckerStatistics: 2 mSolverCounterUnknown, 609 SdHoareTripleChecker+Valid, 7.5s IncrementalHoareTripleChecker+Time, 0 mSdLazyCounter, 561 mSDsluCounter, 3614 SdHoareTripleChecker+Invalid, 7.2s Time, 0 mProtectedAction, 0 SdHoareTripleChecker+Unchecked, 0 IncrementalHoareTripleChecker+Unchecked, 2798 mSDsCounter, 571 IncrementalHoareTripleChecker+Valid, 0 mProtectedPredicate, 2052 IncrementalHoareTripleChecker+Invalid, 2625 SdHoareTripleChecker+Unknown, 0 mSolverCounterNotChecked, 571 mSolverCounterUnsat, 816 mSDtfsCounter, 2052 mSolverCounterSat, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Unknown, PredicateUnifierStatistics: 0 DeclaredPredicates, 1647 GetRequests, 1443 SyntacticMatches, 14 SemanticMatches, 190 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 438 ImplicationChecksByTransitivity, 6.4s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=335occurred in iteration=17, InterpolantAutomatonStates: 152, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 0.0s DumpTime, AutomataMinimizationStatistics: 0.3s AutomataMinimizationTime, 17 MinimizatonAttempts, 132 StatesRemovedByMinimization, 13 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TRACE_CHECK: 0.1s SsaConstructionTime, 0.5s SatisfiabilityAnalysisTime, 10.1s InterpolantComputationTime, 1103 NumberOfCodeBlocks, 1083 NumberOfCodeBlocksAsserted, 21 NumberOfCheckSat, 1532 ConstructedInterpolants, 0 QuantifiedInterpolants, 6387 SizeOfPredicates, 66 NumberOfNonLiveVariables, 3127 ConjunctsInSsa, 313 ConjunctsInUnsatCore, 27 InterpolantComputations, 7 PerfectInterpolantSequences, 1781/1978 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-03-17 21:21:19,730 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...