/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/AutomizerC.xml -s ../../../trunk/examples/settings/default/automizer/svcomp-Reach-32bit-Automizer_Default.epf -i ../../../trunk/examples/svcomp/nla-digbench-scaling/hard2_unwindbound100.c -------------------------------------------------------------------------------- This is Ultimate 0.2.2-dev-5d317bd [2022-03-18 14:55:23,211 INFO L177 SettingsManager]: Resetting all preferences to default values... [2022-03-18 14:55:23,213 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2022-03-18 14:55:23,259 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2022-03-18 14:55:23,260 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2022-03-18 14:55:23,261 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2022-03-18 14:55:23,268 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2022-03-18 14:55:23,271 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2022-03-18 14:55:23,273 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2022-03-18 14:55:23,277 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2022-03-18 14:55:23,278 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2022-03-18 14:55:23,279 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2022-03-18 14:55:23,279 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2022-03-18 14:55:23,281 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2022-03-18 14:55:23,282 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2022-03-18 14:55:23,285 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2022-03-18 14:55:23,285 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2022-03-18 14:55:23,286 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2022-03-18 14:55:23,288 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2022-03-18 14:55:23,293 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2022-03-18 14:55:23,295 INFO L181 SettingsManager]: Resetting HornVerifier preferences to default values [2022-03-18 14:55:23,297 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2022-03-18 14:55:23,297 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2022-03-18 14:55:23,298 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2022-03-18 14:55:23,300 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2022-03-18 14:55:23,305 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2022-03-18 14:55:23,306 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2022-03-18 14:55:23,306 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2022-03-18 14:55:23,307 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2022-03-18 14:55:23,307 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2022-03-18 14:55:23,309 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2022-03-18 14:55:23,309 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2022-03-18 14:55:23,311 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2022-03-18 14:55:23,311 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2022-03-18 14:55:23,312 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2022-03-18 14:55:23,312 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2022-03-18 14:55:23,313 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2022-03-18 14:55:23,313 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2022-03-18 14:55:23,314 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2022-03-18 14:55:23,314 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2022-03-18 14:55:23,314 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2022-03-18 14:55:23,316 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2022-03-18 14:55:23,316 INFO L101 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/default/automizer/svcomp-Reach-32bit-Automizer_Default.epf [2022-03-18 14:55:23,348 INFO L113 SettingsManager]: Loading preferences was successful [2022-03-18 14:55:23,348 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2022-03-18 14:55:23,349 INFO L136 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2022-03-18 14:55:23,349 INFO L138 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2022-03-18 14:55:23,350 INFO L136 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2022-03-18 14:55:23,350 INFO L138 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2022-03-18 14:55:23,351 INFO L136 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2022-03-18 14:55:23,351 INFO L138 SettingsManager]: * Create parallel compositions if possible=false [2022-03-18 14:55:23,351 INFO L138 SettingsManager]: * Use SBE=true [2022-03-18 14:55:23,352 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2022-03-18 14:55:23,352 INFO L138 SettingsManager]: * sizeof long=4 [2022-03-18 14:55:23,353 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2022-03-18 14:55:23,353 INFO L138 SettingsManager]: * sizeof POINTER=4 [2022-03-18 14:55:23,353 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2022-03-18 14:55:23,353 INFO L138 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2022-03-18 14:55:23,353 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2022-03-18 14:55:23,353 INFO L138 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2022-03-18 14:55:23,354 INFO L138 SettingsManager]: * sizeof long double=12 [2022-03-18 14:55:23,355 INFO L138 SettingsManager]: * Check if freed pointer was valid=false [2022-03-18 14:55:23,355 INFO L138 SettingsManager]: * Use constant arrays=true [2022-03-18 14:55:23,355 INFO L138 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2022-03-18 14:55:23,355 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2022-03-18 14:55:23,356 INFO L138 SettingsManager]: * Size of a code block=SequenceOfStatements [2022-03-18 14:55:23,356 INFO L138 SettingsManager]: * SMT solver=External_DefaultMode [2022-03-18 14:55:23,356 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-03-18 14:55:23,356 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2022-03-18 14:55:23,356 INFO L138 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2022-03-18 14:55:23,357 INFO L138 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2022-03-18 14:55:23,357 INFO L138 SettingsManager]: * Trace refinement strategy=CAMEL [2022-03-18 14:55:23,357 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2022-03-18 14:55:23,357 INFO L138 SettingsManager]: * Large block encoding in concurrent analysis=OFF [2022-03-18 14:55:23,357 INFO L138 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2022-03-18 14:55:23,357 INFO L138 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2022-03-18 14:55:23,358 INFO L138 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode WARNING: An illegal reflective access operation has occurred WARNING: Illegal reflective access by com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 (file:/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/com.sun.xml.bind_2.2.0.v201505121915.jar) to method java.lang.ClassLoader.defineClass(java.lang.String,byte[],int,int) WARNING: Please consider reporting this to the maintainers of com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 WARNING: Use --illegal-access=warn to enable warnings of further illegal reflective access operations WARNING: All illegal access operations will be denied in a future release Applying setting for plugin de.uni_freiburg.informatik.ultimate.core: Log level for class -> de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=WARN; [2022-03-18 14:55:23,596 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2022-03-18 14:55:23,614 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2022-03-18 14:55:23,616 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2022-03-18 14:55:23,617 INFO L271 PluginConnector]: Initializing CDTParser... [2022-03-18 14:55:23,619 INFO L275 PluginConnector]: CDTParser initialized [2022-03-18 14:55:23,620 INFO L432 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/svcomp/nla-digbench-scaling/hard2_unwindbound100.c [2022-03-18 14:55:23,684 INFO L220 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/9c504bb9c/95c1b3eae8b347ae9afc857b318f0184/FLAG4b5276b4d [2022-03-18 14:55:24,073 INFO L306 CDTParser]: Found 1 translation units. [2022-03-18 14:55:24,073 INFO L160 CDTParser]: Scanning /storage/repos/ultimate/trunk/examples/svcomp/nla-digbench-scaling/hard2_unwindbound100.c [2022-03-18 14:55:24,082 INFO L349 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/9c504bb9c/95c1b3eae8b347ae9afc857b318f0184/FLAG4b5276b4d [2022-03-18 14:55:24,496 INFO L357 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/9c504bb9c/95c1b3eae8b347ae9afc857b318f0184 [2022-03-18 14:55:24,498 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2022-03-18 14:55:24,499 INFO L131 ToolchainWalker]: Walking toolchain with 4 elements. [2022-03-18 14:55:24,504 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2022-03-18 14:55:24,504 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2022-03-18 14:55:24,507 INFO L275 PluginConnector]: CACSL2BoogieTranslator initialized [2022-03-18 14:55:24,507 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 18.03 02:55:24" (1/1) ... [2022-03-18 14:55:24,508 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@7e1c971d and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.03 02:55:24, skipping insertion in model container [2022-03-18 14:55:24,508 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 18.03 02:55:24" (1/1) ... [2022-03-18 14:55:24,514 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2022-03-18 14:55:24,531 INFO L178 MainTranslator]: Built tables and reachable declarations [2022-03-18 14:55:24,671 WARN L230 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/trunk/examples/svcomp/nla-digbench-scaling/hard2_unwindbound100.c[526,539] [2022-03-18 14:55:24,686 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-03-18 14:55:24,693 INFO L203 MainTranslator]: Completed pre-run [2022-03-18 14:55:24,708 WARN L230 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/trunk/examples/svcomp/nla-digbench-scaling/hard2_unwindbound100.c[526,539] [2022-03-18 14:55:24,726 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-03-18 14:55:24,744 INFO L208 MainTranslator]: Completed translation [2022-03-18 14:55:24,745 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.03 02:55:24 WrapperNode [2022-03-18 14:55:24,745 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2022-03-18 14:55:24,746 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2022-03-18 14:55:24,746 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2022-03-18 14:55:24,747 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2022-03-18 14:55:24,755 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.03 02:55:24" (1/1) ... [2022-03-18 14:55:24,756 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.03 02:55:24" (1/1) ... [2022-03-18 14:55:24,762 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.03 02:55:24" (1/1) ... [2022-03-18 14:55:24,762 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.03 02:55:24" (1/1) ... [2022-03-18 14:55:24,766 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.03 02:55:24" (1/1) ... [2022-03-18 14:55:24,770 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.03 02:55:24" (1/1) ... [2022-03-18 14:55:24,771 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.03 02:55:24" (1/1) ... [2022-03-18 14:55:24,772 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2022-03-18 14:55:24,773 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2022-03-18 14:55:24,773 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2022-03-18 14:55:24,773 INFO L275 PluginConnector]: RCFGBuilder initialized [2022-03-18 14:55:24,774 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.03 02:55:24" (1/1) ... [2022-03-18 14:55:24,788 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-03-18 14:55:24,801 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-18 14:55:24,821 INFO L229 MonitoredProcess]: Starting monitored process 1 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) [2022-03-18 14:55:24,848 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Waiting until timeout for monitored process [2022-03-18 14:55:24,870 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.init [2022-03-18 14:55:24,871 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2022-03-18 14:55:24,871 INFO L138 BoogieDeclarations]: Found implementation of procedure reach_error [2022-03-18 14:55:24,871 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2022-03-18 14:55:24,872 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2022-03-18 14:55:24,872 INFO L138 BoogieDeclarations]: Found implementation of procedure main [2022-03-18 14:55:24,872 INFO L130 BoogieDeclarations]: Found specification of procedure abort [2022-03-18 14:55:24,872 INFO L130 BoogieDeclarations]: Found specification of procedure __assert_fail [2022-03-18 14:55:24,872 INFO L130 BoogieDeclarations]: Found specification of procedure reach_error [2022-03-18 14:55:24,872 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2022-03-18 14:55:24,873 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_nondet_int [2022-03-18 14:55:24,873 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2022-03-18 14:55:24,873 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2022-03-18 14:55:24,873 INFO L130 BoogieDeclarations]: Found specification of procedure main [2022-03-18 14:55:24,873 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.init [2022-03-18 14:55:24,873 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2022-03-18 14:55:24,873 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2022-03-18 14:55:24,873 INFO L130 BoogieDeclarations]: Found specification of procedure write~int [2022-03-18 14:55:24,873 INFO L130 BoogieDeclarations]: Found specification of procedure read~int [2022-03-18 14:55:24,873 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2022-03-18 14:55:24,940 INFO L234 CfgBuilder]: Building ICFG [2022-03-18 14:55:24,941 INFO L260 CfgBuilder]: Building CFG for each procedure with an implementation [2022-03-18 14:55:25,051 INFO L275 CfgBuilder]: Performing block encoding [2022-03-18 14:55:25,057 INFO L294 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2022-03-18 14:55:25,057 INFO L299 CfgBuilder]: Removed 2 assume(true) statements. [2022-03-18 14:55:25,059 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 18.03 02:55:25 BoogieIcfgContainer [2022-03-18 14:55:25,059 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2022-03-18 14:55:25,060 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2022-03-18 14:55:25,060 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2022-03-18 14:55:25,064 INFO L275 PluginConnector]: TraceAbstraction initialized [2022-03-18 14:55:25,064 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 18.03 02:55:24" (1/3) ... [2022-03-18 14:55:25,065 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@c95885c and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 18.03 02:55:25, skipping insertion in model container [2022-03-18 14:55:25,065 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.03 02:55:24" (2/3) ... [2022-03-18 14:55:25,065 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@c95885c and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 18.03 02:55:25, skipping insertion in model container [2022-03-18 14:55:25,065 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 18.03 02:55:25" (3/3) ... [2022-03-18 14:55:25,066 INFO L111 eAbstractionObserver]: Analyzing ICFG hard2_unwindbound100.c [2022-03-18 14:55:25,071 INFO L205 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2022-03-18 14:55:25,071 INFO L164 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2022-03-18 14:55:25,109 INFO L339 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2022-03-18 14:55:25,127 INFO L340 AbstractCegarLoop]: Settings: SEPARATE_VIOLATION_CHECK=true, mInterprocedural=true, mMaxIterations=1000000, mWatchIteration=1000000, mArtifact=RCFG, mInterpolation=FPandBP, mInterpolantAutomaton=STRAIGHT_LINE, mDumpAutomata=false, mAutomataFormat=ATS_NUMERATE, mDumpPath=., mDeterminiation=PREDICATE_ABSTRACTION, mMinimize=MINIMIZE_SEVPA, mHoare=true, mAutomataTypeConcurrency=PETRI_NET, mHoareTripleChecks=INCREMENTAL, mHoareAnnotationPositions=LoopsAndPotentialCycles, mDumpOnlyReuseAutomata=false, mLimitTraceHistogram=0, mErrorLocTimeLimit=0, mLimitPathProgramCount=0, mCollectInterpolantStatistics=true, mHeuristicEmptinessCheck=false, mHeuristicEmptinessCheckAStarHeuristic=ZERO, mHeuristicEmptinessCheckAStarHeuristicRandomSeed=1337, mHeuristicEmptinessCheckSmtFeatureScoringMethod=DAGSIZE, mSMTFeatureExtraction=false, mSMTFeatureExtractionDumpPath=., mOverrideInterpolantAutomaton=false, mMcrInterpolantMethod=WP [2022-03-18 14:55:25,127 INFO L341 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2022-03-18 14:55:25,167 INFO L276 IsEmpty]: Start isEmpty. Operand has 31 states, 17 states have (on average 1.5294117647058822) internal successors, (26), 18 states have internal predecessors, (26), 9 states have call successors, (9), 3 states have call predecessors, (9), 3 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2022-03-18 14:55:25,172 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 13 [2022-03-18 14:55:25,173 INFO L492 BasicCegarLoop]: Found error trace [2022-03-18 14:55:25,173 INFO L500 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-18 14:55:25,174 INFO L403 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-18 14:55:25,179 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-18 14:55:25,179 INFO L85 PathProgramCache]: Analyzing trace with hash -1682617676, now seen corresponding path program 1 times [2022-03-18 14:55:25,186 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-18 14:55:25,187 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [219592837] [2022-03-18 14:55:25,187 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-18 14:55:25,188 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-18 14:55:25,261 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-18 14:55:25,312 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-03-18 14:55:25,316 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-18 14:55:25,335 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-03-18 14:55:25,335 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-18 14:55:25,336 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [219592837] [2022-03-18 14:55:25,336 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [219592837] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-18 14:55:25,336 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-18 14:55:25,337 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2022-03-18 14:55:25,338 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1042766908] [2022-03-18 14:55:25,339 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-18 14:55:25,342 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2022-03-18 14:55:25,343 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-18 14:55:25,367 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2022-03-18 14:55:25,368 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2022-03-18 14:55:25,370 INFO L87 Difference]: Start difference. First operand has 31 states, 17 states have (on average 1.5294117647058822) internal successors, (26), 18 states have internal predecessors, (26), 9 states have call successors, (9), 3 states have call predecessors, (9), 3 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) Second operand has 3 states, 3 states have (on average 2.6666666666666665) internal successors, (8), 2 states have internal predecessors, (8), 2 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-03-18 14:55:25,449 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-18 14:55:25,449 INFO L93 Difference]: Finished difference Result 57 states and 91 transitions. [2022-03-18 14:55:25,455 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2022-03-18 14:55:25,457 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 2.6666666666666665) internal successors, (8), 2 states have internal predecessors, (8), 2 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 12 [2022-03-18 14:55:25,457 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-18 14:55:25,464 INFO L225 Difference]: With dead ends: 57 [2022-03-18 14:55:25,464 INFO L226 Difference]: Without dead ends: 27 [2022-03-18 14:55:25,467 INFO L911 BasicCegarLoop]: 0 DeclaredPredicates, 4 GetRequests, 3 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2022-03-18 14:55:25,470 INFO L912 BasicCegarLoop]: 40 mSDtfsCounter, 6 mSDsluCounter, 4 mSDsCounter, 0 mSdLazyCounter, 23 mSolverCounterSat, 8 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 6 SdHoareTripleChecker+Valid, 44 SdHoareTripleChecker+Invalid, 31 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 8 IncrementalHoareTripleChecker+Valid, 23 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-03-18 14:55:25,471 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [6 Valid, 44 Invalid, 31 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [8 Valid, 23 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-03-18 14:55:25,484 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 27 states. [2022-03-18 14:55:25,502 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 27 to 26. [2022-03-18 14:55:25,503 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 26 states, 14 states have (on average 1.4285714285714286) internal successors, (20), 15 states have internal predecessors, (20), 9 states have call successors, (9), 3 states have call predecessors, (9), 2 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2022-03-18 14:55:25,507 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 26 states to 26 states and 36 transitions. [2022-03-18 14:55:25,509 INFO L78 Accepts]: Start accepts. Automaton has 26 states and 36 transitions. Word has length 12 [2022-03-18 14:55:25,509 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-18 14:55:25,509 INFO L478 AbstractCegarLoop]: Abstraction has 26 states and 36 transitions. [2022-03-18 14:55:25,509 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 2.6666666666666665) internal successors, (8), 2 states have internal predecessors, (8), 2 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-03-18 14:55:25,510 INFO L276 IsEmpty]: Start isEmpty. Operand 26 states and 36 transitions. [2022-03-18 14:55:25,510 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 13 [2022-03-18 14:55:25,510 INFO L492 BasicCegarLoop]: Found error trace [2022-03-18 14:55:25,510 INFO L500 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-18 14:55:25,511 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2022-03-18 14:55:25,511 INFO L403 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-18 14:55:25,512 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-18 14:55:25,512 INFO L85 PathProgramCache]: Analyzing trace with hash -2144676086, now seen corresponding path program 1 times [2022-03-18 14:55:25,512 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-18 14:55:25,512 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1165710723] [2022-03-18 14:55:25,512 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-18 14:55:25,512 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-18 14:55:25,537 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-18 14:55:25,593 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-03-18 14:55:25,596 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-18 14:55:25,603 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-03-18 14:55:25,604 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-18 14:55:25,604 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1165710723] [2022-03-18 14:55:25,604 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1165710723] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-18 14:55:25,604 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-18 14:55:25,604 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2022-03-18 14:55:25,604 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [339571908] [2022-03-18 14:55:25,605 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-18 14:55:25,606 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2022-03-18 14:55:25,606 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-18 14:55:25,606 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2022-03-18 14:55:25,607 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2022-03-18 14:55:25,607 INFO L87 Difference]: Start difference. First operand 26 states and 36 transitions. Second operand has 6 states, 6 states have (on average 1.3333333333333333) internal successors, (8), 4 states have internal predecessors, (8), 2 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-03-18 14:55:25,756 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-18 14:55:25,756 INFO L93 Difference]: Finished difference Result 41 states and 56 transitions. [2022-03-18 14:55:25,756 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2022-03-18 14:55:25,757 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 1.3333333333333333) internal successors, (8), 4 states have internal predecessors, (8), 2 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 12 [2022-03-18 14:55:25,757 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-18 14:55:25,758 INFO L225 Difference]: With dead ends: 41 [2022-03-18 14:55:25,758 INFO L226 Difference]: Without dead ends: 39 [2022-03-18 14:55:25,759 INFO L911 BasicCegarLoop]: 0 DeclaredPredicates, 11 GetRequests, 3 SyntacticMatches, 0 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 5 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=28, Invalid=62, Unknown=0, NotChecked=0, Total=90 [2022-03-18 14:55:25,760 INFO L912 BasicCegarLoop]: 34 mSDtfsCounter, 24 mSDsluCounter, 57 mSDsCounter, 0 mSdLazyCounter, 74 mSolverCounterSat, 13 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 30 SdHoareTripleChecker+Valid, 91 SdHoareTripleChecker+Invalid, 87 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 13 IncrementalHoareTripleChecker+Valid, 74 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-03-18 14:55:25,762 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [30 Valid, 91 Invalid, 87 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [13 Valid, 74 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-03-18 14:55:25,763 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 39 states. [2022-03-18 14:55:25,771 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 39 to 30. [2022-03-18 14:55:25,771 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 30 states, 17 states have (on average 1.3529411764705883) internal successors, (23), 18 states have internal predecessors, (23), 9 states have call successors, (9), 4 states have call predecessors, (9), 3 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2022-03-18 14:55:25,772 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 30 states to 30 states and 39 transitions. [2022-03-18 14:55:25,772 INFO L78 Accepts]: Start accepts. Automaton has 30 states and 39 transitions. Word has length 12 [2022-03-18 14:55:25,773 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-18 14:55:25,773 INFO L478 AbstractCegarLoop]: Abstraction has 30 states and 39 transitions. [2022-03-18 14:55:25,773 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 1.3333333333333333) internal successors, (8), 4 states have internal predecessors, (8), 2 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-03-18 14:55:25,773 INFO L276 IsEmpty]: Start isEmpty. Operand 30 states and 39 transitions. [2022-03-18 14:55:25,774 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 15 [2022-03-18 14:55:25,774 INFO L492 BasicCegarLoop]: Found error trace [2022-03-18 14:55:25,774 INFO L500 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-18 14:55:25,774 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2022-03-18 14:55:25,775 INFO L403 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-18 14:55:25,776 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-18 14:55:25,776 INFO L85 PathProgramCache]: Analyzing trace with hash 1842794081, now seen corresponding path program 1 times [2022-03-18 14:55:25,776 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-18 14:55:25,776 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [299794745] [2022-03-18 14:55:25,776 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-18 14:55:25,777 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-18 14:55:25,789 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-18 14:55:25,837 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-03-18 14:55:25,843 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-18 14:55:25,850 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-03-18 14:55:25,851 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-18 14:55:25,851 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [299794745] [2022-03-18 14:55:25,851 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [299794745] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-18 14:55:25,851 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-18 14:55:25,852 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2022-03-18 14:55:25,852 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1907771141] [2022-03-18 14:55:25,852 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-18 14:55:25,852 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-03-18 14:55:25,852 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-18 14:55:25,853 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-03-18 14:55:25,853 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-03-18 14:55:25,853 INFO L87 Difference]: Start difference. First operand 30 states and 39 transitions. Second operand has 5 states, 4 states have (on average 2.5) internal successors, (10), 3 states have internal predecessors, (10), 3 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-03-18 14:55:25,923 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-18 14:55:25,923 INFO L93 Difference]: Finished difference Result 46 states and 61 transitions. [2022-03-18 14:55:25,923 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2022-03-18 14:55:25,924 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 4 states have (on average 2.5) internal successors, (10), 3 states have internal predecessors, (10), 3 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 14 [2022-03-18 14:55:25,924 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-18 14:55:25,924 INFO L225 Difference]: With dead ends: 46 [2022-03-18 14:55:25,925 INFO L226 Difference]: Without dead ends: 32 [2022-03-18 14:55:25,925 INFO L911 BasicCegarLoop]: 0 DeclaredPredicates, 7 GetRequests, 3 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2022-03-18 14:55:25,926 INFO L912 BasicCegarLoop]: 34 mSDtfsCounter, 6 mSDsluCounter, 39 mSDsCounter, 0 mSdLazyCounter, 51 mSolverCounterSat, 8 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 6 SdHoareTripleChecker+Valid, 73 SdHoareTripleChecker+Invalid, 59 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 8 IncrementalHoareTripleChecker+Valid, 51 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-03-18 14:55:25,927 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [6 Valid, 73 Invalid, 59 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [8 Valid, 51 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-03-18 14:55:25,928 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 32 states. [2022-03-18 14:55:25,933 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 32 to 32. [2022-03-18 14:55:25,933 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 32 states, 19 states have (on average 1.3157894736842106) internal successors, (25), 20 states have internal predecessors, (25), 9 states have call successors, (9), 4 states have call predecessors, (9), 3 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2022-03-18 14:55:25,934 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 32 states to 32 states and 41 transitions. [2022-03-18 14:55:25,934 INFO L78 Accepts]: Start accepts. Automaton has 32 states and 41 transitions. Word has length 14 [2022-03-18 14:55:25,934 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-18 14:55:25,935 INFO L478 AbstractCegarLoop]: Abstraction has 32 states and 41 transitions. [2022-03-18 14:55:25,935 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 4 states have (on average 2.5) internal successors, (10), 3 states have internal predecessors, (10), 3 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-03-18 14:55:25,935 INFO L276 IsEmpty]: Start isEmpty. Operand 32 states and 41 transitions. [2022-03-18 14:55:25,935 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 18 [2022-03-18 14:55:25,935 INFO L492 BasicCegarLoop]: Found error trace [2022-03-18 14:55:25,936 INFO L500 BasicCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-18 14:55:25,936 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2 [2022-03-18 14:55:25,936 INFO L403 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-18 14:55:25,936 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-18 14:55:25,937 INFO L85 PathProgramCache]: Analyzing trace with hash 311129497, now seen corresponding path program 1 times [2022-03-18 14:55:25,937 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-18 14:55:25,937 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1610801203] [2022-03-18 14:55:25,937 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-18 14:55:25,937 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-18 14:55:25,949 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-18 14:55:25,988 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-03-18 14:55:25,990 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-18 14:55:25,995 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 8 [2022-03-18 14:55:25,998 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-18 14:55:26,002 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-03-18 14:55:26,003 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-18 14:55:26,003 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1610801203] [2022-03-18 14:55:26,003 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1610801203] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-18 14:55:26,003 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-18 14:55:26,003 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2022-03-18 14:55:26,003 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [983236110] [2022-03-18 14:55:26,003 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-18 14:55:26,004 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2022-03-18 14:55:26,004 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-18 14:55:26,004 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2022-03-18 14:55:26,005 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2022-03-18 14:55:26,005 INFO L87 Difference]: Start difference. First operand 32 states and 41 transitions. Second operand has 6 states, 6 states have (on average 1.8333333333333333) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2022-03-18 14:55:26,134 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-18 14:55:26,135 INFO L93 Difference]: Finished difference Result 46 states and 60 transitions. [2022-03-18 14:55:26,135 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2022-03-18 14:55:26,136 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 1.8333333333333333) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) Word has length 17 [2022-03-18 14:55:26,137 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-18 14:55:26,139 INFO L225 Difference]: With dead ends: 46 [2022-03-18 14:55:26,139 INFO L226 Difference]: Without dead ends: 44 [2022-03-18 14:55:26,140 INFO L911 BasicCegarLoop]: 0 DeclaredPredicates, 13 GetRequests, 5 SyntacticMatches, 0 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=28, Invalid=62, Unknown=0, NotChecked=0, Total=90 [2022-03-18 14:55:26,149 INFO L912 BasicCegarLoop]: 34 mSDtfsCounter, 19 mSDsluCounter, 50 mSDsCounter, 0 mSdLazyCounter, 87 mSolverCounterSat, 13 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 24 SdHoareTripleChecker+Valid, 84 SdHoareTripleChecker+Invalid, 100 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 13 IncrementalHoareTripleChecker+Valid, 87 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-03-18 14:55:26,151 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [24 Valid, 84 Invalid, 100 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [13 Valid, 87 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-03-18 14:55:26,153 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 44 states. [2022-03-18 14:55:26,160 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 44 to 36. [2022-03-18 14:55:26,163 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 36 states, 22 states have (on average 1.2727272727272727) internal successors, (28), 23 states have internal predecessors, (28), 9 states have call successors, (9), 5 states have call predecessors, (9), 4 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2022-03-18 14:55:26,165 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 36 states to 36 states and 44 transitions. [2022-03-18 14:55:26,165 INFO L78 Accepts]: Start accepts. Automaton has 36 states and 44 transitions. Word has length 17 [2022-03-18 14:55:26,165 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-18 14:55:26,165 INFO L478 AbstractCegarLoop]: Abstraction has 36 states and 44 transitions. [2022-03-18 14:55:26,166 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 1.8333333333333333) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2022-03-18 14:55:26,166 INFO L276 IsEmpty]: Start isEmpty. Operand 36 states and 44 transitions. [2022-03-18 14:55:26,166 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 23 [2022-03-18 14:55:26,166 INFO L492 BasicCegarLoop]: Found error trace [2022-03-18 14:55:26,167 INFO L500 BasicCegarLoop]: trace histogram [3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-18 14:55:26,167 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3 [2022-03-18 14:55:26,167 INFO L403 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-18 14:55:26,169 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-18 14:55:26,169 INFO L85 PathProgramCache]: Analyzing trace with hash -1912623062, now seen corresponding path program 1 times [2022-03-18 14:55:26,169 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-18 14:55:26,169 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [563490839] [2022-03-18 14:55:26,169 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-18 14:55:26,169 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-18 14:55:26,192 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-18 14:55:26,192 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1904908181] [2022-03-18 14:55:26,192 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-18 14:55:26,192 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-18 14:55:26,193 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-18 14:55:26,207 INFO L229 MonitoredProcess]: Starting monitored process 2 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-18 14:55:26,238 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2022-03-18 14:55:26,264 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-18 14:55:26,267 INFO L263 TraceCheckSpWp]: Trace formula consists of 93 conjuncts, 9 conjunts are in the unsatisfiable core [2022-03-18 14:55:26,272 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-18 14:55:26,437 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2022-03-18 14:55:26,437 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-03-18 14:55:26,437 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-18 14:55:26,437 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [563490839] [2022-03-18 14:55:26,438 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-18 14:55:26,438 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1904908181] [2022-03-18 14:55:26,438 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1904908181] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-18 14:55:26,438 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-18 14:55:26,438 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-03-18 14:55:26,438 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1360773014] [2022-03-18 14:55:26,438 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-18 14:55:26,439 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-03-18 14:55:26,439 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-18 14:55:26,441 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-03-18 14:55:26,441 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-03-18 14:55:26,441 INFO L87 Difference]: Start difference. First operand 36 states and 44 transitions. Second operand has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2022-03-18 14:55:26,503 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-18 14:55:26,504 INFO L93 Difference]: Finished difference Result 65 states and 87 transitions. [2022-03-18 14:55:26,504 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-03-18 14:55:26,504 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) Word has length 22 [2022-03-18 14:55:26,505 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-18 14:55:26,506 INFO L225 Difference]: With dead ends: 65 [2022-03-18 14:55:26,506 INFO L226 Difference]: Without dead ends: 50 [2022-03-18 14:55:26,509 INFO L911 BasicCegarLoop]: 0 DeclaredPredicates, 22 GetRequests, 18 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2022-03-18 14:55:26,510 INFO L912 BasicCegarLoop]: 38 mSDtfsCounter, 10 mSDsluCounter, 93 mSDsCounter, 0 mSdLazyCounter, 36 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 14 SdHoareTripleChecker+Valid, 131 SdHoareTripleChecker+Invalid, 39 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 36 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-03-18 14:55:26,511 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [14 Valid, 131 Invalid, 39 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 36 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-03-18 14:55:26,512 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 50 states. [2022-03-18 14:55:26,521 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 50 to 50. [2022-03-18 14:55:26,522 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 50 states, 29 states have (on average 1.2758620689655173) internal successors, (37), 31 states have internal predecessors, (37), 15 states have call successors, (15), 6 states have call predecessors, (15), 5 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) [2022-03-18 14:55:26,523 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 50 states to 50 states and 64 transitions. [2022-03-18 14:55:26,523 INFO L78 Accepts]: Start accepts. Automaton has 50 states and 64 transitions. Word has length 22 [2022-03-18 14:55:26,523 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-18 14:55:26,523 INFO L478 AbstractCegarLoop]: Abstraction has 50 states and 64 transitions. [2022-03-18 14:55:26,523 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2022-03-18 14:55:26,524 INFO L276 IsEmpty]: Start isEmpty. Operand 50 states and 64 transitions. [2022-03-18 14:55:26,524 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 31 [2022-03-18 14:55:26,524 INFO L492 BasicCegarLoop]: Found error trace [2022-03-18 14:55:26,524 INFO L500 BasicCegarLoop]: trace histogram [4, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-18 14:55:26,546 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Forceful destruction successful, exit code 0 [2022-03-18 14:55:26,735 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-18 14:55:26,736 INFO L403 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-18 14:55:26,736 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-18 14:55:26,736 INFO L85 PathProgramCache]: Analyzing trace with hash 214651490, now seen corresponding path program 1 times [2022-03-18 14:55:26,736 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-18 14:55:26,736 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [776666548] [2022-03-18 14:55:26,736 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-18 14:55:26,737 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-18 14:55:26,746 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-18 14:55:26,747 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [606474107] [2022-03-18 14:55:26,747 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-18 14:55:26,747 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-18 14:55:26,747 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-18 14:55:26,748 INFO L229 MonitoredProcess]: Starting monitored process 3 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-18 14:55:26,755 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2022-03-18 14:55:26,792 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-18 14:55:26,793 INFO L263 TraceCheckSpWp]: Trace formula consists of 108 conjuncts, 7 conjunts are in the unsatisfiable core [2022-03-18 14:55:26,796 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-18 14:55:26,870 INFO L134 CoverageAnalysis]: Checked inductivity of 18 backedges. 6 proven. 0 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2022-03-18 14:55:26,870 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-03-18 14:55:26,870 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-18 14:55:26,870 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [776666548] [2022-03-18 14:55:26,870 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-18 14:55:26,870 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [606474107] [2022-03-18 14:55:26,871 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [606474107] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-18 14:55:26,871 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-18 14:55:26,871 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-03-18 14:55:26,871 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1172106778] [2022-03-18 14:55:26,871 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-18 14:55:26,871 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-03-18 14:55:26,872 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-18 14:55:26,872 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-03-18 14:55:26,872 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2022-03-18 14:55:26,872 INFO L87 Difference]: Start difference. First operand 50 states and 64 transitions. Second operand has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 4 states have call successors, (6), 4 states have call predecessors, (6), 2 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2022-03-18 14:55:26,897 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-18 14:55:26,898 INFO L93 Difference]: Finished difference Result 70 states and 80 transitions. [2022-03-18 14:55:26,898 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-03-18 14:55:26,898 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 4 states have call successors, (6), 4 states have call predecessors, (6), 2 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) Word has length 30 [2022-03-18 14:55:26,898 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-18 14:55:26,899 INFO L225 Difference]: With dead ends: 70 [2022-03-18 14:55:26,899 INFO L226 Difference]: Without dead ends: 63 [2022-03-18 14:55:26,899 INFO L911 BasicCegarLoop]: 0 DeclaredPredicates, 29 GetRequests, 26 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2022-03-18 14:55:26,900 INFO L912 BasicCegarLoop]: 36 mSDtfsCounter, 3 mSDsluCounter, 88 mSDsCounter, 0 mSdLazyCounter, 19 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 3 SdHoareTripleChecker+Valid, 124 SdHoareTripleChecker+Invalid, 22 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 19 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-03-18 14:55:26,900 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [3 Valid, 124 Invalid, 22 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 19 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-03-18 14:55:26,901 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 63 states. [2022-03-18 14:55:26,907 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 63 to 62. [2022-03-18 14:55:26,907 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 62 states, 38 states have (on average 1.1842105263157894) internal successors, (45), 40 states have internal predecessors, (45), 15 states have call successors, (15), 9 states have call predecessors, (15), 8 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) [2022-03-18 14:55:26,908 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 62 states to 62 states and 72 transitions. [2022-03-18 14:55:26,908 INFO L78 Accepts]: Start accepts. Automaton has 62 states and 72 transitions. Word has length 30 [2022-03-18 14:55:26,908 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-18 14:55:26,908 INFO L478 AbstractCegarLoop]: Abstraction has 62 states and 72 transitions. [2022-03-18 14:55:26,909 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 4 states have call successors, (6), 4 states have call predecessors, (6), 2 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2022-03-18 14:55:26,909 INFO L276 IsEmpty]: Start isEmpty. Operand 62 states and 72 transitions. [2022-03-18 14:55:26,909 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 31 [2022-03-18 14:55:26,909 INFO L492 BasicCegarLoop]: Found error trace [2022-03-18 14:55:26,909 INFO L500 BasicCegarLoop]: trace histogram [4, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-18 14:55:26,937 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Ended with exit code 0 [2022-03-18 14:55:27,135 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 3 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable5 [2022-03-18 14:55:27,136 INFO L403 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-18 14:55:27,136 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-18 14:55:27,136 INFO L85 PathProgramCache]: Analyzing trace with hash 216379368, now seen corresponding path program 1 times [2022-03-18 14:55:27,137 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-18 14:55:27,137 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [127458271] [2022-03-18 14:55:27,137 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-18 14:55:27,137 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-18 14:55:27,146 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-18 14:55:27,147 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1597563065] [2022-03-18 14:55:27,147 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-18 14:55:27,147 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-18 14:55:27,147 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-18 14:55:27,154 INFO L229 MonitoredProcess]: Starting monitored process 4 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-18 14:55:27,156 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2022-03-18 14:55:27,198 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-18 14:55:27,199 INFO L263 TraceCheckSpWp]: Trace formula consists of 108 conjuncts, 7 conjunts are in the unsatisfiable core [2022-03-18 14:55:27,205 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-18 14:55:27,327 INFO L134 CoverageAnalysis]: Checked inductivity of 18 backedges. 6 proven. 0 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2022-03-18 14:55:27,327 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-03-18 14:55:27,327 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-18 14:55:27,327 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [127458271] [2022-03-18 14:55:27,327 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-18 14:55:27,327 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1597563065] [2022-03-18 14:55:27,327 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1597563065] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-18 14:55:27,328 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-18 14:55:27,328 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-03-18 14:55:27,328 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1056819320] [2022-03-18 14:55:27,328 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-18 14:55:27,328 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-03-18 14:55:27,329 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-18 14:55:27,330 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-03-18 14:55:27,330 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-03-18 14:55:27,330 INFO L87 Difference]: Start difference. First operand 62 states and 72 transitions. Second operand has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2022-03-18 14:55:27,374 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-18 14:55:27,375 INFO L93 Difference]: Finished difference Result 76 states and 91 transitions. [2022-03-18 14:55:27,375 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-03-18 14:55:27,375 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) Word has length 30 [2022-03-18 14:55:27,376 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-18 14:55:27,378 INFO L225 Difference]: With dead ends: 76 [2022-03-18 14:55:27,378 INFO L226 Difference]: Without dead ends: 64 [2022-03-18 14:55:27,378 INFO L911 BasicCegarLoop]: 0 DeclaredPredicates, 30 GetRequests, 26 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2022-03-18 14:55:27,381 INFO L912 BasicCegarLoop]: 29 mSDtfsCounter, 11 mSDsluCounter, 74 mSDsCounter, 0 mSdLazyCounter, 39 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 14 SdHoareTripleChecker+Valid, 103 SdHoareTripleChecker+Invalid, 42 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 39 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-03-18 14:55:27,382 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [14 Valid, 103 Invalid, 42 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 39 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-03-18 14:55:27,387 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 64 states. [2022-03-18 14:55:27,397 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 64 to 63. [2022-03-18 14:55:27,397 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 63 states, 39 states have (on average 1.2307692307692308) internal successors, (48), 41 states have internal predecessors, (48), 15 states have call successors, (15), 9 states have call predecessors, (15), 8 states have return successors, (13), 12 states have call predecessors, (13), 13 states have call successors, (13) [2022-03-18 14:55:27,398 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 63 states to 63 states and 76 transitions. [2022-03-18 14:55:27,398 INFO L78 Accepts]: Start accepts. Automaton has 63 states and 76 transitions. Word has length 30 [2022-03-18 14:55:27,398 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-18 14:55:27,398 INFO L478 AbstractCegarLoop]: Abstraction has 63 states and 76 transitions. [2022-03-18 14:55:27,398 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2022-03-18 14:55:27,399 INFO L276 IsEmpty]: Start isEmpty. Operand 63 states and 76 transitions. [2022-03-18 14:55:27,404 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 38 [2022-03-18 14:55:27,404 INFO L492 BasicCegarLoop]: Found error trace [2022-03-18 14:55:27,405 INFO L500 BasicCegarLoop]: trace histogram [5, 4, 4, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-18 14:55:27,432 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Forceful destruction successful, exit code 0 [2022-03-18 14:55:27,627 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-18 14:55:27,628 INFO L403 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-18 14:55:27,628 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-18 14:55:27,628 INFO L85 PathProgramCache]: Analyzing trace with hash -1255015940, now seen corresponding path program 1 times [2022-03-18 14:55:27,628 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-18 14:55:27,628 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [516684971] [2022-03-18 14:55:27,629 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-18 14:55:27,629 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-18 14:55:27,639 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-18 14:55:27,639 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [594918882] [2022-03-18 14:55:27,640 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-18 14:55:27,640 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-18 14:55:27,640 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-18 14:55:27,648 INFO L229 MonitoredProcess]: Starting monitored process 5 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-18 14:55:27,649 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2022-03-18 14:55:27,695 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-18 14:55:27,697 INFO L263 TraceCheckSpWp]: Trace formula consists of 126 conjuncts, 7 conjunts are in the unsatisfiable core [2022-03-18 14:55:27,703 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-18 14:55:27,783 INFO L134 CoverageAnalysis]: Checked inductivity of 34 backedges. 18 proven. 2 refuted. 0 times theorem prover too weak. 14 trivial. 0 not checked. [2022-03-18 14:55:27,783 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-18 14:55:27,891 INFO L134 CoverageAnalysis]: Checked inductivity of 34 backedges. 8 proven. 2 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2022-03-18 14:55:27,892 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-18 14:55:27,892 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [516684971] [2022-03-18 14:55:27,892 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-18 14:55:27,892 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [594918882] [2022-03-18 14:55:27,892 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [594918882] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-18 14:55:27,892 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-03-18 14:55:27,892 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 5] total 8 [2022-03-18 14:55:27,893 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [160712153] [2022-03-18 14:55:27,893 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-03-18 14:55:27,893 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2022-03-18 14:55:27,893 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-18 14:55:27,894 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2022-03-18 14:55:27,894 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=20, Invalid=36, Unknown=0, NotChecked=0, Total=56 [2022-03-18 14:55:27,894 INFO L87 Difference]: Start difference. First operand 63 states and 76 transitions. Second operand has 8 states, 8 states have (on average 3.625) internal successors, (29), 8 states have internal predecessors, (29), 6 states have call successors, (12), 5 states have call predecessors, (12), 5 states have return successors, (10), 5 states have call predecessors, (10), 4 states have call successors, (10) [2022-03-18 14:55:27,989 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-18 14:55:27,989 INFO L93 Difference]: Finished difference Result 144 states and 177 transitions. [2022-03-18 14:55:27,989 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2022-03-18 14:55:27,990 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 8 states have (on average 3.625) internal successors, (29), 8 states have internal predecessors, (29), 6 states have call successors, (12), 5 states have call predecessors, (12), 5 states have return successors, (10), 5 states have call predecessors, (10), 4 states have call successors, (10) Word has length 37 [2022-03-18 14:55:27,991 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-18 14:55:27,993 INFO L225 Difference]: With dead ends: 144 [2022-03-18 14:55:27,994 INFO L226 Difference]: Without dead ends: 119 [2022-03-18 14:55:27,997 INFO L911 BasicCegarLoop]: 0 DeclaredPredicates, 76 GetRequests, 67 SyntacticMatches, 0 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 7 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=40, Invalid=70, Unknown=0, NotChecked=0, Total=110 [2022-03-18 14:55:27,997 INFO L912 BasicCegarLoop]: 45 mSDtfsCounter, 41 mSDsluCounter, 162 mSDsCounter, 0 mSdLazyCounter, 57 mSolverCounterSat, 14 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 41 SdHoareTripleChecker+Valid, 207 SdHoareTripleChecker+Invalid, 71 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 14 IncrementalHoareTripleChecker+Valid, 57 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-03-18 14:55:27,998 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [41 Valid, 207 Invalid, 71 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [14 Valid, 57 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-03-18 14:55:27,999 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 119 states. [2022-03-18 14:55:28,016 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 119 to 112. [2022-03-18 14:55:28,017 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 112 states, 71 states have (on average 1.2112676056338028) internal successors, (86), 74 states have internal predecessors, (86), 25 states have call successors, (25), 16 states have call predecessors, (25), 15 states have return successors, (22), 21 states have call predecessors, (22), 22 states have call successors, (22) [2022-03-18 14:55:28,018 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 112 states to 112 states and 133 transitions. [2022-03-18 14:55:28,018 INFO L78 Accepts]: Start accepts. Automaton has 112 states and 133 transitions. Word has length 37 [2022-03-18 14:55:28,018 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-18 14:55:28,018 INFO L478 AbstractCegarLoop]: Abstraction has 112 states and 133 transitions. [2022-03-18 14:55:28,019 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 8 states have (on average 3.625) internal successors, (29), 8 states have internal predecessors, (29), 6 states have call successors, (12), 5 states have call predecessors, (12), 5 states have return successors, (10), 5 states have call predecessors, (10), 4 states have call successors, (10) [2022-03-18 14:55:28,019 INFO L276 IsEmpty]: Start isEmpty. Operand 112 states and 133 transitions. [2022-03-18 14:55:28,019 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 41 [2022-03-18 14:55:28,019 INFO L492 BasicCegarLoop]: Found error trace [2022-03-18 14:55:28,020 INFO L500 BasicCegarLoop]: trace histogram [6, 5, 5, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-18 14:55:28,048 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Forceful destruction successful, exit code 0 [2022-03-18 14:55:28,243 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-18 14:55:28,244 INFO L403 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-18 14:55:28,244 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-18 14:55:28,244 INFO L85 PathProgramCache]: Analyzing trace with hash -1057559728, now seen corresponding path program 1 times [2022-03-18 14:55:28,244 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-18 14:55:28,244 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1624988392] [2022-03-18 14:55:28,245 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-18 14:55:28,245 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-18 14:55:28,253 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-18 14:55:28,253 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1665493930] [2022-03-18 14:55:28,253 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-18 14:55:28,254 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-18 14:55:28,254 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-18 14:55:28,262 INFO L229 MonitoredProcess]: Starting monitored process 6 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-18 14:55:28,263 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2022-03-18 14:55:28,311 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-18 14:55:28,312 INFO L263 TraceCheckSpWp]: Trace formula consists of 130 conjuncts, 13 conjunts are in the unsatisfiable core [2022-03-18 14:55:28,314 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-18 14:55:28,467 INFO L134 CoverageAnalysis]: Checked inductivity of 55 backedges. 10 proven. 5 refuted. 0 times theorem prover too weak. 40 trivial. 0 not checked. [2022-03-18 14:55:28,467 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-18 14:55:28,573 INFO L134 CoverageAnalysis]: Checked inductivity of 55 backedges. 10 proven. 0 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2022-03-18 14:55:28,574 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-18 14:55:28,574 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1624988392] [2022-03-18 14:55:28,574 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-18 14:55:28,574 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1665493930] [2022-03-18 14:55:28,574 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1665493930] provided 1 perfect and 1 imperfect interpolant sequences [2022-03-18 14:55:28,574 INFO L184 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2022-03-18 14:55:28,574 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [6] total 7 [2022-03-18 14:55:28,575 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1651796274] [2022-03-18 14:55:28,575 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-18 14:55:28,575 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-03-18 14:55:28,575 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-18 14:55:28,576 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-03-18 14:55:28,576 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=29, Unknown=0, NotChecked=0, Total=42 [2022-03-18 14:55:28,576 INFO L87 Difference]: Start difference. First operand 112 states and 133 transitions. Second operand has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2022-03-18 14:55:28,626 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-18 14:55:28,626 INFO L93 Difference]: Finished difference Result 129 states and 154 transitions. [2022-03-18 14:55:28,626 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-03-18 14:55:28,627 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) Word has length 40 [2022-03-18 14:55:28,627 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-18 14:55:28,628 INFO L225 Difference]: With dead ends: 129 [2022-03-18 14:55:28,628 INFO L226 Difference]: Without dead ends: 125 [2022-03-18 14:55:28,628 INFO L911 BasicCegarLoop]: 0 DeclaredPredicates, 80 GetRequests, 72 SyntacticMatches, 2 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=17, Invalid=39, Unknown=0, NotChecked=0, Total=56 [2022-03-18 14:55:28,629 INFO L912 BasicCegarLoop]: 34 mSDtfsCounter, 11 mSDsluCounter, 79 mSDsCounter, 0 mSdLazyCounter, 36 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 14 SdHoareTripleChecker+Valid, 113 SdHoareTripleChecker+Invalid, 37 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 36 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-03-18 14:55:28,629 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [14 Valid, 113 Invalid, 37 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 36 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-03-18 14:55:28,630 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 125 states. [2022-03-18 14:55:28,639 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 125 to 122. [2022-03-18 14:55:28,640 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 122 states, 78 states have (on average 1.1794871794871795) internal successors, (92), 81 states have internal predecessors, (92), 27 states have call successors, (27), 18 states have call predecessors, (27), 16 states have return successors, (24), 22 states have call predecessors, (24), 24 states have call successors, (24) [2022-03-18 14:55:28,641 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 122 states to 122 states and 143 transitions. [2022-03-18 14:55:28,641 INFO L78 Accepts]: Start accepts. Automaton has 122 states and 143 transitions. Word has length 40 [2022-03-18 14:55:28,641 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-18 14:55:28,642 INFO L478 AbstractCegarLoop]: Abstraction has 122 states and 143 transitions. [2022-03-18 14:55:28,642 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2022-03-18 14:55:28,642 INFO L276 IsEmpty]: Start isEmpty. Operand 122 states and 143 transitions. [2022-03-18 14:55:28,643 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 54 [2022-03-18 14:55:28,643 INFO L492 BasicCegarLoop]: Found error trace [2022-03-18 14:55:28,644 INFO L500 BasicCegarLoop]: trace histogram [8, 7, 7, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-18 14:55:28,671 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Forceful destruction successful, exit code 0 [2022-03-18 14:55:28,859 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-18 14:55:28,860 INFO L403 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-18 14:55:28,860 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-18 14:55:28,860 INFO L85 PathProgramCache]: Analyzing trace with hash 529029787, now seen corresponding path program 1 times [2022-03-18 14:55:28,860 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-18 14:55:28,860 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1524942597] [2022-03-18 14:55:28,860 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-18 14:55:28,861 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-18 14:55:28,870 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-18 14:55:28,870 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2051315974] [2022-03-18 14:55:28,870 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-18 14:55:28,870 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-18 14:55:28,871 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-18 14:55:28,882 INFO L229 MonitoredProcess]: Starting monitored process 7 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-18 14:55:28,903 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2022-03-18 14:55:28,932 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-18 14:55:28,933 INFO L263 TraceCheckSpWp]: Trace formula consists of 154 conjuncts, 9 conjunts are in the unsatisfiable core [2022-03-18 14:55:28,942 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-18 14:55:29,055 INFO L134 CoverageAnalysis]: Checked inductivity of 104 backedges. 36 proven. 42 refuted. 0 times theorem prover too weak. 26 trivial. 0 not checked. [2022-03-18 14:55:29,055 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-18 14:55:29,178 INFO L134 CoverageAnalysis]: Checked inductivity of 104 backedges. 14 proven. 6 refuted. 0 times theorem prover too weak. 84 trivial. 0 not checked. [2022-03-18 14:55:29,179 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-18 14:55:29,179 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1524942597] [2022-03-18 14:55:29,179 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-18 14:55:29,179 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2051315974] [2022-03-18 14:55:29,179 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2051315974] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-18 14:55:29,179 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-03-18 14:55:29,179 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 10 [2022-03-18 14:55:29,179 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1595369392] [2022-03-18 14:55:29,179 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-03-18 14:55:29,180 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2022-03-18 14:55:29,180 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-18 14:55:29,180 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2022-03-18 14:55:29,180 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=33, Invalid=57, Unknown=0, NotChecked=0, Total=90 [2022-03-18 14:55:29,181 INFO L87 Difference]: Start difference. First operand 122 states and 143 transitions. Second operand has 10 states, 10 states have (on average 3.6) internal successors, (36), 10 states have internal predecessors, (36), 8 states have call successors, (18), 6 states have call predecessors, (18), 6 states have return successors, (16), 7 states have call predecessors, (16), 6 states have call successors, (16) [2022-03-18 14:55:29,316 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-18 14:55:29,316 INFO L93 Difference]: Finished difference Result 245 states and 298 transitions. [2022-03-18 14:55:29,316 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2022-03-18 14:55:29,317 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 10 states have (on average 3.6) internal successors, (36), 10 states have internal predecessors, (36), 8 states have call successors, (18), 6 states have call predecessors, (18), 6 states have return successors, (16), 7 states have call predecessors, (16), 6 states have call successors, (16) Word has length 53 [2022-03-18 14:55:29,317 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-18 14:55:29,319 INFO L225 Difference]: With dead ends: 245 [2022-03-18 14:55:29,319 INFO L226 Difference]: Without dead ends: 224 [2022-03-18 14:55:29,319 INFO L911 BasicCegarLoop]: 0 DeclaredPredicates, 108 GetRequests, 97 SyntacticMatches, 0 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 11 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=52, Invalid=104, Unknown=0, NotChecked=0, Total=156 [2022-03-18 14:55:29,320 INFO L912 BasicCegarLoop]: 59 mSDtfsCounter, 80 mSDsluCounter, 243 mSDsCounter, 0 mSdLazyCounter, 119 mSolverCounterSat, 24 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 80 SdHoareTripleChecker+Valid, 302 SdHoareTripleChecker+Invalid, 143 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 24 IncrementalHoareTripleChecker+Valid, 119 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-03-18 14:55:29,320 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [80 Valid, 302 Invalid, 143 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [24 Valid, 119 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-03-18 14:55:29,320 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 224 states. [2022-03-18 14:55:29,335 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 224 to 217. [2022-03-18 14:55:29,336 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 217 states, 139 states have (on average 1.1942446043165467) internal successors, (166), 148 states have internal predecessors, (166), 51 states have call successors, (51), 28 states have call predecessors, (51), 26 states have return successors, (46), 40 states have call predecessors, (46), 46 states have call successors, (46) [2022-03-18 14:55:29,337 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 217 states to 217 states and 263 transitions. [2022-03-18 14:55:29,337 INFO L78 Accepts]: Start accepts. Automaton has 217 states and 263 transitions. Word has length 53 [2022-03-18 14:55:29,337 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-18 14:55:29,337 INFO L478 AbstractCegarLoop]: Abstraction has 217 states and 263 transitions. [2022-03-18 14:55:29,338 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 10 states have (on average 3.6) internal successors, (36), 10 states have internal predecessors, (36), 8 states have call successors, (18), 6 states have call predecessors, (18), 6 states have return successors, (16), 7 states have call predecessors, (16), 6 states have call successors, (16) [2022-03-18 14:55:29,338 INFO L276 IsEmpty]: Start isEmpty. Operand 217 states and 263 transitions. [2022-03-18 14:55:29,339 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 63 [2022-03-18 14:55:29,339 INFO L492 BasicCegarLoop]: Found error trace [2022-03-18 14:55:29,339 INFO L500 BasicCegarLoop]: trace histogram [9, 8, 8, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-18 14:55:29,366 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-03-18 14:55:29,559 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable9,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-18 14:55:29,559 INFO L403 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-18 14:55:29,560 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-18 14:55:29,560 INFO L85 PathProgramCache]: Analyzing trace with hash -41602886, now seen corresponding path program 1 times [2022-03-18 14:55:29,560 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-18 14:55:29,560 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [361302665] [2022-03-18 14:55:29,560 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-18 14:55:29,560 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-18 14:55:29,569 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-18 14:55:29,569 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1400546536] [2022-03-18 14:55:29,570 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-18 14:55:29,570 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-18 14:55:29,570 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-18 14:55:29,579 INFO L229 MonitoredProcess]: Starting monitored process 8 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-18 14:55:29,580 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2022-03-18 14:55:29,626 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-18 14:55:29,628 INFO L263 TraceCheckSpWp]: Trace formula consists of 178 conjuncts, 25 conjunts are in the unsatisfiable core [2022-03-18 14:55:29,630 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-18 14:55:29,984 INFO L134 CoverageAnalysis]: Checked inductivity of 137 backedges. 16 proven. 9 refuted. 0 times theorem prover too weak. 112 trivial. 0 not checked. [2022-03-18 14:55:29,984 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-18 14:55:31,022 INFO L134 CoverageAnalysis]: Checked inductivity of 137 backedges. 16 proven. 9 refuted. 0 times theorem prover too weak. 112 trivial. 0 not checked. [2022-03-18 14:55:31,023 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-18 14:55:31,023 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [361302665] [2022-03-18 14:55:31,023 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-18 14:55:31,023 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1400546536] [2022-03-18 14:55:31,023 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1400546536] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-18 14:55:31,023 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-03-18 14:55:31,023 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7] total 10 [2022-03-18 14:55:31,024 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1488914233] [2022-03-18 14:55:31,024 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-03-18 14:55:31,024 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2022-03-18 14:55:31,024 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-18 14:55:31,025 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2022-03-18 14:55:31,025 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=24, Invalid=66, Unknown=0, NotChecked=0, Total=90 [2022-03-18 14:55:31,025 INFO L87 Difference]: Start difference. First operand 217 states and 263 transitions. Second operand has 10 states, 10 states have (on average 3.4) internal successors, (34), 9 states have internal predecessors, (34), 7 states have call successors, (20), 2 states have call predecessors, (20), 1 states have return successors, (17), 5 states have call predecessors, (17), 5 states have call successors, (17) [2022-03-18 14:55:35,902 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-18 14:55:35,902 INFO L93 Difference]: Finished difference Result 371 states and 479 transitions. [2022-03-18 14:55:35,903 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2022-03-18 14:55:35,903 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 10 states have (on average 3.4) internal successors, (34), 9 states have internal predecessors, (34), 7 states have call successors, (20), 2 states have call predecessors, (20), 1 states have return successors, (17), 5 states have call predecessors, (17), 5 states have call successors, (17) Word has length 62 [2022-03-18 14:55:35,903 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-18 14:55:35,905 INFO L225 Difference]: With dead ends: 371 [2022-03-18 14:55:35,905 INFO L226 Difference]: Without dead ends: 303 [2022-03-18 14:55:35,906 INFO L911 BasicCegarLoop]: 0 DeclaredPredicates, 127 GetRequests, 112 SyntacticMatches, 3 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 9 ImplicationChecksByTransitivity, 4.2s TimeCoverageRelationStatistics Valid=50, Invalid=132, Unknown=0, NotChecked=0, Total=182 [2022-03-18 14:55:35,907 INFO L912 BasicCegarLoop]: 51 mSDtfsCounter, 49 mSDsluCounter, 243 mSDsCounter, 0 mSdLazyCounter, 218 mSolverCounterSat, 68 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.7s Time, 0 mProtectedPredicate, 0 mProtectedAction, 55 SdHoareTripleChecker+Valid, 294 SdHoareTripleChecker+Invalid, 286 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 68 IncrementalHoareTripleChecker+Valid, 218 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.8s IncrementalHoareTripleChecker+Time [2022-03-18 14:55:35,907 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [55 Valid, 294 Invalid, 286 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [68 Valid, 218 Invalid, 0 Unknown, 0 Unchecked, 0.8s Time] [2022-03-18 14:55:35,908 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 303 states. [2022-03-18 14:55:35,931 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 303 to 274. [2022-03-18 14:55:35,931 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 274 states, 185 states have (on average 1.2324324324324325) internal successors, (228), 191 states have internal predecessors, (228), 58 states have call successors, (58), 31 states have call predecessors, (58), 30 states have return successors, (55), 51 states have call predecessors, (55), 55 states have call successors, (55) [2022-03-18 14:55:35,933 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 274 states to 274 states and 341 transitions. [2022-03-18 14:55:35,933 INFO L78 Accepts]: Start accepts. Automaton has 274 states and 341 transitions. Word has length 62 [2022-03-18 14:55:35,933 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-18 14:55:35,933 INFO L478 AbstractCegarLoop]: Abstraction has 274 states and 341 transitions. [2022-03-18 14:55:35,934 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 10 states have (on average 3.4) internal successors, (34), 9 states have internal predecessors, (34), 7 states have call successors, (20), 2 states have call predecessors, (20), 1 states have return successors, (17), 5 states have call predecessors, (17), 5 states have call successors, (17) [2022-03-18 14:55:35,934 INFO L276 IsEmpty]: Start isEmpty. Operand 274 states and 341 transitions. [2022-03-18 14:55:35,935 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 74 [2022-03-18 14:55:35,935 INFO L492 BasicCegarLoop]: Found error trace [2022-03-18 14:55:35,935 INFO L500 BasicCegarLoop]: trace histogram [11, 10, 10, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-18 14:55:35,956 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Ended with exit code 0 [2022-03-18 14:55:36,147 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable10,8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-18 14:55:36,148 INFO L403 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-18 14:55:36,148 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-18 14:55:36,148 INFO L85 PathProgramCache]: Analyzing trace with hash 73149133, now seen corresponding path program 1 times [2022-03-18 14:55:36,148 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-18 14:55:36,148 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [469300686] [2022-03-18 14:55:36,148 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-18 14:55:36,149 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-18 14:55:36,157 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-18 14:55:36,158 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1546644477] [2022-03-18 14:55:36,158 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-18 14:55:36,158 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-18 14:55:36,158 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-18 14:55:36,161 INFO L229 MonitoredProcess]: Starting monitored process 9 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-18 14:55:36,162 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2022-03-18 14:55:36,209 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-18 14:55:36,211 INFO L263 TraceCheckSpWp]: Trace formula consists of 198 conjuncts, 35 conjunts are in the unsatisfiable core [2022-03-18 14:55:36,214 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-18 14:55:36,760 INFO L134 CoverageAnalysis]: Checked inductivity of 211 backedges. 66 proven. 13 refuted. 0 times theorem prover too weak. 132 trivial. 0 not checked. [2022-03-18 14:55:36,760 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-18 14:55:37,010 INFO L134 CoverageAnalysis]: Checked inductivity of 211 backedges. 68 proven. 2 refuted. 0 times theorem prover too weak. 141 trivial. 0 not checked. [2022-03-18 14:55:37,011 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-18 14:55:37,011 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [469300686] [2022-03-18 14:55:37,011 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-18 14:55:37,011 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1546644477] [2022-03-18 14:55:37,011 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1546644477] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-18 14:55:37,011 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-03-18 14:55:37,011 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 9] total 16 [2022-03-18 14:55:37,012 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1271838050] [2022-03-18 14:55:37,012 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-03-18 14:55:37,012 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2022-03-18 14:55:37,012 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-18 14:55:37,013 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2022-03-18 14:55:37,013 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=51, Invalid=189, Unknown=0, NotChecked=0, Total=240 [2022-03-18 14:55:37,013 INFO L87 Difference]: Start difference. First operand 274 states and 341 transitions. Second operand has 16 states, 12 states have (on average 3.0833333333333335) internal successors, (37), 11 states have internal predecessors, (37), 8 states have call successors, (20), 2 states have call predecessors, (20), 2 states have return successors, (18), 7 states have call predecessors, (18), 6 states have call successors, (18) [2022-03-18 14:55:37,439 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-18 14:55:37,440 INFO L93 Difference]: Finished difference Result 335 states and 416 transitions. [2022-03-18 14:55:37,440 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2022-03-18 14:55:37,440 INFO L78 Accepts]: Start accepts. Automaton has has 16 states, 12 states have (on average 3.0833333333333335) internal successors, (37), 11 states have internal predecessors, (37), 8 states have call successors, (20), 2 states have call predecessors, (20), 2 states have return successors, (18), 7 states have call predecessors, (18), 6 states have call successors, (18) Word has length 73 [2022-03-18 14:55:37,441 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-18 14:55:37,442 INFO L225 Difference]: With dead ends: 335 [2022-03-18 14:55:37,442 INFO L226 Difference]: Without dead ends: 239 [2022-03-18 14:55:37,443 INFO L911 BasicCegarLoop]: 0 DeclaredPredicates, 149 GetRequests, 129 SyntacticMatches, 2 SemanticMatches, 18 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 39 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=76, Invalid=304, Unknown=0, NotChecked=0, Total=380 [2022-03-18 14:55:37,443 INFO L912 BasicCegarLoop]: 35 mSDtfsCounter, 54 mSDsluCounter, 229 mSDsCounter, 0 mSdLazyCounter, 364 mSolverCounterSat, 69 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 68 SdHoareTripleChecker+Valid, 264 SdHoareTripleChecker+Invalid, 433 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 69 IncrementalHoareTripleChecker+Valid, 364 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2022-03-18 14:55:37,444 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [68 Valid, 264 Invalid, 433 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [69 Valid, 364 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2022-03-18 14:55:37,444 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 239 states. [2022-03-18 14:55:37,461 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 239 to 223. [2022-03-18 14:55:37,462 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 223 states, 150 states have (on average 1.1933333333333334) internal successors, (179), 154 states have internal predecessors, (179), 45 states have call successors, (45), 29 states have call predecessors, (45), 27 states have return successors, (42), 39 states have call predecessors, (42), 42 states have call successors, (42) [2022-03-18 14:55:37,463 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 223 states to 223 states and 266 transitions. [2022-03-18 14:55:37,463 INFO L78 Accepts]: Start accepts. Automaton has 223 states and 266 transitions. Word has length 73 [2022-03-18 14:55:37,463 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-18 14:55:37,464 INFO L478 AbstractCegarLoop]: Abstraction has 223 states and 266 transitions. [2022-03-18 14:55:37,464 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 16 states, 12 states have (on average 3.0833333333333335) internal successors, (37), 11 states have internal predecessors, (37), 8 states have call successors, (20), 2 states have call predecessors, (20), 2 states have return successors, (18), 7 states have call predecessors, (18), 6 states have call successors, (18) [2022-03-18 14:55:37,464 INFO L276 IsEmpty]: Start isEmpty. Operand 223 states and 266 transitions. [2022-03-18 14:55:37,465 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 83 [2022-03-18 14:55:37,465 INFO L492 BasicCegarLoop]: Found error trace [2022-03-18 14:55:37,465 INFO L500 BasicCegarLoop]: trace histogram [13, 12, 12, 3, 3, 3, 3, 3, 3, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-18 14:55:37,493 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Forceful destruction successful, exit code 0 [2022-03-18 14:55:37,684 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 9 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable11 [2022-03-18 14:55:37,684 INFO L403 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-18 14:55:37,685 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-18 14:55:37,685 INFO L85 PathProgramCache]: Analyzing trace with hash 1894150768, now seen corresponding path program 1 times [2022-03-18 14:55:37,685 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-18 14:55:37,685 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2129850173] [2022-03-18 14:55:37,685 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-18 14:55:37,685 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-18 14:55:37,691 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-18 14:55:37,692 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [847223477] [2022-03-18 14:55:37,692 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-18 14:55:37,692 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-18 14:55:37,692 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-18 14:55:37,693 INFO L229 MonitoredProcess]: Starting monitored process 10 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-18 14:55:37,695 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Waiting until timeout for monitored process [2022-03-18 14:55:37,739 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-18 14:55:37,740 INFO L263 TraceCheckSpWp]: Trace formula consists of 211 conjuncts, 4 conjunts are in the unsatisfiable core [2022-03-18 14:55:37,742 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-18 14:55:37,962 INFO L134 CoverageAnalysis]: Checked inductivity of 306 backedges. 84 proven. 0 refuted. 0 times theorem prover too weak. 222 trivial. 0 not checked. [2022-03-18 14:55:37,963 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-03-18 14:55:37,963 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-18 14:55:37,963 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2129850173] [2022-03-18 14:55:37,963 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-18 14:55:37,963 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [847223477] [2022-03-18 14:55:37,963 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [847223477] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-18 14:55:37,963 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-18 14:55:37,963 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-03-18 14:55:37,963 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1031216727] [2022-03-18 14:55:37,963 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-18 14:55:37,964 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-03-18 14:55:37,964 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-18 14:55:37,964 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-03-18 14:55:37,964 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=10, Invalid=10, Unknown=0, NotChecked=0, Total=20 [2022-03-18 14:55:37,964 INFO L87 Difference]: Start difference. First operand 223 states and 266 transitions. Second operand has 5 states, 5 states have (on average 4.6) internal successors, (23), 5 states have internal predecessors, (23), 5 states have call successors, (15), 2 states have call predecessors, (15), 2 states have return successors, (13), 5 states have call predecessors, (13), 5 states have call successors, (13) [2022-03-18 14:55:38,022 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-18 14:55:38,022 INFO L93 Difference]: Finished difference Result 242 states and 289 transitions. [2022-03-18 14:55:38,022 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-03-18 14:55:38,023 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 4.6) internal successors, (23), 5 states have internal predecessors, (23), 5 states have call successors, (15), 2 states have call predecessors, (15), 2 states have return successors, (13), 5 states have call predecessors, (13), 5 states have call successors, (13) Word has length 82 [2022-03-18 14:55:38,023 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-18 14:55:38,024 INFO L225 Difference]: With dead ends: 242 [2022-03-18 14:55:38,024 INFO L226 Difference]: Without dead ends: 222 [2022-03-18 14:55:38,024 INFO L911 BasicCegarLoop]: 0 DeclaredPredicates, 81 GetRequests, 78 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=10, Invalid=10, Unknown=0, NotChecked=0, Total=20 [2022-03-18 14:55:38,025 INFO L912 BasicCegarLoop]: 57 mSDtfsCounter, 24 mSDsluCounter, 64 mSDsCounter, 0 mSdLazyCounter, 33 mSolverCounterSat, 13 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 31 SdHoareTripleChecker+Valid, 121 SdHoareTripleChecker+Invalid, 46 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 13 IncrementalHoareTripleChecker+Valid, 33 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-03-18 14:55:38,025 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [31 Valid, 121 Invalid, 46 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [13 Valid, 33 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-03-18 14:55:38,026 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 222 states. [2022-03-18 14:55:38,043 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 222 to 217. [2022-03-18 14:55:38,043 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 217 states, 147 states have (on average 1.163265306122449) internal successors, (171), 149 states have internal predecessors, (171), 43 states have call successors, (43), 27 states have call predecessors, (43), 26 states have return successors, (41), 40 states have call predecessors, (41), 41 states have call successors, (41) [2022-03-18 14:55:38,044 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 217 states to 217 states and 255 transitions. [2022-03-18 14:55:38,045 INFO L78 Accepts]: Start accepts. Automaton has 217 states and 255 transitions. Word has length 82 [2022-03-18 14:55:38,045 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-18 14:55:38,045 INFO L478 AbstractCegarLoop]: Abstraction has 217 states and 255 transitions. [2022-03-18 14:55:38,045 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 4.6) internal successors, (23), 5 states have internal predecessors, (23), 5 states have call successors, (15), 2 states have call predecessors, (15), 2 states have return successors, (13), 5 states have call predecessors, (13), 5 states have call successors, (13) [2022-03-18 14:55:38,045 INFO L276 IsEmpty]: Start isEmpty. Operand 217 states and 255 transitions. [2022-03-18 14:55:38,046 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 95 [2022-03-18 14:55:38,046 INFO L492 BasicCegarLoop]: Found error trace [2022-03-18 14:55:38,046 INFO L500 BasicCegarLoop]: trace histogram [14, 13, 13, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-18 14:55:38,077 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Forceful destruction successful, exit code 0 [2022-03-18 14:55:38,271 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 10 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable12 [2022-03-18 14:55:38,272 INFO L403 AbstractCegarLoop]: === Iteration 14 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-18 14:55:38,272 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-18 14:55:38,272 INFO L85 PathProgramCache]: Analyzing trace with hash -612515316, now seen corresponding path program 2 times [2022-03-18 14:55:38,272 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-18 14:55:38,272 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2083777819] [2022-03-18 14:55:38,272 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-18 14:55:38,272 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-18 14:55:38,287 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-18 14:55:38,287 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1098656312] [2022-03-18 14:55:38,287 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-03-18 14:55:38,287 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-18 14:55:38,287 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-18 14:55:38,290 INFO L229 MonitoredProcess]: Starting monitored process 11 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-18 14:55:38,313 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Waiting until timeout for monitored process [2022-03-18 14:55:38,352 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-03-18 14:55:38,352 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-18 14:55:38,354 INFO L263 TraceCheckSpWp]: Trace formula consists of 248 conjuncts, 39 conjunts are in the unsatisfiable core [2022-03-18 14:55:38,357 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-18 14:55:38,987 INFO L134 CoverageAnalysis]: Checked inductivity of 368 backedges. 26 proven. 30 refuted. 0 times theorem prover too weak. 312 trivial. 0 not checked. [2022-03-18 14:55:38,987 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-18 14:55:55,561 INFO L134 CoverageAnalysis]: Checked inductivity of 368 backedges. 26 proven. 30 refuted. 0 times theorem prover too weak. 312 trivial. 0 not checked. [2022-03-18 14:55:55,561 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-18 14:55:55,561 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2083777819] [2022-03-18 14:55:55,561 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-18 14:55:55,561 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1098656312] [2022-03-18 14:55:55,561 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1098656312] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-18 14:55:55,561 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-03-18 14:55:55,561 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10] total 16 [2022-03-18 14:55:55,562 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1151943128] [2022-03-18 14:55:55,562 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-03-18 14:55:55,562 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2022-03-18 14:55:55,562 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-18 14:55:55,562 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2022-03-18 14:55:55,563 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=60, Invalid=180, Unknown=0, NotChecked=0, Total=240 [2022-03-18 14:55:55,563 INFO L87 Difference]: Start difference. First operand 217 states and 255 transitions. Second operand has 16 states, 16 states have (on average 3.0) internal successors, (48), 15 states have internal predecessors, (48), 11 states have call successors, (30), 2 states have call predecessors, (30), 1 states have return successors, (27), 9 states have call predecessors, (27), 9 states have call successors, (27) [2022-03-18 14:56:23,988 WARN L232 SmtUtils]: Spent 28.18s on a formula simplification. DAG size of input: 192 DAG size of output: 86 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-03-18 14:56:32,310 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-18 14:56:34,479 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-18 14:56:36,802 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-18 14:56:39,642 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-18 14:56:42,224 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-18 14:56:46,597 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.92s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-18 14:56:46,968 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-18 14:56:46,968 INFO L93 Difference]: Finished difference Result 332 states and 434 transitions. [2022-03-18 14:56:46,969 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2022-03-18 14:56:46,969 INFO L78 Accepts]: Start accepts. Automaton has has 16 states, 16 states have (on average 3.0) internal successors, (48), 15 states have internal predecessors, (48), 11 states have call successors, (30), 2 states have call predecessors, (30), 1 states have return successors, (27), 9 states have call predecessors, (27), 9 states have call successors, (27) Word has length 94 [2022-03-18 14:56:46,969 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-18 14:56:46,970 INFO L225 Difference]: With dead ends: 332 [2022-03-18 14:56:46,971 INFO L226 Difference]: Without dead ends: 275 [2022-03-18 14:56:46,971 INFO L911 BasicCegarLoop]: 0 DeclaredPredicates, 194 GetRequests, 170 SyntacticMatches, 4 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 24 ImplicationChecksByTransitivity, 37.8s TimeCoverageRelationStatistics Valid=126, Invalid=336, Unknown=0, NotChecked=0, Total=462 [2022-03-18 14:56:46,972 INFO L912 BasicCegarLoop]: 73 mSDtfsCounter, 130 mSDsluCounter, 587 mSDsCounter, 0 mSdLazyCounter, 519 mSolverCounterSat, 176 mSolverCounterUnsat, 5 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 16.9s Time, 0 mProtectedPredicate, 0 mProtectedAction, 141 SdHoareTripleChecker+Valid, 660 SdHoareTripleChecker+Invalid, 700 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 176 IncrementalHoareTripleChecker+Valid, 519 IncrementalHoareTripleChecker+Invalid, 5 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 17.0s IncrementalHoareTripleChecker+Time [2022-03-18 14:56:46,972 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [141 Valid, 660 Invalid, 700 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [176 Valid, 519 Invalid, 5 Unknown, 0 Unchecked, 17.0s Time] [2022-03-18 14:56:46,973 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 275 states. [2022-03-18 14:56:46,998 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 275 to 257. [2022-03-18 14:56:46,999 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 257 states, 172 states have (on average 1.2267441860465116) internal successors, (211), 177 states have internal predecessors, (211), 57 states have call successors, (57), 28 states have call predecessors, (57), 27 states have return successors, (55), 51 states have call predecessors, (55), 55 states have call successors, (55) [2022-03-18 14:56:47,001 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 257 states to 257 states and 323 transitions. [2022-03-18 14:56:47,001 INFO L78 Accepts]: Start accepts. Automaton has 257 states and 323 transitions. Word has length 94 [2022-03-18 14:56:47,001 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-18 14:56:47,002 INFO L478 AbstractCegarLoop]: Abstraction has 257 states and 323 transitions. [2022-03-18 14:56:47,002 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 16 states, 16 states have (on average 3.0) internal successors, (48), 15 states have internal predecessors, (48), 11 states have call successors, (30), 2 states have call predecessors, (30), 1 states have return successors, (27), 9 states have call predecessors, (27), 9 states have call successors, (27) [2022-03-18 14:56:47,002 INFO L276 IsEmpty]: Start isEmpty. Operand 257 states and 323 transitions. [2022-03-18 14:56:47,003 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 101 [2022-03-18 14:56:47,003 INFO L492 BasicCegarLoop]: Found error trace [2022-03-18 14:56:47,003 INFO L500 BasicCegarLoop]: trace histogram [15, 14, 14, 5, 4, 4, 4, 4, 4, 4, 4, 4, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-18 14:56:47,029 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Forceful destruction successful, exit code 0 [2022-03-18 14:56:47,223 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 11 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable13 [2022-03-18 14:56:47,224 INFO L403 AbstractCegarLoop]: === Iteration 15 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-18 14:56:47,224 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-18 14:56:47,224 INFO L85 PathProgramCache]: Analyzing trace with hash -1539828763, now seen corresponding path program 1 times [2022-03-18 14:56:47,224 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-18 14:56:47,224 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [127823171] [2022-03-18 14:56:47,224 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-18 14:56:47,225 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-18 14:56:47,237 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-18 14:56:47,237 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1207203355] [2022-03-18 14:56:47,238 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-18 14:56:47,238 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-18 14:56:47,238 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-18 14:56:47,245 INFO L229 MonitoredProcess]: Starting monitored process 12 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-18 14:56:47,246 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Waiting until timeout for monitored process [2022-03-18 14:56:47,293 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-18 14:56:47,294 INFO L263 TraceCheckSpWp]: Trace formula consists of 261 conjuncts, 13 conjunts are in the unsatisfiable core [2022-03-18 14:56:47,296 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-18 14:56:47,468 INFO L134 CoverageAnalysis]: Checked inductivity of 438 backedges. 120 proven. 260 refuted. 0 times theorem prover too weak. 58 trivial. 0 not checked. [2022-03-18 14:56:47,468 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-18 14:56:47,649 INFO L134 CoverageAnalysis]: Checked inductivity of 438 backedges. 28 proven. 44 refuted. 0 times theorem prover too weak. 366 trivial. 0 not checked. [2022-03-18 14:56:47,650 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-18 14:56:47,650 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [127823171] [2022-03-18 14:56:47,650 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-18 14:56:47,650 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1207203355] [2022-03-18 14:56:47,650 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1207203355] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-18 14:56:47,650 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-03-18 14:56:47,650 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 14 [2022-03-18 14:56:47,650 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [618323039] [2022-03-18 14:56:47,650 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-03-18 14:56:47,651 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2022-03-18 14:56:47,651 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-18 14:56:47,651 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2022-03-18 14:56:47,651 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=71, Invalid=111, Unknown=0, NotChecked=0, Total=182 [2022-03-18 14:56:47,652 INFO L87 Difference]: Start difference. First operand 257 states and 323 transitions. Second operand has 14 states, 14 states have (on average 4.214285714285714) internal successors, (59), 14 states have internal predecessors, (59), 12 states have call successors, (32), 8 states have call predecessors, (32), 8 states have return successors, (30), 11 states have call predecessors, (30), 10 states have call successors, (30) [2022-03-18 14:56:47,990 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-18 14:56:47,990 INFO L93 Difference]: Finished difference Result 746 states and 1016 transitions. [2022-03-18 14:56:47,990 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 22 states. [2022-03-18 14:56:47,991 INFO L78 Accepts]: Start accepts. Automaton has has 14 states, 14 states have (on average 4.214285714285714) internal successors, (59), 14 states have internal predecessors, (59), 12 states have call successors, (32), 8 states have call predecessors, (32), 8 states have return successors, (30), 11 states have call predecessors, (30), 10 states have call successors, (30) Word has length 100 [2022-03-18 14:56:47,991 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-18 14:56:47,994 INFO L225 Difference]: With dead ends: 746 [2022-03-18 14:56:47,994 INFO L226 Difference]: Without dead ends: 659 [2022-03-18 14:56:47,996 INFO L911 BasicCegarLoop]: 0 DeclaredPredicates, 208 GetRequests, 187 SyntacticMatches, 0 SemanticMatches, 21 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 55 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=184, Invalid=322, Unknown=0, NotChecked=0, Total=506 [2022-03-18 14:56:47,996 INFO L912 BasicCegarLoop]: 80 mSDtfsCounter, 177 mSDsluCounter, 298 mSDsCounter, 0 mSdLazyCounter, 191 mSolverCounterSat, 89 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 177 SdHoareTripleChecker+Valid, 378 SdHoareTripleChecker+Invalid, 280 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 89 IncrementalHoareTripleChecker+Valid, 191 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2022-03-18 14:56:47,996 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [177 Valid, 378 Invalid, 280 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [89 Valid, 191 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2022-03-18 14:56:47,997 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 659 states. [2022-03-18 14:56:48,058 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 659 to 552. [2022-03-18 14:56:48,059 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 552 states, 361 states have (on average 1.2825484764542936) internal successors, (463), 378 states have internal predecessors, (463), 136 states have call successors, (136), 56 states have call predecessors, (136), 54 states have return successors, (131), 117 states have call predecessors, (131), 131 states have call successors, (131) [2022-03-18 14:56:48,062 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 552 states to 552 states and 730 transitions. [2022-03-18 14:56:48,062 INFO L78 Accepts]: Start accepts. Automaton has 552 states and 730 transitions. Word has length 100 [2022-03-18 14:56:48,062 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-18 14:56:48,063 INFO L478 AbstractCegarLoop]: Abstraction has 552 states and 730 transitions. [2022-03-18 14:56:48,063 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 14 states, 14 states have (on average 4.214285714285714) internal successors, (59), 14 states have internal predecessors, (59), 12 states have call successors, (32), 8 states have call predecessors, (32), 8 states have return successors, (30), 11 states have call predecessors, (30), 10 states have call successors, (30) [2022-03-18 14:56:48,063 INFO L276 IsEmpty]: Start isEmpty. Operand 552 states and 730 transitions. [2022-03-18 14:56:48,064 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 109 [2022-03-18 14:56:48,064 INFO L492 BasicCegarLoop]: Found error trace [2022-03-18 14:56:48,064 INFO L500 BasicCegarLoop]: trace histogram [16, 15, 15, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-18 14:56:48,093 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Forceful destruction successful, exit code 0 [2022-03-18 14:56:48,279 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 12 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable14 [2022-03-18 14:56:48,279 INFO L403 AbstractCegarLoop]: === Iteration 16 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-18 14:56:48,280 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-18 14:56:48,280 INFO L85 PathProgramCache]: Analyzing trace with hash 1894816690, now seen corresponding path program 1 times [2022-03-18 14:56:48,280 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-18 14:56:48,280 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1155857901] [2022-03-18 14:56:48,280 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-18 14:56:48,280 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-18 14:56:48,288 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-18 14:56:48,288 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [265013756] [2022-03-18 14:56:48,289 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-18 14:56:48,289 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-18 14:56:48,289 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-18 14:56:48,290 INFO L229 MonitoredProcess]: Starting monitored process 13 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-18 14:56:48,291 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Waiting until timeout for monitored process [2022-03-18 14:56:48,344 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-18 14:56:48,346 INFO L263 TraceCheckSpWp]: Trace formula consists of 281 conjuncts, 17 conjunts are in the unsatisfiable core [2022-03-18 14:56:48,349 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-18 14:56:48,604 INFO L134 CoverageAnalysis]: Checked inductivity of 492 backedges. 30 proven. 414 refuted. 0 times theorem prover too weak. 48 trivial. 0 not checked. [2022-03-18 14:56:48,604 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-18 14:56:48,839 INFO L134 CoverageAnalysis]: Checked inductivity of 492 backedges. 30 proven. 42 refuted. 0 times theorem prover too weak. 420 trivial. 0 not checked. [2022-03-18 14:56:48,839 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-18 14:56:48,839 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1155857901] [2022-03-18 14:56:48,839 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-18 14:56:48,839 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [265013756] [2022-03-18 14:56:48,839 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [265013756] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-18 14:56:48,840 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-03-18 14:56:48,840 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10] total 18 [2022-03-18 14:56:48,840 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1272527990] [2022-03-18 14:56:48,840 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-03-18 14:56:48,840 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 18 states [2022-03-18 14:56:48,840 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-18 14:56:48,841 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 18 interpolants. [2022-03-18 14:56:48,841 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=125, Invalid=181, Unknown=0, NotChecked=0, Total=306 [2022-03-18 14:56:48,841 INFO L87 Difference]: Start difference. First operand 552 states and 730 transitions. Second operand has 18 states, 18 states have (on average 4.222222222222222) internal successors, (76), 18 states have internal predecessors, (76), 16 states have call successors, (34), 10 states have call predecessors, (34), 9 states have return successors, (32), 14 states have call predecessors, (32), 13 states have call successors, (32) [2022-03-18 14:56:49,385 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-18 14:56:49,386 INFO L93 Difference]: Finished difference Result 1159 states and 1613 transitions. [2022-03-18 14:56:49,386 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 27 states. [2022-03-18 14:56:49,386 INFO L78 Accepts]: Start accepts. Automaton has has 18 states, 18 states have (on average 4.222222222222222) internal successors, (76), 18 states have internal predecessors, (76), 16 states have call successors, (34), 10 states have call predecessors, (34), 9 states have return successors, (32), 14 states have call predecessors, (32), 13 states have call successors, (32) Word has length 108 [2022-03-18 14:56:49,387 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-18 14:56:49,392 INFO L225 Difference]: With dead ends: 1159 [2022-03-18 14:56:49,392 INFO L226 Difference]: Without dead ends: 1122 [2022-03-18 14:56:49,393 INFO L911 BasicCegarLoop]: 0 DeclaredPredicates, 225 GetRequests, 199 SyntacticMatches, 0 SemanticMatches, 26 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 79 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=259, Invalid=497, Unknown=0, NotChecked=0, Total=756 [2022-03-18 14:56:49,393 INFO L912 BasicCegarLoop]: 100 mSDtfsCounter, 314 mSDsluCounter, 403 mSDsCounter, 0 mSdLazyCounter, 296 mSolverCounterSat, 198 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 314 SdHoareTripleChecker+Valid, 503 SdHoareTripleChecker+Invalid, 494 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 198 IncrementalHoareTripleChecker+Valid, 296 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2022-03-18 14:56:49,394 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [314 Valid, 503 Invalid, 494 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [198 Valid, 296 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2022-03-18 14:56:49,395 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1122 states. [2022-03-18 14:56:49,505 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1122 to 1097. [2022-03-18 14:56:49,507 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 1097 states, 729 states have (on average 1.2455418381344308) internal successors, (908), 758 states have internal predecessors, (908), 279 states have call successors, (279), 90 states have call predecessors, (279), 88 states have return successors, (270), 248 states have call predecessors, (270), 270 states have call successors, (270) [2022-03-18 14:56:49,512 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1097 states to 1097 states and 1457 transitions. [2022-03-18 14:56:49,512 INFO L78 Accepts]: Start accepts. Automaton has 1097 states and 1457 transitions. Word has length 108 [2022-03-18 14:56:49,512 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-18 14:56:49,513 INFO L478 AbstractCegarLoop]: Abstraction has 1097 states and 1457 transitions. [2022-03-18 14:56:49,513 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 18 states, 18 states have (on average 4.222222222222222) internal successors, (76), 18 states have internal predecessors, (76), 16 states have call successors, (34), 10 states have call predecessors, (34), 9 states have return successors, (32), 14 states have call predecessors, (32), 13 states have call successors, (32) [2022-03-18 14:56:49,513 INFO L276 IsEmpty]: Start isEmpty. Operand 1097 states and 1457 transitions. [2022-03-18 14:56:49,514 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 111 [2022-03-18 14:56:49,514 INFO L492 BasicCegarLoop]: Found error trace [2022-03-18 14:56:49,514 INFO L500 BasicCegarLoop]: trace histogram [17, 16, 16, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-18 14:56:49,541 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Forceful destruction successful, exit code 0 [2022-03-18 14:56:49,731 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 13 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable15 [2022-03-18 14:56:49,732 INFO L403 AbstractCegarLoop]: === Iteration 17 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-18 14:56:49,732 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-18 14:56:49,732 INFO L85 PathProgramCache]: Analyzing trace with hash 1873291208, now seen corresponding path program 1 times [2022-03-18 14:56:49,732 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-18 14:56:49,732 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1071817257] [2022-03-18 14:56:49,732 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-18 14:56:49,732 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-18 14:56:49,738 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-18 14:56:49,739 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1706205281] [2022-03-18 14:56:49,739 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-18 14:56:49,739 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-18 14:56:49,739 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-18 14:56:49,746 INFO L229 MonitoredProcess]: Starting monitored process 14 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-18 14:56:49,747 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Waiting until timeout for monitored process [2022-03-18 14:56:49,789 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-18 14:56:49,790 INFO L263 TraceCheckSpWp]: Trace formula consists of 277 conjuncts, 14 conjunts are in the unsatisfiable core [2022-03-18 14:56:49,792 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-18 14:56:50,110 INFO L134 CoverageAnalysis]: Checked inductivity of 546 backedges. 32 proven. 34 refuted. 0 times theorem prover too weak. 480 trivial. 0 not checked. [2022-03-18 14:56:50,111 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-18 14:56:50,983 INFO L134 CoverageAnalysis]: Checked inductivity of 546 backedges. 32 proven. 34 refuted. 0 times theorem prover too weak. 480 trivial. 0 not checked. [2022-03-18 14:56:50,983 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-18 14:56:50,983 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1071817257] [2022-03-18 14:56:50,983 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-18 14:56:50,983 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1706205281] [2022-03-18 14:56:50,983 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1706205281] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-18 14:56:50,983 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-03-18 14:56:50,983 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7] total 10 [2022-03-18 14:56:50,984 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1381042057] [2022-03-18 14:56:50,984 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-03-18 14:56:50,984 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2022-03-18 14:56:50,984 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-18 14:56:50,984 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2022-03-18 14:56:50,984 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=20, Invalid=70, Unknown=0, NotChecked=0, Total=90 [2022-03-18 14:56:50,985 INFO L87 Difference]: Start difference. First operand 1097 states and 1457 transitions. Second operand has 10 states, 10 states have (on average 5.0) internal successors, (50), 9 states have internal predecessors, (50), 7 states have call successors, (36), 2 states have call predecessors, (36), 1 states have return successors, (33), 7 states have call predecessors, (33), 7 states have call successors, (33) [2022-03-18 14:56:51,495 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-18 14:56:51,496 INFO L93 Difference]: Finished difference Result 1103 states and 1463 transitions. [2022-03-18 14:56:51,496 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2022-03-18 14:56:51,496 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 10 states have (on average 5.0) internal successors, (50), 9 states have internal predecessors, (50), 7 states have call successors, (36), 2 states have call predecessors, (36), 1 states have return successors, (33), 7 states have call predecessors, (33), 7 states have call successors, (33) Word has length 110 [2022-03-18 14:56:51,497 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-18 14:56:51,501 INFO L225 Difference]: With dead ends: 1103 [2022-03-18 14:56:51,502 INFO L226 Difference]: Without dead ends: 1097 [2022-03-18 14:56:51,502 INFO L911 BasicCegarLoop]: 0 DeclaredPredicates, 220 GetRequests, 207 SyntacticMatches, 4 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 5 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=24, Invalid=86, Unknown=0, NotChecked=0, Total=110 [2022-03-18 14:56:51,503 INFO L912 BasicCegarLoop]: 65 mSDtfsCounter, 2 mSDsluCounter, 329 mSDsCounter, 0 mSdLazyCounter, 159 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 394 SdHoareTripleChecker+Invalid, 159 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 159 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2022-03-18 14:56:51,503 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 394 Invalid, 159 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 159 Invalid, 0 Unknown, 0 Unchecked, 0.4s Time] [2022-03-18 14:56:51,504 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1097 states. [2022-03-18 14:56:51,632 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1097 to 1097. [2022-03-18 14:56:51,634 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 1097 states, 729 states have (on average 1.242798353909465) internal successors, (906), 758 states have internal predecessors, (906), 279 states have call successors, (279), 90 states have call predecessors, (279), 88 states have return successors, (270), 248 states have call predecessors, (270), 270 states have call successors, (270) [2022-03-18 14:56:51,639 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1097 states to 1097 states and 1455 transitions. [2022-03-18 14:56:51,639 INFO L78 Accepts]: Start accepts. Automaton has 1097 states and 1455 transitions. Word has length 110 [2022-03-18 14:56:51,639 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-18 14:56:51,639 INFO L478 AbstractCegarLoop]: Abstraction has 1097 states and 1455 transitions. [2022-03-18 14:56:51,639 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 10 states have (on average 5.0) internal successors, (50), 9 states have internal predecessors, (50), 7 states have call successors, (36), 2 states have call predecessors, (36), 1 states have return successors, (33), 7 states have call predecessors, (33), 7 states have call successors, (33) [2022-03-18 14:56:51,640 INFO L276 IsEmpty]: Start isEmpty. Operand 1097 states and 1455 transitions. [2022-03-18 14:56:51,643 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 125 [2022-03-18 14:56:51,643 INFO L492 BasicCegarLoop]: Found error trace [2022-03-18 14:56:51,643 INFO L500 BasicCegarLoop]: trace histogram [19, 18, 18, 4, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-18 14:56:51,675 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Forceful destruction successful, exit code 0 [2022-03-18 14:56:51,871 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 14 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable16 [2022-03-18 14:56:51,871 INFO L403 AbstractCegarLoop]: === Iteration 18 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-18 14:56:51,872 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-18 14:56:51,872 INFO L85 PathProgramCache]: Analyzing trace with hash -1491499276, now seen corresponding path program 2 times [2022-03-18 14:56:51,872 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-18 14:56:51,872 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [472425980] [2022-03-18 14:56:51,872 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-18 14:56:51,872 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-18 14:56:51,879 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-18 14:56:51,879 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1138478245] [2022-03-18 14:56:51,879 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-03-18 14:56:51,879 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-18 14:56:51,880 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-18 14:56:51,881 INFO L229 MonitoredProcess]: Starting monitored process 15 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-18 14:56:51,895 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Waiting until timeout for monitored process [2022-03-18 14:56:51,942 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-03-18 14:56:51,942 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-18 14:56:51,943 INFO L263 TraceCheckSpWp]: Trace formula consists of 310 conjuncts, 12 conjunts are in the unsatisfiable core [2022-03-18 14:56:51,945 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-18 14:56:52,098 INFO L134 CoverageAnalysis]: Checked inductivity of 699 backedges. 102 proven. 51 refuted. 0 times theorem prover too weak. 546 trivial. 0 not checked. [2022-03-18 14:56:52,099 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-18 14:56:52,480 INFO L134 CoverageAnalysis]: Checked inductivity of 699 backedges. 69 proven. 18 refuted. 0 times theorem prover too weak. 612 trivial. 0 not checked. [2022-03-18 14:56:52,481 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-18 14:56:52,481 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [472425980] [2022-03-18 14:56:52,481 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-18 14:56:52,481 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1138478245] [2022-03-18 14:56:52,481 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1138478245] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-18 14:56:52,481 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-03-18 14:56:52,481 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 9 [2022-03-18 14:56:52,481 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [709481709] [2022-03-18 14:56:52,481 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-03-18 14:56:52,482 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2022-03-18 14:56:52,482 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-18 14:56:52,482 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2022-03-18 14:56:52,482 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=27, Invalid=45, Unknown=0, NotChecked=0, Total=72 [2022-03-18 14:56:52,483 INFO L87 Difference]: Start difference. First operand 1097 states and 1455 transitions. Second operand has 9 states, 9 states have (on average 6.222222222222222) internal successors, (56), 9 states have internal predecessors, (56), 9 states have call successors, (37), 2 states have call predecessors, (37), 2 states have return successors, (35), 9 states have call predecessors, (35), 9 states have call successors, (35) [2022-03-18 14:56:52,649 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-18 14:56:52,649 INFO L93 Difference]: Finished difference Result 1320 states and 1738 transitions. [2022-03-18 14:56:52,649 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-03-18 14:56:52,650 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 9 states have (on average 6.222222222222222) internal successors, (56), 9 states have internal predecessors, (56), 9 states have call successors, (37), 2 states have call predecessors, (37), 2 states have return successors, (35), 9 states have call predecessors, (35), 9 states have call successors, (35) Word has length 124 [2022-03-18 14:56:52,652 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-18 14:56:52,656 INFO L225 Difference]: With dead ends: 1320 [2022-03-18 14:56:52,656 INFO L226 Difference]: Without dead ends: 907 [2022-03-18 14:56:52,660 INFO L911 BasicCegarLoop]: 0 DeclaredPredicates, 247 GetRequests, 237 SyntacticMatches, 3 SemanticMatches, 7 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 6 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=27, Invalid=45, Unknown=0, NotChecked=0, Total=72 [2022-03-18 14:56:52,660 INFO L912 BasicCegarLoop]: 67 mSDtfsCounter, 4 mSDsluCounter, 180 mSDsCounter, 0 mSdLazyCounter, 73 mSolverCounterSat, 7 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 5 SdHoareTripleChecker+Valid, 247 SdHoareTripleChecker+Invalid, 80 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 7 IncrementalHoareTripleChecker+Valid, 73 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-03-18 14:56:52,661 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [5 Valid, 247 Invalid, 80 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [7 Valid, 73 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-03-18 14:56:52,662 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 907 states. [2022-03-18 14:56:52,744 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 907 to 905. [2022-03-18 14:56:52,745 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 905 states, 598 states have (on average 1.2040133779264215) internal successors, (720), 627 states have internal predecessors, (720), 221 states have call successors, (221), 87 states have call predecessors, (221), 85 states have return successors, (212), 190 states have call predecessors, (212), 212 states have call successors, (212) [2022-03-18 14:56:52,749 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 905 states to 905 states and 1153 transitions. [2022-03-18 14:56:52,750 INFO L78 Accepts]: Start accepts. Automaton has 905 states and 1153 transitions. Word has length 124 [2022-03-18 14:56:52,750 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-18 14:56:52,751 INFO L478 AbstractCegarLoop]: Abstraction has 905 states and 1153 transitions. [2022-03-18 14:56:52,751 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 9 states have (on average 6.222222222222222) internal successors, (56), 9 states have internal predecessors, (56), 9 states have call successors, (37), 2 states have call predecessors, (37), 2 states have return successors, (35), 9 states have call predecessors, (35), 9 states have call successors, (35) [2022-03-18 14:56:52,751 INFO L276 IsEmpty]: Start isEmpty. Operand 905 states and 1153 transitions. [2022-03-18 14:56:52,753 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 127 [2022-03-18 14:56:52,753 INFO L492 BasicCegarLoop]: Found error trace [2022-03-18 14:56:52,753 INFO L500 BasicCegarLoop]: trace histogram [19, 18, 18, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-18 14:56:52,779 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Forceful destruction successful, exit code 0 [2022-03-18 14:56:52,967 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable17,15 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-18 14:56:52,967 INFO L403 AbstractCegarLoop]: === Iteration 19 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-18 14:56:52,968 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-18 14:56:52,968 INFO L85 PathProgramCache]: Analyzing trace with hash 1372095454, now seen corresponding path program 3 times [2022-03-18 14:56:52,968 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-18 14:56:52,968 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [815728363] [2022-03-18 14:56:52,968 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-18 14:56:52,968 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-18 14:56:52,975 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-18 14:56:52,976 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1802210045] [2022-03-18 14:56:52,976 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2022-03-18 14:56:52,976 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-18 14:56:52,976 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-18 14:56:52,979 INFO L229 MonitoredProcess]: Starting monitored process 16 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-18 14:56:52,981 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Waiting until timeout for monitored process [2022-03-18 14:56:53,081 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2022-03-18 14:56:53,081 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-18 14:56:53,083 INFO L263 TraceCheckSpWp]: Trace formula consists of 216 conjuncts, 24 conjunts are in the unsatisfiable core [2022-03-18 14:56:53,085 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-18 14:56:53,361 WARN L907 QuantifierPusher]: no eliminatee completely removed, nonetheless the elimination was considered successful [2022-03-18 14:56:53,458 WARN L907 QuantifierPusher]: no eliminatee completely removed, nonetheless the elimination was considered successful [2022-03-18 14:56:53,557 WARN L907 QuantifierPusher]: no eliminatee completely removed, nonetheless the elimination was considered successful [2022-03-18 14:56:53,776 INFO L134 CoverageAnalysis]: Checked inductivity of 711 backedges. 145 proven. 2 refuted. 0 times theorem prover too weak. 564 trivial. 0 not checked. [2022-03-18 14:56:53,776 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-18 14:57:06,145 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-18 14:57:06,145 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [815728363] [2022-03-18 14:57:06,145 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-18 14:57:06,146 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1802210045] [2022-03-18 14:57:06,146 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1802210045] provided 0 perfect and 1 imperfect interpolant sequences [2022-03-18 14:57:06,146 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-03-18 14:57:06,146 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9] total 9 [2022-03-18 14:57:06,146 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [651657343] [2022-03-18 14:57:06,146 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2022-03-18 14:57:06,146 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2022-03-18 14:57:06,146 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-18 14:57:06,147 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2022-03-18 14:57:06,147 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=34, Invalid=122, Unknown=0, NotChecked=0, Total=156 [2022-03-18 14:57:06,147 INFO L87 Difference]: Start difference. First operand 905 states and 1153 transitions. Second operand has 9 states, 9 states have (on average 2.6666666666666665) internal successors, (24), 8 states have internal predecessors, (24), 3 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (8), 4 states have call predecessors, (8), 3 states have call successors, (8) [2022-03-18 14:57:06,309 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-18 14:57:06,310 INFO L93 Difference]: Finished difference Result 935 states and 1182 transitions. [2022-03-18 14:57:06,310 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2022-03-18 14:57:06,310 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 9 states have (on average 2.6666666666666665) internal successors, (24), 8 states have internal predecessors, (24), 3 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (8), 4 states have call predecessors, (8), 3 states have call successors, (8) Word has length 126 [2022-03-18 14:57:06,310 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-18 14:57:06,314 INFO L225 Difference]: With dead ends: 935 [2022-03-18 14:57:06,315 INFO L226 Difference]: Without dead ends: 921 [2022-03-18 14:57:06,315 INFO L911 BasicCegarLoop]: 0 DeclaredPredicates, 136 GetRequests, 120 SyntacticMatches, 3 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 31 ImplicationChecksByTransitivity, 2.6s TimeCoverageRelationStatistics Valid=45, Invalid=165, Unknown=0, NotChecked=0, Total=210 [2022-03-18 14:57:06,316 INFO L912 BasicCegarLoop]: 23 mSDtfsCounter, 19 mSDsluCounter, 95 mSDsCounter, 0 mSdLazyCounter, 81 mSolverCounterSat, 10 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 24 SdHoareTripleChecker+Valid, 118 SdHoareTripleChecker+Invalid, 91 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 10 IncrementalHoareTripleChecker+Valid, 81 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-03-18 14:57:06,316 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [24 Valid, 118 Invalid, 91 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [10 Valid, 81 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-03-18 14:57:06,317 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 921 states. [2022-03-18 14:57:06,403 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 921 to 695. [2022-03-18 14:57:06,404 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 695 states, 468 states have (on average 1.1752136752136753) internal successors, (550), 470 states have internal predecessors, (550), 153 states have call successors, (153), 75 states have call predecessors, (153), 73 states have return successors, (150), 149 states have call predecessors, (150), 150 states have call successors, (150) [2022-03-18 14:57:06,408 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 695 states to 695 states and 853 transitions. [2022-03-18 14:57:06,408 INFO L78 Accepts]: Start accepts. Automaton has 695 states and 853 transitions. Word has length 126 [2022-03-18 14:57:06,408 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-18 14:57:06,408 INFO L478 AbstractCegarLoop]: Abstraction has 695 states and 853 transitions. [2022-03-18 14:57:06,409 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 9 states have (on average 2.6666666666666665) internal successors, (24), 8 states have internal predecessors, (24), 3 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (8), 4 states have call predecessors, (8), 3 states have call successors, (8) [2022-03-18 14:57:06,409 INFO L276 IsEmpty]: Start isEmpty. Operand 695 states and 853 transitions. [2022-03-18 14:57:06,410 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 129 [2022-03-18 14:57:06,410 INFO L492 BasicCegarLoop]: Found error trace [2022-03-18 14:57:06,410 INFO L500 BasicCegarLoop]: trace histogram [20, 19, 19, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-18 14:57:06,436 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Forceful destruction successful, exit code 0 [2022-03-18 14:57:06,623 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable18,16 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-18 14:57:06,623 INFO L403 AbstractCegarLoop]: === Iteration 20 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-18 14:57:06,623 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-18 14:57:06,623 INFO L85 PathProgramCache]: Analyzing trace with hash 388866286, now seen corresponding path program 3 times [2022-03-18 14:57:06,624 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-18 14:57:06,624 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [750405171] [2022-03-18 14:57:06,624 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-18 14:57:06,624 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-18 14:57:06,631 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-18 14:57:06,632 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1398826120] [2022-03-18 14:57:06,632 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2022-03-18 14:57:06,632 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-18 14:57:06,633 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-18 14:57:06,634 INFO L229 MonitoredProcess]: Starting monitored process 17 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-18 14:57:06,635 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Waiting until timeout for monitored process [2022-03-18 14:57:06,685 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2022-03-18 14:57:06,686 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-18 14:57:06,687 INFO L263 TraceCheckSpWp]: Trace formula consists of 188 conjuncts, 12 conjunts are in the unsatisfiable core [2022-03-18 14:57:06,689 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-18 14:57:06,931 INFO L134 CoverageAnalysis]: Checked inductivity of 774 backedges. 90 proven. 4 refuted. 0 times theorem prover too weak. 680 trivial. 0 not checked. [2022-03-18 14:57:06,931 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-18 14:57:07,159 INFO L134 CoverageAnalysis]: Checked inductivity of 774 backedges. 90 proven. 4 refuted. 0 times theorem prover too weak. 680 trivial. 0 not checked. [2022-03-18 14:57:07,159 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-18 14:57:07,160 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [750405171] [2022-03-18 14:57:07,160 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-18 14:57:07,160 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1398826120] [2022-03-18 14:57:07,160 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1398826120] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-18 14:57:07,160 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-03-18 14:57:07,160 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 8] total 12 [2022-03-18 14:57:07,160 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [580423443] [2022-03-18 14:57:07,160 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-03-18 14:57:07,161 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2022-03-18 14:57:07,162 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-18 14:57:07,162 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2022-03-18 14:57:07,162 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=31, Invalid=101, Unknown=0, NotChecked=0, Total=132 [2022-03-18 14:57:07,163 INFO L87 Difference]: Start difference. First operand 695 states and 853 transitions. Second operand has 12 states, 10 states have (on average 3.3) internal successors, (33), 9 states have internal predecessors, (33), 4 states have call successors, (16), 2 states have call predecessors, (16), 2 states have return successors, (15), 6 states have call predecessors, (15), 4 states have call successors, (15) [2022-03-18 14:57:07,334 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-18 14:57:07,335 INFO L93 Difference]: Finished difference Result 771 states and 912 transitions. [2022-03-18 14:57:07,335 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2022-03-18 14:57:07,335 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 10 states have (on average 3.3) internal successors, (33), 9 states have internal predecessors, (33), 4 states have call successors, (16), 2 states have call predecessors, (16), 2 states have return successors, (15), 6 states have call predecessors, (15), 4 states have call successors, (15) Word has length 128 [2022-03-18 14:57:07,336 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-18 14:57:07,338 INFO L225 Difference]: With dead ends: 771 [2022-03-18 14:57:07,339 INFO L226 Difference]: Without dead ends: 755 [2022-03-18 14:57:07,339 INFO L911 BasicCegarLoop]: 0 DeclaredPredicates, 259 GetRequests, 245 SyntacticMatches, 1 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 27 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=51, Invalid=159, Unknown=0, NotChecked=0, Total=210 [2022-03-18 14:57:07,340 INFO L912 BasicCegarLoop]: 23 mSDtfsCounter, 27 mSDsluCounter, 152 mSDsCounter, 0 mSdLazyCounter, 152 mSolverCounterSat, 16 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 32 SdHoareTripleChecker+Valid, 175 SdHoareTripleChecker+Invalid, 168 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 16 IncrementalHoareTripleChecker+Valid, 152 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-03-18 14:57:07,340 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [32 Valid, 175 Invalid, 168 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [16 Valid, 152 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-03-18 14:57:07,341 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 755 states. [2022-03-18 14:57:07,413 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 755 to 539. [2022-03-18 14:57:07,414 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 539 states, 362 states have (on average 1.1049723756906078) internal successors, (400), 373 states have internal predecessors, (400), 103 states have call successors, (103), 74 states have call predecessors, (103), 73 states have return successors, (101), 91 states have call predecessors, (101), 101 states have call successors, (101) [2022-03-18 14:57:07,417 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 539 states to 539 states and 604 transitions. [2022-03-18 14:57:07,417 INFO L78 Accepts]: Start accepts. Automaton has 539 states and 604 transitions. Word has length 128 [2022-03-18 14:57:07,417 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-18 14:57:07,417 INFO L478 AbstractCegarLoop]: Abstraction has 539 states and 604 transitions. [2022-03-18 14:57:07,417 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 10 states have (on average 3.3) internal successors, (33), 9 states have internal predecessors, (33), 4 states have call successors, (16), 2 states have call predecessors, (16), 2 states have return successors, (15), 6 states have call predecessors, (15), 4 states have call successors, (15) [2022-03-18 14:57:07,418 INFO L276 IsEmpty]: Start isEmpty. Operand 539 states and 604 transitions. [2022-03-18 14:57:07,420 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 225 [2022-03-18 14:57:07,420 INFO L492 BasicCegarLoop]: Found error trace [2022-03-18 14:57:07,420 INFO L500 BasicCegarLoop]: trace histogram [33, 32, 32, 11, 10, 10, 10, 10, 10, 10, 10, 4, 4, 4, 4, 4, 4, 4, 4, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-18 14:57:07,447 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Forceful destruction successful, exit code 0 [2022-03-18 14:57:07,638 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable19,17 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-18 14:57:07,638 INFO L403 AbstractCegarLoop]: === Iteration 21 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-18 14:57:07,638 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-18 14:57:07,638 INFO L85 PathProgramCache]: Analyzing trace with hash -1492475124, now seen corresponding path program 2 times [2022-03-18 14:57:07,638 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-18 14:57:07,639 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2070752857] [2022-03-18 14:57:07,639 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-18 14:57:07,639 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-18 14:57:07,648 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-18 14:57:07,649 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1088630662] [2022-03-18 14:57:07,649 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-03-18 14:57:07,649 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-18 14:57:07,649 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-18 14:57:07,651 INFO L229 MonitoredProcess]: Starting monitored process 18 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-18 14:57:07,653 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (18)] Waiting until timeout for monitored process [2022-03-18 14:57:07,728 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-03-18 14:57:07,729 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-18 14:57:07,731 INFO L263 TraceCheckSpWp]: Trace formula consists of 549 conjuncts, 33 conjunts are in the unsatisfiable core [2022-03-18 14:57:07,735 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-18 14:57:08,180 INFO L134 CoverageAnalysis]: Checked inductivity of 2374 backedges. 64 proven. 2222 refuted. 0 times theorem prover too weak. 88 trivial. 0 not checked. [2022-03-18 14:57:08,181 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-18 14:57:08,766 INFO L134 CoverageAnalysis]: Checked inductivity of 2374 backedges. 64 proven. 326 refuted. 0 times theorem prover too weak. 1984 trivial. 0 not checked. [2022-03-18 14:57:08,766 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-18 14:57:08,766 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2070752857] [2022-03-18 14:57:08,767 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-18 14:57:08,767 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1088630662] [2022-03-18 14:57:08,767 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1088630662] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-18 14:57:08,767 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-03-18 14:57:08,767 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [18, 18] total 34 [2022-03-18 14:57:08,767 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [705864974] [2022-03-18 14:57:08,767 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-03-18 14:57:08,768 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 34 states [2022-03-18 14:57:08,768 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-18 14:57:08,768 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 34 interpolants. [2022-03-18 14:57:08,769 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=501, Invalid=621, Unknown=0, NotChecked=0, Total=1122 [2022-03-18 14:57:08,769 INFO L87 Difference]: Start difference. First operand 539 states and 604 transitions. Second operand has 34 states, 34 states have (on average 4.764705882352941) internal successors, (162), 34 states have internal predecessors, (162), 32 states have call successors, (68), 18 states have call predecessors, (68), 17 states have return successors, (66), 30 states have call predecessors, (66), 29 states have call successors, (66) [2022-03-18 14:57:09,979 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-18 14:57:09,980 INFO L93 Difference]: Finished difference Result 1289 states and 1514 transitions. [2022-03-18 14:57:09,980 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 58 states. [2022-03-18 14:57:09,980 INFO L78 Accepts]: Start accepts. Automaton has has 34 states, 34 states have (on average 4.764705882352941) internal successors, (162), 34 states have internal predecessors, (162), 32 states have call successors, (68), 18 states have call predecessors, (68), 17 states have return successors, (66), 30 states have call predecessors, (66), 29 states have call successors, (66) Word has length 224 [2022-03-18 14:57:09,981 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-18 14:57:09,987 INFO L225 Difference]: With dead ends: 1289 [2022-03-18 14:57:09,987 INFO L226 Difference]: Without dead ends: 1276 [2022-03-18 14:57:09,989 INFO L911 BasicCegarLoop]: 0 DeclaredPredicates, 472 GetRequests, 415 SyntacticMatches, 0 SemanticMatches, 57 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 434 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=1212, Invalid=2210, Unknown=0, NotChecked=0, Total=3422 [2022-03-18 14:57:09,989 INFO L912 BasicCegarLoop]: 169 mSDtfsCounter, 786 mSDsluCounter, 668 mSDsCounter, 0 mSdLazyCounter, 617 mSolverCounterSat, 724 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 786 SdHoareTripleChecker+Valid, 837 SdHoareTripleChecker+Invalid, 1341 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 724 IncrementalHoareTripleChecker+Valid, 617 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.7s IncrementalHoareTripleChecker+Time [2022-03-18 14:57:09,990 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [786 Valid, 837 Invalid, 1341 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [724 Valid, 617 Invalid, 0 Unknown, 0 Unchecked, 0.7s Time] [2022-03-18 14:57:09,991 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1276 states. [2022-03-18 14:57:10,148 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1276 to 1275. [2022-03-18 14:57:10,151 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 1275 states, 858 states have (on average 1.118881118881119) internal successors, (960), 885 states have internal predecessors, (960), 247 states have call successors, (247), 170 states have call predecessors, (247), 169 states have return successors, (245), 219 states have call predecessors, (245), 245 states have call successors, (245) [2022-03-18 14:57:10,154 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1275 states to 1275 states and 1452 transitions. [2022-03-18 14:57:10,154 INFO L78 Accepts]: Start accepts. Automaton has 1275 states and 1452 transitions. Word has length 224 [2022-03-18 14:57:10,155 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-18 14:57:10,155 INFO L478 AbstractCegarLoop]: Abstraction has 1275 states and 1452 transitions. [2022-03-18 14:57:10,155 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 34 states, 34 states have (on average 4.764705882352941) internal successors, (162), 34 states have internal predecessors, (162), 32 states have call successors, (68), 18 states have call predecessors, (68), 17 states have return successors, (66), 30 states have call predecessors, (66), 29 states have call successors, (66) [2022-03-18 14:57:10,155 INFO L276 IsEmpty]: Start isEmpty. Operand 1275 states and 1452 transitions. [2022-03-18 14:57:10,163 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 449 [2022-03-18 14:57:10,163 INFO L492 BasicCegarLoop]: Found error trace [2022-03-18 14:57:10,163 INFO L500 BasicCegarLoop]: trace histogram [65, 64, 64, 27, 26, 26, 26, 26, 26, 26, 26, 4, 4, 4, 4, 4, 4, 4, 4, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-18 14:57:10,195 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-03-18 14:57:10,379 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable20,18 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-18 14:57:10,380 INFO L403 AbstractCegarLoop]: === Iteration 22 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-18 14:57:10,380 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-18 14:57:10,380 INFO L85 PathProgramCache]: Analyzing trace with hash -1239263796, now seen corresponding path program 3 times [2022-03-18 14:57:10,380 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-18 14:57:10,380 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [430782715] [2022-03-18 14:57:10,380 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-18 14:57:10,380 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-18 14:57:10,398 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-18 14:57:10,398 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1328151683] [2022-03-18 14:57:10,398 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2022-03-18 14:57:10,398 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-18 14:57:10,398 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-18 14:57:10,400 INFO L229 MonitoredProcess]: Starting monitored process 19 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-18 14:57:10,401 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (19)] Waiting until timeout for monitored process [2022-03-18 14:57:13,169 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 42 check-sat command(s) [2022-03-18 14:57:13,169 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-18 14:57:13,185 INFO L263 TraceCheckSpWp]: Trace formula consists of 1068 conjuncts, 65 conjunts are in the unsatisfiable core [2022-03-18 14:57:13,193 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-18 14:57:14,212 INFO L134 CoverageAnalysis]: Checked inductivity of 10230 backedges. 128 proven. 9950 refuted. 0 times theorem prover too weak. 152 trivial. 0 not checked. [2022-03-18 14:57:14,213 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-18 14:57:15,849 INFO L134 CoverageAnalysis]: Checked inductivity of 10230 backedges. 128 proven. 2038 refuted. 0 times theorem prover too weak. 8064 trivial. 0 not checked. [2022-03-18 14:57:15,849 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-18 14:57:15,849 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [430782715] [2022-03-18 14:57:15,849 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-18 14:57:15,849 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1328151683] [2022-03-18 14:57:15,849 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1328151683] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-18 14:57:15,849 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-03-18 14:57:15,849 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [34, 34] total 66 [2022-03-18 14:57:15,849 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [7328285] [2022-03-18 14:57:15,849 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-03-18 14:57:15,850 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 66 states [2022-03-18 14:57:15,850 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-18 14:57:15,851 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 66 interpolants. [2022-03-18 14:57:15,852 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=2021, Invalid=2269, Unknown=0, NotChecked=0, Total=4290 [2022-03-18 14:57:15,853 INFO L87 Difference]: Start difference. First operand 1275 states and 1452 transitions. Second operand has 66 states, 66 states have (on average 5.121212121212121) internal successors, (338), 66 states have internal predecessors, (338), 64 states have call successors, (132), 34 states have call predecessors, (132), 33 states have return successors, (130), 62 states have call predecessors, (130), 61 states have call successors, (130) [2022-03-18 14:57:19,648 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-18 14:57:19,649 INFO L93 Difference]: Finished difference Result 2761 states and 3258 transitions. [2022-03-18 14:57:19,655 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 122 states. [2022-03-18 14:57:19,656 INFO L78 Accepts]: Start accepts. Automaton has has 66 states, 66 states have (on average 5.121212121212121) internal successors, (338), 66 states have internal predecessors, (338), 64 states have call successors, (132), 34 states have call predecessors, (132), 33 states have return successors, (130), 62 states have call predecessors, (130), 61 states have call successors, (130) Word has length 448 [2022-03-18 14:57:19,657 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-18 14:57:19,670 INFO L225 Difference]: With dead ends: 2761 [2022-03-18 14:57:19,670 INFO L226 Difference]: Without dead ends: 2748 [2022-03-18 14:57:19,675 INFO L911 BasicCegarLoop]: 0 DeclaredPredicates, 952 GetRequests, 831 SyntacticMatches, 0 SemanticMatches, 121 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2122 ImplicationChecksByTransitivity, 2.4s TimeCoverageRelationStatistics Valid=5468, Invalid=9538, Unknown=0, NotChecked=0, Total=15006 [2022-03-18 14:57:19,676 INFO L912 BasicCegarLoop]: 329 mSDtfsCounter, 2083 mSDsluCounter, 1328 mSDsCounter, 0 mSdLazyCounter, 1684 mSolverCounterSat, 1749 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2083 SdHoareTripleChecker+Valid, 1657 SdHoareTripleChecker+Invalid, 3433 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1749 IncrementalHoareTripleChecker+Valid, 1684 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.6s IncrementalHoareTripleChecker+Time [2022-03-18 14:57:19,676 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [2083 Valid, 1657 Invalid, 3433 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1749 Valid, 1684 Invalid, 0 Unknown, 0 Unchecked, 1.6s Time] [2022-03-18 14:57:19,679 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 2748 states. [2022-03-18 14:57:20,019 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 2748 to 2747. [2022-03-18 14:57:20,024 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 2747 states, 1850 states have (on average 1.1243243243243244) internal successors, (2080), 1909 states have internal predecessors, (2080), 535 states have call successors, (535), 362 states have call predecessors, (535), 361 states have return successors, (533), 475 states have call predecessors, (533), 533 states have call successors, (533) [2022-03-18 14:57:20,031 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 2747 states to 2747 states and 3148 transitions. [2022-03-18 14:57:20,032 INFO L78 Accepts]: Start accepts. Automaton has 2747 states and 3148 transitions. Word has length 448 [2022-03-18 14:57:20,034 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-18 14:57:20,034 INFO L478 AbstractCegarLoop]: Abstraction has 2747 states and 3148 transitions. [2022-03-18 14:57:20,034 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 66 states, 66 states have (on average 5.121212121212121) internal successors, (338), 66 states have internal predecessors, (338), 64 states have call successors, (132), 34 states have call predecessors, (132), 33 states have return successors, (130), 62 states have call predecessors, (130), 61 states have call successors, (130) [2022-03-18 14:57:20,034 INFO L276 IsEmpty]: Start isEmpty. Operand 2747 states and 3148 transitions. [2022-03-18 14:57:20,062 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 897 [2022-03-18 14:57:20,062 INFO L492 BasicCegarLoop]: Found error trace [2022-03-18 14:57:20,063 INFO L500 BasicCegarLoop]: trace histogram [129, 128, 128, 59, 58, 58, 58, 58, 58, 58, 58, 4, 4, 4, 4, 4, 4, 4, 4, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-18 14:57:20,079 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (19)] Forceful destruction successful, exit code 0 [2022-03-18 14:57:20,276 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable21,19 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-18 14:57:20,277 INFO L403 AbstractCegarLoop]: === Iteration 23 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-18 14:57:20,277 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-18 14:57:20,277 INFO L85 PathProgramCache]: Analyzing trace with hash -583353524, now seen corresponding path program 4 times [2022-03-18 14:57:20,277 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-18 14:57:20,277 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1696188921] [2022-03-18 14:57:20,277 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-18 14:57:20,277 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-18 14:57:20,306 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-18 14:57:20,306 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [629487628] [2022-03-18 14:57:20,306 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2022-03-18 14:57:20,306 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-18 14:57:20,307 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-18 14:57:20,308 INFO L229 MonitoredProcess]: Starting monitored process 20 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-18 14:57:20,312 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (20)] Waiting until timeout for monitored process