/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/AutomizerCInline.xml -s ../../../trunk/examples/settings/automizer/BvToInt/svcomp-Reach-64bit-Automizer_Bitvector.epf -i ../../../trunk/examples/svcomp/nla-digbench-scaling/egcd3-ll_unwindbound100.c -------------------------------------------------------------------------------- This is Ultimate 0.2.2-dev-a10ec3b [2022-01-10 03:09:41,031 INFO L177 SettingsManager]: Resetting all preferences to default values... [2022-01-10 03:09:41,032 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2022-01-10 03:09:41,055 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2022-01-10 03:09:41,055 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2022-01-10 03:09:41,056 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2022-01-10 03:09:41,057 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2022-01-10 03:09:41,058 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2022-01-10 03:09:41,059 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2022-01-10 03:09:41,060 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2022-01-10 03:09:41,060 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2022-01-10 03:09:41,061 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2022-01-10 03:09:41,061 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2022-01-10 03:09:41,062 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2022-01-10 03:09:41,063 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2022-01-10 03:09:41,064 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2022-01-10 03:09:41,064 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2022-01-10 03:09:41,065 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2022-01-10 03:09:41,066 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2022-01-10 03:09:41,067 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2022-01-10 03:09:41,097 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2022-01-10 03:09:41,098 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2022-01-10 03:09:41,098 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2022-01-10 03:09:41,099 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2022-01-10 03:09:41,101 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2022-01-10 03:09:41,101 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2022-01-10 03:09:41,101 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2022-01-10 03:09:41,102 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2022-01-10 03:09:41,102 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2022-01-10 03:09:41,103 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2022-01-10 03:09:41,103 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2022-01-10 03:09:41,108 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2022-01-10 03:09:41,109 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2022-01-10 03:09:41,109 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2022-01-10 03:09:41,110 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2022-01-10 03:09:41,110 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2022-01-10 03:09:41,111 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2022-01-10 03:09:41,111 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2022-01-10 03:09:41,111 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2022-01-10 03:09:41,112 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2022-01-10 03:09:41,112 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2022-01-10 03:09:41,116 INFO L101 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/automizer/BvToInt/svcomp-Reach-64bit-Automizer_Bitvector.epf [2022-01-10 03:09:41,148 INFO L113 SettingsManager]: Loading preferences was successful [2022-01-10 03:09:41,148 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2022-01-10 03:09:41,149 INFO L136 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2022-01-10 03:09:41,149 INFO L138 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2022-01-10 03:09:41,149 INFO L136 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2022-01-10 03:09:41,150 INFO L138 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2022-01-10 03:09:41,151 INFO L136 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2022-01-10 03:09:41,151 INFO L138 SettingsManager]: * Create parallel compositions if possible=false [2022-01-10 03:09:41,151 INFO L138 SettingsManager]: * Use SBE=true [2022-01-10 03:09:41,151 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2022-01-10 03:09:41,152 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2022-01-10 03:09:41,152 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2022-01-10 03:09:41,152 INFO L138 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2022-01-10 03:09:41,152 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2022-01-10 03:09:41,153 INFO L138 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2022-01-10 03:09:41,153 INFO L138 SettingsManager]: * Adapt memory model on pointer casts if necessary=true [2022-01-10 03:09:41,153 INFO L138 SettingsManager]: * Use bitvectors instead of ints=true [2022-01-10 03:09:41,153 INFO L138 SettingsManager]: * Memory model=HoenickeLindenmann_4ByteResolution [2022-01-10 03:09:41,153 INFO L138 SettingsManager]: * Check if freed pointer was valid=false [2022-01-10 03:09:41,153 INFO L138 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2022-01-10 03:09:41,153 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2022-01-10 03:09:41,153 INFO L138 SettingsManager]: * Size of a code block=SequenceOfStatements [2022-01-10 03:09:41,153 INFO L138 SettingsManager]: * SMT solver=External_DefaultMode [2022-01-10 03:09:41,153 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-01-10 03:09:41,154 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2022-01-10 03:09:41,154 INFO L138 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2022-01-10 03:09:41,155 INFO L138 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2022-01-10 03:09:41,155 INFO L138 SettingsManager]: * Trace refinement strategy=WOLF [2022-01-10 03:09:41,155 INFO L138 SettingsManager]: * Command for external solver=cvc4 --incremental --print-success --lang smt [2022-01-10 03:09:41,155 INFO L138 SettingsManager]: * Large block encoding in concurrent analysis=OFF [2022-01-10 03:09:41,155 INFO L138 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2022-01-10 03:09:41,155 INFO L138 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2022-01-10 03:09:41,155 INFO L138 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2022-01-10 03:09:41,156 INFO L138 SettingsManager]: * Logic for external solver=AUFBV 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-01-10 03:09:41,376 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2022-01-10 03:09:41,400 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2022-01-10 03:09:41,402 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2022-01-10 03:09:41,403 INFO L271 PluginConnector]: Initializing CDTParser... [2022-01-10 03:09:41,405 INFO L275 PluginConnector]: CDTParser initialized [2022-01-10 03:09:41,406 INFO L432 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/svcomp/nla-digbench-scaling/egcd3-ll_unwindbound100.c [2022-01-10 03:09:41,463 INFO L220 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/137684a4d/3991d1bd4f9b40a09862c3a3ffa22be5/FLAG54d9cd9b0 [2022-01-10 03:09:41,793 INFO L306 CDTParser]: Found 1 translation units. [2022-01-10 03:09:41,793 INFO L160 CDTParser]: Scanning /storage/repos/ultimate/trunk/examples/svcomp/nla-digbench-scaling/egcd3-ll_unwindbound100.c [2022-01-10 03:09:41,798 INFO L349 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/137684a4d/3991d1bd4f9b40a09862c3a3ffa22be5/FLAG54d9cd9b0 [2022-01-10 03:09:42,205 INFO L357 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/137684a4d/3991d1bd4f9b40a09862c3a3ffa22be5 [2022-01-10 03:09:42,207 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2022-01-10 03:09:42,208 INFO L131 ToolchainWalker]: Walking toolchain with 5 elements. [2022-01-10 03:09:42,210 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2022-01-10 03:09:42,210 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2022-01-10 03:09:42,212 INFO L275 PluginConnector]: CACSL2BoogieTranslator initialized [2022-01-10 03:09:42,213 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 10.01 03:09:42" (1/1) ... [2022-01-10 03:09:42,214 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@19e7d5d1 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.01 03:09:42, skipping insertion in model container [2022-01-10 03:09:42,214 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 10.01 03:09:42" (1/1) ... [2022-01-10 03:09:42,221 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2022-01-10 03:09:42,234 INFO L178 MainTranslator]: Built tables and reachable declarations [2022-01-10 03:09:42,359 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/egcd3-ll_unwindbound100.c[490,503] [2022-01-10 03:09:42,413 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-01-10 03:09:42,433 INFO L203 MainTranslator]: Completed pre-run [2022-01-10 03:09:42,445 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/egcd3-ll_unwindbound100.c[490,503] [2022-01-10 03:09:42,467 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-01-10 03:09:42,479 INFO L208 MainTranslator]: Completed translation [2022-01-10 03:09:42,479 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.01 03:09:42 WrapperNode [2022-01-10 03:09:42,479 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2022-01-10 03:09:42,480 INFO L113 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2022-01-10 03:09:42,480 INFO L271 PluginConnector]: Initializing Boogie Procedure Inliner... [2022-01-10 03:09:42,480 INFO L275 PluginConnector]: Boogie Procedure Inliner initialized [2022-01-10 03:09:42,485 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.01 03:09:42" (1/1) ... [2022-01-10 03:09:42,496 INFO L185 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.01 03:09:42" (1/1) ... [2022-01-10 03:09:42,515 INFO L137 Inliner]: procedures = 14, calls = 14, calls flagged for inlining = 2, calls inlined = 2, statements flattened = 89 [2022-01-10 03:09:42,516 INFO L132 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2022-01-10 03:09:42,516 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2022-01-10 03:09:42,516 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2022-01-10 03:09:42,516 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2022-01-10 03:09:42,522 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.01 03:09:42" (1/1) ... [2022-01-10 03:09:42,522 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.01 03:09:42" (1/1) ... [2022-01-10 03:09:42,526 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.01 03:09:42" (1/1) ... [2022-01-10 03:09:42,527 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.01 03:09:42" (1/1) ... [2022-01-10 03:09:42,538 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.01 03:09:42" (1/1) ... [2022-01-10 03:09:42,542 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.01 03:09:42" (1/1) ... [2022-01-10 03:09:42,546 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.01 03:09:42" (1/1) ... [2022-01-10 03:09:42,550 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2022-01-10 03:09:42,551 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2022-01-10 03:09:42,551 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2022-01-10 03:09:42,551 INFO L275 PluginConnector]: RCFGBuilder initialized [2022-01-10 03:09:42,552 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.01 03:09:42" (1/1) ... [2022-01-10 03:09:42,557 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-01-10 03:09:42,564 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-01-10 03:09:42,577 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-01-10 03:09:42,583 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-01-10 03:09:42,605 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2022-01-10 03:09:42,606 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~intINTTYPE1 [2022-01-10 03:09:42,606 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2022-01-10 03:09:42,606 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2022-01-10 03:09:42,606 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2022-01-10 03:09:42,606 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2022-01-10 03:09:42,606 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2022-01-10 03:09:42,606 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2022-01-10 03:09:42,647 INFO L234 CfgBuilder]: Building ICFG [2022-01-10 03:09:42,648 INFO L260 CfgBuilder]: Building CFG for each procedure with an implementation [2022-01-10 03:09:42,939 INFO L275 CfgBuilder]: Performing block encoding [2022-01-10 03:09:42,943 INFO L294 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2022-01-10 03:09:42,943 INFO L299 CfgBuilder]: Removed 3 assume(true) statements. [2022-01-10 03:09:42,944 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 10.01 03:09:42 BoogieIcfgContainer [2022-01-10 03:09:42,945 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2022-01-10 03:09:42,946 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2022-01-10 03:09:42,946 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2022-01-10 03:09:42,948 INFO L275 PluginConnector]: TraceAbstraction initialized [2022-01-10 03:09:42,948 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 10.01 03:09:42" (1/3) ... [2022-01-10 03:09:42,949 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@34febe9f and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 10.01 03:09:42, skipping insertion in model container [2022-01-10 03:09:42,949 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.01 03:09:42" (2/3) ... [2022-01-10 03:09:42,949 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@34febe9f and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 10.01 03:09:42, skipping insertion in model container [2022-01-10 03:09:42,949 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 10.01 03:09:42" (3/3) ... [2022-01-10 03:09:42,952 INFO L111 eAbstractionObserver]: Analyzing ICFG egcd3-ll_unwindbound100.c [2022-01-10 03:09:42,956 INFO L204 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2022-01-10 03:09:42,956 INFO L163 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2022-01-10 03:09:42,997 INFO L338 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2022-01-10 03:09:43,004 INFO L339 AbstractCegarLoop]: Settings: SEPARATE_VIOLATION_CHECK=true, mInterprocedural=true, mMaxIterations=1000000, mWatchIteration=1000000, mArtifact=RCFG, mInterpolation=FPandBP, mInterpolantAutomaton=STRAIGHT_LINE, mDumpAutomata=false, mAutomataFormat=ATS_NUMERATE, mDumpPath=., mDeterminiation=PREDICATE_ABSTRACTION, mMinimize=MINIMIZE_SEVPA, mHoare=true, mAutomataTypeConcurrency=PETRI_NET, mHoareTripleChecks=INCREMENTAL, mHoareAnnotationPositions=LoopsAndPotentialCycles, mDumpOnlyReuseAutomata=false, mLimitTraceHistogram=0, mErrorLocTimeLimit=0, mLimitPathProgramCount=0, mCollectInterpolantStatistics=true, mHeuristicEmptinessCheck=false, mHeuristicEmptinessCheckAStarHeuristic=ZERO, mHeuristicEmptinessCheckAStarHeuristicRandomSeed=1337, mHeuristicEmptinessCheckSmtFeatureScoringMethod=DAGSIZE, mSMTFeatureExtraction=false, mSMTFeatureExtractionDumpPath=., mOverrideInterpolantAutomaton=false, mMcrInterpolantMethod=WP, mLoopAccelerationTechnique=FAST_UPR [2022-01-10 03:09:43,004 INFO L340 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2022-01-10 03:09:43,020 INFO L276 IsEmpty]: Start isEmpty. Operand has 35 states, 24 states have (on average 1.5) internal successors, (36), 25 states have internal predecessors, (36), 7 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2022-01-10 03:09:43,022 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 19 [2022-01-10 03:09:43,023 INFO L506 BasicCegarLoop]: Found error trace [2022-01-10 03:09:43,023 INFO L514 BasicCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-01-10 03:09:43,024 INFO L402 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-01-10 03:09:43,027 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-01-10 03:09:43,027 INFO L85 PathProgramCache]: Analyzing trace with hash 1663185933, now seen corresponding path program 1 times [2022-01-10 03:09:43,035 INFO L121 FreeRefinementEngine]: Executing refinement strategy WOLF [2022-01-10 03:09:43,035 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleMathsat [1229540684] [2022-01-10 03:09:43,035 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-01-10 03:09:43,036 INFO L168 SolverBuilder]: Constructing external solver with command: mathsat -unsat_core_generation=3 [2022-01-10 03:09:43,036 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat [2022-01-10 03:09:43,037 INFO L229 MonitoredProcess]: Starting monitored process 2 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (exit command is (exit), workingDir is null) [2022-01-10 03:09:43,038 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (2)] Waiting until timeout for monitored process [2022-01-10 03:09:43,147 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-10 03:09:43,163 INFO L263 TraceCheckSpWp]: Trace formula consists of 43 conjuncts, 1 conjunts are in the unsatisfiable core [2022-01-10 03:09:43,166 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-01-10 03:09:43,216 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2022-01-10 03:09:43,216 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-01-10 03:09:43,216 INFO L139 FreeRefinementEngine]: Strategy WOLF found an infeasible trace [2022-01-10 03:09:43,216 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleMathsat [1229540684] [2022-01-10 03:09:43,217 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleMathsat [1229540684] provided 1 perfect and 0 imperfect interpolant sequences [2022-01-10 03:09:43,217 INFO L186 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-01-10 03:09:43,217 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2022-01-10 03:09:43,218 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [679119636] [2022-01-10 03:09:43,219 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-01-10 03:09:43,221 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2022-01-10 03:09:43,221 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy WOLF [2022-01-10 03:09:43,239 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2022-01-10 03:09:43,239 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2022-01-10 03:09:43,241 INFO L87 Difference]: Start difference. First operand has 35 states, 24 states have (on average 1.5) internal successors, (36), 25 states have internal predecessors, (36), 7 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) Second operand has 2 states, 2 states have (on average 5.0) internal successors, (10), 2 states have internal predecessors, (10), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2022-01-10 03:09:43,264 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-01-10 03:09:43,264 INFO L93 Difference]: Finished difference Result 67 states and 103 transitions. [2022-01-10 03:09:43,265 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2022-01-10 03:09:43,266 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 5.0) internal successors, (10), 2 states have internal predecessors, (10), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) Word has length 18 [2022-01-10 03:09:43,267 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-01-10 03:09:43,271 INFO L225 Difference]: With dead ends: 67 [2022-01-10 03:09:43,271 INFO L226 Difference]: Without dead ends: 31 [2022-01-10 03:09:43,274 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 17 GetRequests, 17 SyntacticMatches, 0 SemanticMatches, 0 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2022-01-10 03:09:43,276 INFO L933 BasicCegarLoop]: 45 mSDtfsCounter, 0 mSDsluCounter, 0 mSDsCounter, 0 mSdLazyCounter, 0 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 45 SdHoareTripleChecker+Invalid, 0 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 0 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-01-10 03:09:43,277 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [0 Valid, 45 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 0 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-01-10 03:09:43,290 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 31 states. [2022-01-10 03:09:43,302 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 31 to 31. [2022-01-10 03:09:43,302 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 31 states, 21 states have (on average 1.3333333333333333) internal successors, (28), 22 states have internal predecessors, (28), 7 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2022-01-10 03:09:43,303 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 31 states to 31 states and 41 transitions. [2022-01-10 03:09:43,304 INFO L78 Accepts]: Start accepts. Automaton has 31 states and 41 transitions. Word has length 18 [2022-01-10 03:09:43,304 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-01-10 03:09:43,305 INFO L470 AbstractCegarLoop]: Abstraction has 31 states and 41 transitions. [2022-01-10 03:09:43,305 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 2 states have (on average 5.0) internal successors, (10), 2 states have internal predecessors, (10), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2022-01-10 03:09:43,305 INFO L276 IsEmpty]: Start isEmpty. Operand 31 states and 41 transitions. [2022-01-10 03:09:43,306 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 20 [2022-01-10 03:09:43,306 INFO L506 BasicCegarLoop]: Found error trace [2022-01-10 03:09:43,306 INFO L514 BasicCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-01-10 03:09:43,316 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (2)] Ended with exit code 0 [2022-01-10 03:09:43,514 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 [2022-01-10 03:09:43,515 INFO L402 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-01-10 03:09:43,516 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-01-10 03:09:43,516 INFO L85 PathProgramCache]: Analyzing trace with hash 1013747788, now seen corresponding path program 1 times [2022-01-10 03:09:43,516 INFO L121 FreeRefinementEngine]: Executing refinement strategy WOLF [2022-01-10 03:09:43,517 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleMathsat [1663023905] [2022-01-10 03:09:43,517 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-01-10 03:09:43,517 INFO L168 SolverBuilder]: Constructing external solver with command: mathsat -unsat_core_generation=3 [2022-01-10 03:09:43,517 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat [2022-01-10 03:09:43,518 INFO L229 MonitoredProcess]: Starting monitored process 3 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (exit command is (exit), workingDir is null) [2022-01-10 03:09:43,520 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (3)] Waiting until timeout for monitored process [2022-01-10 03:09:43,626 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-10 03:09:43,643 INFO L263 TraceCheckSpWp]: Trace formula consists of 45 conjuncts, 3 conjunts are in the unsatisfiable core [2022-01-10 03:09:43,645 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-01-10 03:09:43,760 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2022-01-10 03:09:43,760 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-01-10 03:09:43,760 INFO L139 FreeRefinementEngine]: Strategy WOLF found an infeasible trace [2022-01-10 03:09:43,760 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleMathsat [1663023905] [2022-01-10 03:09:43,760 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleMathsat [1663023905] provided 1 perfect and 0 imperfect interpolant sequences [2022-01-10 03:09:43,761 INFO L186 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-01-10 03:09:43,761 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2022-01-10 03:09:43,761 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1512569210] [2022-01-10 03:09:43,761 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-01-10 03:09:43,762 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2022-01-10 03:09:43,762 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy WOLF [2022-01-10 03:09:43,762 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2022-01-10 03:09:43,763 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2022-01-10 03:09:43,763 INFO L87 Difference]: Start difference. First operand 31 states and 41 transitions. Second operand has 4 states, 4 states have (on average 2.75) internal successors, (11), 3 states have internal predecessors, (11), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2022-01-10 03:09:43,799 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-01-10 03:09:43,800 INFO L93 Difference]: Finished difference Result 40 states and 50 transitions. [2022-01-10 03:09:43,800 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2022-01-10 03:09:43,800 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 2.75) internal successors, (11), 3 states have internal predecessors, (11), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) Word has length 19 [2022-01-10 03:09:43,800 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-01-10 03:09:43,801 INFO L225 Difference]: With dead ends: 40 [2022-01-10 03:09:43,801 INFO L226 Difference]: Without dead ends: 33 [2022-01-10 03:09:43,801 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 18 GetRequests, 16 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2022-01-10 03:09:43,803 INFO L933 BasicCegarLoop]: 39 mSDtfsCounter, 0 mSDsluCounter, 64 mSDsCounter, 0 mSdLazyCounter, 10 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 103 SdHoareTripleChecker+Invalid, 10 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 10 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-01-10 03:09:43,803 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [0 Valid, 103 Invalid, 10 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 10 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-01-10 03:09:43,804 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 33 states. [2022-01-10 03:09:43,808 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 33 to 33. [2022-01-10 03:09:43,809 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 33 states, 23 states have (on average 1.3043478260869565) internal successors, (30), 24 states have internal predecessors, (30), 7 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2022-01-10 03:09:43,810 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 33 states to 33 states and 43 transitions. [2022-01-10 03:09:43,810 INFO L78 Accepts]: Start accepts. Automaton has 33 states and 43 transitions. Word has length 19 [2022-01-10 03:09:43,811 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-01-10 03:09:43,811 INFO L470 AbstractCegarLoop]: Abstraction has 33 states and 43 transitions. [2022-01-10 03:09:43,811 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 2.75) internal successors, (11), 3 states have internal predecessors, (11), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2022-01-10 03:09:43,811 INFO L276 IsEmpty]: Start isEmpty. Operand 33 states and 43 transitions. [2022-01-10 03:09:43,812 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 21 [2022-01-10 03:09:43,812 INFO L506 BasicCegarLoop]: Found error trace [2022-01-10 03:09:43,812 INFO L514 BasicCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-01-10 03:09:43,823 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (3)] Forceful destruction successful, exit code 0 [2022-01-10 03:09:44,013 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 3 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 [2022-01-10 03:09:44,013 INFO L402 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-01-10 03:09:44,014 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-01-10 03:09:44,014 INFO L85 PathProgramCache]: Analyzing trace with hash 1341775226, now seen corresponding path program 1 times [2022-01-10 03:09:44,014 INFO L121 FreeRefinementEngine]: Executing refinement strategy WOLF [2022-01-10 03:09:44,014 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleMathsat [744006787] [2022-01-10 03:09:44,015 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-01-10 03:09:44,015 INFO L168 SolverBuilder]: Constructing external solver with command: mathsat -unsat_core_generation=3 [2022-01-10 03:09:44,015 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat [2022-01-10 03:09:44,017 INFO L229 MonitoredProcess]: Starting monitored process 4 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (exit command is (exit), workingDir is null) [2022-01-10 03:09:44,018 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (4)] Waiting until timeout for monitored process [2022-01-10 03:09:44,130 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-10 03:09:44,147 INFO L263 TraceCheckSpWp]: Trace formula consists of 46 conjuncts, 5 conjunts are in the unsatisfiable core [2022-01-10 03:09:44,149 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-01-10 03:09:44,333 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 3 proven. 0 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2022-01-10 03:09:44,333 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-01-10 03:09:44,333 INFO L139 FreeRefinementEngine]: Strategy WOLF found an infeasible trace [2022-01-10 03:09:44,334 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleMathsat [744006787] [2022-01-10 03:09:44,334 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleMathsat [744006787] provided 1 perfect and 0 imperfect interpolant sequences [2022-01-10 03:09:44,334 INFO L186 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-01-10 03:09:44,334 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2022-01-10 03:09:44,334 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1121023000] [2022-01-10 03:09:44,334 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-01-10 03:09:44,335 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2022-01-10 03:09:44,335 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy WOLF [2022-01-10 03:09:44,335 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2022-01-10 03:09:44,335 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2022-01-10 03:09:44,336 INFO L87 Difference]: Start difference. First operand 33 states and 43 transitions. Second operand has 6 states, 6 states have (on average 2.5) internal successors, (15), 5 states have internal predecessors, (15), 2 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) [2022-01-10 03:09:44,413 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-01-10 03:09:44,413 INFO L93 Difference]: Finished difference Result 41 states and 51 transitions. [2022-01-10 03:09:44,413 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2022-01-10 03:09:44,413 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 2.5) internal successors, (15), 5 states have internal predecessors, (15), 2 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) Word has length 20 [2022-01-10 03:09:44,413 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-01-10 03:09:44,414 INFO L225 Difference]: With dead ends: 41 [2022-01-10 03:09:44,414 INFO L226 Difference]: Without dead ends: 34 [2022-01-10 03:09:44,414 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 21 GetRequests, 15 SyntacticMatches, 0 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=17, Invalid=39, Unknown=0, NotChecked=0, Total=56 [2022-01-10 03:09:44,415 INFO L933 BasicCegarLoop]: 36 mSDtfsCounter, 5 mSDsluCounter, 130 mSDsCounter, 0 mSdLazyCounter, 18 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 5 SdHoareTripleChecker+Valid, 166 SdHoareTripleChecker+Invalid, 27 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 18 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 9 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-01-10 03:09:44,416 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [5 Valid, 166 Invalid, 27 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 18 Invalid, 0 Unknown, 9 Unchecked, 0.0s Time] [2022-01-10 03:09:44,416 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 34 states. [2022-01-10 03:09:44,420 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 34 to 34. [2022-01-10 03:09:44,421 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 34 states, 24 states have (on average 1.2916666666666667) internal successors, (31), 25 states have internal predecessors, (31), 7 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2022-01-10 03:09:44,421 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 34 states to 34 states and 44 transitions. [2022-01-10 03:09:44,421 INFO L78 Accepts]: Start accepts. Automaton has 34 states and 44 transitions. Word has length 20 [2022-01-10 03:09:44,422 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-01-10 03:09:44,422 INFO L470 AbstractCegarLoop]: Abstraction has 34 states and 44 transitions. [2022-01-10 03:09:44,422 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 2.5) internal successors, (15), 5 states have internal predecessors, (15), 2 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) [2022-01-10 03:09:44,422 INFO L276 IsEmpty]: Start isEmpty. Operand 34 states and 44 transitions. [2022-01-10 03:09:44,423 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 26 [2022-01-10 03:09:44,423 INFO L506 BasicCegarLoop]: Found error trace [2022-01-10 03:09:44,423 INFO L514 BasicCegarLoop]: trace histogram [2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-01-10 03:09:44,433 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (4)] Ended with exit code 0 [2022-01-10 03:09:44,633 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 [2022-01-10 03:09:44,633 INFO L402 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-01-10 03:09:44,634 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-01-10 03:09:44,634 INFO L85 PathProgramCache]: Analyzing trace with hash -1315139464, now seen corresponding path program 1 times [2022-01-10 03:09:44,634 INFO L121 FreeRefinementEngine]: Executing refinement strategy WOLF [2022-01-10 03:09:44,634 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleMathsat [23671708] [2022-01-10 03:09:44,634 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-01-10 03:09:44,635 INFO L168 SolverBuilder]: Constructing external solver with command: mathsat -unsat_core_generation=3 [2022-01-10 03:09:44,635 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat [2022-01-10 03:09:44,636 INFO L229 MonitoredProcess]: Starting monitored process 5 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (exit command is (exit), workingDir is null) [2022-01-10 03:09:44,636 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (5)] Waiting until timeout for monitored process [2022-01-10 03:09:44,784 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-10 03:09:44,810 INFO L263 TraceCheckSpWp]: Trace formula consists of 61 conjuncts, 5 conjunts are in the unsatisfiable core [2022-01-10 03:09:44,811 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-01-10 03:09:44,907 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2022-01-10 03:09:44,908 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-01-10 03:09:44,908 INFO L139 FreeRefinementEngine]: Strategy WOLF found an infeasible trace [2022-01-10 03:09:44,908 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleMathsat [23671708] [2022-01-10 03:09:44,911 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleMathsat [23671708] provided 1 perfect and 0 imperfect interpolant sequences [2022-01-10 03:09:44,912 INFO L186 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-01-10 03:09:44,912 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2022-01-10 03:09:44,912 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [824413697] [2022-01-10 03:09:44,912 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-01-10 03:09:44,912 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-01-10 03:09:44,913 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy WOLF [2022-01-10 03:09:44,913 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-01-10 03:09:44,913 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-01-10 03:09:44,914 INFO L87 Difference]: Start difference. First operand 34 states and 44 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, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2022-01-10 03:09:44,974 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-01-10 03:09:44,974 INFO L93 Difference]: Finished difference Result 58 states and 78 transitions. [2022-01-10 03:09:44,975 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-01-10 03:09:44,975 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, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) Word has length 25 [2022-01-10 03:09:44,975 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-01-10 03:09:44,977 INFO L225 Difference]: With dead ends: 58 [2022-01-10 03:09:44,977 INFO L226 Difference]: Without dead ends: 36 [2022-01-10 03:09:44,979 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 24 GetRequests, 21 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-01-10 03:09:44,981 INFO L933 BasicCegarLoop]: 38 mSDtfsCounter, 0 mSDsluCounter, 95 mSDsCounter, 0 mSdLazyCounter, 21 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 133 SdHoareTripleChecker+Invalid, 21 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 21 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-01-10 03:09:44,982 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [0 Valid, 133 Invalid, 21 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 21 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-01-10 03:09:44,983 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 36 states. [2022-01-10 03:09:44,986 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 36 to 36. [2022-01-10 03:09:44,986 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 36 states, 26 states have (on average 1.2692307692307692) internal successors, (33), 27 states have internal predecessors, (33), 7 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2022-01-10 03:09:44,987 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 36 states to 36 states and 46 transitions. [2022-01-10 03:09:44,987 INFO L78 Accepts]: Start accepts. Automaton has 36 states and 46 transitions. Word has length 25 [2022-01-10 03:09:44,987 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-01-10 03:09:44,987 INFO L470 AbstractCegarLoop]: Abstraction has 36 states and 46 transitions. [2022-01-10 03:09:44,987 INFO L471 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, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2022-01-10 03:09:44,987 INFO L276 IsEmpty]: Start isEmpty. Operand 36 states and 46 transitions. [2022-01-10 03:09:44,988 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 26 [2022-01-10 03:09:44,988 INFO L506 BasicCegarLoop]: Found error trace [2022-01-10 03:09:44,988 INFO L514 BasicCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-01-10 03:09:45,001 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (5)] Ended with exit code 0 [2022-01-10 03:09:45,200 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 [2022-01-10 03:09:45,201 INFO L402 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-01-10 03:09:45,201 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-01-10 03:09:45,201 INFO L85 PathProgramCache]: Analyzing trace with hash 570907173, now seen corresponding path program 1 times [2022-01-10 03:09:45,202 INFO L121 FreeRefinementEngine]: Executing refinement strategy WOLF [2022-01-10 03:09:45,202 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleMathsat [671337896] [2022-01-10 03:09:45,202 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-01-10 03:09:45,202 INFO L168 SolverBuilder]: Constructing external solver with command: mathsat -unsat_core_generation=3 [2022-01-10 03:09:45,202 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat [2022-01-10 03:09:45,203 INFO L229 MonitoredProcess]: Starting monitored process 6 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (exit command is (exit), workingDir is null) [2022-01-10 03:09:45,204 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (6)] Waiting until timeout for monitored process [2022-01-10 03:09:45,284 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-10 03:09:45,292 INFO L263 TraceCheckSpWp]: Trace formula consists of 57 conjuncts, 12 conjunts are in the unsatisfiable core [2022-01-10 03:09:45,294 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-01-10 03:09:45,629 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2022-01-10 03:09:45,629 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-01-10 03:09:45,630 INFO L139 FreeRefinementEngine]: Strategy WOLF found an infeasible trace [2022-01-10 03:09:45,630 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleMathsat [671337896] [2022-01-10 03:09:45,630 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleMathsat [671337896] provided 1 perfect and 0 imperfect interpolant sequences [2022-01-10 03:09:45,630 INFO L186 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-01-10 03:09:45,630 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [9] imperfect sequences [] total 9 [2022-01-10 03:09:45,630 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [409377669] [2022-01-10 03:09:45,630 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-01-10 03:09:45,630 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2022-01-10 03:09:45,630 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy WOLF [2022-01-10 03:09:45,631 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2022-01-10 03:09:45,631 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=18, Invalid=54, Unknown=0, NotChecked=0, Total=72 [2022-01-10 03:09:45,631 INFO L87 Difference]: Start difference. First operand 36 states and 46 transitions. Second operand has 9 states, 8 states have (on average 2.125) internal successors, (17), 6 states have internal predecessors, (17), 3 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2022-01-10 03:09:47,873 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-01-10 03:09:47,873 INFO L93 Difference]: Finished difference Result 54 states and 71 transitions. [2022-01-10 03:09:47,881 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2022-01-10 03:09:47,882 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 8 states have (on average 2.125) internal successors, (17), 6 states have internal predecessors, (17), 3 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) Word has length 25 [2022-01-10 03:09:47,882 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-01-10 03:09:47,882 INFO L225 Difference]: With dead ends: 54 [2022-01-10 03:09:47,882 INFO L226 Difference]: Without dead ends: 52 [2022-01-10 03:09:47,883 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 26 GetRequests, 17 SyntacticMatches, 0 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 9 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=26, Invalid=84, Unknown=0, NotChecked=0, Total=110 [2022-01-10 03:09:47,883 INFO L933 BasicCegarLoop]: 36 mSDtfsCounter, 71 mSDsluCounter, 159 mSDsCounter, 0 mSdLazyCounter, 66 mSolverCounterSat, 10 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 2.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 80 SdHoareTripleChecker+Valid, 195 SdHoareTripleChecker+Invalid, 76 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 10 IncrementalHoareTripleChecker+Valid, 66 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 2.2s IncrementalHoareTripleChecker+Time [2022-01-10 03:09:47,884 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [80 Valid, 195 Invalid, 76 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [10 Valid, 66 Invalid, 0 Unknown, 0 Unchecked, 2.2s Time] [2022-01-10 03:09:47,884 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 52 states. [2022-01-10 03:09:47,889 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 52 to 51. [2022-01-10 03:09:47,889 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 51 states, 36 states have (on average 1.3055555555555556) internal successors, (47), 37 states have internal predecessors, (47), 11 states have call successors, (11), 3 states have call predecessors, (11), 3 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2022-01-10 03:09:47,890 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 51 states to 51 states and 68 transitions. [2022-01-10 03:09:47,890 INFO L78 Accepts]: Start accepts. Automaton has 51 states and 68 transitions. Word has length 25 [2022-01-10 03:09:47,890 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-01-10 03:09:47,890 INFO L470 AbstractCegarLoop]: Abstraction has 51 states and 68 transitions. [2022-01-10 03:09:47,891 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 8 states have (on average 2.125) internal successors, (17), 6 states have internal predecessors, (17), 3 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2022-01-10 03:09:47,891 INFO L276 IsEmpty]: Start isEmpty. Operand 51 states and 68 transitions. [2022-01-10 03:09:47,891 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 27 [2022-01-10 03:09:47,891 INFO L506 BasicCegarLoop]: Found error trace [2022-01-10 03:09:47,891 INFO L514 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] [2022-01-10 03:09:47,899 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (6)] Forceful destruction successful, exit code 0 [2022-01-10 03:09:48,099 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 [2022-01-10 03:09:48,100 INFO L402 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-01-10 03:09:48,100 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-01-10 03:09:48,100 INFO L85 PathProgramCache]: Analyzing trace with hash -1698298847, now seen corresponding path program 1 times [2022-01-10 03:09:48,101 INFO L121 FreeRefinementEngine]: Executing refinement strategy WOLF [2022-01-10 03:09:48,101 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleMathsat [1041433699] [2022-01-10 03:09:48,101 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-01-10 03:09:48,101 INFO L168 SolverBuilder]: Constructing external solver with command: mathsat -unsat_core_generation=3 [2022-01-10 03:09:48,101 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat [2022-01-10 03:09:48,102 INFO L229 MonitoredProcess]: Starting monitored process 7 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (exit command is (exit), workingDir is null) [2022-01-10 03:09:48,103 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (7)] Waiting until timeout for monitored process [2022-01-10 03:09:48,277 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-10 03:09:48,303 INFO L263 TraceCheckSpWp]: Trace formula consists of 62 conjuncts, 7 conjunts are in the unsatisfiable core [2022-01-10 03:09:48,304 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-01-10 03:09:48,482 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2022-01-10 03:09:48,483 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-01-10 03:09:48,700 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2022-01-10 03:09:48,700 INFO L139 FreeRefinementEngine]: Strategy WOLF found an infeasible trace [2022-01-10 03:09:48,700 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleMathsat [1041433699] [2022-01-10 03:09:48,700 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleMathsat [1041433699] provided 0 perfect and 2 imperfect interpolant sequences [2022-01-10 03:09:48,700 INFO L186 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-01-10 03:09:48,701 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 6] total 10 [2022-01-10 03:09:48,701 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1951976312] [2022-01-10 03:09:48,701 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-01-10 03:09:48,701 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2022-01-10 03:09:48,701 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy WOLF [2022-01-10 03:09:48,701 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2022-01-10 03:09:48,702 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=27, Invalid=63, Unknown=0, NotChecked=0, Total=90 [2022-01-10 03:09:48,702 INFO L87 Difference]: Start difference. First operand 51 states and 68 transitions. Second operand has 10 states, 10 states have (on average 3.3) internal successors, (33), 10 states have internal predecessors, (33), 3 states have call successors, (5), 3 states have call predecessors, (5), 2 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2022-01-10 03:09:52,321 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.20s for a HTC check with result INVALID. Formula has sorts [Bool, BitVec], hasArrays=false, hasNonlinArith=false, quantifiers [] [2022-01-10 03:09:55,367 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-01-10 03:09:55,367 INFO L93 Difference]: Finished difference Result 147 states and 193 transitions. [2022-01-10 03:09:55,376 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2022-01-10 03:09:55,376 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 10 states have (on average 3.3) internal successors, (33), 10 states have internal predecessors, (33), 3 states have call successors, (5), 3 states have call predecessors, (5), 2 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) Word has length 26 [2022-01-10 03:09:55,376 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-01-10 03:09:55,378 INFO L225 Difference]: With dead ends: 147 [2022-01-10 03:09:55,378 INFO L226 Difference]: Without dead ends: 140 [2022-01-10 03:09:55,378 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 55 GetRequests, 42 SyntacticMatches, 0 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 15 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=67, Invalid=143, Unknown=0, NotChecked=0, Total=210 [2022-01-10 03:09:55,379 INFO L933 BasicCegarLoop]: 49 mSDtfsCounter, 98 mSDsluCounter, 194 mSDsCounter, 0 mSdLazyCounter, 117 mSolverCounterSat, 69 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 6.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 98 SdHoareTripleChecker+Valid, 243 SdHoareTripleChecker+Invalid, 186 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 69 IncrementalHoareTripleChecker+Valid, 117 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 6.4s IncrementalHoareTripleChecker+Time [2022-01-10 03:09:55,379 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [98 Valid, 243 Invalid, 186 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [69 Valid, 117 Invalid, 0 Unknown, 0 Unchecked, 6.4s Time] [2022-01-10 03:09:55,379 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 140 states. [2022-01-10 03:09:55,396 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 140 to 97. [2022-01-10 03:09:55,397 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 97 states, 69 states have (on average 1.3333333333333333) internal successors, (92), 71 states have internal predecessors, (92), 20 states have call successors, (20), 7 states have call predecessors, (20), 7 states have return successors, (18), 18 states have call predecessors, (18), 18 states have call successors, (18) [2022-01-10 03:09:55,398 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 97 states to 97 states and 130 transitions. [2022-01-10 03:09:55,398 INFO L78 Accepts]: Start accepts. Automaton has 97 states and 130 transitions. Word has length 26 [2022-01-10 03:09:55,398 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-01-10 03:09:55,398 INFO L470 AbstractCegarLoop]: Abstraction has 97 states and 130 transitions. [2022-01-10 03:09:55,398 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 10 states have (on average 3.3) internal successors, (33), 10 states have internal predecessors, (33), 3 states have call successors, (5), 3 states have call predecessors, (5), 2 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2022-01-10 03:09:55,398 INFO L276 IsEmpty]: Start isEmpty. Operand 97 states and 130 transitions. [2022-01-10 03:09:55,399 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 28 [2022-01-10 03:09:55,399 INFO L506 BasicCegarLoop]: Found error trace [2022-01-10 03:09:55,399 INFO L514 BasicCegarLoop]: trace histogram [2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-01-10 03:09:55,413 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (7)] Forceful destruction successful, exit code 0 [2022-01-10 03:09:55,603 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 [2022-01-10 03:09:55,604 INFO L402 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-01-10 03:09:55,604 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-01-10 03:09:55,604 INFO L85 PathProgramCache]: Analyzing trace with hash -1127291835, now seen corresponding path program 1 times [2022-01-10 03:09:55,604 INFO L121 FreeRefinementEngine]: Executing refinement strategy WOLF [2022-01-10 03:09:55,604 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleMathsat [1861070165] [2022-01-10 03:09:55,605 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-01-10 03:09:55,605 INFO L168 SolverBuilder]: Constructing external solver with command: mathsat -unsat_core_generation=3 [2022-01-10 03:09:55,605 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat [2022-01-10 03:09:55,606 INFO L229 MonitoredProcess]: Starting monitored process 8 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (exit command is (exit), workingDir is null) [2022-01-10 03:09:55,607 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (8)] Waiting until timeout for monitored process [2022-01-10 03:09:55,780 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-10 03:09:55,810 INFO L263 TraceCheckSpWp]: Trace formula consists of 63 conjuncts, 7 conjunts are in the unsatisfiable core [2022-01-10 03:09:55,811 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-01-10 03:09:56,140 INFO L134 CoverageAnalysis]: Checked inductivity of 7 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2022-01-10 03:09:56,140 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-01-10 03:09:56,853 INFO L134 CoverageAnalysis]: Checked inductivity of 7 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2022-01-10 03:09:56,854 INFO L139 FreeRefinementEngine]: Strategy WOLF found an infeasible trace [2022-01-10 03:09:56,854 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleMathsat [1861070165] [2022-01-10 03:09:56,854 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleMathsat [1861070165] provided 0 perfect and 2 imperfect interpolant sequences [2022-01-10 03:09:56,854 INFO L186 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-01-10 03:09:56,854 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 13 [2022-01-10 03:09:56,854 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [129223660] [2022-01-10 03:09:56,854 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-01-10 03:09:56,854 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 13 states [2022-01-10 03:09:56,854 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy WOLF [2022-01-10 03:09:56,855 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2022-01-10 03:09:56,855 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=29, Invalid=127, Unknown=0, NotChecked=0, Total=156 [2022-01-10 03:09:56,855 INFO L87 Difference]: Start difference. First operand 97 states and 130 transitions. Second operand has 13 states, 13 states have (on average 2.6923076923076925) internal successors, (35), 11 states have internal predecessors, (35), 4 states have call successors, (4), 2 states have call predecessors, (4), 2 states have return successors, (4), 2 states have call predecessors, (4), 3 states have call successors, (4) [2022-01-10 03:09:57,073 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-01-10 03:09:57,074 INFO L93 Difference]: Finished difference Result 103 states and 135 transitions. [2022-01-10 03:09:57,076 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2022-01-10 03:09:57,076 INFO L78 Accepts]: Start accepts. Automaton has has 13 states, 13 states have (on average 2.6923076923076925) internal successors, (35), 11 states have internal predecessors, (35), 4 states have call successors, (4), 2 states have call predecessors, (4), 2 states have return successors, (4), 2 states have call predecessors, (4), 3 states have call successors, (4) Word has length 27 [2022-01-10 03:09:57,076 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-01-10 03:09:57,077 INFO L225 Difference]: With dead ends: 103 [2022-01-10 03:09:57,077 INFO L226 Difference]: Without dead ends: 96 [2022-01-10 03:09:57,077 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 54 GetRequests, 41 SyntacticMatches, 0 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 11 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=40, Invalid=170, Unknown=0, NotChecked=0, Total=210 [2022-01-10 03:09:57,078 INFO L933 BasicCegarLoop]: 35 mSDtfsCounter, 5 mSDsluCounter, 251 mSDsCounter, 0 mSdLazyCounter, 42 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 5 SdHoareTripleChecker+Valid, 286 SdHoareTripleChecker+Invalid, 47 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 42 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 5 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-01-10 03:09:57,078 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [5 Valid, 286 Invalid, 47 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 42 Invalid, 0 Unknown, 5 Unchecked, 0.1s Time] [2022-01-10 03:09:57,078 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 96 states. [2022-01-10 03:09:57,091 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 96 to 96. [2022-01-10 03:09:57,091 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 96 states, 69 states have (on average 1.318840579710145) internal successors, (91), 70 states have internal predecessors, (91), 19 states have call successors, (19), 7 states have call predecessors, (19), 7 states have return successors, (18), 18 states have call predecessors, (18), 18 states have call successors, (18) [2022-01-10 03:09:57,092 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 96 states to 96 states and 128 transitions. [2022-01-10 03:09:57,092 INFO L78 Accepts]: Start accepts. Automaton has 96 states and 128 transitions. Word has length 27 [2022-01-10 03:09:57,092 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-01-10 03:09:57,092 INFO L470 AbstractCegarLoop]: Abstraction has 96 states and 128 transitions. [2022-01-10 03:09:57,093 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 13 states, 13 states have (on average 2.6923076923076925) internal successors, (35), 11 states have internal predecessors, (35), 4 states have call successors, (4), 2 states have call predecessors, (4), 2 states have return successors, (4), 2 states have call predecessors, (4), 3 states have call successors, (4) [2022-01-10 03:09:57,093 INFO L276 IsEmpty]: Start isEmpty. Operand 96 states and 128 transitions. [2022-01-10 03:09:57,093 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 31 [2022-01-10 03:09:57,093 INFO L506 BasicCegarLoop]: Found error trace [2022-01-10 03:09:57,093 INFO L514 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, 1, 1] [2022-01-10 03:09:57,112 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (8)] Forceful destruction successful, exit code 0 [2022-01-10 03:09:57,314 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 [2022-01-10 03:09:57,315 INFO L402 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-01-10 03:09:57,315 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-01-10 03:09:57,315 INFO L85 PathProgramCache]: Analyzing trace with hash -200071253, now seen corresponding path program 1 times [2022-01-10 03:09:57,315 INFO L121 FreeRefinementEngine]: Executing refinement strategy WOLF [2022-01-10 03:09:57,315 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleMathsat [121399648] [2022-01-10 03:09:57,316 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-01-10 03:09:57,316 INFO L168 SolverBuilder]: Constructing external solver with command: mathsat -unsat_core_generation=3 [2022-01-10 03:09:57,316 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat [2022-01-10 03:09:57,317 INFO L229 MonitoredProcess]: Starting monitored process 9 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (exit command is (exit), workingDir is null) [2022-01-10 03:09:57,317 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (9)] Waiting until timeout for monitored process [2022-01-10 03:09:57,437 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-10 03:09:57,454 INFO L263 TraceCheckSpWp]: Trace formula consists of 64 conjuncts, 12 conjunts are in the unsatisfiable core [2022-01-10 03:09:57,455 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-01-10 03:09:57,988 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2022-01-10 03:09:57,988 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-01-10 03:09:57,988 INFO L139 FreeRefinementEngine]: Strategy WOLF found an infeasible trace [2022-01-10 03:09:57,988 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleMathsat [121399648] [2022-01-10 03:09:57,988 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleMathsat [121399648] provided 1 perfect and 0 imperfect interpolant sequences [2022-01-10 03:09:57,988 INFO L186 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-01-10 03:09:57,989 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [9] imperfect sequences [] total 9 [2022-01-10 03:09:57,989 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2032566071] [2022-01-10 03:09:57,989 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-01-10 03:09:57,989 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2022-01-10 03:09:57,989 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy WOLF [2022-01-10 03:09:57,989 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2022-01-10 03:09:57,989 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=18, Invalid=54, Unknown=0, NotChecked=0, Total=72 [2022-01-10 03:09:57,990 INFO L87 Difference]: Start difference. First operand 96 states and 128 transitions. Second operand has 9 states, 8 states have (on average 2.5) internal successors, (20), 6 states have internal predecessors, (20), 3 states have call successors, (4), 2 states have call predecessors, (4), 2 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2022-01-10 03:10:00,413 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-01-10 03:10:00,413 INFO L93 Difference]: Finished difference Result 112 states and 143 transitions. [2022-01-10 03:10:00,421 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2022-01-10 03:10:00,422 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 8 states have (on average 2.5) internal successors, (20), 6 states have internal predecessors, (20), 3 states have call successors, (4), 2 states have call predecessors, (4), 2 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) Word has length 30 [2022-01-10 03:10:00,422 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-01-10 03:10:00,423 INFO L225 Difference]: With dead ends: 112 [2022-01-10 03:10:00,423 INFO L226 Difference]: Without dead ends: 110 [2022-01-10 03:10:00,423 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 31 GetRequests, 22 SyntacticMatches, 0 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 9 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=26, Invalid=84, Unknown=0, NotChecked=0, Total=110 [2022-01-10 03:10:00,424 INFO L933 BasicCegarLoop]: 37 mSDtfsCounter, 39 mSDsluCounter, 189 mSDsCounter, 0 mSdLazyCounter, 87 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 2.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 47 SdHoareTripleChecker+Valid, 226 SdHoareTripleChecker+Invalid, 89 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 87 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 2.4s IncrementalHoareTripleChecker+Time [2022-01-10 03:10:00,424 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [47 Valid, 226 Invalid, 89 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 87 Invalid, 0 Unknown, 0 Unchecked, 2.4s Time] [2022-01-10 03:10:00,424 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 110 states. [2022-01-10 03:10:00,436 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 110 to 108. [2022-01-10 03:10:00,436 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 108 states, 78 states have (on average 1.2820512820512822) internal successors, (100), 79 states have internal predecessors, (100), 19 states have call successors, (19), 10 states have call predecessors, (19), 10 states have return successors, (18), 18 states have call predecessors, (18), 18 states have call successors, (18) [2022-01-10 03:10:00,437 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 108 states to 108 states and 137 transitions. [2022-01-10 03:10:00,437 INFO L78 Accepts]: Start accepts. Automaton has 108 states and 137 transitions. Word has length 30 [2022-01-10 03:10:00,438 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-01-10 03:10:00,438 INFO L470 AbstractCegarLoop]: Abstraction has 108 states and 137 transitions. [2022-01-10 03:10:00,438 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 8 states have (on average 2.5) internal successors, (20), 6 states have internal predecessors, (20), 3 states have call successors, (4), 2 states have call predecessors, (4), 2 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2022-01-10 03:10:00,438 INFO L276 IsEmpty]: Start isEmpty. Operand 108 states and 137 transitions. [2022-01-10 03:10:00,439 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 33 [2022-01-10 03:10:00,439 INFO L506 BasicCegarLoop]: Found error trace [2022-01-10 03:10:00,439 INFO L514 BasicCegarLoop]: trace histogram [2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-01-10 03:10:00,449 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (9)] Ended with exit code 0 [2022-01-10 03:10:00,648 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 9 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 [2022-01-10 03:10:00,651 INFO L402 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-01-10 03:10:00,651 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-01-10 03:10:00,651 INFO L85 PathProgramCache]: Analyzing trace with hash 164485690, now seen corresponding path program 1 times [2022-01-10 03:10:00,651 INFO L121 FreeRefinementEngine]: Executing refinement strategy WOLF [2022-01-10 03:10:00,652 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleMathsat [1866713287] [2022-01-10 03:10:00,652 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-01-10 03:10:00,652 INFO L168 SolverBuilder]: Constructing external solver with command: mathsat -unsat_core_generation=3 [2022-01-10 03:10:00,652 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat [2022-01-10 03:10:00,653 INFO L229 MonitoredProcess]: Starting monitored process 10 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (exit command is (exit), workingDir is null) [2022-01-10 03:10:00,654 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (10)] Waiting until timeout for monitored process [2022-01-10 03:10:00,784 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-10 03:10:00,802 INFO L263 TraceCheckSpWp]: Trace formula consists of 74 conjuncts, 15 conjunts are in the unsatisfiable core [2022-01-10 03:10:00,804 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-01-10 03:10:01,550 INFO L134 CoverageAnalysis]: Checked inductivity of 10 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2022-01-10 03:10:01,550 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-01-10 03:10:15,491 INFO L134 CoverageAnalysis]: Checked inductivity of 10 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2022-01-10 03:10:15,491 INFO L139 FreeRefinementEngine]: Strategy WOLF found an infeasible trace [2022-01-10 03:10:15,491 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleMathsat [1866713287] [2022-01-10 03:10:15,492 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleMathsat [1866713287] provided 0 perfect and 2 imperfect interpolant sequences [2022-01-10 03:10:15,492 INFO L186 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-01-10 03:10:15,492 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 6] total 14 [2022-01-10 03:10:15,492 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1104010084] [2022-01-10 03:10:15,492 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-01-10 03:10:15,492 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2022-01-10 03:10:15,492 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy WOLF [2022-01-10 03:10:15,493 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2022-01-10 03:10:15,493 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=34, Invalid=148, Unknown=0, NotChecked=0, Total=182 [2022-01-10 03:10:15,493 INFO L87 Difference]: Start difference. First operand 108 states and 137 transitions. Second operand has 14 states, 13 states have (on average 3.4615384615384617) internal successors, (45), 10 states have internal predecessors, (45), 4 states have call successors, (5), 3 states have call predecessors, (5), 2 states have return successors, (4), 3 states have call predecessors, (4), 2 states have call successors, (4) [2022-01-10 03:10:23,496 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.09s for a HTC check with result UNKNOWN. Formula has sorts [Bool, BitVec], hasArrays=false, hasNonlinArith=false, quantifiers [] [2022-01-10 03:10:33,861 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-01-10 03:10:33,862 INFO L93 Difference]: Finished difference Result 134 states and 172 transitions. [2022-01-10 03:10:33,888 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2022-01-10 03:10:33,889 INFO L78 Accepts]: Start accepts. Automaton has has 14 states, 13 states have (on average 3.4615384615384617) internal successors, (45), 10 states have internal predecessors, (45), 4 states have call successors, (5), 3 states have call predecessors, (5), 2 states have return successors, (4), 3 states have call predecessors, (4), 2 states have call successors, (4) Word has length 32 [2022-01-10 03:10:33,889 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-01-10 03:10:33,890 INFO L225 Difference]: With dead ends: 134 [2022-01-10 03:10:33,890 INFO L226 Difference]: Without dead ends: 132 [2022-01-10 03:10:33,890 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 66 GetRequests, 50 SyntacticMatches, 0 SemanticMatches, 16 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 38 ImplicationChecksByTransitivity, 12.7s TimeCoverageRelationStatistics Valid=56, Invalid=250, Unknown=0, NotChecked=0, Total=306 [2022-01-10 03:10:33,891 INFO L933 BasicCegarLoop]: 55 mSDtfsCounter, 90 mSDsluCounter, 370 mSDsCounter, 0 mSdLazyCounter, 185 mSolverCounterSat, 25 mSolverCounterUnsat, 1 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 12.9s Time, 0 mProtectedPredicate, 0 mProtectedAction, 99 SdHoareTripleChecker+Valid, 425 SdHoareTripleChecker+Invalid, 211 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 25 IncrementalHoareTripleChecker+Valid, 185 IncrementalHoareTripleChecker+Invalid, 1 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 14.1s IncrementalHoareTripleChecker+Time [2022-01-10 03:10:33,891 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [99 Valid, 425 Invalid, 211 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [25 Valid, 185 Invalid, 1 Unknown, 0 Unchecked, 14.1s Time] [2022-01-10 03:10:33,892 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 132 states. [2022-01-10 03:10:33,905 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 132 to 130. [2022-01-10 03:10:33,905 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 130 states, 95 states have (on average 1.2947368421052632) internal successors, (123), 96 states have internal predecessors, (123), 23 states have call successors, (23), 11 states have call predecessors, (23), 11 states have return successors, (22), 22 states have call predecessors, (22), 22 states have call successors, (22) [2022-01-10 03:10:33,907 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 130 states to 130 states and 168 transitions. [2022-01-10 03:10:33,907 INFO L78 Accepts]: Start accepts. Automaton has 130 states and 168 transitions. Word has length 32 [2022-01-10 03:10:33,907 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-01-10 03:10:33,907 INFO L470 AbstractCegarLoop]: Abstraction has 130 states and 168 transitions. [2022-01-10 03:10:33,907 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 14 states, 13 states have (on average 3.4615384615384617) internal successors, (45), 10 states have internal predecessors, (45), 4 states have call successors, (5), 3 states have call predecessors, (5), 2 states have return successors, (4), 3 states have call predecessors, (4), 2 states have call successors, (4) [2022-01-10 03:10:33,907 INFO L276 IsEmpty]: Start isEmpty. Operand 130 states and 168 transitions. [2022-01-10 03:10:33,908 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 33 [2022-01-10 03:10:33,908 INFO L506 BasicCegarLoop]: Found error trace [2022-01-10 03:10:33,908 INFO L514 BasicCegarLoop]: trace histogram [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-01-10 03:10:33,921 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (10)] Forceful destruction successful, exit code 0 [2022-01-10 03:10:34,117 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 10 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 [2022-01-10 03:10:34,118 INFO L402 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-01-10 03:10:34,118 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-01-10 03:10:34,118 INFO L85 PathProgramCache]: Analyzing trace with hash 1985711111, now seen corresponding path program 1 times [2022-01-10 03:10:34,118 INFO L121 FreeRefinementEngine]: Executing refinement strategy WOLF [2022-01-10 03:10:34,118 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleMathsat [434898320] [2022-01-10 03:10:34,118 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-01-10 03:10:34,119 INFO L168 SolverBuilder]: Constructing external solver with command: mathsat -unsat_core_generation=3 [2022-01-10 03:10:34,119 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat [2022-01-10 03:10:34,120 INFO L229 MonitoredProcess]: Starting monitored process 11 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (exit command is (exit), workingDir is null) [2022-01-10 03:10:34,122 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (11)] Waiting until timeout for monitored process [2022-01-10 03:10:34,268 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-10 03:10:34,296 INFO L263 TraceCheckSpWp]: Trace formula consists of 73 conjuncts, 7 conjunts are in the unsatisfiable core [2022-01-10 03:10:34,297 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-01-10 03:10:34,572 INFO L134 CoverageAnalysis]: Checked inductivity of 9 backedges. 5 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2022-01-10 03:10:34,572 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-01-10 03:10:34,573 INFO L139 FreeRefinementEngine]: Strategy WOLF found an infeasible trace [2022-01-10 03:10:34,573 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleMathsat [434898320] [2022-01-10 03:10:34,573 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleMathsat [434898320] provided 1 perfect and 0 imperfect interpolant sequences [2022-01-10 03:10:34,573 INFO L186 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-01-10 03:10:34,573 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-01-10 03:10:34,573 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1557346173] [2022-01-10 03:10:34,573 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-01-10 03:10:34,573 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2022-01-10 03:10:34,573 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy WOLF [2022-01-10 03:10:34,574 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2022-01-10 03:10:34,574 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2022-01-10 03:10:34,574 INFO L87 Difference]: Start difference. First operand 130 states and 168 transitions. Second operand has 6 states, 6 states have (on average 4.0) internal successors, (24), 5 states have internal predecessors, (24), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2022-01-10 03:10:34,691 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-01-10 03:10:34,692 INFO L93 Difference]: Finished difference Result 197 states and 261 transitions. [2022-01-10 03:10:34,692 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2022-01-10 03:10:34,692 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 4.0) internal successors, (24), 5 states have internal predecessors, (24), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) Word has length 32 [2022-01-10 03:10:34,692 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-01-10 03:10:34,693 INFO L225 Difference]: With dead ends: 197 [2022-01-10 03:10:34,693 INFO L226 Difference]: Without dead ends: 130 [2022-01-10 03:10:34,694 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 31 GetRequests, 27 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2022-01-10 03:10:34,694 INFO L933 BasicCegarLoop]: 37 mSDtfsCounter, 2 mSDsluCounter, 126 mSDsCounter, 0 mSdLazyCounter, 36 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 163 SdHoareTripleChecker+Invalid, 36 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 36 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-01-10 03:10:34,694 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 163 Invalid, 36 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 36 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-01-10 03:10:34,695 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 130 states. [2022-01-10 03:10:34,702 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 130 to 130. [2022-01-10 03:10:34,702 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 130 states, 95 states have (on average 1.2842105263157895) internal successors, (122), 96 states have internal predecessors, (122), 23 states have call successors, (23), 11 states have call predecessors, (23), 11 states have return successors, (22), 22 states have call predecessors, (22), 22 states have call successors, (22) [2022-01-10 03:10:34,703 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 130 states to 130 states and 167 transitions. [2022-01-10 03:10:34,703 INFO L78 Accepts]: Start accepts. Automaton has 130 states and 167 transitions. Word has length 32 [2022-01-10 03:10:34,703 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-01-10 03:10:34,703 INFO L470 AbstractCegarLoop]: Abstraction has 130 states and 167 transitions. [2022-01-10 03:10:34,703 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 4.0) internal successors, (24), 5 states have internal predecessors, (24), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2022-01-10 03:10:34,704 INFO L276 IsEmpty]: Start isEmpty. Operand 130 states and 167 transitions. [2022-01-10 03:10:34,704 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 34 [2022-01-10 03:10:34,704 INFO L506 BasicCegarLoop]: Found error trace [2022-01-10 03:10:34,704 INFO L514 BasicCegarLoop]: trace histogram [3, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-01-10 03:10:34,716 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (11)] Forceful destruction successful, exit code 0 [2022-01-10 03:10:34,916 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 11 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 [2022-01-10 03:10:34,916 INFO L402 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-01-10 03:10:34,917 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-01-10 03:10:34,917 INFO L85 PathProgramCache]: Analyzing trace with hash -1848416935, now seen corresponding path program 1 times [2022-01-10 03:10:34,917 INFO L121 FreeRefinementEngine]: Executing refinement strategy WOLF [2022-01-10 03:10:34,917 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleMathsat [1421911410] [2022-01-10 03:10:34,917 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-01-10 03:10:34,917 INFO L168 SolverBuilder]: Constructing external solver with command: mathsat -unsat_core_generation=3 [2022-01-10 03:10:34,917 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat [2022-01-10 03:10:34,918 INFO L229 MonitoredProcess]: Starting monitored process 12 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (exit command is (exit), workingDir is null) [2022-01-10 03:10:34,919 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (12)] Waiting until timeout for monitored process [2022-01-10 03:10:35,149 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-10 03:10:35,184 INFO L263 TraceCheckSpWp]: Trace formula consists of 79 conjuncts, 9 conjunts are in the unsatisfiable core [2022-01-10 03:10:35,185 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-01-10 03:10:35,486 INFO L134 CoverageAnalysis]: Checked inductivity of 16 backedges. 7 proven. 5 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2022-01-10 03:10:35,486 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-01-10 03:10:35,859 INFO L134 CoverageAnalysis]: Checked inductivity of 16 backedges. 7 proven. 5 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2022-01-10 03:10:35,859 INFO L139 FreeRefinementEngine]: Strategy WOLF found an infeasible trace [2022-01-10 03:10:35,859 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleMathsat [1421911410] [2022-01-10 03:10:35,859 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleMathsat [1421911410] provided 0 perfect and 2 imperfect interpolant sequences [2022-01-10 03:10:35,859 INFO L186 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-01-10 03:10:35,859 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 7] total 12 [2022-01-10 03:10:35,860 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1478392933] [2022-01-10 03:10:35,860 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-01-10 03:10:35,860 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2022-01-10 03:10:35,860 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy WOLF [2022-01-10 03:10:35,860 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2022-01-10 03:10:35,861 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=38, Invalid=94, Unknown=0, NotChecked=0, Total=132 [2022-01-10 03:10:35,861 INFO L87 Difference]: Start difference. First operand 130 states and 167 transitions. Second operand has 12 states, 12 states have (on average 3.5833333333333335) internal successors, (43), 12 states have internal predecessors, (43), 3 states have call successors, (5), 3 states have call predecessors, (5), 2 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2022-01-10 03:10:46,516 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-01-10 03:10:46,516 INFO L93 Difference]: Finished difference Result 340 states and 445 transitions. [2022-01-10 03:10:46,527 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2022-01-10 03:10:46,528 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 12 states have (on average 3.5833333333333335) internal successors, (43), 12 states have internal predecessors, (43), 3 states have call successors, (5), 3 states have call predecessors, (5), 2 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) Word has length 33 [2022-01-10 03:10:46,528 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-01-10 03:10:46,529 INFO L225 Difference]: With dead ends: 340 [2022-01-10 03:10:46,530 INFO L226 Difference]: Without dead ends: 293 [2022-01-10 03:10:46,530 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 72 GetRequests, 54 SyntacticMatches, 0 SemanticMatches, 18 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 34 ImplicationChecksByTransitivity, 0.8s TimeCoverageRelationStatistics Valid=117, Invalid=263, Unknown=0, NotChecked=0, Total=380 [2022-01-10 03:10:46,531 INFO L933 BasicCegarLoop]: 63 mSDtfsCounter, 168 mSDsluCounter, 273 mSDsCounter, 0 mSdLazyCounter, 211 mSolverCounterSat, 129 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 9.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 168 SdHoareTripleChecker+Valid, 336 SdHoareTripleChecker+Invalid, 340 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 129 IncrementalHoareTripleChecker+Valid, 211 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 10.1s IncrementalHoareTripleChecker+Time [2022-01-10 03:10:46,531 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [168 Valid, 336 Invalid, 340 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [129 Valid, 211 Invalid, 0 Unknown, 0 Unchecked, 10.1s Time] [2022-01-10 03:10:46,531 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 293 states. [2022-01-10 03:10:46,559 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 293 to 268. [2022-01-10 03:10:46,560 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 268 states, 190 states have (on average 1.2789473684210526) internal successors, (243), 194 states have internal predecessors, (243), 54 states have call successors, (54), 23 states have call predecessors, (54), 23 states have return successors, (50), 50 states have call predecessors, (50), 50 states have call successors, (50) [2022-01-10 03:10:46,561 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 268 states to 268 states and 347 transitions. [2022-01-10 03:10:46,561 INFO L78 Accepts]: Start accepts. Automaton has 268 states and 347 transitions. Word has length 33 [2022-01-10 03:10:46,562 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-01-10 03:10:46,562 INFO L470 AbstractCegarLoop]: Abstraction has 268 states and 347 transitions. [2022-01-10 03:10:46,562 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 12 states have (on average 3.5833333333333335) internal successors, (43), 12 states have internal predecessors, (43), 3 states have call successors, (5), 3 states have call predecessors, (5), 2 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2022-01-10 03:10:46,562 INFO L276 IsEmpty]: Start isEmpty. Operand 268 states and 347 transitions. [2022-01-10 03:10:46,562 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 36 [2022-01-10 03:10:46,563 INFO L506 BasicCegarLoop]: Found error trace [2022-01-10 03:10:46,563 INFO L514 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, 1, 1] [2022-01-10 03:10:46,585 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (12)] Forceful destruction successful, exit code 0 [2022-01-10 03:10:46,785 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 12 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 [2022-01-10 03:10:46,787 INFO L402 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-01-10 03:10:46,787 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-01-10 03:10:46,787 INFO L85 PathProgramCache]: Analyzing trace with hash 1730540965, now seen corresponding path program 1 times [2022-01-10 03:10:46,787 INFO L121 FreeRefinementEngine]: Executing refinement strategy WOLF [2022-01-10 03:10:46,787 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleMathsat [1899793782] [2022-01-10 03:10:46,787 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-01-10 03:10:46,788 INFO L168 SolverBuilder]: Constructing external solver with command: mathsat -unsat_core_generation=3 [2022-01-10 03:10:46,788 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat [2022-01-10 03:10:46,789 INFO L229 MonitoredProcess]: Starting monitored process 13 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (exit command is (exit), workingDir is null) [2022-01-10 03:10:46,789 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (13)] Waiting until timeout for monitored process [2022-01-10 03:10:46,980 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-10 03:10:47,002 INFO L263 TraceCheckSpWp]: Trace formula consists of 71 conjuncts, 13 conjunts are in the unsatisfiable core [2022-01-10 03:10:47,003 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-01-10 03:10:47,982 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 8 trivial. 0 not checked. [2022-01-10 03:10:47,982 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-01-10 03:10:47,983 INFO L139 FreeRefinementEngine]: Strategy WOLF found an infeasible trace [2022-01-10 03:10:47,983 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleMathsat [1899793782] [2022-01-10 03:10:47,983 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleMathsat [1899793782] provided 1 perfect and 0 imperfect interpolant sequences [2022-01-10 03:10:47,983 INFO L186 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-01-10 03:10:47,983 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [10] imperfect sequences [] total 10 [2022-01-10 03:10:47,983 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [367323213] [2022-01-10 03:10:47,983 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-01-10 03:10:47,983 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2022-01-10 03:10:47,983 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy WOLF [2022-01-10 03:10:47,984 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2022-01-10 03:10:47,984 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=19, Invalid=71, Unknown=0, NotChecked=0, Total=90 [2022-01-10 03:10:47,984 INFO L87 Difference]: Start difference. First operand 268 states and 347 transitions. Second operand has 10 states, 9 states have (on average 2.2222222222222223) internal successors, (20), 7 states have internal predecessors, (20), 3 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (4), 3 states have call predecessors, (4), 3 states have call successors, (4) [2022-01-10 03:10:49,596 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.16s for a HTC check with result INVALID. Formula has sorts [Bool, BitVec], hasArrays=false, hasNonlinArith=false, quantifiers [] [2022-01-10 03:10:50,061 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-01-10 03:10:50,062 INFO L93 Difference]: Finished difference Result 274 states and 352 transitions. [2022-01-10 03:10:50,074 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2022-01-10 03:10:50,074 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 9 states have (on average 2.2222222222222223) internal successors, (20), 7 states have internal predecessors, (20), 3 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (4), 3 states have call predecessors, (4), 3 states have call successors, (4) Word has length 35 [2022-01-10 03:10:50,074 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-01-10 03:10:50,076 INFO L225 Difference]: With dead ends: 274 [2022-01-10 03:10:50,076 INFO L226 Difference]: Without dead ends: 272 [2022-01-10 03:10:50,076 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 37 GetRequests, 26 SyntacticMatches, 0 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 13 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=32, Invalid=124, Unknown=0, NotChecked=0, Total=156 [2022-01-10 03:10:50,076 INFO L933 BasicCegarLoop]: 37 mSDtfsCounter, 17 mSDsluCounter, 223 mSDsCounter, 0 mSdLazyCounter, 43 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.8s Time, 0 mProtectedPredicate, 0 mProtectedAction, 18 SdHoareTripleChecker+Valid, 260 SdHoareTripleChecker+Invalid, 65 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 43 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 22 IncrementalHoareTripleChecker+Unchecked, 1.9s IncrementalHoareTripleChecker+Time [2022-01-10 03:10:50,077 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [18 Valid, 260 Invalid, 65 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 43 Invalid, 0 Unknown, 22 Unchecked, 1.9s Time] [2022-01-10 03:10:50,077 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 272 states. [2022-01-10 03:10:50,092 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 272 to 272. [2022-01-10 03:10:50,093 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 272 states, 193 states have (on average 1.2746113989637307) internal successors, (246), 197 states have internal predecessors, (246), 54 states have call successors, (54), 24 states have call predecessors, (54), 24 states have return successors, (50), 50 states have call predecessors, (50), 50 states have call successors, (50) [2022-01-10 03:10:50,094 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 272 states to 272 states and 350 transitions. [2022-01-10 03:10:50,094 INFO L78 Accepts]: Start accepts. Automaton has 272 states and 350 transitions. Word has length 35 [2022-01-10 03:10:50,094 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-01-10 03:10:50,094 INFO L470 AbstractCegarLoop]: Abstraction has 272 states and 350 transitions. [2022-01-10 03:10:50,095 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 9 states have (on average 2.2222222222222223) internal successors, (20), 7 states have internal predecessors, (20), 3 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (4), 3 states have call predecessors, (4), 3 states have call successors, (4) [2022-01-10 03:10:50,095 INFO L276 IsEmpty]: Start isEmpty. Operand 272 states and 350 transitions. [2022-01-10 03:10:50,099 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 35 [2022-01-10 03:10:50,099 INFO L506 BasicCegarLoop]: Found error trace [2022-01-10 03:10:50,099 INFO L514 BasicCegarLoop]: trace histogram [3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-01-10 03:10:50,119 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (13)] Forceful destruction successful, exit code 0 [2022-01-10 03:10:50,310 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 13 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 [2022-01-10 03:10:50,310 INFO L402 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-01-10 03:10:50,310 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-01-10 03:10:50,310 INFO L85 PathProgramCache]: Analyzing trace with hash -856313062, now seen corresponding path program 2 times [2022-01-10 03:10:50,310 INFO L121 FreeRefinementEngine]: Executing refinement strategy WOLF [2022-01-10 03:10:50,311 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleMathsat [1498920500] [2022-01-10 03:10:50,311 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-01-10 03:10:50,311 INFO L168 SolverBuilder]: Constructing external solver with command: mathsat -unsat_core_generation=3 [2022-01-10 03:10:50,311 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat [2022-01-10 03:10:50,312 INFO L229 MonitoredProcess]: Starting monitored process 14 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (exit command is (exit), workingDir is null) [2022-01-10 03:10:50,312 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (14)] Waiting until timeout for monitored process [2022-01-10 03:10:50,543 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-01-10 03:10:50,543 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-01-10 03:10:50,579 INFO L263 TraceCheckSpWp]: Trace formula consists of 80 conjuncts, 9 conjunts are in the unsatisfiable core [2022-01-10 03:10:50,580 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-01-10 03:10:51,135 INFO L134 CoverageAnalysis]: Checked inductivity of 17 backedges. 3 proven. 10 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2022-01-10 03:10:51,135 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-01-10 03:10:52,011 INFO L134 CoverageAnalysis]: Checked inductivity of 17 backedges. 6 proven. 7 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2022-01-10 03:10:52,011 INFO L139 FreeRefinementEngine]: Strategy WOLF found an infeasible trace [2022-01-10 03:10:52,012 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleMathsat [1498920500] [2022-01-10 03:10:52,012 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleMathsat [1498920500] provided 0 perfect and 2 imperfect interpolant sequences [2022-01-10 03:10:52,012 INFO L186 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-01-10 03:10:52,012 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 5] total 11 [2022-01-10 03:10:52,012 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [177351950] [2022-01-10 03:10:52,012 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-01-10 03:10:52,012 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 11 states [2022-01-10 03:10:52,012 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy WOLF [2022-01-10 03:10:52,013 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2022-01-10 03:10:52,013 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=22, Invalid=88, Unknown=0, NotChecked=0, Total=110 [2022-01-10 03:10:52,013 INFO L87 Difference]: Start difference. First operand 272 states and 350 transitions. Second operand has 11 states, 11 states have (on average 4.090909090909091) internal successors, (45), 10 states have internal predecessors, (45), 2 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (3), 2 states have call predecessors, (3), 1 states have call successors, (3) [2022-01-10 03:10:52,941 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-01-10 03:10:52,941 INFO L93 Difference]: Finished difference Result 345 states and 445 transitions. [2022-01-10 03:10:52,941 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2022-01-10 03:10:52,941 INFO L78 Accepts]: Start accepts. Automaton has has 11 states, 11 states have (on average 4.090909090909091) internal successors, (45), 10 states have internal predecessors, (45), 2 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (3), 2 states have call predecessors, (3), 1 states have call successors, (3) Word has length 34 [2022-01-10 03:10:52,942 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-01-10 03:10:52,943 INFO L225 Difference]: With dead ends: 345 [2022-01-10 03:10:52,943 INFO L226 Difference]: Without dead ends: 328 [2022-01-10 03:10:52,943 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 77 GetRequests, 59 SyntacticMatches, 1 SemanticMatches, 17 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 31 ImplicationChecksByTransitivity, 1.6s TimeCoverageRelationStatistics Valid=63, Invalid=279, Unknown=0, NotChecked=0, Total=342 [2022-01-10 03:10:52,944 INFO L933 BasicCegarLoop]: 52 mSDtfsCounter, 16 mSDsluCounter, 351 mSDsCounter, 0 mSdLazyCounter, 37 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 16 SdHoareTripleChecker+Valid, 403 SdHoareTripleChecker+Invalid, 61 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 37 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 23 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-01-10 03:10:52,944 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [16 Valid, 403 Invalid, 61 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 37 Invalid, 0 Unknown, 23 Unchecked, 0.1s Time] [2022-01-10 03:10:52,944 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 328 states. [2022-01-10 03:10:52,958 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 328 to 306. [2022-01-10 03:10:52,959 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 306 states, 227 states have (on average 1.2863436123348018) internal successors, (292), 231 states have internal predecessors, (292), 54 states have call successors, (54), 24 states have call predecessors, (54), 24 states have return successors, (50), 50 states have call predecessors, (50), 50 states have call successors, (50) [2022-01-10 03:10:52,960 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 306 states to 306 states and 396 transitions. [2022-01-10 03:10:52,960 INFO L78 Accepts]: Start accepts. Automaton has 306 states and 396 transitions. Word has length 34 [2022-01-10 03:10:52,961 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-01-10 03:10:52,961 INFO L470 AbstractCegarLoop]: Abstraction has 306 states and 396 transitions. [2022-01-10 03:10:52,961 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 11 states, 11 states have (on average 4.090909090909091) internal successors, (45), 10 states have internal predecessors, (45), 2 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (3), 2 states have call predecessors, (3), 1 states have call successors, (3) [2022-01-10 03:10:52,961 INFO L276 IsEmpty]: Start isEmpty. Operand 306 states and 396 transitions. [2022-01-10 03:10:52,962 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 38 [2022-01-10 03:10:52,962 INFO L506 BasicCegarLoop]: Found error trace [2022-01-10 03:10:52,962 INFO L514 BasicCegarLoop]: trace histogram [2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-01-10 03:10:52,979 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (14)] Forceful destruction successful, exit code 0 [2022-01-10 03:10:53,178 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 14 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 [2022-01-10 03:10:53,178 INFO L402 AbstractCegarLoop]: === Iteration 14 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-01-10 03:10:53,179 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-01-10 03:10:53,179 INFO L85 PathProgramCache]: Analyzing trace with hash -2009961290, now seen corresponding path program 1 times [2022-01-10 03:10:53,179 INFO L121 FreeRefinementEngine]: Executing refinement strategy WOLF [2022-01-10 03:10:53,179 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleMathsat [495827907] [2022-01-10 03:10:53,179 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-01-10 03:10:53,179 INFO L168 SolverBuilder]: Constructing external solver with command: mathsat -unsat_core_generation=3 [2022-01-10 03:10:53,179 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat [2022-01-10 03:10:53,180 INFO L229 MonitoredProcess]: Starting monitored process 15 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (exit command is (exit), workingDir is null) [2022-01-10 03:10:53,181 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (15)] Waiting until timeout for monitored process [2022-01-10 03:10:53,391 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-10 03:10:53,418 INFO L263 TraceCheckSpWp]: Trace formula consists of 81 conjuncts, 20 conjunts are in the unsatisfiable core [2022-01-10 03:10:53,419 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-01-10 03:10:54,761 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 2 proven. 6 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2022-01-10 03:10:54,762 INFO L328 TraceCheckSpWp]: Computing backward predicates...