/usr/bin/java -Xmx8000000000 -Xss4m -jar ./plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata ./data --core.log.level.for.class de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=WARN -tc ../../../trunk/examples/toolchains/AutomizerCTransformed.xml -s ../../../trunk/examples/settings/automizer/LoopAccelerationJordanC.epf -i ../../../trunk/examples/svcomp/nla-digbench-scaling/egcd-ll_unwindbound100.c -------------------------------------------------------------------------------- This is Ultimate 0.2.2-dev-34549b5 [2022-04-06 06:41:20,341 INFO L177 SettingsManager]: Resetting all preferences to default values... [2022-04-06 06:41:20,343 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2022-04-06 06:41:20,366 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2022-04-06 06:41:20,366 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2022-04-06 06:41:20,367 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2022-04-06 06:41:20,369 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2022-04-06 06:41:20,370 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2022-04-06 06:41:20,372 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2022-04-06 06:41:20,373 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2022-04-06 06:41:20,374 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2022-04-06 06:41:20,375 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2022-04-06 06:41:20,375 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2022-04-06 06:41:20,376 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2022-04-06 06:41:20,377 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2022-04-06 06:41:20,378 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2022-04-06 06:41:20,379 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2022-04-06 06:41:20,379 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2022-04-06 06:41:20,381 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2022-04-06 06:41:20,382 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2022-04-06 06:41:20,384 INFO L181 SettingsManager]: Resetting HornVerifier preferences to default values [2022-04-06 06:41:20,388 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2022-04-06 06:41:20,389 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2022-04-06 06:41:20,390 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2022-04-06 06:41:20,390 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2022-04-06 06:41:20,393 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2022-04-06 06:41:20,393 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2022-04-06 06:41:20,393 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2022-04-06 06:41:20,394 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2022-04-06 06:41:20,394 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2022-04-06 06:41:20,395 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2022-04-06 06:41:20,395 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2022-04-06 06:41:20,396 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2022-04-06 06:41:20,397 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2022-04-06 06:41:20,397 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2022-04-06 06:41:20,398 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2022-04-06 06:41:20,399 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2022-04-06 06:41:20,399 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2022-04-06 06:41:20,399 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2022-04-06 06:41:20,400 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2022-04-06 06:41:20,401 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2022-04-06 06:41:20,410 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2022-04-06 06:41:20,410 INFO L101 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/automizer/LoopAccelerationJordanC.epf [2022-04-06 06:41:20,425 INFO L113 SettingsManager]: Loading preferences was successful [2022-04-06 06:41:20,426 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2022-04-06 06:41:20,427 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2022-04-06 06:41:20,427 INFO L138 SettingsManager]: * sizeof long=4 [2022-04-06 06:41:20,427 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2022-04-06 06:41:20,427 INFO L138 SettingsManager]: * sizeof POINTER=4 [2022-04-06 06:41:20,427 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2022-04-06 06:41:20,428 INFO L138 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2022-04-06 06:41:20,428 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2022-04-06 06:41:20,428 INFO L138 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2022-04-06 06:41:20,429 INFO L138 SettingsManager]: * sizeof long double=12 [2022-04-06 06:41:20,429 INFO L138 SettingsManager]: * Check if freed pointer was valid=false [2022-04-06 06:41:20,429 INFO L138 SettingsManager]: * Use constant arrays=true [2022-04-06 06:41:20,429 INFO L138 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2022-04-06 06:41:20,429 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2022-04-06 06:41:20,429 INFO L138 SettingsManager]: * Size of a code block=SequenceOfStatements [2022-04-06 06:41:20,430 INFO L138 SettingsManager]: * To the following directory=./dump/ [2022-04-06 06:41:20,430 INFO L138 SettingsManager]: * SMT solver=External_DefaultMode [2022-04-06 06:41:20,430 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-04-06 06:41:20,430 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2022-04-06 06:41:20,430 INFO L138 SettingsManager]: * Trace refinement strategy=CAMEL [2022-04-06 06:41:20,431 INFO L136 SettingsManager]: Preferences of IcfgTransformer differ from their defaults: [2022-04-06 06:41:20,431 INFO L138 SettingsManager]: * TransformationType=LOOP_ACCELERATION_JORDAN WARNING: An illegal reflective access operation has occurred WARNING: Illegal reflective access by com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 (file:/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/com.sun.xml.bind_2.2.0.v201505121915.jar) to method java.lang.ClassLoader.defineClass(java.lang.String,byte[],int,int) WARNING: Please consider reporting this to the maintainers of com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 WARNING: Use --illegal-access=warn to enable warnings of further illegal reflective access operations WARNING: All illegal access operations will be denied in a future release Applying setting for plugin de.uni_freiburg.informatik.ultimate.core: Log level for class -> de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=WARN; [2022-04-06 06:41:20,658 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2022-04-06 06:41:20,681 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2022-04-06 06:41:20,683 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2022-04-06 06:41:20,684 INFO L271 PluginConnector]: Initializing CDTParser... [2022-04-06 06:41:20,686 INFO L275 PluginConnector]: CDTParser initialized [2022-04-06 06:41:20,687 INFO L432 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/svcomp/nla-digbench-scaling/egcd-ll_unwindbound100.c [2022-04-06 06:41:20,744 INFO L220 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/25a213411/1831dc1d1b9b4f06931bf302eeb32c49/FLAG7a3f4f2ca [2022-04-06 06:41:21,071 INFO L306 CDTParser]: Found 1 translation units. [2022-04-06 06:41:21,072 INFO L160 CDTParser]: Scanning /storage/repos/ultimate/trunk/examples/svcomp/nla-digbench-scaling/egcd-ll_unwindbound100.c [2022-04-06 06:41:21,076 INFO L349 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/25a213411/1831dc1d1b9b4f06931bf302eeb32c49/FLAG7a3f4f2ca [2022-04-06 06:41:21,507 INFO L357 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/25a213411/1831dc1d1b9b4f06931bf302eeb32c49 [2022-04-06 06:41:21,509 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2022-04-06 06:41:21,510 INFO L131 ToolchainWalker]: Walking toolchain with 5 elements. [2022-04-06 06:41:21,511 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2022-04-06 06:41:21,511 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2022-04-06 06:41:21,514 INFO L275 PluginConnector]: CACSL2BoogieTranslator initialized [2022-04-06 06:41:21,514 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 06.04 06:41:21" (1/1) ... [2022-04-06 06:41:21,515 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@27e1743b and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 06:41:21, skipping insertion in model container [2022-04-06 06:41:21,515 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 06.04 06:41:21" (1/1) ... [2022-04-06 06:41:21,520 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2022-04-06 06:41:21,533 INFO L178 MainTranslator]: Built tables and reachable declarations [2022-04-06 06:41:21,659 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/egcd-ll_unwindbound100.c[489,502] [2022-04-06 06:41:21,674 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-04-06 06:41:21,679 INFO L203 MainTranslator]: Completed pre-run [2022-04-06 06:41:21,687 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/egcd-ll_unwindbound100.c[489,502] [2022-04-06 06:41:21,693 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-04-06 06:41:21,705 INFO L208 MainTranslator]: Completed translation [2022-04-06 06:41:21,705 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 06:41:21 WrapperNode [2022-04-06 06:41:21,705 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2022-04-06 06:41:21,706 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2022-04-06 06:41:21,706 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2022-04-06 06:41:21,706 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2022-04-06 06:41:21,714 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 06:41:21" (1/1) ... [2022-04-06 06:41:21,714 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 06:41:21" (1/1) ... [2022-04-06 06:41:21,719 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 06:41:21" (1/1) ... [2022-04-06 06:41:21,719 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 06:41:21" (1/1) ... [2022-04-06 06:41:21,723 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 06:41:21" (1/1) ... [2022-04-06 06:41:21,726 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 06:41:21" (1/1) ... [2022-04-06 06:41:21,727 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 06:41:21" (1/1) ... [2022-04-06 06:41:21,728 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2022-04-06 06:41:21,729 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2022-04-06 06:41:21,729 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2022-04-06 06:41:21,729 INFO L275 PluginConnector]: RCFGBuilder initialized [2022-04-06 06:41:21,740 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 06:41:21" (1/1) ... [2022-04-06 06:41:21,746 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-04-06 06:41:21,756 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 06:41:21,765 INFO L229 MonitoredProcess]: Starting monitored process 1 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) [2022-04-06 06:41:21,766 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Waiting until timeout for monitored process [2022-04-06 06:41:21,793 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.init [2022-04-06 06:41:21,794 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2022-04-06 06:41:21,794 INFO L138 BoogieDeclarations]: Found implementation of procedure reach_error [2022-04-06 06:41:21,794 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2022-04-06 06:41:21,794 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2022-04-06 06:41:21,794 INFO L138 BoogieDeclarations]: Found implementation of procedure main [2022-04-06 06:41:21,794 INFO L130 BoogieDeclarations]: Found specification of procedure abort [2022-04-06 06:41:21,794 INFO L130 BoogieDeclarations]: Found specification of procedure __assert_fail [2022-04-06 06:41:21,794 INFO L130 BoogieDeclarations]: Found specification of procedure reach_error [2022-04-06 06:41:21,795 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2022-04-06 06:41:21,795 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_nondet_int [2022-04-06 06:41:21,795 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2022-04-06 06:41:21,795 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2022-04-06 06:41:21,795 INFO L130 BoogieDeclarations]: Found specification of procedure main [2022-04-06 06:41:21,795 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.init [2022-04-06 06:41:21,795 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2022-04-06 06:41:21,796 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2022-04-06 06:41:21,796 INFO L130 BoogieDeclarations]: Found specification of procedure write~int [2022-04-06 06:41:21,796 INFO L130 BoogieDeclarations]: Found specification of procedure read~int [2022-04-06 06:41:21,796 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2022-04-06 06:41:21,849 INFO L234 CfgBuilder]: Building ICFG [2022-04-06 06:41:21,850 INFO L260 CfgBuilder]: Building CFG for each procedure with an implementation [2022-04-06 06:41:21,960 INFO L275 CfgBuilder]: Performing block encoding [2022-04-06 06:41:21,965 INFO L294 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2022-04-06 06:41:21,965 INFO L299 CfgBuilder]: Removed 1 assume(true) statements. [2022-04-06 06:41:21,967 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 06.04 06:41:21 BoogieIcfgContainer [2022-04-06 06:41:21,967 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2022-04-06 06:41:21,968 INFO L113 PluginConnector]: ------------------------IcfgTransformer---------------------------- [2022-04-06 06:41:21,968 INFO L271 PluginConnector]: Initializing IcfgTransformer... [2022-04-06 06:41:21,969 INFO L275 PluginConnector]: IcfgTransformer initialized [2022-04-06 06:41:21,971 INFO L185 PluginConnector]: Executing the observer IcfgTransformationObserver from plugin IcfgTransformer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 06.04 06:41:21" (1/1) ... [2022-04-06 06:41:21,973 INFO L168 ansformationObserver]: Applying ICFG transformation LOOP_ACCELERATION_JORDAN [2022-04-06 06:41:22,010 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.icfgtransformation CFG 06.04 06:41:22 BasicIcfg [2022-04-06 06:41:22,010 INFO L132 PluginConnector]: ------------------------ END IcfgTransformer---------------------------- [2022-04-06 06:41:22,012 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2022-04-06 06:41:22,012 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2022-04-06 06:41:22,024 INFO L275 PluginConnector]: TraceAbstraction initialized [2022-04-06 06:41:22,024 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 06.04 06:41:21" (1/4) ... [2022-04-06 06:41:22,025 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@4a30dbe1 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 06.04 06:41:22, skipping insertion in model container [2022-04-06 06:41:22,025 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 06:41:21" (2/4) ... [2022-04-06 06:41:22,026 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@4a30dbe1 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 06.04 06:41:22, skipping insertion in model container [2022-04-06 06:41:22,026 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 06.04 06:41:21" (3/4) ... [2022-04-06 06:41:22,026 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@4a30dbe1 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 06.04 06:41:22, skipping insertion in model container [2022-04-06 06:41:22,026 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.icfgtransformation CFG 06.04 06:41:22" (4/4) ... [2022-04-06 06:41:22,027 INFO L111 eAbstractionObserver]: Analyzing ICFG egcd-ll_unwindbound100.cJordan [2022-04-06 06:41:22,031 INFO L203 ceAbstractionStarter]: Automizer settings: Hoare:false NWA Interpolation:ForwardPredicates Determinization: PREDICATE_ABSTRACTION [2022-04-06 06:41:22,031 INFO L162 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2022-04-06 06:41:22,062 INFO L339 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2022-04-06 06:41:22,068 INFO L340 AbstractCegarLoop]: Settings: SEPARATE_VIOLATION_CHECK=true, mInterprocedural=true, mMaxIterations=1000000, mWatchIteration=1000000, mArtifact=RCFG, mInterpolation=ForwardPredicates, mInterpolantAutomaton=STRAIGHT_LINE, mDumpAutomata=false, mAutomataFormat=ATS_NUMERATE, mDumpPath=., mDeterminiation=PREDICATE_ABSTRACTION, mMinimize=MINIMIZE_SEVPA, mHoare=false, mAutomataTypeConcurrency=FINITE_AUTOMATA, mHoareTripleChecks=INCREMENTAL, mHoareAnnotationPositions=All, mDumpOnlyReuseAutomata=false, mLimitTraceHistogram=0, mErrorLocTimeLimit=0, mLimitPathProgramCount=0, mCollectInterpolantStatistics=true, mHeuristicEmptinessCheck=false, mHeuristicEmptinessCheckAStarHeuristic=ZERO, mHeuristicEmptinessCheckAStarHeuristicRandomSeed=1337, mHeuristicEmptinessCheckSmtFeatureScoringMethod=DAGSIZE, mSMTFeatureExtraction=false, mSMTFeatureExtractionDumpPath=., mOverrideInterpolantAutomaton=false, mMcrInterpolantMethod=WP [2022-04-06 06:41:22,069 INFO L341 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2022-04-06 06:41:22,088 INFO L276 IsEmpty]: Start isEmpty. Operand has 35 states, 18 states have (on average 1.3888888888888888) internal successors, (25), 19 states have internal predecessors, (25), 11 states have call successors, (11), 4 states have call predecessors, (11), 4 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2022-04-06 06:41:22,095 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 23 [2022-04-06 06:41:22,095 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 06:41:22,096 INFO L499 BasicCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 06:41:22,096 INFO L403 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 06:41:22,101 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 06:41:22,101 INFO L85 PathProgramCache]: Analyzing trace with hash 2051628946, now seen corresponding path program 1 times [2022-04-06 06:41:22,109 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 06:41:22,109 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [978884572] [2022-04-06 06:41:22,109 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 06:41:22,110 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 06:41:22,192 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 06:41:22,247 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-04-06 06:41:22,251 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 06:41:22,258 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2022-04-06 06:41:22,260 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 06:41:22,265 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 11 [2022-04-06 06:41:22,267 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 06:41:22,272 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2022-04-06 06:41:22,273 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 06:41:22,273 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [978884572] [2022-04-06 06:41:22,274 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [978884572] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 06:41:22,274 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 06:41:22,274 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2022-04-06 06:41:22,275 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2141887675] [2022-04-06 06:41:22,276 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 06:41:22,280 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2022-04-06 06:41:22,280 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-06 06:41:22,302 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2022-04-06 06:41:22,303 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2022-04-06 06:41:22,304 INFO L87 Difference]: Start difference. First operand has 35 states, 18 states have (on average 1.3888888888888888) internal successors, (25), 19 states have internal predecessors, (25), 11 states have call successors, (11), 4 states have call predecessors, (11), 4 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) Second operand has 3 states, 3 states have (on average 3.6666666666666665) internal successors, (11), 2 states have internal predecessors, (11), 2 states have call successors, (5), 3 states have call predecessors, (5), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) [2022-04-06 06:41:22,377 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 06:41:22,377 INFO L93 Difference]: Finished difference Result 36 states and 45 transitions. [2022-04-06 06:41:22,378 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2022-04-06 06:41:22,380 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 3.6666666666666665) internal successors, (11), 2 states have internal predecessors, (11), 2 states have call successors, (5), 3 states have call predecessors, (5), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) Word has length 22 [2022-04-06 06:41:22,380 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 06:41:22,391 INFO L225 Difference]: With dead ends: 36 [2022-04-06 06:41:22,391 INFO L226 Difference]: Without dead ends: 31 [2022-04-06 06:41:22,393 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 8 GetRequests, 7 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2022-04-06 06:41:22,399 INFO L913 BasicCegarLoop]: 41 mSDtfsCounter, 10 mSDsluCounter, 4 mSDsCounter, 0 mSdLazyCounter, 20 mSolverCounterSat, 10 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 12 SdHoareTripleChecker+Valid, 45 SdHoareTripleChecker+Invalid, 30 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 10 IncrementalHoareTripleChecker+Valid, 20 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-04-06 06:41:22,401 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [12 Valid, 45 Invalid, 30 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [10 Valid, 20 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-06 06:41:22,415 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 31 states. [2022-04-06 06:41:22,434 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 31 to 30. [2022-04-06 06:41:22,436 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 30 states, 15 states have (on average 1.2666666666666666) internal successors, (19), 16 states have internal predecessors, (19), 11 states have call successors, (11), 4 states have call predecessors, (11), 3 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2022-04-06 06:41:22,441 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 30 states to 30 states and 39 transitions. [2022-04-06 06:41:22,442 INFO L78 Accepts]: Start accepts. Automaton has 30 states and 39 transitions. Word has length 22 [2022-04-06 06:41:22,443 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 06:41:22,443 INFO L478 AbstractCegarLoop]: Abstraction has 30 states and 39 transitions. [2022-04-06 06:41:22,444 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 3.6666666666666665) internal successors, (11), 2 states have internal predecessors, (11), 2 states have call successors, (5), 3 states have call predecessors, (5), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) [2022-04-06 06:41:22,444 INFO L276 IsEmpty]: Start isEmpty. Operand 30 states and 39 transitions. [2022-04-06 06:41:22,445 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 24 [2022-04-06 06:41:22,445 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 06:41:22,445 INFO L499 BasicCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 06:41:22,446 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2022-04-06 06:41:22,446 INFO L403 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 06:41:22,447 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 06:41:22,447 INFO L85 PathProgramCache]: Analyzing trace with hash -794581502, now seen corresponding path program 1 times [2022-04-06 06:41:22,447 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 06:41:22,447 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [217584874] [2022-04-06 06:41:22,447 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 06:41:22,448 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 06:41:22,469 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 06:41:22,517 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-04-06 06:41:22,523 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 06:41:22,531 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2022-04-06 06:41:22,534 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 06:41:22,539 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 11 [2022-04-06 06:41:22,543 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 06:41:22,547 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2022-04-06 06:41:22,547 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 06:41:22,548 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [217584874] [2022-04-06 06:41:22,548 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [217584874] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 06:41:22,548 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 06:41:22,548 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-06 06:41:22,548 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [852761644] [2022-04-06 06:41:22,548 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 06:41:22,550 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-04-06 06:41:22,550 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-06 06:41:22,550 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-04-06 06:41:22,551 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-04-06 06:41:22,551 INFO L87 Difference]: Start difference. First operand 30 states and 39 transitions. Second operand has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 3 states have call successors, (5), 4 states have call predecessors, (5), 2 states have return successors, (3), 1 states have call predecessors, (3), 2 states have call successors, (3) [2022-04-06 06:41:22,681 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 06:41:22,681 INFO L93 Difference]: Finished difference Result 32 states and 41 transitions. [2022-04-06 06:41:22,682 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2022-04-06 06:41:22,682 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), 3 states have call successors, (5), 4 states have call predecessors, (5), 2 states have return successors, (3), 1 states have call predecessors, (3), 2 states have call successors, (3) Word has length 23 [2022-04-06 06:41:22,682 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 06:41:22,683 INFO L225 Difference]: With dead ends: 32 [2022-04-06 06:41:22,683 INFO L226 Difference]: Without dead ends: 32 [2022-04-06 06:41:22,683 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 12 GetRequests, 8 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2022-04-06 06:41:22,685 INFO L913 BasicCegarLoop]: 35 mSDtfsCounter, 13 mSDsluCounter, 30 mSDsCounter, 0 mSdLazyCounter, 55 mSolverCounterSat, 14 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 13 SdHoareTripleChecker+Valid, 65 SdHoareTripleChecker+Invalid, 69 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 14 IncrementalHoareTripleChecker+Valid, 55 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-04-06 06:41:22,685 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [13 Valid, 65 Invalid, 69 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [14 Valid, 55 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-06 06:41:22,686 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 32 states. [2022-04-06 06:41:22,690 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 32 to 32. [2022-04-06 06:41:22,690 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 32 states, 17 states have (on average 1.2352941176470589) internal successors, (21), 18 states have internal predecessors, (21), 11 states have call successors, (11), 4 states have call predecessors, (11), 3 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2022-04-06 06:41:22,699 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 32 states to 32 states and 41 transitions. [2022-04-06 06:41:22,699 INFO L78 Accepts]: Start accepts. Automaton has 32 states and 41 transitions. Word has length 23 [2022-04-06 06:41:22,700 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 06:41:22,700 INFO L478 AbstractCegarLoop]: Abstraction has 32 states and 41 transitions. [2022-04-06 06:41:22,700 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), 3 states have call successors, (5), 4 states have call predecessors, (5), 2 states have return successors, (3), 1 states have call predecessors, (3), 2 states have call successors, (3) [2022-04-06 06:41:22,701 INFO L276 IsEmpty]: Start isEmpty. Operand 32 states and 41 transitions. [2022-04-06 06:41:22,701 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 24 [2022-04-06 06:41:22,702 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 06:41:22,702 INFO L499 BasicCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 06:41:22,702 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2022-04-06 06:41:22,702 INFO L403 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 06:41:22,704 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 06:41:22,704 INFO L85 PathProgramCache]: Analyzing trace with hash -793509026, now seen corresponding path program 1 times [2022-04-06 06:41:22,704 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 06:41:22,705 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2125609303] [2022-04-06 06:41:22,705 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 06:41:22,705 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 06:41:22,760 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 06:41:22,760 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [61722336] [2022-04-06 06:41:22,761 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 06:41:22,761 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 06:41:22,761 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 06:41:22,771 INFO L229 MonitoredProcess]: Starting monitored process 2 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-06 06:41:22,804 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2022-04-06 06:41:22,844 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 06:41:22,846 INFO L263 TraceCheckSpWp]: Trace formula consists of 99 conjuncts, 9 conjunts are in the unsatisfiable core [2022-04-06 06:41:22,851 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 06:41:23,019 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2022-04-06 06:41:23,019 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-04-06 06:41:23,019 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 06:41:23,019 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2125609303] [2022-04-06 06:41:23,020 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 06:41:23,020 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [61722336] [2022-04-06 06:41:23,021 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [61722336] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 06:41:23,023 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 06:41:23,023 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-06 06:41:23,023 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [936711534] [2022-04-06 06:41:23,023 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 06:41:23,024 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-04-06 06:41:23,024 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-06 06:41:23,024 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-04-06 06:41:23,024 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-04-06 06:41:23,025 INFO L87 Difference]: Start difference. First operand 32 states and 41 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, (5), 2 states have call predecessors, (5), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) [2022-04-06 06:41:23,071 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 06:41:23,071 INFO L93 Difference]: Finished difference Result 47 states and 64 transitions. [2022-04-06 06:41:23,071 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-04-06 06:41:23,072 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, (5), 2 states have call predecessors, (5), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) Word has length 23 [2022-04-06 06:41:23,072 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 06:41:23,073 INFO L225 Difference]: With dead ends: 47 [2022-04-06 06:41:23,073 INFO L226 Difference]: Without dead ends: 47 [2022-04-06 06:41:23,073 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 23 GetRequests, 19 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2022-04-06 06:41:23,074 INFO L913 BasicCegarLoop]: 43 mSDtfsCounter, 8 mSDsluCounter, 97 mSDsCounter, 0 mSdLazyCounter, 47 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 14 SdHoareTripleChecker+Valid, 140 SdHoareTripleChecker+Invalid, 49 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 47 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-06 06:41:23,074 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [14 Valid, 140 Invalid, 49 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 47 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-06 06:41:23,075 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 47 states. [2022-04-06 06:41:23,081 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 47 to 46. [2022-04-06 06:41:23,082 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 46 states, 24 states have (on average 1.2916666666666667) internal successors, (31), 26 states have internal predecessors, (31), 17 states have call successors, (17), 5 states have call predecessors, (17), 4 states have return successors, (15), 14 states have call predecessors, (15), 15 states have call successors, (15) [2022-04-06 06:41:23,083 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 46 states to 46 states and 63 transitions. [2022-04-06 06:41:23,083 INFO L78 Accepts]: Start accepts. Automaton has 46 states and 63 transitions. Word has length 23 [2022-04-06 06:41:23,084 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 06:41:23,084 INFO L478 AbstractCegarLoop]: Abstraction has 46 states and 63 transitions. [2022-04-06 06:41:23,084 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, (5), 2 states have call predecessors, (5), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) [2022-04-06 06:41:23,084 INFO L276 IsEmpty]: Start isEmpty. Operand 46 states and 63 transitions. [2022-04-06 06:41:23,085 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 29 [2022-04-06 06:41:23,085 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 06:41:23,085 INFO L499 BasicCegarLoop]: trace histogram [2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 06:41:23,104 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Ended with exit code 0 [2022-04-06 06:41:23,291 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2,2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 06:41:23,292 INFO L403 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 06:41:23,292 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 06:41:23,293 INFO L85 PathProgramCache]: Analyzing trace with hash 2115229340, now seen corresponding path program 1 times [2022-04-06 06:41:23,293 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 06:41:23,295 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2078787860] [2022-04-06 06:41:23,295 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 06:41:23,296 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 06:41:23,307 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 06:41:23,307 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1454159797] [2022-04-06 06:41:23,307 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 06:41:23,308 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 06:41:23,308 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 06:41:23,323 INFO L229 MonitoredProcess]: Starting monitored process 3 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-06 06:41:23,352 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2022-04-06 06:41:23,375 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 06:41:23,377 INFO L263 TraceCheckSpWp]: Trace formula consists of 108 conjuncts, 14 conjunts are in the unsatisfiable core [2022-04-06 06:41:23,380 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 06:41:23,545 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 2 proven. 3 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2022-04-06 06:41:23,545 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 06:41:23,635 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 06:41:23,636 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2078787860] [2022-04-06 06:41:23,636 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 06:41:23,637 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1454159797] [2022-04-06 06:41:23,638 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1454159797] provided 0 perfect and 1 imperfect interpolant sequences [2022-04-06 06:41:23,641 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-04-06 06:41:23,641 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8] total 8 [2022-04-06 06:41:23,641 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1735986171] [2022-04-06 06:41:23,641 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2022-04-06 06:41:23,642 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2022-04-06 06:41:23,642 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-06 06:41:23,643 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2022-04-06 06:41:23,643 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=17, Invalid=55, Unknown=0, NotChecked=0, Total=72 [2022-04-06 06:41:23,643 INFO L87 Difference]: Start difference. First operand 46 states and 63 transitions. Second operand has 8 states, 8 states have (on average 2.25) internal successors, (18), 6 states have internal predecessors, (18), 3 states have call successors, (6), 2 states have call predecessors, (6), 2 states have return successors, (4), 3 states have call predecessors, (4), 3 states have call successors, (4) [2022-04-06 06:41:23,761 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 06:41:23,761 INFO L93 Difference]: Finished difference Result 51 states and 67 transitions. [2022-04-06 06:41:23,761 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2022-04-06 06:41:23,762 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 8 states have (on average 2.25) internal successors, (18), 6 states have internal predecessors, (18), 3 states have call successors, (6), 2 states have call predecessors, (6), 2 states have return successors, (4), 3 states have call predecessors, (4), 3 states have call successors, (4) Word has length 28 [2022-04-06 06:41:23,762 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 06:41:23,764 INFO L225 Difference]: With dead ends: 51 [2022-04-06 06:41:23,764 INFO L226 Difference]: Without dead ends: 51 [2022-04-06 06:41:23,765 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 34 GetRequests, 24 SyntacticMatches, 1 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 7 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=25, Invalid=85, Unknown=0, NotChecked=0, Total=110 [2022-04-06 06:41:23,768 INFO L913 BasicCegarLoop]: 41 mSDtfsCounter, 24 mSDsluCounter, 131 mSDsCounter, 0 mSdLazyCounter, 121 mSolverCounterSat, 7 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 35 SdHoareTripleChecker+Valid, 172 SdHoareTripleChecker+Invalid, 128 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 7 IncrementalHoareTripleChecker+Valid, 121 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-04-06 06:41:23,768 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [35 Valid, 172 Invalid, 128 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [7 Valid, 121 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-06 06:41:23,770 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 51 states. [2022-04-06 06:41:23,782 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 51 to 50. [2022-04-06 06:41:23,782 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 50 states, 27 states have (on average 1.2592592592592593) internal successors, (34), 29 states have internal predecessors, (34), 17 states have call successors, (17), 6 states have call predecessors, (17), 5 states have return successors, (15), 14 states have call predecessors, (15), 15 states have call successors, (15) [2022-04-06 06:41:23,786 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 50 states to 50 states and 66 transitions. [2022-04-06 06:41:23,786 INFO L78 Accepts]: Start accepts. Automaton has 50 states and 66 transitions. Word has length 28 [2022-04-06 06:41:23,786 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 06:41:23,786 INFO L478 AbstractCegarLoop]: Abstraction has 50 states and 66 transitions. [2022-04-06 06:41:23,786 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 8 states have (on average 2.25) internal successors, (18), 6 states have internal predecessors, (18), 3 states have call successors, (6), 2 states have call predecessors, (6), 2 states have return successors, (4), 3 states have call predecessors, (4), 3 states have call successors, (4) [2022-04-06 06:41:23,787 INFO L276 IsEmpty]: Start isEmpty. Operand 50 states and 66 transitions. [2022-04-06 06:41:23,787 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 34 [2022-04-06 06:41:23,787 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 06:41:23,787 INFO L499 BasicCegarLoop]: trace histogram [3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 06:41:23,804 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Ended with exit code 0 [2022-04-06 06:41:23,991 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,SelfDestructingSolverStorable3 [2022-04-06 06:41:23,992 INFO L403 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 06:41:23,992 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 06:41:23,993 INFO L85 PathProgramCache]: Analyzing trace with hash -864241798, now seen corresponding path program 1 times [2022-04-06 06:41:23,993 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 06:41:23,993 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1703710940] [2022-04-06 06:41:23,993 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 06:41:23,993 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 06:41:24,012 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 06:41:24,013 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [889407322] [2022-04-06 06:41:24,013 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 06:41:24,013 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 06:41:24,013 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 06:41:24,023 INFO L229 MonitoredProcess]: Starting monitored process 4 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-06 06:41:24,025 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2022-04-06 06:41:24,071 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 06:41:24,072 INFO L263 TraceCheckSpWp]: Trace formula consists of 117 conjuncts, 14 conjunts are in the unsatisfiable core [2022-04-06 06:41:24,075 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 06:41:24,248 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 4 proven. 3 refuted. 0 times theorem prover too weak. 5 trivial. 0 not checked. [2022-04-06 06:41:24,248 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 06:41:24,361 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 8 trivial. 0 not checked. [2022-04-06 06:41:24,361 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 06:41:24,361 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1703710940] [2022-04-06 06:41:24,362 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 06:41:24,362 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [889407322] [2022-04-06 06:41:24,362 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [889407322] provided 1 perfect and 1 imperfect interpolant sequences [2022-04-06 06:41:24,362 INFO L184 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2022-04-06 06:41:24,362 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [8] total 9 [2022-04-06 06:41:24,362 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1503192594] [2022-04-06 06:41:24,362 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 06:41:24,363 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-04-06 06:41:24,363 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-06 06:41:24,363 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-04-06 06:41:24,363 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=17, Invalid=55, Unknown=0, NotChecked=0, Total=72 [2022-04-06 06:41:24,364 INFO L87 Difference]: Start difference. First operand 50 states and 66 transitions. Second operand has 5 states, 5 states have (on average 3.0) internal successors, (15), 4 states have internal predecessors, (15), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2022-04-06 06:41:24,413 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 06:41:24,413 INFO L93 Difference]: Finished difference Result 73 states and 105 transitions. [2022-04-06 06:41:24,413 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-04-06 06:41:24,414 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.0) internal successors, (15), 4 states have internal predecessors, (15), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) Word has length 33 [2022-04-06 06:41:24,414 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 06:41:24,416 INFO L225 Difference]: With dead ends: 73 [2022-04-06 06:41:24,416 INFO L226 Difference]: Without dead ends: 71 [2022-04-06 06:41:24,416 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 66 GetRequests, 57 SyntacticMatches, 1 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 5 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=21, Invalid=69, Unknown=0, NotChecked=0, Total=90 [2022-04-06 06:41:24,417 INFO L913 BasicCegarLoop]: 41 mSDtfsCounter, 9 mSDsluCounter, 87 mSDsCounter, 0 mSdLazyCounter, 51 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 13 SdHoareTripleChecker+Valid, 128 SdHoareTripleChecker+Invalid, 52 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 51 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-06 06:41:24,417 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [13 Valid, 128 Invalid, 52 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 51 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-06 06:41:24,418 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 71 states. [2022-04-06 06:41:24,424 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 71 to 71. [2022-04-06 06:41:24,424 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 71 states, 36 states have (on average 1.3333333333333333) internal successors, (48), 40 states have internal predecessors, (48), 28 states have call successors, (28), 7 states have call predecessors, (28), 6 states have return successors, (24), 23 states have call predecessors, (24), 24 states have call successors, (24) [2022-04-06 06:41:24,425 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 71 states to 71 states and 100 transitions. [2022-04-06 06:41:24,425 INFO L78 Accepts]: Start accepts. Automaton has 71 states and 100 transitions. Word has length 33 [2022-04-06 06:41:24,425 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 06:41:24,425 INFO L478 AbstractCegarLoop]: Abstraction has 71 states and 100 transitions. [2022-04-06 06:41:24,426 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.0) internal successors, (15), 4 states have internal predecessors, (15), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2022-04-06 06:41:24,426 INFO L276 IsEmpty]: Start isEmpty. Operand 71 states and 100 transitions. [2022-04-06 06:41:24,426 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 40 [2022-04-06 06:41:24,427 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 06:41:24,427 INFO L499 BasicCegarLoop]: trace histogram [4, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 06:41:24,450 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Forceful destruction successful, exit code 0 [2022-04-06 06:41:24,650 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 06:41:24,650 INFO L403 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 06:41:24,651 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 06:41:24,651 INFO L85 PathProgramCache]: Analyzing trace with hash -120478471, now seen corresponding path program 1 times [2022-04-06 06:41:24,651 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 06:41:24,651 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1704557158] [2022-04-06 06:41:24,651 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 06:41:24,651 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 06:41:24,661 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 06:41:24,661 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1661131364] [2022-04-06 06:41:24,661 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 06:41:24,662 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 06:41:24,662 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 06:41:24,663 INFO L229 MonitoredProcess]: Starting monitored process 5 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-06 06:41:24,677 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2022-04-06 06:41:24,717 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 06:41:24,718 INFO L263 TraceCheckSpWp]: Trace formula consists of 128 conjuncts, 5 conjunts are in the unsatisfiable core [2022-04-06 06:41:24,720 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 06:41:24,780 INFO L134 CoverageAnalysis]: Checked inductivity of 22 backedges. 6 proven. 0 refuted. 0 times theorem prover too weak. 16 trivial. 0 not checked. [2022-04-06 06:41:24,780 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-04-06 06:41:24,780 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 06:41:24,781 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1704557158] [2022-04-06 06:41:24,781 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 06:41:24,781 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1661131364] [2022-04-06 06:41:24,781 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1661131364] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 06:41:24,781 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 06:41:24,781 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-06 06:41:24,781 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1133407930] [2022-04-06 06:41:24,781 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 06:41:24,782 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-04-06 06:41:24,782 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-06 06:41:24,783 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-04-06 06:41:24,783 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-04-06 06:41:24,783 INFO L87 Difference]: Start difference. First operand 71 states and 100 transitions. Second operand has 5 states, 4 states have (on average 4.0) internal successors, (16), 4 states have internal predecessors, (16), 2 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (6), 1 states have call predecessors, (6), 1 states have call successors, (6) [2022-04-06 06:41:24,819 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 06:41:24,819 INFO L93 Difference]: Finished difference Result 85 states and 121 transitions. [2022-04-06 06:41:24,819 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-04-06 06:41:24,819 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 4 states have (on average 4.0) internal successors, (16), 4 states have internal predecessors, (16), 2 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (6), 1 states have call predecessors, (6), 1 states have call successors, (6) Word has length 39 [2022-04-06 06:41:24,821 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 06:41:24,823 INFO L225 Difference]: With dead ends: 85 [2022-04-06 06:41:24,824 INFO L226 Difference]: Without dead ends: 85 [2022-04-06 06:41:24,824 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 39 GetRequests, 35 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2022-04-06 06:41:24,825 INFO L913 BasicCegarLoop]: 44 mSDtfsCounter, 5 mSDsluCounter, 100 mSDsCounter, 0 mSdLazyCounter, 34 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 8 SdHoareTripleChecker+Valid, 144 SdHoareTripleChecker+Invalid, 34 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 34 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-06 06:41:24,825 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [8 Valid, 144 Invalid, 34 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 34 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-06 06:41:24,826 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 85 states. [2022-04-06 06:41:24,842 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 85 to 78. [2022-04-06 06:41:24,843 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 78 states, 39 states have (on average 1.3076923076923077) internal successors, (51), 46 states have internal predecessors, (51), 31 states have call successors, (31), 8 states have call predecessors, (31), 7 states have return successors, (27), 23 states have call predecessors, (27), 27 states have call successors, (27) [2022-04-06 06:41:24,844 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 78 states to 78 states and 109 transitions. [2022-04-06 06:41:24,844 INFO L78 Accepts]: Start accepts. Automaton has 78 states and 109 transitions. Word has length 39 [2022-04-06 06:41:24,845 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 06:41:24,845 INFO L478 AbstractCegarLoop]: Abstraction has 78 states and 109 transitions. [2022-04-06 06:41:24,845 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 4 states have (on average 4.0) internal successors, (16), 4 states have internal predecessors, (16), 2 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (6), 1 states have call predecessors, (6), 1 states have call successors, (6) [2022-04-06 06:41:24,845 INFO L276 IsEmpty]: Start isEmpty. Operand 78 states and 109 transitions. [2022-04-06 06:41:24,846 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 43 [2022-04-06 06:41:24,846 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 06:41:24,847 INFO L499 BasicCegarLoop]: trace histogram [4, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 06:41:24,872 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Forceful destruction successful, exit code 0 [2022-04-06 06:41:25,061 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 06:41:25,061 INFO L403 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 06:41:25,062 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 06:41:25,062 INFO L85 PathProgramCache]: Analyzing trace with hash -1628466672, now seen corresponding path program 1 times [2022-04-06 06:41:25,062 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 06:41:25,062 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1402457241] [2022-04-06 06:41:25,062 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 06:41:25,062 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 06:41:25,073 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 06:41:25,073 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1037925976] [2022-04-06 06:41:25,073 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 06:41:25,073 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 06:41:25,073 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 06:41:25,074 INFO L229 MonitoredProcess]: Starting monitored process 6 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-06 06:41:25,099 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2022-04-06 06:41:25,127 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 06:41:25,128 INFO L263 TraceCheckSpWp]: Trace formula consists of 139 conjuncts, 7 conjunts are in the unsatisfiable core [2022-04-06 06:41:25,130 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 06:41:25,228 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 6 proven. 2 refuted. 0 times theorem prover too weak. 16 trivial. 0 not checked. [2022-04-06 06:41:25,228 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 06:41:25,335 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 6 proven. 2 refuted. 0 times theorem prover too weak. 16 trivial. 0 not checked. [2022-04-06 06:41:25,336 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 06:41:25,336 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1402457241] [2022-04-06 06:41:25,336 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 06:41:25,336 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1037925976] [2022-04-06 06:41:25,336 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1037925976] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-06 06:41:25,336 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-06 06:41:25,336 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 5] total 8 [2022-04-06 06:41:25,336 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1929974867] [2022-04-06 06:41:25,336 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-04-06 06:41:25,337 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2022-04-06 06:41:25,337 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-06 06:41:25,337 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2022-04-06 06:41:25,337 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=20, Invalid=36, Unknown=0, NotChecked=0, Total=56 [2022-04-06 06:41:25,338 INFO L87 Difference]: Start difference. First operand 78 states and 109 transitions. Second operand has 8 states, 8 states have (on average 4.375) internal successors, (35), 8 states have internal predecessors, (35), 6 states have call successors, (14), 5 states have call predecessors, (14), 4 states have return successors, (12), 4 states have call predecessors, (12), 5 states have call successors, (12) [2022-04-06 06:41:25,462 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 06:41:25,462 INFO L93 Difference]: Finished difference Result 202 states and 256 transitions. [2022-04-06 06:41:25,463 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2022-04-06 06:41:25,463 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 8 states have (on average 4.375) internal successors, (35), 8 states have internal predecessors, (35), 6 states have call successors, (14), 5 states have call predecessors, (14), 4 states have return successors, (12), 4 states have call predecessors, (12), 5 states have call successors, (12) Word has length 42 [2022-04-06 06:41:25,463 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 06:41:25,465 INFO L225 Difference]: With dead ends: 202 [2022-04-06 06:41:25,465 INFO L226 Difference]: Without dead ends: 200 [2022-04-06 06:41:25,465 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 86 GetRequests, 77 SyntacticMatches, 0 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 7 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=40, Invalid=70, Unknown=0, NotChecked=0, Total=110 [2022-04-06 06:41:25,466 INFO L913 BasicCegarLoop]: 55 mSDtfsCounter, 57 mSDsluCounter, 121 mSDsCounter, 0 mSdLazyCounter, 55 mSolverCounterSat, 17 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 57 SdHoareTripleChecker+Valid, 176 SdHoareTripleChecker+Invalid, 72 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 17 IncrementalHoareTripleChecker+Valid, 55 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-04-06 06:41:25,466 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [57 Valid, 176 Invalid, 72 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [17 Valid, 55 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-06 06:41:25,466 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 200 states. [2022-04-06 06:41:25,477 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 200 to 194. [2022-04-06 06:41:25,477 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 194 states, 109 states have (on average 1.2201834862385321) internal successors, (133), 120 states have internal predecessors, (133), 63 states have call successors, (63), 23 states have call predecessors, (63), 21 states have return successors, (55), 50 states have call predecessors, (55), 55 states have call successors, (55) [2022-04-06 06:41:25,479 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 194 states to 194 states and 251 transitions. [2022-04-06 06:41:25,479 INFO L78 Accepts]: Start accepts. Automaton has 194 states and 251 transitions. Word has length 42 [2022-04-06 06:41:25,480 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 06:41:25,480 INFO L478 AbstractCegarLoop]: Abstraction has 194 states and 251 transitions. [2022-04-06 06:41:25,480 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 8 states have (on average 4.375) internal successors, (35), 8 states have internal predecessors, (35), 6 states have call successors, (14), 5 states have call predecessors, (14), 4 states have return successors, (12), 4 states have call predecessors, (12), 5 states have call successors, (12) [2022-04-06 06:41:25,480 INFO L276 IsEmpty]: Start isEmpty. Operand 194 states and 251 transitions. [2022-04-06 06:41:25,481 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 43 [2022-04-06 06:41:25,481 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 06:41:25,481 INFO L499 BasicCegarLoop]: trace histogram [4, 3, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 06:41:25,504 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Forceful destruction successful, exit code 0 [2022-04-06 06:41:25,704 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 06:41:25,705 INFO L403 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 06:41:25,705 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 06:41:25,705 INFO L85 PathProgramCache]: Analyzing trace with hash -1627394196, now seen corresponding path program 1 times [2022-04-06 06:41:25,706 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 06:41:25,706 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [259821090] [2022-04-06 06:41:25,706 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 06:41:25,706 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 06:41:25,714 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 06:41:25,715 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2082196259] [2022-04-06 06:41:25,715 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 06:41:25,715 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 06:41:25,715 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 06:41:25,721 INFO L229 MonitoredProcess]: Starting monitored process 7 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-06 06:41:25,722 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2022-04-06 06:41:25,765 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 06:41:25,766 INFO L263 TraceCheckSpWp]: Trace formula consists of 139 conjuncts, 11 conjunts are in the unsatisfiable core [2022-04-06 06:41:25,768 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 06:41:25,925 INFO L134 CoverageAnalysis]: Checked inductivity of 25 backedges. 6 proven. 0 refuted. 0 times theorem prover too weak. 19 trivial. 0 not checked. [2022-04-06 06:41:25,926 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-04-06 06:41:25,926 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 06:41:25,926 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [259821090] [2022-04-06 06:41:25,926 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 06:41:25,926 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2082196259] [2022-04-06 06:41:25,926 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2082196259] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 06:41:25,926 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 06:41:25,927 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-06 06:41:25,927 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [944488138] [2022-04-06 06:41:25,927 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 06:41:25,927 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-04-06 06:41:25,927 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-06 06:41:25,928 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-04-06 06:41:25,928 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-04-06 06:41:25,928 INFO L87 Difference]: Start difference. First operand 194 states and 251 transitions. Second operand has 5 states, 5 states have (on average 3.4) internal successors, (17), 4 states have internal predecessors, (17), 2 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) [2022-04-06 06:41:25,964 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 06:41:25,965 INFO L93 Difference]: Finished difference Result 206 states and 260 transitions. [2022-04-06 06:41:25,965 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-04-06 06:41:25,965 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.4) internal successors, (17), 4 states have internal predecessors, (17), 2 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) Word has length 42 [2022-04-06 06:41:25,965 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 06:41:25,967 INFO L225 Difference]: With dead ends: 206 [2022-04-06 06:41:25,967 INFO L226 Difference]: Without dead ends: 203 [2022-04-06 06:41:25,967 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 42 GetRequests, 37 SyntacticMatches, 1 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2022-04-06 06:41:25,968 INFO L913 BasicCegarLoop]: 39 mSDtfsCounter, 7 mSDsluCounter, 93 mSDsCounter, 0 mSdLazyCounter, 38 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 9 SdHoareTripleChecker+Valid, 132 SdHoareTripleChecker+Invalid, 39 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 38 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-06 06:41:25,968 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [9 Valid, 132 Invalid, 39 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 38 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-06 06:41:25,968 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 203 states. [2022-04-06 06:41:25,977 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 203 to 203. [2022-04-06 06:41:25,978 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 203 states, 118 states have (on average 1.2033898305084745) internal successors, (142), 129 states have internal predecessors, (142), 60 states have call successors, (60), 26 states have call predecessors, (60), 24 states have return successors, (52), 47 states have call predecessors, (52), 52 states have call successors, (52) [2022-04-06 06:41:25,979 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 203 states to 203 states and 254 transitions. [2022-04-06 06:41:25,979 INFO L78 Accepts]: Start accepts. Automaton has 203 states and 254 transitions. Word has length 42 [2022-04-06 06:41:25,980 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 06:41:25,980 INFO L478 AbstractCegarLoop]: Abstraction has 203 states and 254 transitions. [2022-04-06 06:41:25,980 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.4) internal successors, (17), 4 states have internal predecessors, (17), 2 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) [2022-04-06 06:41:25,980 INFO L276 IsEmpty]: Start isEmpty. Operand 203 states and 254 transitions. [2022-04-06 06:41:25,981 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 45 [2022-04-06 06:41:25,981 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 06:41:25,981 INFO L499 BasicCegarLoop]: trace histogram [5, 4, 4, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 06:41:26,004 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Forceful destruction successful, exit code 0 [2022-04-06 06:41:26,195 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 06:41:26,196 INFO L403 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 06:41:26,196 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 06:41:26,196 INFO L85 PathProgramCache]: Analyzing trace with hash -1527150038, now seen corresponding path program 1 times [2022-04-06 06:41:26,196 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 06:41:26,196 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1588775996] [2022-04-06 06:41:26,196 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 06:41:26,197 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 06:41:26,205 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 06:41:26,205 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [737193862] [2022-04-06 06:41:26,206 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 06:41:26,206 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 06:41:26,206 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 06:41:26,207 INFO L229 MonitoredProcess]: Starting monitored process 8 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-06 06:41:26,237 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2022-04-06 06:41:26,262 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 06:41:26,263 INFO L263 TraceCheckSpWp]: Trace formula consists of 137 conjuncts, 10 conjunts are in the unsatisfiable core [2022-04-06 06:41:26,265 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 06:41:26,361 INFO L134 CoverageAnalysis]: Checked inductivity of 36 backedges. 10 proven. 7 refuted. 0 times theorem prover too weak. 19 trivial. 0 not checked. [2022-04-06 06:41:26,361 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 06:41:26,484 INFO L134 CoverageAnalysis]: Checked inductivity of 36 backedges. 10 proven. 7 refuted. 0 times theorem prover too weak. 19 trivial. 0 not checked. [2022-04-06 06:41:26,484 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 06:41:26,484 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1588775996] [2022-04-06 06:41:26,484 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 06:41:26,485 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [737193862] [2022-04-06 06:41:26,485 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [737193862] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-06 06:41:26,485 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-06 06:41:26,485 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 9 [2022-04-06 06:41:26,485 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [413386275] [2022-04-06 06:41:26,485 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-04-06 06:41:26,486 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2022-04-06 06:41:26,486 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-06 06:41:26,486 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2022-04-06 06:41:26,486 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=19, Invalid=53, Unknown=0, NotChecked=0, Total=72 [2022-04-06 06:41:26,486 INFO L87 Difference]: Start difference. First operand 203 states and 254 transitions. Second operand has 9 states, 8 states have (on average 2.625) internal successors, (21), 7 states have internal predecessors, (21), 3 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (7), 3 states have call predecessors, (7), 3 states have call successors, (7) [2022-04-06 06:41:26,615 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 06:41:26,615 INFO L93 Difference]: Finished difference Result 230 states and 285 transitions. [2022-04-06 06:41:26,615 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2022-04-06 06:41:26,616 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 8 states have (on average 2.625) internal successors, (21), 7 states have internal predecessors, (21), 3 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (7), 3 states have call predecessors, (7), 3 states have call successors, (7) Word has length 44 [2022-04-06 06:41:26,617 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 06:41:26,619 INFO L225 Difference]: With dead ends: 230 [2022-04-06 06:41:26,619 INFO L226 Difference]: Without dead ends: 216 [2022-04-06 06:41:26,619 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 90 GetRequests, 79 SyntacticMatches, 1 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 7 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=36, Invalid=96, Unknown=0, NotChecked=0, Total=132 [2022-04-06 06:41:26,621 INFO L913 BasicCegarLoop]: 29 mSDtfsCounter, 20 mSDsluCounter, 93 mSDsCounter, 0 mSdLazyCounter, 143 mSolverCounterSat, 13 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 23 SdHoareTripleChecker+Valid, 122 SdHoareTripleChecker+Invalid, 156 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 13 IncrementalHoareTripleChecker+Valid, 143 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-04-06 06:41:26,621 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [23 Valid, 122 Invalid, 156 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [13 Valid, 143 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-06 06:41:26,622 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 216 states. [2022-04-06 06:41:26,635 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 216 to 214. [2022-04-06 06:41:26,635 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 214 states, 128 states have (on average 1.1640625) internal successors, (149), 139 states have internal predecessors, (149), 59 states have call successors, (59), 27 states have call predecessors, (59), 26 states have return successors, (54), 47 states have call predecessors, (54), 54 states have call successors, (54) [2022-04-06 06:41:26,638 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 214 states to 214 states and 262 transitions. [2022-04-06 06:41:26,638 INFO L78 Accepts]: Start accepts. Automaton has 214 states and 262 transitions. Word has length 44 [2022-04-06 06:41:26,638 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 06:41:26,638 INFO L478 AbstractCegarLoop]: Abstraction has 214 states and 262 transitions. [2022-04-06 06:41:26,639 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 8 states have (on average 2.625) internal successors, (21), 7 states have internal predecessors, (21), 3 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (7), 3 states have call predecessors, (7), 3 states have call successors, (7) [2022-04-06 06:41:26,639 INFO L276 IsEmpty]: Start isEmpty. Operand 214 states and 262 transitions. [2022-04-06 06:41:26,642 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 48 [2022-04-06 06:41:26,642 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 06:41:26,642 INFO L499 BasicCegarLoop]: trace histogram [5, 4, 4, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 06:41:26,667 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Forceful destruction successful, exit code 0 [2022-04-06 06:41:26,863 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 06:41:26,864 INFO L403 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 06:41:26,864 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 06:41:26,864 INFO L85 PathProgramCache]: Analyzing trace with hash -1237367986, now seen corresponding path program 2 times [2022-04-06 06:41:26,864 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 06:41:26,864 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [167956400] [2022-04-06 06:41:26,865 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 06:41:26,865 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 06:41:26,885 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 06:41:26,885 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [954948702] [2022-04-06 06:41:26,885 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-06 06:41:26,886 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 06:41:26,886 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 06:41:26,900 INFO L229 MonitoredProcess]: Starting monitored process 9 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-06 06:41:26,914 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2022-04-06 06:41:26,944 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-06 06:41:26,944 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-06 06:41:26,945 INFO L263 TraceCheckSpWp]: Trace formula consists of 148 conjuncts, 25 conjunts are in the unsatisfiable core [2022-04-06 06:41:26,947 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 06:41:27,156 INFO L134 CoverageAnalysis]: Checked inductivity of 40 backedges. 8 proven. 4 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2022-04-06 06:41:27,156 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 06:41:27,261 INFO L134 CoverageAnalysis]: Checked inductivity of 40 backedges. 8 proven. 4 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2022-04-06 06:41:27,262 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 06:41:27,262 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [167956400] [2022-04-06 06:41:27,262 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 06:41:27,262 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [954948702] [2022-04-06 06:41:27,262 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [954948702] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-06 06:41:27,262 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-06 06:41:27,262 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 8 [2022-04-06 06:41:27,262 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2093591536] [2022-04-06 06:41:27,262 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-04-06 06:41:27,263 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2022-04-06 06:41:27,263 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-06 06:41:27,263 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2022-04-06 06:41:27,263 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=16, Invalid=40, Unknown=0, NotChecked=0, Total=56 [2022-04-06 06:41:27,264 INFO L87 Difference]: Start difference. First operand 214 states and 262 transitions. Second operand has 8 states, 8 states have (on average 3.25) internal successors, (26), 7 states have internal predecessors, (26), 5 states have call successors, (14), 2 states have call predecessors, (14), 1 states have return successors, (11), 5 states have call predecessors, (11), 5 states have call successors, (11) [2022-04-06 06:41:27,741 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 06:41:27,741 INFO L93 Difference]: Finished difference Result 251 states and 310 transitions. [2022-04-06 06:41:27,743 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2022-04-06 06:41:27,743 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 8 states have (on average 3.25) internal successors, (26), 7 states have internal predecessors, (26), 5 states have call successors, (14), 2 states have call predecessors, (14), 1 states have return successors, (11), 5 states have call predecessors, (11), 5 states have call successors, (11) Word has length 47 [2022-04-06 06:41:27,743 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 06:41:27,744 INFO L225 Difference]: With dead ends: 251 [2022-04-06 06:41:27,745 INFO L226 Difference]: Without dead ends: 229 [2022-04-06 06:41:27,745 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 96 GetRequests, 86 SyntacticMatches, 1 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=31, Invalid=79, Unknown=0, NotChecked=0, Total=110 [2022-04-06 06:41:27,745 INFO L913 BasicCegarLoop]: 44 mSDtfsCounter, 14 mSDsluCounter, 121 mSDsCounter, 0 mSdLazyCounter, 176 mSolverCounterSat, 34 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 14 SdHoareTripleChecker+Valid, 165 SdHoareTripleChecker+Invalid, 210 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 34 IncrementalHoareTripleChecker+Valid, 176 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2022-04-06 06:41:27,745 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [14 Valid, 165 Invalid, 210 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [34 Valid, 176 Invalid, 0 Unknown, 0 Unchecked, 0.4s Time] [2022-04-06 06:41:27,746 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 229 states. [2022-04-06 06:41:27,751 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 229 to 210. [2022-04-06 06:41:27,752 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 210 states, 134 states have (on average 1.126865671641791) internal successors, (151), 142 states have internal predecessors, (151), 47 states have call successors, (47), 29 states have call predecessors, (47), 28 states have return successors, (42), 38 states have call predecessors, (42), 42 states have call successors, (42) [2022-04-06 06:41:27,753 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 210 states to 210 states and 240 transitions. [2022-04-06 06:41:27,753 INFO L78 Accepts]: Start accepts. Automaton has 210 states and 240 transitions. Word has length 47 [2022-04-06 06:41:27,753 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 06:41:27,754 INFO L478 AbstractCegarLoop]: Abstraction has 210 states and 240 transitions. [2022-04-06 06:41:27,754 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 8 states have (on average 3.25) internal successors, (26), 7 states have internal predecessors, (26), 5 states have call successors, (14), 2 states have call predecessors, (14), 1 states have return successors, (11), 5 states have call predecessors, (11), 5 states have call successors, (11) [2022-04-06 06:41:27,754 INFO L276 IsEmpty]: Start isEmpty. Operand 210 states and 240 transitions. [2022-04-06 06:41:27,754 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 62 [2022-04-06 06:41:27,754 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 06:41:27,755 INFO L499 BasicCegarLoop]: trace histogram [7, 6, 6, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 06:41:27,779 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Forceful destruction successful, exit code 0 [2022-04-06 06:41:27,978 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,SelfDestructingSolverStorable9 [2022-04-06 06:41:27,979 INFO L403 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 06:41:27,979 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 06:41:27,979 INFO L85 PathProgramCache]: Analyzing trace with hash -264996897, now seen corresponding path program 1 times [2022-04-06 06:41:27,979 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 06:41:27,979 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1358162447] [2022-04-06 06:41:27,979 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 06:41:27,980 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 06:41:27,988 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 06:41:27,989 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [831461928] [2022-04-06 06:41:27,989 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 06:41:27,989 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 06:41:27,989 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 06:41:27,990 INFO L229 MonitoredProcess]: Starting monitored process 10 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-06 06:41:27,995 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Waiting until timeout for monitored process [2022-04-06 06:41:28,041 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 06:41:28,043 INFO L263 TraceCheckSpWp]: Trace formula consists of 179 conjuncts, 19 conjunts are in the unsatisfiable core [2022-04-06 06:41:28,045 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 06:41:28,332 INFO L134 CoverageAnalysis]: Checked inductivity of 89 backedges. 12 proven. 13 refuted. 0 times theorem prover too weak. 64 trivial. 0 not checked. [2022-04-06 06:41:28,332 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 06:41:28,474 INFO L134 CoverageAnalysis]: Checked inductivity of 89 backedges. 12 proven. 0 refuted. 0 times theorem prover too weak. 77 trivial. 0 not checked. [2022-04-06 06:41:28,474 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 06:41:28,474 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1358162447] [2022-04-06 06:41:28,474 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 06:41:28,474 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [831461928] [2022-04-06 06:41:28,475 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [831461928] provided 1 perfect and 1 imperfect interpolant sequences [2022-04-06 06:41:28,475 INFO L184 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2022-04-06 06:41:28,475 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [7] total 8 [2022-04-06 06:41:28,475 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [709997323] [2022-04-06 06:41:28,475 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 06:41:28,476 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-04-06 06:41:28,476 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-06 06:41:28,477 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-04-06 06:41:28,477 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=16, Invalid=40, Unknown=0, NotChecked=0, Total=56 [2022-04-06 06:41:28,477 INFO L87 Difference]: Start difference. First operand 210 states and 240 transitions. Second operand has 5 states, 5 states have (on average 3.6) internal successors, (18), 4 states have internal predecessors, (18), 2 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) [2022-04-06 06:41:28,513 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 06:41:28,514 INFO L93 Difference]: Finished difference Result 214 states and 242 transitions. [2022-04-06 06:41:28,514 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-04-06 06:41:28,514 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.6) internal successors, (18), 4 states have internal predecessors, (18), 2 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) Word has length 61 [2022-04-06 06:41:28,514 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 06:41:28,516 INFO L225 Difference]: With dead ends: 214 [2022-04-06 06:41:28,516 INFO L226 Difference]: Without dead ends: 192 [2022-04-06 06:41:28,517 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 122 GetRequests, 112 SyntacticMatches, 3 SemanticMatches, 7 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=20, Invalid=52, Unknown=0, NotChecked=0, Total=72 [2022-04-06 06:41:28,517 INFO L913 BasicCegarLoop]: 32 mSDtfsCounter, 7 mSDsluCounter, 69 mSDsCounter, 0 mSdLazyCounter, 32 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 9 SdHoareTripleChecker+Valid, 101 SdHoareTripleChecker+Invalid, 33 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 32 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-06 06:41:28,517 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [9 Valid, 101 Invalid, 33 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 32 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-06 06:41:28,518 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 192 states. [2022-04-06 06:41:28,526 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 192 to 189. [2022-04-06 06:41:28,527 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 189 states, 125 states have (on average 1.112) internal successors, (139), 129 states have internal predecessors, (139), 38 states have call successors, (38), 26 states have call predecessors, (38), 25 states have return successors, (35), 33 states have call predecessors, (35), 35 states have call successors, (35) [2022-04-06 06:41:28,528 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 189 states to 189 states and 212 transitions. [2022-04-06 06:41:28,528 INFO L78 Accepts]: Start accepts. Automaton has 189 states and 212 transitions. Word has length 61 [2022-04-06 06:41:28,528 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 06:41:28,528 INFO L478 AbstractCegarLoop]: Abstraction has 189 states and 212 transitions. [2022-04-06 06:41:28,528 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.6) internal successors, (18), 4 states have internal predecessors, (18), 2 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) [2022-04-06 06:41:28,528 INFO L276 IsEmpty]: Start isEmpty. Operand 189 states and 212 transitions. [2022-04-06 06:41:28,531 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 100 [2022-04-06 06:41:28,531 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 06:41:28,531 INFO L499 BasicCegarLoop]: trace histogram [13, 12, 12, 5, 4, 4, 4, 4, 4, 4, 4, 4, 4, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 06:41:28,552 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-04-06 06:41:28,743 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable10,10 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 06:41:28,744 INFO L403 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 06:41:28,744 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 06:41:28,744 INFO L85 PathProgramCache]: Analyzing trace with hash 1503864962, now seen corresponding path program 2 times [2022-04-06 06:41:28,744 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 06:41:28,744 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1166040192] [2022-04-06 06:41:28,744 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 06:41:28,744 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 06:41:28,754 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 06:41:28,754 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1720845758] [2022-04-06 06:41:28,754 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-06 06:41:28,754 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 06:41:28,755 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 06:41:28,756 INFO L229 MonitoredProcess]: Starting monitored process 11 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-06 06:41:28,760 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Waiting until timeout for monitored process [2022-04-06 06:41:28,824 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-06 06:41:28,825 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-06 06:41:28,826 INFO L263 TraceCheckSpWp]: Trace formula consists of 259 conjuncts, 13 conjunts are in the unsatisfiable core [2022-04-06 06:41:28,831 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 06:41:29,018 INFO L134 CoverageAnalysis]: Checked inductivity of 342 backedges. 24 proven. 266 refuted. 0 times theorem prover too weak. 52 trivial. 0 not checked. [2022-04-06 06:41:29,019 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 06:41:29,236 INFO L134 CoverageAnalysis]: Checked inductivity of 342 backedges. 24 proven. 50 refuted. 0 times theorem prover too weak. 268 trivial. 0 not checked. [2022-04-06 06:41:29,237 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 06:41:29,237 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1166040192] [2022-04-06 06:41:29,237 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 06:41:29,237 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1720845758] [2022-04-06 06:41:29,237 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1720845758] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-06 06:41:29,237 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-06 06:41:29,237 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 14 [2022-04-06 06:41:29,237 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [214301865] [2022-04-06 06:41:29,238 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-04-06 06:41:29,238 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2022-04-06 06:41:29,238 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-06 06:41:29,238 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2022-04-06 06:41:29,239 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=71, Invalid=111, Unknown=0, NotChecked=0, Total=182 [2022-04-06 06:41:29,239 INFO L87 Difference]: Start difference. First operand 189 states and 212 transitions. Second operand has 14 states, 14 states have (on average 4.857142857142857) internal successors, (68), 14 states have internal predecessors, (68), 12 states have call successors, (32), 8 states have call predecessors, (32), 7 states have return successors, (30), 10 states have call predecessors, (30), 11 states have call successors, (30) [2022-04-06 06:41:29,465 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 06:41:29,466 INFO L93 Difference]: Finished difference Result 507 states and 572 transitions. [2022-04-06 06:41:29,466 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 22 states. [2022-04-06 06:41:29,466 INFO L78 Accepts]: Start accepts. Automaton has has 14 states, 14 states have (on average 4.857142857142857) internal successors, (68), 14 states have internal predecessors, (68), 12 states have call successors, (32), 8 states have call predecessors, (32), 7 states have return successors, (30), 10 states have call predecessors, (30), 11 states have call successors, (30) Word has length 99 [2022-04-06 06:41:29,466 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 06:41:29,469 INFO L225 Difference]: With dead ends: 507 [2022-04-06 06:41:29,469 INFO L226 Difference]: Without dead ends: 507 [2022-04-06 06:41:29,469 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 206 GetRequests, 185 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-04-06 06:41:29,470 INFO L913 BasicCegarLoop]: 59 mSDtfsCounter, 94 mSDsluCounter, 171 mSDsCounter, 0 mSdLazyCounter, 146 mSolverCounterSat, 60 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 94 SdHoareTripleChecker+Valid, 230 SdHoareTripleChecker+Invalid, 206 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 60 IncrementalHoareTripleChecker+Valid, 146 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-04-06 06:41:29,470 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [94 Valid, 230 Invalid, 206 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [60 Valid, 146 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-06 06:41:29,470 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 507 states. [2022-04-06 06:41:29,482 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 507 to 507. [2022-04-06 06:41:29,482 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 507 states, 335 states have (on average 1.0955223880597016) internal successors, (367), 345 states have internal predecessors, (367), 104 states have call successors, (104), 68 states have call predecessors, (104), 67 states have return successors, (101), 93 states have call predecessors, (101), 101 states have call successors, (101) [2022-04-06 06:41:29,484 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 507 states to 507 states and 572 transitions. [2022-04-06 06:41:29,485 INFO L78 Accepts]: Start accepts. Automaton has 507 states and 572 transitions. Word has length 99 [2022-04-06 06:41:29,485 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 06:41:29,485 INFO L478 AbstractCegarLoop]: Abstraction has 507 states and 572 transitions. [2022-04-06 06:41:29,486 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 14 states, 14 states have (on average 4.857142857142857) internal successors, (68), 14 states have internal predecessors, (68), 12 states have call successors, (32), 8 states have call predecessors, (32), 7 states have return successors, (30), 10 states have call predecessors, (30), 11 states have call successors, (30) [2022-04-06 06:41:29,486 INFO L276 IsEmpty]: Start isEmpty. Operand 507 states and 572 transitions. [2022-04-06 06:41:29,489 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 214 [2022-04-06 06:41:29,489 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 06:41:29,489 INFO L499 BasicCegarLoop]: trace histogram [31, 30, 30, 11, 10, 10, 10, 10, 10, 10, 10, 10, 10, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 06:41:29,515 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Forceful destruction successful, exit code 0 [2022-04-06 06:41:29,703 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,SelfDestructingSolverStorable11 [2022-04-06 06:41:29,704 INFO L403 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 06:41:29,704 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 06:41:29,704 INFO L85 PathProgramCache]: Analyzing trace with hash 1084056642, now seen corresponding path program 3 times [2022-04-06 06:41:29,704 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 06:41:29,704 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1756918625] [2022-04-06 06:41:29,704 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 06:41:29,704 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 06:41:29,716 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 06:41:29,717 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [291496585] [2022-04-06 06:41:29,717 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2022-04-06 06:41:29,717 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 06:41:29,717 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 06:41:29,718 INFO L229 MonitoredProcess]: Starting monitored process 12 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-06 06:41:29,722 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Waiting until timeout for monitored process [2022-04-06 06:41:29,847 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 20 check-sat command(s) [2022-04-06 06:41:29,847 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-06 06:41:29,849 INFO L263 TraceCheckSpWp]: Trace formula consists of 472 conjuncts, 25 conjunts are in the unsatisfiable core [2022-04-06 06:41:29,854 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 06:41:30,352 INFO L134 CoverageAnalysis]: Checked inductivity of 2139 backedges. 60 proven. 1955 refuted. 0 times theorem prover too weak. 124 trivial. 0 not checked. [2022-04-06 06:41:30,352 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 06:41:30,887 INFO L134 CoverageAnalysis]: Checked inductivity of 2139 backedges. 60 proven. 335 refuted. 0 times theorem prover too weak. 1744 trivial. 0 not checked. [2022-04-06 06:41:30,887 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 06:41:30,888 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1756918625] [2022-04-06 06:41:30,888 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 06:41:30,888 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [291496585] [2022-04-06 06:41:30,888 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [291496585] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-06 06:41:30,888 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-06 06:41:30,888 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 14] total 26 [2022-04-06 06:41:30,888 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1192946048] [2022-04-06 06:41:30,888 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-04-06 06:41:30,889 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 26 states [2022-04-06 06:41:30,889 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-06 06:41:30,889 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 26 interpolants. [2022-04-06 06:41:30,890 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=281, Invalid=369, Unknown=0, NotChecked=0, Total=650 [2022-04-06 06:41:30,890 INFO L87 Difference]: Start difference. First operand 507 states and 572 transitions. Second operand has 26 states, 26 states have (on average 5.153846153846154) internal successors, (134), 26 states have internal predecessors, (134), 24 states have call successors, (68), 14 states have call predecessors, (68), 13 states have return successors, (66), 22 states have call predecessors, (66), 23 states have call successors, (66) [2022-04-06 06:41:31,496 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 06:41:31,496 INFO L93 Difference]: Finished difference Result 1143 states and 1292 transitions. [2022-04-06 06:41:31,497 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 46 states. [2022-04-06 06:41:31,497 INFO L78 Accepts]: Start accepts. Automaton has has 26 states, 26 states have (on average 5.153846153846154) internal successors, (134), 26 states have internal predecessors, (134), 24 states have call successors, (68), 14 states have call predecessors, (68), 13 states have return successors, (66), 22 states have call predecessors, (66), 23 states have call successors, (66) Word has length 213 [2022-04-06 06:41:31,497 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 06:41:31,502 INFO L225 Difference]: With dead ends: 1143 [2022-04-06 06:41:31,502 INFO L226 Difference]: Without dead ends: 1143 [2022-04-06 06:41:31,503 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 446 GetRequests, 401 SyntacticMatches, 0 SemanticMatches, 45 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 286 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=796, Invalid=1366, Unknown=0, NotChecked=0, Total=2162 [2022-04-06 06:41:31,504 INFO L913 BasicCegarLoop]: 95 mSDtfsCounter, 323 mSDsluCounter, 259 mSDsCounter, 0 mSdLazyCounter, 290 mSolverCounterSat, 232 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 323 SdHoareTripleChecker+Valid, 354 SdHoareTripleChecker+Invalid, 522 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 232 IncrementalHoareTripleChecker+Valid, 290 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2022-04-06 06:41:31,504 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [323 Valid, 354 Invalid, 522 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [232 Valid, 290 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2022-04-06 06:41:31,505 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1143 states. [2022-04-06 06:41:31,525 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1143 to 1143. [2022-04-06 06:41:31,526 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 1143 states, 755 states have (on average 1.0900662251655628) internal successors, (823), 777 states have internal predecessors, (823), 236 states have call successors, (236), 152 states have call predecessors, (236), 151 states have return successors, (233), 213 states have call predecessors, (233), 233 states have call successors, (233) [2022-04-06 06:41:31,531 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1143 states to 1143 states and 1292 transitions. [2022-04-06 06:41:31,531 INFO L78 Accepts]: Start accepts. Automaton has 1143 states and 1292 transitions. Word has length 213 [2022-04-06 06:41:31,531 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 06:41:31,531 INFO L478 AbstractCegarLoop]: Abstraction has 1143 states and 1292 transitions. [2022-04-06 06:41:31,532 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 26 states, 26 states have (on average 5.153846153846154) internal successors, (134), 26 states have internal predecessors, (134), 24 states have call successors, (68), 14 states have call predecessors, (68), 13 states have return successors, (66), 22 states have call predecessors, (66), 23 states have call successors, (66) [2022-04-06 06:41:31,532 INFO L276 IsEmpty]: Start isEmpty. Operand 1143 states and 1292 transitions. [2022-04-06 06:41:31,540 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 442 [2022-04-06 06:41:31,540 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 06:41:31,540 INFO L499 BasicCegarLoop]: trace histogram [67, 66, 66, 23, 22, 22, 22, 22, 22, 22, 22, 22, 22, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 06:41:31,565 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Forceful destruction successful, exit code 0 [2022-04-06 06:41:31,755 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,SelfDestructingSolverStorable12 [2022-04-06 06:41:31,756 INFO L403 AbstractCegarLoop]: === Iteration 14 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 06:41:31,756 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 06:41:31,756 INFO L85 PathProgramCache]: Analyzing trace with hash -597128254, now seen corresponding path program 4 times [2022-04-06 06:41:31,756 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 06:41:31,756 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [56234670] [2022-04-06 06:41:31,756 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 06:41:31,756 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 06:41:31,775 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 06:41:31,775 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [587460905] [2022-04-06 06:41:31,775 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2022-04-06 06:41:31,775 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 06:41:31,776 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 06:41:31,777 INFO L229 MonitoredProcess]: Starting monitored process 13 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-06 06:41:31,778 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Waiting until timeout for monitored process [2022-04-06 06:41:31,978 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2022-04-06 06:41:31,978 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-06 06:41:31,982 INFO L263 TraceCheckSpWp]: Trace formula consists of 979 conjuncts, 49 conjunts are in the unsatisfiable core [2022-04-06 06:41:31,990 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 06:41:32,940 INFO L134 CoverageAnalysis]: Checked inductivity of 10377 backedges. 132 proven. 9977 refuted. 0 times theorem prover too weak. 268 trivial. 0 not checked. [2022-04-06 06:41:32,940 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 06:41:34,135 INFO L134 CoverageAnalysis]: Checked inductivity of 10377 backedges. 132 proven. 1661 refuted. 0 times theorem prover too weak. 8584 trivial. 0 not checked. [2022-04-06 06:41:34,135 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 06:41:34,135 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [56234670] [2022-04-06 06:41:34,135 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 06:41:34,136 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [587460905] [2022-04-06 06:41:34,136 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [587460905] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-06 06:41:34,136 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-06 06:41:34,136 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [26, 26] total 50 [2022-04-06 06:41:34,136 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2101397654] [2022-04-06 06:41:34,136 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-04-06 06:41:34,137 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 50 states [2022-04-06 06:41:34,137 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-06 06:41:34,138 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 50 interpolants. [2022-04-06 06:41:34,138 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1133, Invalid=1317, Unknown=0, NotChecked=0, Total=2450 [2022-04-06 06:41:34,139 INFO L87 Difference]: Start difference. First operand 1143 states and 1292 transitions. Second operand has 50 states, 50 states have (on average 5.32) internal successors, (266), 50 states have internal predecessors, (266), 48 states have call successors, (140), 26 states have call predecessors, (140), 25 states have return successors, (138), 46 states have call predecessors, (138), 47 states have call successors, (138) [2022-04-06 06:41:35,829 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 06:41:35,829 INFO L93 Difference]: Finished difference Result 2415 states and 2732 transitions. [2022-04-06 06:41:35,829 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 94 states. [2022-04-06 06:41:35,830 INFO L78 Accepts]: Start accepts. Automaton has has 50 states, 50 states have (on average 5.32) internal successors, (266), 50 states have internal predecessors, (266), 48 states have call successors, (140), 26 states have call predecessors, (140), 25 states have return successors, (138), 46 states have call predecessors, (138), 47 states have call successors, (138) Word has length 441 [2022-04-06 06:41:35,831 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 06:41:35,839 INFO L225 Difference]: With dead ends: 2415 [2022-04-06 06:41:35,839 INFO L226 Difference]: Without dead ends: 2415 [2022-04-06 06:41:35,842 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 926 GetRequests, 833 SyntacticMatches, 0 SemanticMatches, 93 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1288 ImplicationChecksByTransitivity, 1.5s TimeCoverageRelationStatistics Valid=3316, Invalid=5614, Unknown=0, NotChecked=0, Total=8930 [2022-04-06 06:41:35,842 INFO L913 BasicCegarLoop]: 167 mSDtfsCounter, 651 mSDsluCounter, 681 mSDsCounter, 0 mSdLazyCounter, 649 mSolverCounterSat, 447 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 651 SdHoareTripleChecker+Valid, 848 SdHoareTripleChecker+Invalid, 1096 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 447 IncrementalHoareTripleChecker+Valid, 649 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.7s IncrementalHoareTripleChecker+Time [2022-04-06 06:41:35,842 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [651 Valid, 848 Invalid, 1096 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [447 Valid, 649 Invalid, 0 Unknown, 0 Unchecked, 0.7s Time] [2022-04-06 06:41:35,844 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 2415 states. [2022-04-06 06:41:35,886 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 2415 to 2415. [2022-04-06 06:41:35,889 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 2415 states, 1595 states have (on average 1.0877742946708464) internal successors, (1735), 1641 states have internal predecessors, (1735), 500 states have call successors, (500), 320 states have call predecessors, (500), 319 states have return successors, (497), 453 states have call predecessors, (497), 497 states have call successors, (497) [2022-04-06 06:41:35,897 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 2415 states to 2415 states and 2732 transitions. [2022-04-06 06:41:35,898 INFO L78 Accepts]: Start accepts. Automaton has 2415 states and 2732 transitions. Word has length 441 [2022-04-06 06:41:35,898 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 06:41:35,899 INFO L478 AbstractCegarLoop]: Abstraction has 2415 states and 2732 transitions. [2022-04-06 06:41:35,899 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 50 states, 50 states have (on average 5.32) internal successors, (266), 50 states have internal predecessors, (266), 48 states have call successors, (140), 26 states have call predecessors, (140), 25 states have return successors, (138), 46 states have call predecessors, (138), 47 states have call successors, (138) [2022-04-06 06:41:35,899 INFO L276 IsEmpty]: Start isEmpty. Operand 2415 states and 2732 transitions. [2022-04-06 06:41:35,923 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 898 [2022-04-06 06:41:35,923 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 06:41:35,923 INFO L499 BasicCegarLoop]: trace histogram [139, 138, 138, 47, 46, 46, 46, 46, 46, 46, 46, 46, 46, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 06:41:35,951 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-04-06 06:41:36,139 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,SelfDestructingSolverStorable13 [2022-04-06 06:41:36,140 INFO L403 AbstractCegarLoop]: === Iteration 15 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 06:41:36,140 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 06:41:36,140 INFO L85 PathProgramCache]: Analyzing trace with hash -806774078, now seen corresponding path program 5 times [2022-04-06 06:41:36,140 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 06:41:36,140 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [505836310] [2022-04-06 06:41:36,140 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 06:41:36,140 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 06:41:36,181 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 06:41:36,181 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1595370862] [2022-04-06 06:41:36,182 INFO L93 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2022-04-06 06:41:36,182 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 06:41:36,182 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 06:41:36,183 INFO L229 MonitoredProcess]: Starting monitored process 14 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-06 06:41:36,215 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Waiting until timeout for monitored process [2022-04-06 06:51:18,061 INFO L228 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 90 check-sat command(s) [2022-04-06 06:51:18,062 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-06 06:51:18,203 INFO L263 TraceCheckSpWp]: Trace formula consists of 1939 conjuncts, 97 conjunts are in the unsatisfiable core [2022-04-06 06:51:18,218 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 06:51:20,352 INFO L134 CoverageAnalysis]: Checked inductivity of 45429 backedges. 276 proven. 44597 refuted. 0 times theorem prover too weak. 556 trivial. 0 not checked. [2022-04-06 06:51:20,352 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 06:51:23,652 INFO L134 CoverageAnalysis]: Checked inductivity of 45429 backedges. 276 proven. 7337 refuted. 0 times theorem prover too weak. 37816 trivial. 0 not checked. [2022-04-06 06:51:23,652 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 06:51:23,652 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [505836310] [2022-04-06 06:51:23,652 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 06:51:23,653 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1595370862] [2022-04-06 06:51:23,653 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1595370862] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-06 06:51:23,653 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-06 06:51:23,653 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [50, 50] total 98 [2022-04-06 06:51:23,653 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [245331703] [2022-04-06 06:51:23,653 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-04-06 06:51:23,655 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 98 states [2022-04-06 06:51:23,655 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-06 06:51:23,656 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 98 interpolants. [2022-04-06 06:51:23,658 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=4565, Invalid=4941, Unknown=0, NotChecked=0, Total=9506 [2022-04-06 06:51:23,659 INFO L87 Difference]: Start difference. First operand 2415 states and 2732 transitions. Second operand has 98 states, 98 states have (on average 5.408163265306122) internal successors, (530), 98 states have internal predecessors, (530), 96 states have call successors, (284), 50 states have call predecessors, (284), 49 states have return successors, (282), 94 states have call predecessors, (282), 95 states have call successors, (282) [2022-04-06 06:51:28,695 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 06:51:28,696 INFO L93 Difference]: Finished difference Result 4959 states and 5612 transitions. [2022-04-06 06:51:28,697 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 190 states. [2022-04-06 06:51:28,698 INFO L78 Accepts]: Start accepts. Automaton has has 98 states, 98 states have (on average 5.408163265306122) internal successors, (530), 98 states have internal predecessors, (530), 96 states have call successors, (284), 50 states have call predecessors, (284), 49 states have return successors, (282), 94 states have call predecessors, (282), 95 states have call successors, (282) Word has length 897 [2022-04-06 06:51:28,699 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 06:51:28,714 INFO L225 Difference]: With dead ends: 4959 [2022-04-06 06:51:28,715 INFO L226 Difference]: Without dead ends: 4959 [2022-04-06 06:51:28,722 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 1886 GetRequests, 1697 SyntacticMatches, 0 SemanticMatches, 189 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 5452 ImplicationChecksByTransitivity, 5.3s TimeCoverageRelationStatistics Valid=13540, Invalid=22750, Unknown=0, NotChecked=0, Total=36290 [2022-04-06 06:51:28,723 INFO L913 BasicCegarLoop]: 311 mSDtfsCounter, 1689 mSDsluCounter, 1237 mSDsCounter, 0 mSdLazyCounter, 1486 mSolverCounterSat, 1182 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 1689 SdHoareTripleChecker+Valid, 1548 SdHoareTripleChecker+Invalid, 2668 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1182 IncrementalHoareTripleChecker+Valid, 1486 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.3s IncrementalHoareTripleChecker+Time [2022-04-06 06:51:28,723 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [1689 Valid, 1548 Invalid, 2668 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1182 Valid, 1486 Invalid, 0 Unknown, 0 Unchecked, 1.3s Time] [2022-04-06 06:51:28,727 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 4959 states. [2022-04-06 06:51:28,816 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 4959 to 4959. [2022-04-06 06:51:28,822 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 4959 states, 3275 states have (on average 1.0867175572519083) internal successors, (3559), 3369 states have internal predecessors, (3559), 1028 states have call successors, (1028), 656 states have call predecessors, (1028), 655 states have return successors, (1025), 933 states have call predecessors, (1025), 1025 states have call successors, (1025) [2022-04-06 06:51:28,836 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 4959 states to 4959 states and 5612 transitions. [2022-04-06 06:51:28,836 INFO L78 Accepts]: Start accepts. Automaton has 4959 states and 5612 transitions. Word has length 897 [2022-04-06 06:51:28,838 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 06:51:28,838 INFO L478 AbstractCegarLoop]: Abstraction has 4959 states and 5612 transitions. [2022-04-06 06:51:28,839 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 98 states, 98 states have (on average 5.408163265306122) internal successors, (530), 98 states have internal predecessors, (530), 96 states have call successors, (284), 50 states have call predecessors, (284), 49 states have return successors, (282), 94 states have call predecessors, (282), 95 states have call successors, (282) [2022-04-06 06:51:28,839 INFO L276 IsEmpty]: Start isEmpty. Operand 4959 states and 5612 transitions. [2022-04-06 06:51:28,904 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 1810 [2022-04-06 06:51:28,904 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 06:51:28,905 INFO L499 BasicCegarLoop]: trace histogram [283, 282, 282, 95, 94, 94, 94, 94, 94, 94, 94, 94, 94, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 06:51:29,014 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Forceful destruction successful, exit code 0 [2022-04-06 06:51:29,115 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,SelfDestructingSolverStorable14 [2022-04-06 06:51:29,115 INFO L403 AbstractCegarLoop]: === Iteration 16 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 06:51:29,116 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 06:51:29,116 INFO L85 PathProgramCache]: Analyzing trace with hash 1393998018, now seen corresponding path program 6 times [2022-04-06 06:51:29,116 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 06:51:29,116 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1571399120] [2022-04-06 06:51:29,117 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 06:51:29,117 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 06:51:29,170 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 06:51:29,171 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2128555116] [2022-04-06 06:51:29,171 INFO L93 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2022-04-06 06:51:29,171 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 06:51:29,171 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 06:51:29,172 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-04-06 06:51:29,175 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Waiting until timeout for monitored process