/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-05ce600 [2022-02-23 22:35:40,897 INFO L177 SettingsManager]: Resetting all preferences to default values... [2022-02-23 22:35:40,926 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2022-02-23 22:35:40,945 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2022-02-23 22:35:40,945 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2022-02-23 22:35:40,946 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2022-02-23 22:35:40,946 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2022-02-23 22:35:40,948 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2022-02-23 22:35:40,949 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2022-02-23 22:35:40,949 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2022-02-23 22:35:40,950 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2022-02-23 22:35:40,951 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2022-02-23 22:35:40,951 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2022-02-23 22:35:40,952 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2022-02-23 22:35:40,952 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2022-02-23 22:35:40,953 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2022-02-23 22:35:40,954 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2022-02-23 22:35:40,954 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2022-02-23 22:35:40,956 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2022-02-23 22:35:40,957 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2022-02-23 22:35:40,958 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2022-02-23 22:35:40,958 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2022-02-23 22:35:40,959 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2022-02-23 22:35:40,960 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2022-02-23 22:35:40,961 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2022-02-23 22:35:40,962 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2022-02-23 22:35:40,962 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2022-02-23 22:35:40,962 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2022-02-23 22:35:40,963 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2022-02-23 22:35:40,963 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2022-02-23 22:35:40,963 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2022-02-23 22:35:40,964 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2022-02-23 22:35:40,964 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2022-02-23 22:35:40,965 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2022-02-23 22:35:40,965 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2022-02-23 22:35:40,966 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2022-02-23 22:35:40,966 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2022-02-23 22:35:40,966 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2022-02-23 22:35:40,966 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2022-02-23 22:35:40,967 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2022-02-23 22:35:40,967 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2022-02-23 22:35:40,968 INFO L101 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/loopacceleration/qvasr/qvasr_64.epf [2022-02-23 22:35:40,982 INFO L113 SettingsManager]: Loading preferences was successful [2022-02-23 22:35:40,982 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2022-02-23 22:35:40,982 INFO L136 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2022-02-23 22:35:40,982 INFO L138 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2022-02-23 22:35:40,983 INFO L136 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2022-02-23 22:35:40,983 INFO L138 SettingsManager]: * Create parallel compositions if possible=false [2022-02-23 22:35:40,983 INFO L138 SettingsManager]: * Use SBE=true [2022-02-23 22:35:40,983 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2022-02-23 22:35:40,983 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2022-02-23 22:35:40,983 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2022-02-23 22:35:40,983 INFO L138 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2022-02-23 22:35:40,984 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2022-02-23 22:35:40,984 INFO L138 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2022-02-23 22:35:40,984 INFO L138 SettingsManager]: * Check if freed pointer was valid=false [2022-02-23 22:35:40,984 INFO L138 SettingsManager]: * Use constant arrays=true [2022-02-23 22:35:40,984 INFO L138 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2022-02-23 22:35:40,984 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2022-02-23 22:35:40,984 INFO L138 SettingsManager]: * Size of a code block=SequenceOfStatements [2022-02-23 22:35:40,984 INFO L138 SettingsManager]: * SMT solver=External_DefaultMode [2022-02-23 22:35:40,985 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-02-23 22:35:40,985 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2022-02-23 22:35:40,985 INFO L138 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2022-02-23 22:35:40,985 INFO L138 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2022-02-23 22:35:40,985 INFO L138 SettingsManager]: * Trace refinement strategy=CAMEL [2022-02-23 22:35:40,985 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2022-02-23 22:35:40,985 INFO L138 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2022-02-23 22:35:40,985 INFO L138 SettingsManager]: * Trace refinement exception blacklist=NONE [2022-02-23 22:35:40,985 INFO L138 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2022-02-23 22:35:40,986 INFO L136 SettingsManager]: Preferences of IcfgTransformer differ from their defaults: [2022-02-23 22:35:40,986 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-02-23 22:35:41,175 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2022-02-23 22:35:41,192 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2022-02-23 22:35:41,193 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2022-02-23 22:35:41,194 INFO L271 PluginConnector]: Initializing CDTParser... [2022-02-23 22:35:41,194 INFO L275 PluginConnector]: CDTParser initialized [2022-02-23 22:35:41,195 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-02-23 22:35:41,240 INFO L220 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/78e352354/f05df0cd3d5241169331c9de92d40d06/FLAG75810bfa7 [2022-02-23 22:35:41,586 INFO L306 CDTParser]: Found 1 translation units. [2022-02-23 22:35:41,586 INFO L160 CDTParser]: Scanning /storage/repos/ultimate/trunk/examples/svcomp/nla-digbench-scaling/egcd2-ll_unwindbound5.c [2022-02-23 22:35:41,590 INFO L349 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/78e352354/f05df0cd3d5241169331c9de92d40d06/FLAG75810bfa7 [2022-02-23 22:35:42,011 INFO L357 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/78e352354/f05df0cd3d5241169331c9de92d40d06 [2022-02-23 22:35:42,013 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2022-02-23 22:35:42,014 INFO L131 ToolchainWalker]: Walking toolchain with 5 elements. [2022-02-23 22:35:42,018 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2022-02-23 22:35:42,018 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2022-02-23 22:35:42,021 INFO L275 PluginConnector]: CACSL2BoogieTranslator initialized [2022-02-23 22:35:42,022 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 23.02 10:35:42" (1/1) ... [2022-02-23 22:35:42,023 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@1ce091c1 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.02 10:35:42, skipping insertion in model container [2022-02-23 22:35:42,023 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 23.02 10:35:42" (1/1) ... [2022-02-23 22:35:42,032 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2022-02-23 22:35:42,053 INFO L178 MainTranslator]: Built tables and reachable declarations [2022-02-23 22:35:42,175 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-02-23 22:35:42,201 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-02-23 22:35:42,213 INFO L203 MainTranslator]: Completed pre-run [2022-02-23 22:35:42,222 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-02-23 22:35:42,229 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-02-23 22:35:42,237 INFO L208 MainTranslator]: Completed translation [2022-02-23 22:35:42,238 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.02 10:35:42 WrapperNode [2022-02-23 22:35:42,238 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2022-02-23 22:35:42,239 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2022-02-23 22:35:42,239 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2022-02-23 22:35:42,239 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2022-02-23 22:35:42,246 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.02 10:35:42" (1/1) ... [2022-02-23 22:35:42,247 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.02 10:35:42" (1/1) ... [2022-02-23 22:35:42,251 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.02 10:35:42" (1/1) ... [2022-02-23 22:35:42,251 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.02 10:35:42" (1/1) ... [2022-02-23 22:35:42,255 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.02 10:35:42" (1/1) ... [2022-02-23 22:35:42,258 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.02 10:35:42" (1/1) ... [2022-02-23 22:35:42,259 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.02 10:35:42" (1/1) ... [2022-02-23 22:35:42,266 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2022-02-23 22:35:42,267 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2022-02-23 22:35:42,267 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2022-02-23 22:35:42,267 INFO L275 PluginConnector]: RCFGBuilder initialized [2022-02-23 22:35:42,271 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.02 10:35:42" (1/1) ... [2022-02-23 22:35:42,286 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-02-23 22:35:42,293 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-02-23 22:35:42,304 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-02-23 22:35:42,312 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-02-23 22:35:42,334 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.init [2022-02-23 22:35:42,334 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2022-02-23 22:35:42,335 INFO L138 BoogieDeclarations]: Found implementation of procedure reach_error [2022-02-23 22:35:42,335 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2022-02-23 22:35:42,336 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2022-02-23 22:35:42,336 INFO L138 BoogieDeclarations]: Found implementation of procedure main [2022-02-23 22:35:42,336 INFO L130 BoogieDeclarations]: Found specification of procedure abort [2022-02-23 22:35:42,336 INFO L130 BoogieDeclarations]: Found specification of procedure __assert_fail [2022-02-23 22:35:42,337 INFO L130 BoogieDeclarations]: Found specification of procedure reach_error [2022-02-23 22:35:42,337 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2022-02-23 22:35:42,337 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_nondet_int [2022-02-23 22:35:42,337 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2022-02-23 22:35:42,337 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2022-02-23 22:35:42,337 INFO L130 BoogieDeclarations]: Found specification of procedure main [2022-02-23 22:35:42,337 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.init [2022-02-23 22:35:42,337 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2022-02-23 22:35:42,337 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2022-02-23 22:35:42,338 INFO L130 BoogieDeclarations]: Found specification of procedure write~int [2022-02-23 22:35:42,338 INFO L130 BoogieDeclarations]: Found specification of procedure read~int [2022-02-23 22:35:42,338 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2022-02-23 22:35:42,382 INFO L234 CfgBuilder]: Building ICFG [2022-02-23 22:35:42,383 INFO L260 CfgBuilder]: Building CFG for each procedure with an implementation [2022-02-23 22:35:42,520 INFO L275 CfgBuilder]: Performing block encoding [2022-02-23 22:35:42,525 INFO L294 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2022-02-23 22:35:42,525 INFO L299 CfgBuilder]: Removed 2 assume(true) statements. [2022-02-23 22:35:42,526 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 23.02 10:35:42 BoogieIcfgContainer [2022-02-23 22:35:42,526 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2022-02-23 22:35:42,527 INFO L113 PluginConnector]: ------------------------IcfgTransformer---------------------------- [2022-02-23 22:35:42,527 INFO L271 PluginConnector]: Initializing IcfgTransformer... [2022-02-23 22:35:42,528 INFO L275 PluginConnector]: IcfgTransformer initialized [2022-02-23 22:35:42,530 INFO L185 PluginConnector]: Executing the observer IcfgTransformationObserver from plugin IcfgTransformer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 23.02 10:35:42" (1/1) ... [2022-02-23 22:35:42,544 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.icfgtransformation CFG 23.02 10:35:42 BasicIcfg [2022-02-23 22:35:42,544 INFO L132 PluginConnector]: ------------------------ END IcfgTransformer---------------------------- [2022-02-23 22:35:42,545 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2022-02-23 22:35:42,545 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2022-02-23 22:35:42,561 INFO L275 PluginConnector]: TraceAbstraction initialized [2022-02-23 22:35:42,562 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 23.02 10:35:42" (1/4) ... [2022-02-23 22:35:42,562 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@7e4fd10a and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 23.02 10:35:42, skipping insertion in model container [2022-02-23 22:35:42,562 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.02 10:35:42" (2/4) ... [2022-02-23 22:35:42,563 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@7e4fd10a and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 23.02 10:35:42, skipping insertion in model container [2022-02-23 22:35:42,563 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 23.02 10:35:42" (3/4) ... [2022-02-23 22:35:42,563 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@7e4fd10a and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 23.02 10:35:42, skipping insertion in model container [2022-02-23 22:35:42,563 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.icfgtransformation CFG 23.02 10:35:42" (4/4) ... [2022-02-23 22:35:42,564 INFO L111 eAbstractionObserver]: Analyzing ICFG egcd2-ll_unwindbound5.cqvasr [2022-02-23 22:35:42,567 INFO L205 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2022-02-23 22:35:42,567 INFO L164 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2022-02-23 22:35:42,606 INFO L338 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2022-02-23 22:35:42,610 INFO L339 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, mLoopAccelerationTechnique=FAST_UPR [2022-02-23 22:35:42,611 INFO L340 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2022-02-23 22:35:42,627 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-02-23 22:35:42,631 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 33 [2022-02-23 22:35:42,631 INFO L506 BasicCegarLoop]: Found error trace [2022-02-23 22:35:42,632 INFO L514 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-02-23 22:35:42,632 INFO L402 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-02-23 22:35:42,637 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-02-23 22:35:42,637 INFO L85 PathProgramCache]: Analyzing trace with hash -282167495, now seen corresponding path program 1 times [2022-02-23 22:35:42,645 INFO L126 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-02-23 22:35:42,645 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [212060823] [2022-02-23 22:35:42,645 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-02-23 22:35:42,646 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-02-23 22:35:42,715 ERROR L252 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-02-23 22:35:42,715 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1639745588] [2022-02-23 22:35:42,716 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-02-23 22:35:42,716 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-02-23 22:35:42,716 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-02-23 22:35:42,736 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-02-23 22:35:42,738 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-02-23 22:35:42,821 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-02-23 22:35:42,823 INFO L263 TraceCheckSpWp]: Trace formula consists of 121 conjuncts, 1 conjunts are in the unsatisfiable core [2022-02-23 22:35:42,830 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-02-23 22:35:42,922 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2022-02-23 22:35:42,923 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-02-23 22:35:42,923 INFO L144 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-02-23 22:35:42,924 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [212060823] [2022-02-23 22:35:42,924 WARN L317 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-02-23 22:35:42,924 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1639745588] [2022-02-23 22:35:42,925 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1639745588] provided 1 perfect and 0 imperfect interpolant sequences [2022-02-23 22:35:42,925 INFO L191 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-02-23 22:35:42,925 INFO L204 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2022-02-23 22:35:42,927 INFO L118 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [495277583] [2022-02-23 22:35:42,928 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-02-23 22:35:42,931 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2022-02-23 22:35:42,932 INFO L108 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-02-23 22:35:42,957 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2022-02-23 22:35:42,958 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2022-02-23 22:35:42,960 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-02-23 22:35:42,987 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-02-23 22:35:42,987 INFO L93 Difference]: Finished difference Result 71 states and 110 transitions. [2022-02-23 22:35:42,988 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2022-02-23 22:35:42,989 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-02-23 22:35:42,990 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-02-23 22:35:42,996 INFO L225 Difference]: With dead ends: 71 [2022-02-23 22:35:42,997 INFO L226 Difference]: Without dead ends: 34 [2022-02-23 22:35:43,000 INFO L932 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-02-23 22:35:43,011 INFO L933 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-02-23 22:35:43,015 INFO L934 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-02-23 22:35:43,028 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 34 states. [2022-02-23 22:35:43,041 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 34 to 34. [2022-02-23 22:35:43,042 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-02-23 22:35:43,043 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 34 states to 34 states and 45 transitions. [2022-02-23 22:35:43,044 INFO L78 Accepts]: Start accepts. Automaton has 34 states and 45 transitions. Word has length 32 [2022-02-23 22:35:43,045 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-02-23 22:35:43,045 INFO L470 AbstractCegarLoop]: Abstraction has 34 states and 45 transitions. [2022-02-23 22:35:43,045 INFO L471 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-02-23 22:35:43,045 INFO L276 IsEmpty]: Start isEmpty. Operand 34 states and 45 transitions. [2022-02-23 22:35:43,046 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 34 [2022-02-23 22:35:43,046 INFO L506 BasicCegarLoop]: Found error trace [2022-02-23 22:35:43,046 INFO L514 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-02-23 22:35:43,064 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-02-23 22:35:43,264 WARN L452 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-02-23 22:35:43,264 INFO L402 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-02-23 22:35:43,265 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-02-23 22:35:43,265 INFO L85 PathProgramCache]: Analyzing trace with hash -127828113, now seen corresponding path program 1 times [2022-02-23 22:35:43,265 INFO L126 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-02-23 22:35:43,265 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [518326477] [2022-02-23 22:35:43,266 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-02-23 22:35:43,266 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-02-23 22:35:43,279 ERROR L252 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-02-23 22:35:43,279 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [585175001] [2022-02-23 22:35:43,279 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-02-23 22:35:43,280 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-02-23 22:35:43,280 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-02-23 22:35:43,298 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-02-23 22:35:43,300 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-02-23 22:35:43,343 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-02-23 22:35:43,344 INFO L263 TraceCheckSpWp]: Trace formula consists of 125 conjuncts, 5 conjunts are in the unsatisfiable core [2022-02-23 22:35:43,346 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-02-23 22:35:43,424 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2022-02-23 22:35:43,425 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-02-23 22:35:43,425 INFO L144 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-02-23 22:35:43,425 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [518326477] [2022-02-23 22:35:43,425 WARN L317 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-02-23 22:35:43,425 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [585175001] [2022-02-23 22:35:43,425 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleZ3 [585175001] provided 1 perfect and 0 imperfect interpolant sequences [2022-02-23 22:35:43,426 INFO L191 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-02-23 22:35:43,426 INFO L204 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2022-02-23 22:35:43,426 INFO L118 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1520767875] [2022-02-23 22:35:43,426 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-02-23 22:35:43,426 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2022-02-23 22:35:43,427 INFO L108 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-02-23 22:35:43,427 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2022-02-23 22:35:43,427 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2022-02-23 22:35:43,427 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-02-23 22:35:43,438 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-02-23 22:35:43,438 INFO L93 Difference]: Finished difference Result 44 states and 56 transitions. [2022-02-23 22:35:43,439 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2022-02-23 22:35:43,439 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-02-23 22:35:43,439 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-02-23 22:35:43,439 INFO L225 Difference]: With dead ends: 44 [2022-02-23 22:35:43,440 INFO L226 Difference]: Without dead ends: 36 [2022-02-23 22:35:43,440 INFO L932 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-02-23 22:35:43,441 INFO L933 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-02-23 22:35:43,441 INFO L934 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-02-23 22:35:43,442 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 36 states. [2022-02-23 22:35:43,445 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 36 to 36. [2022-02-23 22:35:43,445 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-02-23 22:35:43,446 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 36 states to 36 states and 47 transitions. [2022-02-23 22:35:43,446 INFO L78 Accepts]: Start accepts. Automaton has 36 states and 47 transitions. Word has length 33 [2022-02-23 22:35:43,446 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-02-23 22:35:43,446 INFO L470 AbstractCegarLoop]: Abstraction has 36 states and 47 transitions. [2022-02-23 22:35:43,446 INFO L471 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-02-23 22:35:43,446 INFO L276 IsEmpty]: Start isEmpty. Operand 36 states and 47 transitions. [2022-02-23 22:35:43,447 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 35 [2022-02-23 22:35:43,447 INFO L506 BasicCegarLoop]: Found error trace [2022-02-23 22:35:43,447 INFO L514 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-02-23 22:35:43,466 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Ended with exit code 0 [2022-02-23 22:35:43,665 WARN L452 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-02-23 22:35:43,666 INFO L402 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-02-23 22:35:43,666 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-02-23 22:35:43,667 INFO L85 PathProgramCache]: Analyzing trace with hash 365419517, now seen corresponding path program 1 times [2022-02-23 22:35:43,667 INFO L126 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-02-23 22:35:43,667 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1777228196] [2022-02-23 22:35:43,667 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-02-23 22:35:43,667 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-02-23 22:35:43,704 ERROR L252 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-02-23 22:35:43,704 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1751852631] [2022-02-23 22:35:43,704 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-02-23 22:35:43,705 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-02-23 22:35:43,705 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-02-23 22:35:43,706 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-02-23 22:35:43,707 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-02-23 22:35:43,764 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-02-23 22:35:43,765 INFO L263 TraceCheckSpWp]: Trace formula consists of 127 conjuncts, 7 conjunts are in the unsatisfiable core [2022-02-23 22:35:43,768 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-02-23 22:35:43,846 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 3 proven. 6 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2022-02-23 22:35:43,846 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-02-23 22:35:43,949 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 3 proven. 6 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2022-02-23 22:35:43,950 INFO L144 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-02-23 22:35:43,950 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1777228196] [2022-02-23 22:35:43,950 WARN L317 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-02-23 22:35:43,950 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1751852631] [2022-02-23 22:35:43,950 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1751852631] provided 0 perfect and 2 imperfect interpolant sequences [2022-02-23 22:35:43,950 INFO L191 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-02-23 22:35:43,950 INFO L204 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 7 [2022-02-23 22:35:43,950 INFO L118 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2053160107] [2022-02-23 22:35:43,950 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-02-23 22:35:43,951 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2022-02-23 22:35:43,952 INFO L108 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-02-23 22:35:43,952 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2022-02-23 22:35:43,953 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=29, Unknown=0, NotChecked=0, Total=42 [2022-02-23 22:35:43,953 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-02-23 22:35:44,031 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-02-23 22:35:44,031 INFO L93 Difference]: Finished difference Result 53 states and 71 transitions. [2022-02-23 22:35:44,032 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2022-02-23 22:35:44,032 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-02-23 22:35:44,032 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-02-23 22:35:44,033 INFO L225 Difference]: With dead ends: 53 [2022-02-23 22:35:44,033 INFO L226 Difference]: Without dead ends: 45 [2022-02-23 22:35:44,034 INFO L932 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-02-23 22:35:44,034 INFO L933 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-02-23 22:35:44,037 INFO L934 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-02-23 22:35:44,037 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 45 states. [2022-02-23 22:35:44,042 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 45 to 37. [2022-02-23 22:35:44,042 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-02-23 22:35:44,042 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 37 states to 37 states and 48 transitions. [2022-02-23 22:35:44,042 INFO L78 Accepts]: Start accepts. Automaton has 37 states and 48 transitions. Word has length 34 [2022-02-23 22:35:44,043 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-02-23 22:35:44,043 INFO L470 AbstractCegarLoop]: Abstraction has 37 states and 48 transitions. [2022-02-23 22:35:44,043 INFO L471 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-02-23 22:35:44,043 INFO L276 IsEmpty]: Start isEmpty. Operand 37 states and 48 transitions. [2022-02-23 22:35:44,044 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 37 [2022-02-23 22:35:44,044 INFO L506 BasicCegarLoop]: Found error trace [2022-02-23 22:35:44,044 INFO L514 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-02-23 22:35:44,065 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-02-23 22:35:44,244 WARN L452 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-02-23 22:35:44,244 INFO L402 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-02-23 22:35:44,245 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-02-23 22:35:44,245 INFO L85 PathProgramCache]: Analyzing trace with hash 196514290, now seen corresponding path program 1 times [2022-02-23 22:35:44,245 INFO L126 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-02-23 22:35:44,245 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [777051151] [2022-02-23 22:35:44,245 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-02-23 22:35:44,245 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-02-23 22:35:44,260 ERROR L252 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-02-23 22:35:44,260 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1131162229] [2022-02-23 22:35:44,260 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-02-23 22:35:44,260 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-02-23 22:35:44,260 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-02-23 22:35:44,265 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-02-23 22:35:44,266 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-02-23 22:35:44,321 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-02-23 22:35:44,328 INFO L263 TraceCheckSpWp]: Trace formula consists of 135 conjuncts, 14 conjunts are in the unsatisfiable core [2022-02-23 22:35:44,330 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-02-23 22:35:44,431 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 3 proven. 6 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2022-02-23 22:35:44,432 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-02-23 22:35:44,550 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2022-02-23 22:35:44,550 INFO L144 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-02-23 22:35:44,550 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [777051151] [2022-02-23 22:35:44,550 WARN L317 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-02-23 22:35:44,551 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1131162229] [2022-02-23 22:35:44,551 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1131162229] provided 1 perfect and 1 imperfect interpolant sequences [2022-02-23 22:35:44,551 INFO L191 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2022-02-23 22:35:44,551 INFO L204 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [9] total 10 [2022-02-23 22:35:44,551 INFO L118 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [554889495] [2022-02-23 22:35:44,551 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-02-23 22:35:44,551 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-02-23 22:35:44,551 INFO L108 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-02-23 22:35:44,552 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-02-23 22:35:44,552 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=19, Invalid=71, Unknown=0, NotChecked=0, Total=90 [2022-02-23 22:35:44,552 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-02-23 22:35:44,578 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-02-23 22:35:44,579 INFO L93 Difference]: Finished difference Result 43 states and 53 transitions. [2022-02-23 22:35:44,579 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-02-23 22:35:44,579 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-02-23 22:35:44,579 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-02-23 22:35:44,580 INFO L225 Difference]: With dead ends: 43 [2022-02-23 22:35:44,580 INFO L226 Difference]: Without dead ends: 41 [2022-02-23 22:35:44,580 INFO L932 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-02-23 22:35:44,581 INFO L933 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-02-23 22:35:44,581 INFO L934 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-02-23 22:35:44,581 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 41 states. [2022-02-23 22:35:44,585 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 41 to 41. [2022-02-23 22:35:44,585 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-02-23 22:35:44,586 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 41 states to 41 states and 51 transitions. [2022-02-23 22:35:44,586 INFO L78 Accepts]: Start accepts. Automaton has 41 states and 51 transitions. Word has length 36 [2022-02-23 22:35:44,586 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-02-23 22:35:44,586 INFO L470 AbstractCegarLoop]: Abstraction has 41 states and 51 transitions. [2022-02-23 22:35:44,586 INFO L471 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-02-23 22:35:44,586 INFO L276 IsEmpty]: Start isEmpty. Operand 41 states and 51 transitions. [2022-02-23 22:35:44,587 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 40 [2022-02-23 22:35:44,587 INFO L506 BasicCegarLoop]: Found error trace [2022-02-23 22:35:44,587 INFO L514 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-02-23 22:35:44,603 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-02-23 22:35:44,803 WARN L452 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-02-23 22:35:44,804 INFO L402 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-02-23 22:35:44,804 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-02-23 22:35:44,804 INFO L85 PathProgramCache]: Analyzing trace with hash 56558454, now seen corresponding path program 1 times [2022-02-23 22:35:44,804 INFO L126 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-02-23 22:35:44,804 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1843566535] [2022-02-23 22:35:44,804 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-02-23 22:35:44,805 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-02-23 22:35:44,814 ERROR L252 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-02-23 22:35:44,814 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [428967966] [2022-02-23 22:35:44,814 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-02-23 22:35:44,814 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-02-23 22:35:44,814 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-02-23 22:35:44,815 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-02-23 22:35:44,816 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-02-23 22:35:44,851 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-02-23 22:35:44,852 INFO L263 TraceCheckSpWp]: Trace formula consists of 154 conjuncts, 7 conjunts are in the unsatisfiable core [2022-02-23 22:35:44,853 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-02-23 22:35:44,913 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2022-02-23 22:35:44,913 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-02-23 22:35:44,913 INFO L144 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-02-23 22:35:44,913 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1843566535] [2022-02-23 22:35:44,913 WARN L317 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-02-23 22:35:44,913 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [428967966] [2022-02-23 22:35:44,913 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleZ3 [428967966] provided 1 perfect and 0 imperfect interpolant sequences [2022-02-23 22:35:44,914 INFO L191 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-02-23 22:35:44,914 INFO L204 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-02-23 22:35:44,914 INFO L118 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [509407132] [2022-02-23 22:35:44,914 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-02-23 22:35:44,914 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-02-23 22:35:44,914 INFO L108 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-02-23 22:35:44,914 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-02-23 22:35:44,915 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2022-02-23 22:35:44,915 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-02-23 22:35:44,934 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-02-23 22:35:44,934 INFO L93 Difference]: Finished difference Result 66 states and 84 transitions. [2022-02-23 22:35:44,935 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-02-23 22:35:44,935 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-02-23 22:35:44,935 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-02-23 22:35:44,935 INFO L225 Difference]: With dead ends: 66 [2022-02-23 22:35:44,936 INFO L226 Difference]: Without dead ends: 43 [2022-02-23 22:35:44,936 INFO L932 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-02-23 22:35:44,936 INFO L933 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-02-23 22:35:44,937 INFO L934 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-02-23 22:35:44,937 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 43 states. [2022-02-23 22:35:44,940 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 43 to 43. [2022-02-23 22:35:44,941 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-02-23 22:35:44,941 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 43 states to 43 states and 53 transitions. [2022-02-23 22:35:44,941 INFO L78 Accepts]: Start accepts. Automaton has 43 states and 53 transitions. Word has length 39 [2022-02-23 22:35:44,942 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-02-23 22:35:44,942 INFO L470 AbstractCegarLoop]: Abstraction has 43 states and 53 transitions. [2022-02-23 22:35:44,942 INFO L471 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-02-23 22:35:44,942 INFO L276 IsEmpty]: Start isEmpty. Operand 43 states and 53 transitions. [2022-02-23 22:35:44,942 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 42 [2022-02-23 22:35:44,942 INFO L506 BasicCegarLoop]: Found error trace [2022-02-23 22:35:44,942 INFO L514 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-02-23 22:35:44,959 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Ended with exit code 0 [2022-02-23 22:35:45,158 WARN L452 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-02-23 22:35:45,158 INFO L402 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-02-23 22:35:45,159 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-02-23 22:35:45,159 INFO L85 PathProgramCache]: Analyzing trace with hash 578094295, now seen corresponding path program 1 times [2022-02-23 22:35:45,159 INFO L126 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-02-23 22:35:45,159 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1834839461] [2022-02-23 22:35:45,159 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-02-23 22:35:45,159 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-02-23 22:35:45,168 ERROR L252 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-02-23 22:35:45,168 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1706408764] [2022-02-23 22:35:45,168 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-02-23 22:35:45,168 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-02-23 22:35:45,168 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-02-23 22:35:45,169 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-02-23 22:35:45,170 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-02-23 22:35:45,204 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-02-23 22:35:45,205 INFO L263 TraceCheckSpWp]: Trace formula consists of 144 conjuncts, 14 conjunts are in the unsatisfiable core [2022-02-23 22:35:45,206 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-02-23 22:35:45,332 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 5 proven. 6 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2022-02-23 22:35:45,333 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-02-23 22:35:45,408 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2022-02-23 22:35:45,408 INFO L144 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-02-23 22:35:45,408 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1834839461] [2022-02-23 22:35:45,409 WARN L317 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-02-23 22:35:45,409 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1706408764] [2022-02-23 22:35:45,409 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1706408764] provided 1 perfect and 1 imperfect interpolant sequences [2022-02-23 22:35:45,409 INFO L191 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2022-02-23 22:35:45,409 INFO L204 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [8] total 9 [2022-02-23 22:35:45,409 INFO L118 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1285071846] [2022-02-23 22:35:45,409 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-02-23 22:35:45,409 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-02-23 22:35:45,409 INFO L108 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-02-23 22:35:45,410 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-02-23 22:35:45,410 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=17, Invalid=55, Unknown=0, NotChecked=0, Total=72 [2022-02-23 22:35:45,410 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-02-23 22:35:45,434 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-02-23 22:35:45,434 INFO L93 Difference]: Finished difference Result 57 states and 72 transitions. [2022-02-23 22:35:45,434 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-02-23 22:35:45,434 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-02-23 22:35:45,435 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-02-23 22:35:45,435 INFO L225 Difference]: With dead ends: 57 [2022-02-23 22:35:45,435 INFO L226 Difference]: Without dead ends: 55 [2022-02-23 22:35:45,435 INFO L932 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-02-23 22:35:45,436 INFO L933 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-02-23 22:35:45,436 INFO L934 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-02-23 22:35:45,436 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 55 states. [2022-02-23 22:35:45,441 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 55 to 54. [2022-02-23 22:35:45,441 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-02-23 22:35:45,441 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 54 states to 54 states and 69 transitions. [2022-02-23 22:35:45,441 INFO L78 Accepts]: Start accepts. Automaton has 54 states and 69 transitions. Word has length 41 [2022-02-23 22:35:45,442 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-02-23 22:35:45,442 INFO L470 AbstractCegarLoop]: Abstraction has 54 states and 69 transitions. [2022-02-23 22:35:45,442 INFO L471 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-02-23 22:35:45,442 INFO L276 IsEmpty]: Start isEmpty. Operand 54 states and 69 transitions. [2022-02-23 22:35:45,442 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 47 [2022-02-23 22:35:45,443 INFO L506 BasicCegarLoop]: Found error trace [2022-02-23 22:35:45,443 INFO L514 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-02-23 22:35:45,460 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Forceful destruction successful, exit code 0 [2022-02-23 22:35:45,661 WARN L452 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-02-23 22:35:45,661 INFO L402 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-02-23 22:35:45,661 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-02-23 22:35:45,661 INFO L85 PathProgramCache]: Analyzing trace with hash -1581112078, now seen corresponding path program 1 times [2022-02-23 22:35:45,661 INFO L126 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-02-23 22:35:45,662 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [7679045] [2022-02-23 22:35:45,662 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-02-23 22:35:45,662 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-02-23 22:35:45,669 ERROR L252 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-02-23 22:35:45,669 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1105983072] [2022-02-23 22:35:45,669 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-02-23 22:35:45,670 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-02-23 22:35:45,670 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-02-23 22:35:45,671 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-02-23 22:35:45,672 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-02-23 22:35:45,704 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-02-23 22:35:45,705 INFO L263 TraceCheckSpWp]: Trace formula consists of 153 conjuncts, 14 conjunts are in the unsatisfiable core [2022-02-23 22:35:45,706 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-02-23 22:35:45,855 INFO L134 CoverageAnalysis]: Checked inductivity of 32 backedges. 4 proven. 9 refuted. 0 times theorem prover too weak. 19 trivial. 0 not checked. [2022-02-23 22:35:45,855 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-02-23 22:35:45,949 INFO L134 CoverageAnalysis]: Checked inductivity of 32 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2022-02-23 22:35:45,950 INFO L144 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-02-23 22:35:45,950 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [7679045] [2022-02-23 22:35:45,950 WARN L317 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-02-23 22:35:45,950 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1105983072] [2022-02-23 22:35:45,950 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1105983072] provided 1 perfect and 1 imperfect interpolant sequences [2022-02-23 22:35:45,950 INFO L191 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2022-02-23 22:35:45,950 INFO L204 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [8] total 9 [2022-02-23 22:35:45,950 INFO L118 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [889475221] [2022-02-23 22:35:45,950 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-02-23 22:35:45,951 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-02-23 22:35:45,951 INFO L108 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-02-23 22:35:45,951 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-02-23 22:35:45,951 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=17, Invalid=55, Unknown=0, NotChecked=0, Total=72 [2022-02-23 22:35:45,951 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-02-23 22:35:45,982 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-02-23 22:35:45,982 INFO L93 Difference]: Finished difference Result 61 states and 75 transitions. [2022-02-23 22:35:45,983 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-02-23 22:35:45,983 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-02-23 22:35:45,983 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-02-23 22:35:45,999 INFO L225 Difference]: With dead ends: 61 [2022-02-23 22:35:45,999 INFO L226 Difference]: Without dead ends: 59 [2022-02-23 22:35:46,000 INFO L932 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-02-23 22:35:46,000 INFO L933 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-02-23 22:35:46,001 INFO L934 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-02-23 22:35:46,001 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 59 states. [2022-02-23 22:35:46,005 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 59 to 58. [2022-02-23 22:35:46,006 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-02-23 22:35:46,006 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 58 states to 58 states and 72 transitions. [2022-02-23 22:35:46,006 INFO L78 Accepts]: Start accepts. Automaton has 58 states and 72 transitions. Word has length 46 [2022-02-23 22:35:46,006 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-02-23 22:35:46,006 INFO L470 AbstractCegarLoop]: Abstraction has 58 states and 72 transitions. [2022-02-23 22:35:46,007 INFO L471 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-02-23 22:35:46,007 INFO L276 IsEmpty]: Start isEmpty. Operand 58 states and 72 transitions. [2022-02-23 22:35:46,007 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 52 [2022-02-23 22:35:46,007 INFO L506 BasicCegarLoop]: Found error trace [2022-02-23 22:35:46,008 INFO L514 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-02-23 22:35:46,026 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Forceful destruction successful, exit code 0 [2022-02-23 22:35:46,222 WARN L452 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-02-23 22:35:46,223 INFO L402 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-02-23 22:35:46,223 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-02-23 22:35:46,223 INFO L85 PathProgramCache]: Analyzing trace with hash 1942645143, now seen corresponding path program 1 times [2022-02-23 22:35:46,223 INFO L126 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-02-23 22:35:46,223 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1131646875] [2022-02-23 22:35:46,224 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-02-23 22:35:46,224 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-02-23 22:35:46,231 ERROR L252 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-02-23 22:35:46,231 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1489609562] [2022-02-23 22:35:46,231 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-02-23 22:35:46,231 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-02-23 22:35:46,231 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-02-23 22:35:46,232 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-02-23 22:35:46,233 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-02-23 22:35:46,266 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-02-23 22:35:46,267 INFO L263 TraceCheckSpWp]: Trace formula consists of 162 conjuncts, 28 conjunts are in the unsatisfiable core [2022-02-23 22:35:46,269 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-02-23 22:35:46,469 INFO L134 CoverageAnalysis]: Checked inductivity of 42 backedges. 13 proven. 8 refuted. 0 times theorem prover too weak. 21 trivial. 0 not checked. [2022-02-23 22:35:46,469 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-02-23 22:35:46,558 INFO L144 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-02-23 22:35:46,559 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1131646875] [2022-02-23 22:35:46,559 WARN L317 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-02-23 22:35:46,559 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1489609562] [2022-02-23 22:35:46,559 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1489609562] provided 0 perfect and 1 imperfect interpolant sequences [2022-02-23 22:35:46,559 INFO L191 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-02-23 22:35:46,559 INFO L204 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10] total 10 [2022-02-23 22:35:46,559 INFO L118 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1960267341] [2022-02-23 22:35:46,559 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2022-02-23 22:35:46,560 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2022-02-23 22:35:46,560 INFO L108 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-02-23 22:35:46,560 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2022-02-23 22:35:46,560 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=26, Invalid=106, Unknown=0, NotChecked=0, Total=132 [2022-02-23 22:35:46,560 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-02-23 22:35:46,688 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-02-23 22:35:46,688 INFO L93 Difference]: Finished difference Result 65 states and 78 transitions. [2022-02-23 22:35:46,688 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2022-02-23 22:35:46,688 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-02-23 22:35:46,689 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-02-23 22:35:46,689 INFO L225 Difference]: With dead ends: 65 [2022-02-23 22:35:46,689 INFO L226 Difference]: Without dead ends: 63 [2022-02-23 22:35:46,689 INFO L932 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-02-23 22:35:46,690 INFO L933 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-02-23 22:35:46,690 INFO L934 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-02-23 22:35:46,690 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 63 states. [2022-02-23 22:35:46,695 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 63 to 62. [2022-02-23 22:35:46,695 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-02-23 22:35:46,695 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 62 states to 62 states and 75 transitions. [2022-02-23 22:35:46,695 INFO L78 Accepts]: Start accepts. Automaton has 62 states and 75 transitions. Word has length 51 [2022-02-23 22:35:46,695 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-02-23 22:35:46,695 INFO L470 AbstractCegarLoop]: Abstraction has 62 states and 75 transitions. [2022-02-23 22:35:46,696 INFO L471 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-02-23 22:35:46,696 INFO L276 IsEmpty]: Start isEmpty. Operand 62 states and 75 transitions. [2022-02-23 22:35:46,696 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 61 [2022-02-23 22:35:46,696 INFO L506 BasicCegarLoop]: Found error trace [2022-02-23 22:35:46,696 INFO L514 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-02-23 22:35:46,714 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-02-23 22:35:46,907 WARN L452 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-02-23 22:35:46,907 INFO L402 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-02-23 22:35:46,908 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-02-23 22:35:46,908 INFO L85 PathProgramCache]: Analyzing trace with hash -1573186588, now seen corresponding path program 1 times [2022-02-23 22:35:46,908 INFO L126 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-02-23 22:35:46,908 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1783985735] [2022-02-23 22:35:46,908 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-02-23 22:35:46,908 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-02-23 22:35:46,916 ERROR L252 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-02-23 22:35:46,916 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [11634801] [2022-02-23 22:35:46,916 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-02-23 22:35:46,916 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-02-23 22:35:46,916 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-02-23 22:35:46,917 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-02-23 22:35:46,918 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-02-23 22:35:46,953 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-02-23 22:35:46,954 INFO L263 TraceCheckSpWp]: Trace formula consists of 191 conjuncts, 9 conjunts are in the unsatisfiable core [2022-02-23 22:35:46,955 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-02-23 22:35:47,049 INFO L134 CoverageAnalysis]: Checked inductivity of 58 backedges. 8 proven. 2 refuted. 0 times theorem prover too weak. 48 trivial. 0 not checked. [2022-02-23 22:35:47,049 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-02-23 22:35:47,206 INFO L134 CoverageAnalysis]: Checked inductivity of 58 backedges. 8 proven. 2 refuted. 0 times theorem prover too weak. 48 trivial. 0 not checked. [2022-02-23 22:35:47,207 INFO L144 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-02-23 22:35:47,207 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1783985735] [2022-02-23 22:35:47,207 WARN L317 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-02-23 22:35:47,207 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [11634801] [2022-02-23 22:35:47,207 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleZ3 [11634801] provided 0 perfect and 2 imperfect interpolant sequences [2022-02-23 22:35:47,207 INFO L191 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-02-23 22:35:47,207 INFO L204 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 9 [2022-02-23 22:35:47,209 INFO L118 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [260401773] [2022-02-23 22:35:47,209 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-02-23 22:35:47,210 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2022-02-23 22:35:47,210 INFO L108 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-02-23 22:35:47,210 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2022-02-23 22:35:47,210 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=26, Invalid=46, Unknown=0, NotChecked=0, Total=72 [2022-02-23 22:35:47,211 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-02-23 22:35:47,348 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-02-23 22:35:47,349 INFO L93 Difference]: Finished difference Result 173 states and 202 transitions. [2022-02-23 22:35:47,349 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2022-02-23 22:35:47,349 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-02-23 22:35:47,349 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-02-23 22:35:47,351 INFO L225 Difference]: With dead ends: 173 [2022-02-23 22:35:47,351 INFO L226 Difference]: Without dead ends: 165 [2022-02-23 22:35:47,352 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 122 GetRequests, 111 SyntacticMatches, 1 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 11 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=47, Invalid=85, Unknown=0, NotChecked=0, Total=132 [2022-02-23 22:35:47,354 INFO L933 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-02-23 22:35:47,354 INFO L934 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-02-23 22:35:47,355 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 165 states. [2022-02-23 22:35:47,381 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 165 to 159. [2022-02-23 22:35:47,381 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-02-23 22:35:47,382 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 159 states to 159 states and 187 transitions. [2022-02-23 22:35:47,382 INFO L78 Accepts]: Start accepts. Automaton has 159 states and 187 transitions. Word has length 60 [2022-02-23 22:35:47,383 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-02-23 22:35:47,383 INFO L470 AbstractCegarLoop]: Abstraction has 159 states and 187 transitions. [2022-02-23 22:35:47,383 INFO L471 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-02-23 22:35:47,383 INFO L276 IsEmpty]: Start isEmpty. Operand 159 states and 187 transitions. [2022-02-23 22:35:47,385 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 62 [2022-02-23 22:35:47,385 INFO L506 BasicCegarLoop]: Found error trace [2022-02-23 22:35:47,385 INFO L514 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-02-23 22:35:47,403 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-02-23 22:35:47,601 WARN L452 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-02-23 22:35:47,601 INFO L402 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-02-23 22:35:47,601 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-02-23 22:35:47,602 INFO L85 PathProgramCache]: Analyzing trace with hash -1491020248, now seen corresponding path program 1 times [2022-02-23 22:35:47,602 INFO L126 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-02-23 22:35:47,602 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1922050184] [2022-02-23 22:35:47,602 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-02-23 22:35:47,602 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-02-23 22:35:47,608 ERROR L252 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-02-23 22:35:47,608 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [790989434] [2022-02-23 22:35:47,608 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-02-23 22:35:47,608 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-02-23 22:35:47,609 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-02-23 22:35:47,615 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-02-23 22:35:47,616 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-02-23 22:35:47,688 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-02-23 22:35:47,688 INFO L263 TraceCheckSpWp]: Trace formula consists of 193 conjuncts, 9 conjunts are in the unsatisfiable core [2022-02-23 22:35:47,691 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-02-23 22:35:47,778 INFO L134 CoverageAnalysis]: Checked inductivity of 59 backedges. 8 proven. 12 refuted. 0 times theorem prover too weak. 39 trivial. 0 not checked. [2022-02-23 22:35:47,779 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-02-23 22:35:47,895 INFO L134 CoverageAnalysis]: Checked inductivity of 59 backedges. 8 proven. 12 refuted. 0 times theorem prover too weak. 39 trivial. 0 not checked. [2022-02-23 22:35:47,895 INFO L144 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-02-23 22:35:47,895 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1922050184] [2022-02-23 22:35:47,896 WARN L317 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-02-23 22:35:47,896 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [790989434] [2022-02-23 22:35:47,896 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleZ3 [790989434] provided 0 perfect and 2 imperfect interpolant sequences [2022-02-23 22:35:47,896 INFO L191 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-02-23 22:35:47,896 INFO L204 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 9 [2022-02-23 22:35:47,896 INFO L118 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [506509082] [2022-02-23 22:35:47,896 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-02-23 22:35:47,896 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2022-02-23 22:35:47,896 INFO L108 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-02-23 22:35:47,897 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2022-02-23 22:35:47,897 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=17, Invalid=55, Unknown=0, NotChecked=0, Total=72 [2022-02-23 22:35:47,897 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-02-23 22:35:48,024 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-02-23 22:35:48,024 INFO L93 Difference]: Finished difference Result 225 states and 292 transitions. [2022-02-23 22:35:48,024 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2022-02-23 22:35:48,024 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-02-23 22:35:48,024 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-02-23 22:35:48,025 INFO L225 Difference]: With dead ends: 225 [2022-02-23 22:35:48,025 INFO L226 Difference]: Without dead ends: 211 [2022-02-23 22:35:48,026 INFO L932 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-02-23 22:35:48,026 INFO L933 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-02-23 22:35:48,026 INFO L934 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-02-23 22:35:48,027 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 211 states. [2022-02-23 22:35:48,036 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 211 to 189. [2022-02-23 22:35:48,037 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-02-23 22:35:48,038 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 189 states to 189 states and 237 transitions. [2022-02-23 22:35:48,038 INFO L78 Accepts]: Start accepts. Automaton has 189 states and 237 transitions. Word has length 61 [2022-02-23 22:35:48,038 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-02-23 22:35:48,038 INFO L470 AbstractCegarLoop]: Abstraction has 189 states and 237 transitions. [2022-02-23 22:35:48,038 INFO L471 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-02-23 22:35:48,038 INFO L276 IsEmpty]: Start isEmpty. Operand 189 states and 237 transitions. [2022-02-23 22:35:48,039 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 64 [2022-02-23 22:35:48,039 INFO L506 BasicCegarLoop]: Found error trace [2022-02-23 22:35:48,039 INFO L514 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-02-23 22:35:48,066 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Ended with exit code 0 [2022-02-23 22:35:48,266 WARN L452 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-02-23 22:35:48,266 INFO L402 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-02-23 22:35:48,267 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-02-23 22:35:48,267 INFO L85 PathProgramCache]: Analyzing trace with hash 317217743, now seen corresponding path program 1 times [2022-02-23 22:35:48,267 INFO L126 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-02-23 22:35:48,267 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [441554443] [2022-02-23 22:35:48,267 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-02-23 22:35:48,267 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-02-23 22:35:48,273 ERROR L252 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-02-23 22:35:48,273 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1067885485] [2022-02-23 22:35:48,273 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-02-23 22:35:48,273 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-02-23 22:35:48,273 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-02-23 22:35:48,274 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-02-23 22:35:48,275 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-02-23 22:35:48,324 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-02-23 22:35:48,324 INFO L263 TraceCheckSpWp]: Trace formula consists of 202 conjuncts, 9 conjunts are in the unsatisfiable core [2022-02-23 22:35:48,326 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-02-23 22:35:48,425 INFO L134 CoverageAnalysis]: Checked inductivity of 61 backedges. 11 proven. 2 refuted. 0 times theorem prover too weak. 48 trivial. 0 not checked. [2022-02-23 22:35:48,425 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-02-23 22:35:48,559 INFO L134 CoverageAnalysis]: Checked inductivity of 61 backedges. 11 proven. 2 refuted. 0 times theorem prover too weak. 48 trivial. 0 not checked. [2022-02-23 22:35:48,560 INFO L144 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-02-23 22:35:48,560 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [441554443] [2022-02-23 22:35:48,560 WARN L317 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-02-23 22:35:48,560 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1067885485] [2022-02-23 22:35:48,560 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1067885485] provided 0 perfect and 2 imperfect interpolant sequences [2022-02-23 22:35:48,560 INFO L191 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-02-23 22:35:48,560 INFO L204 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 9 [2022-02-23 22:35:48,560 INFO L118 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [575495914] [2022-02-23 22:35:48,560 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-02-23 22:35:48,560 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2022-02-23 22:35:48,561 INFO L108 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-02-23 22:35:48,561 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2022-02-23 22:35:48,561 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=26, Invalid=46, Unknown=0, NotChecked=0, Total=72 [2022-02-23 22:35:48,561 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-02-23 22:35:48,649 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-02-23 22:35:48,649 INFO L93 Difference]: Finished difference Result 269 states and 350 transitions. [2022-02-23 22:35:48,649 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2022-02-23 22:35:48,649 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-02-23 22:35:48,650 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-02-23 22:35:48,650 INFO L225 Difference]: With dead ends: 269 [2022-02-23 22:35:48,650 INFO L226 Difference]: Without dead ends: 197 [2022-02-23 22:35:48,651 INFO L932 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-02-23 22:35:48,651 INFO L933 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-02-23 22:35:48,652 INFO L934 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-02-23 22:35:48,652 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 197 states. [2022-02-23 22:35:48,661 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 197 to 195. [2022-02-23 22:35:48,661 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-02-23 22:35:48,662 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 195 states to 195 states and 240 transitions. [2022-02-23 22:35:48,662 INFO L78 Accepts]: Start accepts. Automaton has 195 states and 240 transitions. Word has length 63 [2022-02-23 22:35:48,662 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-02-23 22:35:48,662 INFO L470 AbstractCegarLoop]: Abstraction has 195 states and 240 transitions. [2022-02-23 22:35:48,662 INFO L471 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-02-23 22:35:48,662 INFO L276 IsEmpty]: Start isEmpty. Operand 195 states and 240 transitions. [2022-02-23 22:35:48,663 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 69 [2022-02-23 22:35:48,663 INFO L506 BasicCegarLoop]: Found error trace [2022-02-23 22:35:48,663 INFO L514 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-02-23 22:35:48,679 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Ended with exit code 0 [2022-02-23 22:35:48,876 WARN L452 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-02-23 22:35:48,877 INFO L402 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-02-23 22:35:48,877 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-02-23 22:35:48,877 INFO L85 PathProgramCache]: Analyzing trace with hash 918639692, now seen corresponding path program 1 times [2022-02-23 22:35:48,877 INFO L126 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-02-23 22:35:48,877 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [589768936] [2022-02-23 22:35:48,877 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-02-23 22:35:48,877 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-02-23 22:35:48,884 ERROR L252 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-02-23 22:35:48,884 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1923160059] [2022-02-23 22:35:48,884 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-02-23 22:35:48,884 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-02-23 22:35:48,884 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-02-23 22:35:48,885 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-02-23 22:35:48,886 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-02-23 22:35:48,934 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-02-23 22:35:48,935 INFO L263 TraceCheckSpWp]: Trace formula consists of 210 conjuncts, 32 conjunts are in the unsatisfiable core [2022-02-23 22:35:48,936 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-02-23 22:35:49,166 INFO L134 CoverageAnalysis]: Checked inductivity of 81 backedges. 15 proven. 14 refuted. 0 times theorem prover too weak. 52 trivial. 0 not checked. [2022-02-23 22:35:49,167 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-02-23 22:35:49,301 INFO L134 CoverageAnalysis]: Checked inductivity of 81 backedges. 22 proven. 7 refuted. 0 times theorem prover too weak. 52 trivial. 0 not checked. [2022-02-23 22:35:49,301 INFO L144 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-02-23 22:35:49,301 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [589768936] [2022-02-23 22:35:49,301 WARN L317 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-02-23 22:35:49,301 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1923160059] [2022-02-23 22:35:49,301 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1923160059] provided 0 perfect and 2 imperfect interpolant sequences [2022-02-23 22:35:49,301 INFO L191 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-02-23 22:35:49,301 INFO L204 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 8] total 12 [2022-02-23 22:35:49,301 INFO L118 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [633240601] [2022-02-23 22:35:49,301 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-02-23 22:35:49,302 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2022-02-23 22:35:49,302 INFO L108 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-02-23 22:35:49,302 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2022-02-23 22:35:49,302 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=28, Invalid=104, Unknown=0, NotChecked=0, Total=132 [2022-02-23 22:35:49,302 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-02-23 22:35:49,531 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-02-23 22:35:49,531 INFO L93 Difference]: Finished difference Result 272 states and 358 transitions. [2022-02-23 22:35:49,531 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2022-02-23 22:35:49,531 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-02-23 22:35:49,532 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-02-23 22:35:49,534 INFO L225 Difference]: With dead ends: 272 [2022-02-23 22:35:49,534 INFO L226 Difference]: Without dead ends: 267 [2022-02-23 22:35:49,534 INFO L932 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-02-23 22:35:49,535 INFO L933 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-02-23 22:35:49,535 INFO L934 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-02-23 22:35:49,535 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 267 states. [2022-02-23 22:35:49,557 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 267 to 237. [2022-02-23 22:35:49,558 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-02-23 22:35:49,559 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 237 states to 237 states and 301 transitions. [2022-02-23 22:35:49,559 INFO L78 Accepts]: Start accepts. Automaton has 237 states and 301 transitions. Word has length 68 [2022-02-23 22:35:49,559 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-02-23 22:35:49,559 INFO L470 AbstractCegarLoop]: Abstraction has 237 states and 301 transitions. [2022-02-23 22:35:49,559 INFO L471 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-02-23 22:35:49,559 INFO L276 IsEmpty]: Start isEmpty. Operand 237 states and 301 transitions. [2022-02-23 22:35:49,560 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 74 [2022-02-23 22:35:49,560 INFO L506 BasicCegarLoop]: Found error trace [2022-02-23 22:35:49,560 INFO L514 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-02-23 22:35:49,576 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-02-23 22:35:49,773 WARN L452 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-02-23 22:35:49,774 INFO L402 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-02-23 22:35:49,774 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-02-23 22:35:49,774 INFO L85 PathProgramCache]: Analyzing trace with hash -210356579, now seen corresponding path program 2 times [2022-02-23 22:35:49,774 INFO L126 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-02-23 22:35:49,774 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [208673016] [2022-02-23 22:35:49,774 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-02-23 22:35:49,774 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-02-23 22:35:49,781 ERROR L252 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-02-23 22:35:49,781 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1232530075] [2022-02-23 22:35:49,781 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-02-23 22:35:49,781 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-02-23 22:35:49,781 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-02-23 22:35:49,782 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-02-23 22:35:49,783 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-02-23 22:35:49,826 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-02-23 22:35:49,826 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-02-23 22:35:49,827 INFO L263 TraceCheckSpWp]: Trace formula consists of 219 conjuncts, 36 conjunts are in the unsatisfiable core [2022-02-23 22:35:49,830 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-02-23 22:35:50,183 INFO L134 CoverageAnalysis]: Checked inductivity of 104 backedges. 17 proven. 18 refuted. 0 times theorem prover too weak. 69 trivial. 0 not checked. [2022-02-23 22:35:50,183 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-02-23 22:35:50,477 INFO L134 CoverageAnalysis]: Checked inductivity of 104 backedges. 17 proven. 18 refuted. 0 times theorem prover too weak. 69 trivial. 0 not checked. [2022-02-23 22:35:50,477 INFO L144 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-02-23 22:35:50,477 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [208673016] [2022-02-23 22:35:50,477 WARN L317 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-02-23 22:35:50,477 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1232530075] [2022-02-23 22:35:50,477 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1232530075] provided 0 perfect and 2 imperfect interpolant sequences [2022-02-23 22:35:50,477 INFO L191 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-02-23 22:35:50,477 INFO L204 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10] total 15 [2022-02-23 22:35:50,478 INFO L118 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1269934127] [2022-02-23 22:35:50,478 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-02-23 22:35:50,478 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 15 states [2022-02-23 22:35:50,478 INFO L108 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-02-23 22:35:50,478 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2022-02-23 22:35:50,478 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=41, Invalid=169, Unknown=0, NotChecked=0, Total=210 [2022-02-23 22:35:50,479 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-02-23 22:35:53,023 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-02-23 22:35:53,259 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-02-23 22:35:53,260 INFO L93 Difference]: Finished difference Result 256 states and 325 transitions. [2022-02-23 22:35:53,260 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2022-02-23 22:35:53,260 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-02-23 22:35:53,260 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-02-23 22:35:53,261 INFO L225 Difference]: With dead ends: 256 [2022-02-23 22:35:53,261 INFO L226 Difference]: Without dead ends: 253 [2022-02-23 22:35:53,261 INFO L932 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-02-23 22:35:53,262 INFO L933 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-02-23 22:35:53,262 INFO L934 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-02-23 22:35:53,262 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 253 states. [2022-02-23 22:35:53,318 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 253 to 243. [2022-02-23 22:35:53,318 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-02-23 22:35:53,319 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 243 states to 243 states and 304 transitions. [2022-02-23 22:35:53,319 INFO L78 Accepts]: Start accepts. Automaton has 243 states and 304 transitions. Word has length 73 [2022-02-23 22:35:53,320 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-02-23 22:35:53,320 INFO L470 AbstractCegarLoop]: Abstraction has 243 states and 304 transitions. [2022-02-23 22:35:53,320 INFO L471 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-02-23 22:35:53,320 INFO L276 IsEmpty]: Start isEmpty. Operand 243 states and 304 transitions. [2022-02-23 22:35:53,320 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 79 [2022-02-23 22:35:53,320 INFO L506 BasicCegarLoop]: Found error trace [2022-02-23 22:35:53,320 INFO L514 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-02-23 22:35:53,365 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-02-23 22:35:53,521 WARN L452 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-02-23 22:35:53,521 INFO L402 AbstractCegarLoop]: === Iteration 14 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-02-23 22:35:53,521 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-02-23 22:35:53,521 INFO L85 PathProgramCache]: Analyzing trace with hash 952478412, now seen corresponding path program 3 times [2022-02-23 22:35:53,521 INFO L126 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-02-23 22:35:53,522 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1359871130] [2022-02-23 22:35:53,522 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-02-23 22:35:53,522 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-02-23 22:35:53,528 ERROR L252 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-02-23 22:35:53,528 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1725638105] [2022-02-23 22:35:53,528 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2022-02-23 22:35:53,528 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-02-23 22:35:53,528 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-02-23 22:35:53,529 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-02-23 22:35:53,530 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-02-23 22:35:53,574 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2022-02-23 22:35:53,574 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-02-23 22:35:53,575 INFO L263 TraceCheckSpWp]: Trace formula consists of 192 conjuncts, 40 conjunts are in the unsatisfiable core [2022-02-23 22:35:53,577 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-02-23 22:35:54,071 INFO L134 CoverageAnalysis]: Checked inductivity of 131 backedges. 31 proven. 10 refuted. 0 times theorem prover too weak. 90 trivial. 0 not checked. [2022-02-23 22:35:54,071 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-02-23 22:35:54,148 INFO L144 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-02-23 22:35:54,148 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1359871130] [2022-02-23 22:35:54,156 WARN L317 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-02-23 22:35:54,156 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1725638105] [2022-02-23 22:35:54,156 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1725638105] provided 0 perfect and 1 imperfect interpolant sequences [2022-02-23 22:35:54,157 INFO L191 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-02-23 22:35:54,157 INFO L204 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9] total 9 [2022-02-23 22:35:54,157 INFO L118 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [754314183] [2022-02-23 22:35:54,157 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2022-02-23 22:35:54,157 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2022-02-23 22:35:54,157 INFO L108 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-02-23 22:35:54,158 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2022-02-23 22:35:54,158 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=23, Invalid=87, Unknown=0, NotChecked=0, Total=110 [2022-02-23 22:35:54,158 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-02-23 22:35:54,410 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-02-23 22:35:54,411 INFO L93 Difference]: Finished difference Result 266 states and 331 transitions. [2022-02-23 22:35:54,423 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2022-02-23 22:35:54,423 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-02-23 22:35:54,424 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-02-23 22:35:54,426 INFO L225 Difference]: With dead ends: 266 [2022-02-23 22:35:54,426 INFO L226 Difference]: Without dead ends: 262 [2022-02-23 22:35:54,427 INFO L932 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-02-23 22:35:54,427 INFO L933 BasicCegarLoop]: 42 mSDtfsCounter, 24 mSDsluCounter, 207 mSDsCounter, 0 mSdLazyCounter, 190 mSolverCounterSat, 18 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s 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-02-23 22:35:54,427 INFO L934 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-02-23 22:35:54,428 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 262 states. [2022-02-23 22:35:54,449 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 262 to 260. [2022-02-23 22:35:54,450 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-02-23 22:35:54,453 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 260 states to 260 states and 324 transitions. [2022-02-23 22:35:54,453 INFO L78 Accepts]: Start accepts. Automaton has 260 states and 324 transitions. Word has length 78 [2022-02-23 22:35:54,453 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-02-23 22:35:54,454 INFO L470 AbstractCegarLoop]: Abstraction has 260 states and 324 transitions. [2022-02-23 22:35:54,454 INFO L471 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-02-23 22:35:54,454 INFO L276 IsEmpty]: Start isEmpty. Operand 260 states and 324 transitions. [2022-02-23 22:35:54,455 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 85 [2022-02-23 22:35:54,455 INFO L506 BasicCegarLoop]: Found error trace [2022-02-23 22:35:54,455 INFO L514 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-02-23 22:35:54,472 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-02-23 22:35:54,672 WARN L452 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-02-23 22:35:54,672 INFO L402 AbstractCegarLoop]: === Iteration 15 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-02-23 22:35:54,673 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-02-23 22:35:54,673 INFO L85 PathProgramCache]: Analyzing trace with hash 900405455, now seen corresponding path program 1 times [2022-02-23 22:35:54,673 INFO L126 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-02-23 22:35:54,673 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [654000098] [2022-02-23 22:35:54,673 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-02-23 22:35:54,673 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-02-23 22:35:54,693 ERROR L252 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-02-23 22:35:54,693 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [959471841] [2022-02-23 22:35:54,693 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-02-23 22:35:54,693 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-02-23 22:35:54,693 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-02-23 22:35:54,701 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-02-23 22:35:54,702 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-02-23 22:35:54,773 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-02-23 22:35:54,774 INFO L263 TraceCheckSpWp]: Trace formula consists of 239 conjuncts, 42 conjunts are in the unsatisfiable core [2022-02-23 22:35:54,776 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-02-23 22:35:55,261 INFO L134 CoverageAnalysis]: Checked inductivity of 162 backedges. 30 proven. 17 refuted. 0 times theorem prover too weak. 115 trivial. 0 not checked. [2022-02-23 22:35:55,261 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-02-23 22:35:55,739 INFO L134 CoverageAnalysis]: Checked inductivity of 162 backedges. 30 proven. 17 refuted. 0 times theorem prover too weak. 115 trivial. 0 not checked. [2022-02-23 22:35:55,740 INFO L144 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-02-23 22:35:55,740 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [654000098] [2022-02-23 22:35:55,740 WARN L317 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-02-23 22:35:55,740 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [959471841] [2022-02-23 22:35:55,740 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleZ3 [959471841] provided 0 perfect and 2 imperfect interpolant sequences [2022-02-23 22:35:55,740 INFO L191 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-02-23 22:35:55,740 INFO L204 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 12] total 19 [2022-02-23 22:35:55,740 INFO L118 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1059942671] [2022-02-23 22:35:55,740 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-02-23 22:35:55,740 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 19 states [2022-02-23 22:35:55,741 INFO L108 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-02-23 22:35:55,741 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 19 interpolants. [2022-02-23 22:35:55,741 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=58, Invalid=284, Unknown=0, NotChecked=0, Total=342 [2022-02-23 22:35:55,741 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-02-23 22:35:58,499 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-02-23 22:36:00,129 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-02-23 22:36:00,129 INFO L93 Difference]: Finished difference Result 327 states and 422 transitions. [2022-02-23 22:36:00,129 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 26 states. [2022-02-23 22:36:00,129 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-02-23 22:36:00,129 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-02-23 22:36:00,137 INFO L225 Difference]: With dead ends: 327 [2022-02-23 22:36:00,137 INFO L226 Difference]: Without dead ends: 317 [2022-02-23 22:36:00,139 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 185 GetRequests, 149 SyntacticMatches, 1 SemanticMatches, 35 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 233 ImplicationChecksByTransitivity, 0.8s TimeCoverageRelationStatistics Valid=248, Invalid=1084, Unknown=0, NotChecked=0, Total=1332 [2022-02-23 22:36:00,140 INFO L933 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.7s IncrementalHoareTripleChecker+Time [2022-02-23 22:36:00,141 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [101 Valid, 418 Invalid, 657 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [169 Valid, 487 Invalid, 1 Unknown, 0 Unchecked, 3.7s Time] [2022-02-23 22:36:00,142 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 317 states. [2022-02-23 22:36:00,212 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 317 to 301. [2022-02-23 22:36:00,213 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-02-23 22:36:00,214 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 301 states to 301 states and 391 transitions. [2022-02-23 22:36:00,214 INFO L78 Accepts]: Start accepts. Automaton has 301 states and 391 transitions. Word has length 84 [2022-02-23 22:36:00,214 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-02-23 22:36:00,214 INFO L470 AbstractCegarLoop]: Abstraction has 301 states and 391 transitions. [2022-02-23 22:36:00,214 INFO L471 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-02-23 22:36:00,214 INFO L276 IsEmpty]: Start isEmpty. Operand 301 states and 391 transitions. [2022-02-23 22:36:00,223 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 94 [2022-02-23 22:36:00,223 INFO L506 BasicCegarLoop]: Found error trace [2022-02-23 22:36:00,223 INFO L514 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-02-23 22:36:00,255 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-02-23 22:36:00,455 WARN L452 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-02-23 22:36:00,456 INFO L402 AbstractCegarLoop]: === Iteration 16 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-02-23 22:36:00,456 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-02-23 22:36:00,456 INFO L85 PathProgramCache]: Analyzing trace with hash 1881160278, now seen corresponding path program 1 times [2022-02-23 22:36:00,456 INFO L126 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-02-23 22:36:00,456 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [129173784] [2022-02-23 22:36:00,456 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-02-23 22:36:00,457 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-02-23 22:36:00,464 ERROR L252 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-02-23 22:36:00,464 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [771753015] [2022-02-23 22:36:00,464 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-02-23 22:36:00,464 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-02-23 22:36:00,464 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-02-23 22:36:00,482 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-02-23 22:36:00,517 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-02-23 22:36:00,561 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-02-23 22:36:00,562 INFO L263 TraceCheckSpWp]: Trace formula consists of 286 conjuncts, 5 conjunts are in the unsatisfiable core [2022-02-23 22:36:00,563 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-02-23 22:36:00,697 INFO L134 CoverageAnalysis]: Checked inductivity of 181 backedges. 42 proven. 0 refuted. 0 times theorem prover too weak. 139 trivial. 0 not checked. [2022-02-23 22:36:00,697 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-02-23 22:36:00,697 INFO L144 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-02-23 22:36:00,697 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [129173784] [2022-02-23 22:36:00,697 WARN L317 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-02-23 22:36:00,697 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [771753015] [2022-02-23 22:36:00,697 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleZ3 [771753015] provided 1 perfect and 0 imperfect interpolant sequences [2022-02-23 22:36:00,697 INFO L191 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-02-23 22:36:00,697 INFO L204 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-02-23 22:36:00,698 INFO L118 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [5077216] [2022-02-23 22:36:00,698 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-02-23 22:36:00,699 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-02-23 22:36:00,699 INFO L108 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-02-23 22:36:00,699 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-02-23 22:36:00,699 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-02-23 22:36:00,699 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-02-23 22:36:00,807 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-02-23 22:36:00,807 INFO L93 Difference]: Finished difference Result 470 states and 653 transitions. [2022-02-23 22:36:00,807 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2022-02-23 22:36:00,807 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-02-23 22:36:00,808 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-02-23 22:36:00,817 INFO L225 Difference]: With dead ends: 470 [2022-02-23 22:36:00,817 INFO L226 Difference]: Without dead ends: 358 [2022-02-23 22:36:00,818 INFO L932 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-02-23 22:36:00,818 INFO L933 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-02-23 22:36:00,818 INFO L934 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-02-23 22:36:00,819 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 358 states. [2022-02-23 22:36:00,849 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 358 to 327. [2022-02-23 22:36:00,850 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-02-23 22:36:00,851 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 327 states to 327 states and 432 transitions. [2022-02-23 22:36:00,851 INFO L78 Accepts]: Start accepts. Automaton has 327 states and 432 transitions. Word has length 93 [2022-02-23 22:36:00,851 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-02-23 22:36:00,852 INFO L470 AbstractCegarLoop]: Abstraction has 327 states and 432 transitions. [2022-02-23 22:36:00,852 INFO L471 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-02-23 22:36:00,852 INFO L276 IsEmpty]: Start isEmpty. Operand 327 states and 432 transitions. [2022-02-23 22:36:00,852 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 102 [2022-02-23 22:36:00,852 INFO L506 BasicCegarLoop]: Found error trace [2022-02-23 22:36:00,853 INFO L514 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-02-23 22:36:00,869 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Ended with exit code 0 [2022-02-23 22:36:01,065 WARN L452 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-02-23 22:36:01,066 INFO L402 AbstractCegarLoop]: === Iteration 17 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-02-23 22:36:01,066 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-02-23 22:36:01,066 INFO L85 PathProgramCache]: Analyzing trace with hash 653404933, now seen corresponding path program 1 times [2022-02-23 22:36:01,066 INFO L126 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-02-23 22:36:01,066 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [233529397] [2022-02-23 22:36:01,066 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-02-23 22:36:01,066 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-02-23 22:36:01,072 ERROR L252 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-02-23 22:36:01,072 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1296836022] [2022-02-23 22:36:01,072 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-02-23 22:36:01,072 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-02-23 22:36:01,072 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-02-23 22:36:01,073 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-02-23 22:36:01,074 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-02-23 22:36:01,129 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-02-23 22:36:01,131 INFO L263 TraceCheckSpWp]: Trace formula consists of 274 conjuncts, 41 conjunts are in the unsatisfiable core [2022-02-23 22:36:01,133 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-02-23 22:36:02,036 INFO L134 CoverageAnalysis]: Checked inductivity of 288 backedges. 51 proven. 23 refuted. 0 times theorem prover too weak. 214 trivial. 0 not checked. [2022-02-23 22:36:02,036 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-02-23 22:36:02,280 WARN L907 QuantifierPusher]: no eliminatee completely removed, nonetheless the elimination was considered successful [2022-02-23 22:36:06,993 INFO L144 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-02-23 22:36:06,993 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [233529397] [2022-02-23 22:36:06,993 WARN L317 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-02-23 22:36:06,993 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1296836022] [2022-02-23 22:36:06,993 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1296836022] provided 0 perfect and 1 imperfect interpolant sequences [2022-02-23 22:36:06,993 INFO L191 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-02-23 22:36:06,993 INFO L204 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11] total 11 [2022-02-23 22:36:06,993 INFO L118 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [706876712] [2022-02-23 22:36:06,993 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2022-02-23 22:36:06,994 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 11 states [2022-02-23 22:36:06,994 INFO L108 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-02-23 22:36:06,994 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2022-02-23 22:36:06,994 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=44, Invalid=164, Unknown=2, NotChecked=0, Total=210 [2022-02-23 22:36:06,994 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-02-23 22:36:07,415 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-02-23 22:36:07,415 INFO L93 Difference]: Finished difference Result 339 states and 442 transitions. [2022-02-23 22:36:07,415 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2022-02-23 22:36:07,415 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-02-23 22:36:07,416 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-02-23 22:36:07,417 INFO L225 Difference]: With dead ends: 339 [2022-02-23 22:36:07,417 INFO L226 Difference]: Without dead ends: 337 [2022-02-23 22:36:07,418 INFO L932 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-02-23 22:36:07,418 INFO L933 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.3s IncrementalHoareTripleChecker+Time [2022-02-23 22:36:07,418 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [41 Valid, 361 Invalid, 333 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [29 Valid, 304 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2022-02-23 22:36:07,419 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 337 states. [2022-02-23 22:36:07,465 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 337 to 335. [2022-02-23 22:36:07,466 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-02-23 22:36:07,467 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 335 states to 335 states and 438 transitions. [2022-02-23 22:36:07,467 INFO L78 Accepts]: Start accepts. Automaton has 335 states and 438 transitions. Word has length 101 [2022-02-23 22:36:07,467 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-02-23 22:36:07,467 INFO L470 AbstractCegarLoop]: Abstraction has 335 states and 438 transitions. [2022-02-23 22:36:07,467 INFO L471 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-02-23 22:36:07,468 INFO L276 IsEmpty]: Start isEmpty. Operand 335 states and 438 transitions. [2022-02-23 22:36:07,468 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 111 [2022-02-23 22:36:07,468 INFO L506 BasicCegarLoop]: Found error trace [2022-02-23 22:36:07,468 INFO L514 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-02-23 22:36:07,499 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (18)] Forceful destruction successful, exit code 0 [2022-02-23 22:36:07,702 WARN L452 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-02-23 22:36:07,703 INFO L402 AbstractCegarLoop]: === Iteration 18 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-02-23 22:36:07,703 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-02-23 22:36:07,703 INFO L85 PathProgramCache]: Analyzing trace with hash -1392800366, now seen corresponding path program 1 times [2022-02-23 22:36:07,703 INFO L126 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-02-23 22:36:07,703 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2047533912] [2022-02-23 22:36:07,703 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-02-23 22:36:07,703 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-02-23 22:36:07,711 ERROR L252 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-02-23 22:36:07,711 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [422366684] [2022-02-23 22:36:07,711 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-02-23 22:36:07,711 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-02-23 22:36:07,711 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-02-23 22:36:07,728 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-02-23 22:36:07,729 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-02-23 22:36:07,782 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2022-02-23 22:36:07,782 INFO L352 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2022-02-23 22:36:07,807 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2022-02-23 22:36:07,849 INFO L138 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2022-02-23 22:36:07,850 INFO L628 BasicCegarLoop]: Counterexample is feasible [2022-02-23 22:36:07,850 INFO L764 garLoopResultBuilder]: Registering result UNSAFE for location __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION (0 of 1 remaining) [2022-02-23 22:36:07,902 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-02-23 22:36:08,052 WARN L452 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-02-23 22:36:08,055 INFO L732 BasicCegarLoop]: Path program histogram: [3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-02-23 22:36:08,057 INFO L180 ceAbstractionStarter]: Computing trace abstraction results [2022-02-23 22:36:08,099 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 23.02 10:36:08 BasicIcfg [2022-02-23 22:36:08,099 INFO L132 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2022-02-23 22:36:08,099 INFO L158 Benchmark]: Toolchain (without parser) took 26085.32ms. Allocated memory was 199.2MB in the beginning and 294.6MB in the end (delta: 95.4MB). Free memory was 144.7MB in the beginning and 216.0MB in the end (delta: -71.3MB). Peak memory consumption was 23.5MB. Max. memory is 8.0GB. [2022-02-23 22:36:08,099 INFO L158 Benchmark]: CDTParser took 0.10ms. Allocated memory is still 199.2MB. Free memory was 161.0MB in the beginning and 160.9MB in the end (delta: 74.9kB). There was no memory consumed. Max. memory is 8.0GB. [2022-02-23 22:36:08,100 INFO L158 Benchmark]: CACSL2BoogieTranslator took 220.68ms. Allocated memory is still 199.2MB. Free memory was 144.5MB in the beginning and 171.1MB in the end (delta: -26.6MB). Peak memory consumption was 11.5MB. Max. memory is 8.0GB. [2022-02-23 22:36:08,100 INFO L158 Benchmark]: Boogie Preprocessor took 27.26ms. Allocated memory is still 199.2MB. Free memory was 171.1MB in the beginning and 169.4MB in the end (delta: 1.8MB). Peak memory consumption was 2.1MB. Max. memory is 8.0GB. [2022-02-23 22:36:08,100 INFO L158 Benchmark]: RCFGBuilder took 259.43ms. Allocated memory is still 199.2MB. Free memory was 169.4MB in the beginning and 157.0MB in the end (delta: 12.4MB). Peak memory consumption was 12.6MB. Max. memory is 8.0GB. [2022-02-23 22:36:08,100 INFO L158 Benchmark]: IcfgTransformer took 17.74ms. Allocated memory is still 199.2MB. Free memory was 157.0MB in the beginning and 155.4MB in the end (delta: 1.6MB). Peak memory consumption was 1.0MB. Max. memory is 8.0GB. [2022-02-23 22:36:08,100 INFO L158 Benchmark]: TraceAbstraction took 25553.47ms. Allocated memory was 199.2MB in the beginning and 294.6MB in the end (delta: 95.4MB). Free memory was 154.9MB in the beginning and 216.0MB in the end (delta: -61.1MB). Peak memory consumption was 34.8MB. Max. memory is 8.0GB. [2022-02-23 22:36:08,101 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.10ms. Allocated memory is still 199.2MB. Free memory was 161.0MB in the beginning and 160.9MB in the end (delta: 74.9kB). There was no memory consumed. Max. memory is 8.0GB. * CACSL2BoogieTranslator took 220.68ms. Allocated memory is still 199.2MB. Free memory was 144.5MB in the beginning and 171.1MB in the end (delta: -26.6MB). Peak memory consumption was 11.5MB. Max. memory is 8.0GB. * Boogie Preprocessor took 27.26ms. Allocated memory is still 199.2MB. Free memory was 171.1MB in the beginning and 169.4MB in the end (delta: 1.8MB). Peak memory consumption was 2.1MB. Max. memory is 8.0GB. * RCFGBuilder took 259.43ms. Allocated memory is still 199.2MB. Free memory was 169.4MB in the beginning and 157.0MB in the end (delta: 12.4MB). Peak memory consumption was 12.6MB. Max. memory is 8.0GB. * IcfgTransformer took 17.74ms. Allocated memory is still 199.2MB. Free memory was 157.0MB in the beginning and 155.4MB in the end (delta: 1.6MB). Peak memory consumption was 1.0MB. Max. memory is 8.0GB. * TraceAbstraction took 25553.47ms. Allocated memory was 199.2MB in the beginning and 294.6MB in the end (delta: 95.4MB). Free memory was 154.9MB in the beginning and 216.0MB in the end (delta: -61.1MB). Peak memory consumption was 34.8MB. 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: 25.5s, OverallIterations: 18, TraceHistogramMax: 13, PathProgramHistogramMax: 3, EmptinessCheckTime: 0.0s, AutomataDifference: 9.0s, DeadEndRemovalTime: 0.0s, HoareAnnotationTime: 0.0s, InitialAbstractionConstructionTime: 0.0s, PartialOrderReductionTime: 0.0s, HoareTripleCheckerStatistics: 2 mSolverCounterUnknown, 609 SdHoareTripleChecker+Valid, 7.4s IncrementalHoareTripleChecker+Time, 0 mSdLazyCounter, 561 mSDsluCounter, 3614 SdHoareTripleChecker+Invalid, 7.1s 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.4s AutomataMinimizationTime, 17 MinimizatonAttempts, 132 StatesRemovedByMinimization, 13 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TRACE_CHECK: 0.1s SsaConstructionTime, 0.6s SatisfiabilityAnalysisTime, 10.7s 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-02-23 22:36:08,115 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...