/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/recursive-simple/fibo_2calls_4-2.c -------------------------------------------------------------------------------- This is Ultimate 0.2.2-dev-a10ec3b [2022-01-10 06:38:38,250 INFO L177 SettingsManager]: Resetting all preferences to default values... [2022-01-10 06:38:38,252 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2022-01-10 06:38:38,315 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2022-01-10 06:38:38,316 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2022-01-10 06:38:38,319 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2022-01-10 06:38:38,320 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2022-01-10 06:38:38,321 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2022-01-10 06:38:38,321 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2022-01-10 06:38:38,322 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2022-01-10 06:38:38,323 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2022-01-10 06:38:38,323 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2022-01-10 06:38:38,323 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2022-01-10 06:38:38,324 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2022-01-10 06:38:38,325 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2022-01-10 06:38:38,325 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2022-01-10 06:38:38,329 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2022-01-10 06:38:38,329 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2022-01-10 06:38:38,330 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2022-01-10 06:38:38,331 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2022-01-10 06:38:38,332 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2022-01-10 06:38:38,333 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2022-01-10 06:38:38,334 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2022-01-10 06:38:38,334 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2022-01-10 06:38:38,336 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2022-01-10 06:38:38,336 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2022-01-10 06:38:38,336 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2022-01-10 06:38:38,337 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2022-01-10 06:38:38,337 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2022-01-10 06:38:38,338 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2022-01-10 06:38:38,338 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2022-01-10 06:38:38,339 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2022-01-10 06:38:38,339 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2022-01-10 06:38:38,339 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2022-01-10 06:38:38,340 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2022-01-10 06:38:38,340 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2022-01-10 06:38:38,341 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2022-01-10 06:38:38,341 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2022-01-10 06:38:38,341 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2022-01-10 06:38:38,341 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2022-01-10 06:38:38,342 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2022-01-10 06:38:38,343 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 06:38:38,359 INFO L113 SettingsManager]: Loading preferences was successful [2022-01-10 06:38:38,359 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2022-01-10 06:38:38,359 INFO L136 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2022-01-10 06:38:38,359 INFO L138 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2022-01-10 06:38:38,360 INFO L136 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2022-01-10 06:38:38,360 INFO L138 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2022-01-10 06:38:38,360 INFO L136 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2022-01-10 06:38:38,360 INFO L138 SettingsManager]: * Create parallel compositions if possible=false [2022-01-10 06:38:38,360 INFO L138 SettingsManager]: * Use SBE=true [2022-01-10 06:38:38,361 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2022-01-10 06:38:38,361 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2022-01-10 06:38:38,361 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2022-01-10 06:38:38,361 INFO L138 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2022-01-10 06:38:38,361 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2022-01-10 06:38:38,361 INFO L138 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2022-01-10 06:38:38,361 INFO L138 SettingsManager]: * Adapt memory model on pointer casts if necessary=true [2022-01-10 06:38:38,361 INFO L138 SettingsManager]: * Use bitvectors instead of ints=true [2022-01-10 06:38:38,362 INFO L138 SettingsManager]: * Memory model=HoenickeLindenmann_4ByteResolution [2022-01-10 06:38:38,362 INFO L138 SettingsManager]: * Check if freed pointer was valid=false [2022-01-10 06:38:38,362 INFO L138 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2022-01-10 06:38:38,362 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2022-01-10 06:38:38,362 INFO L138 SettingsManager]: * Size of a code block=SequenceOfStatements [2022-01-10 06:38:38,362 INFO L138 SettingsManager]: * SMT solver=External_DefaultMode [2022-01-10 06:38:38,362 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-01-10 06:38:38,362 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2022-01-10 06:38:38,363 INFO L138 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2022-01-10 06:38:38,363 INFO L138 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2022-01-10 06:38:38,363 INFO L138 SettingsManager]: * Trace refinement strategy=WOLF [2022-01-10 06:38:38,363 INFO L138 SettingsManager]: * Command for external solver=cvc4 --incremental --print-success --lang smt [2022-01-10 06:38:38,363 INFO L138 SettingsManager]: * Large block encoding in concurrent analysis=OFF [2022-01-10 06:38:38,363 INFO L138 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2022-01-10 06:38:38,363 INFO L138 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2022-01-10 06:38:38,363 INFO L138 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2022-01-10 06:38:38,364 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 06:38:38,531 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2022-01-10 06:38:38,553 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2022-01-10 06:38:38,555 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2022-01-10 06:38:38,556 INFO L271 PluginConnector]: Initializing CDTParser... [2022-01-10 06:38:38,558 INFO L275 PluginConnector]: CDTParser initialized [2022-01-10 06:38:38,559 INFO L432 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/svcomp/recursive-simple/fibo_2calls_4-2.c [2022-01-10 06:38:38,602 INFO L220 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/8a9651597/2c4f631977354637a4aa7c29008a6e85/FLAGf36186574 [2022-01-10 06:38:38,915 INFO L306 CDTParser]: Found 1 translation units. [2022-01-10 06:38:38,915 INFO L160 CDTParser]: Scanning /storage/repos/ultimate/trunk/examples/svcomp/recursive-simple/fibo_2calls_4-2.c [2022-01-10 06:38:38,919 INFO L349 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/8a9651597/2c4f631977354637a4aa7c29008a6e85/FLAGf36186574 [2022-01-10 06:38:39,384 INFO L357 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/8a9651597/2c4f631977354637a4aa7c29008a6e85 [2022-01-10 06:38:39,386 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2022-01-10 06:38:39,387 INFO L131 ToolchainWalker]: Walking toolchain with 5 elements. [2022-01-10 06:38:39,388 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2022-01-10 06:38:39,388 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2022-01-10 06:38:39,390 INFO L275 PluginConnector]: CACSL2BoogieTranslator initialized [2022-01-10 06:38:39,391 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 10.01 06:38:39" (1/1) ... [2022-01-10 06:38:39,392 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@352b6cb2 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.01 06:38:39, skipping insertion in model container [2022-01-10 06:38:39,392 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 10.01 06:38:39" (1/1) ... [2022-01-10 06:38:39,396 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2022-01-10 06:38:39,403 INFO L178 MainTranslator]: Built tables and reachable declarations [2022-01-10 06:38:39,554 WARN L230 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/trunk/examples/svcomp/recursive-simple/fibo_2calls_4-2.c[946,959] [2022-01-10 06:38:39,558 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-01-10 06:38:39,565 INFO L203 MainTranslator]: Completed pre-run [2022-01-10 06:38:39,578 WARN L230 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/trunk/examples/svcomp/recursive-simple/fibo_2calls_4-2.c[946,959] [2022-01-10 06:38:39,580 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-01-10 06:38:39,591 INFO L208 MainTranslator]: Completed translation [2022-01-10 06:38:39,591 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.01 06:38:39 WrapperNode [2022-01-10 06:38:39,591 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2022-01-10 06:38:39,592 INFO L113 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2022-01-10 06:38:39,592 INFO L271 PluginConnector]: Initializing Boogie Procedure Inliner... [2022-01-10 06:38:39,592 INFO L275 PluginConnector]: Boogie Procedure Inliner initialized [2022-01-10 06:38:39,597 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.01 06:38:39" (1/1) ... [2022-01-10 06:38:39,602 INFO L185 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.01 06:38:39" (1/1) ... [2022-01-10 06:38:39,612 INFO L137 Inliner]: procedures = 14, calls = 12, calls flagged for inlining = 2, calls inlined = 2, statements flattened = 20 [2022-01-10 06:38:39,612 INFO L132 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2022-01-10 06:38:39,613 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2022-01-10 06:38:39,613 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2022-01-10 06:38:39,613 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2022-01-10 06:38:39,619 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.01 06:38:39" (1/1) ... [2022-01-10 06:38:39,619 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.01 06:38:39" (1/1) ... [2022-01-10 06:38:39,622 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.01 06:38:39" (1/1) ... [2022-01-10 06:38:39,622 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.01 06:38:39" (1/1) ... [2022-01-10 06:38:39,630 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.01 06:38:39" (1/1) ... [2022-01-10 06:38:39,631 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.01 06:38:39" (1/1) ... [2022-01-10 06:38:39,635 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.01 06:38:39" (1/1) ... [2022-01-10 06:38:39,640 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2022-01-10 06:38:39,641 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2022-01-10 06:38:39,642 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2022-01-10 06:38:39,642 INFO L275 PluginConnector]: RCFGBuilder initialized [2022-01-10 06:38:39,643 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.01 06:38:39" (1/1) ... [2022-01-10 06:38:39,648 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-01-10 06:38:39,659 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-01-10 06:38:39,669 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 06:38:39,683 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 06:38:39,700 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2022-01-10 06:38:39,700 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~intINTTYPE1 [2022-01-10 06:38:39,700 INFO L130 BoogieDeclarations]: Found specification of procedure fibo2 [2022-01-10 06:38:39,700 INFO L138 BoogieDeclarations]: Found implementation of procedure fibo2 [2022-01-10 06:38:39,700 INFO L130 BoogieDeclarations]: Found specification of procedure fibo1 [2022-01-10 06:38:39,700 INFO L138 BoogieDeclarations]: Found implementation of procedure fibo1 [2022-01-10 06:38:39,700 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2022-01-10 06:38:39,700 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2022-01-10 06:38:39,747 INFO L234 CfgBuilder]: Building ICFG [2022-01-10 06:38:39,749 INFO L260 CfgBuilder]: Building CFG for each procedure with an implementation [2022-01-10 06:38:39,886 INFO L275 CfgBuilder]: Performing block encoding [2022-01-10 06:38:39,890 INFO L294 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2022-01-10 06:38:39,890 INFO L299 CfgBuilder]: Removed 0 assume(true) statements. [2022-01-10 06:38:39,891 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 10.01 06:38:39 BoogieIcfgContainer [2022-01-10 06:38:39,891 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2022-01-10 06:38:39,892 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2022-01-10 06:38:39,892 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2022-01-10 06:38:39,895 INFO L275 PluginConnector]: TraceAbstraction initialized [2022-01-10 06:38:39,895 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 10.01 06:38:39" (1/3) ... [2022-01-10 06:38:39,896 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@3b73be05 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 10.01 06:38:39, skipping insertion in model container [2022-01-10 06:38:39,896 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.01 06:38:39" (2/3) ... [2022-01-10 06:38:39,896 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@3b73be05 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 10.01 06:38:39, skipping insertion in model container [2022-01-10 06:38:39,896 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 10.01 06:38:39" (3/3) ... [2022-01-10 06:38:39,897 INFO L111 eAbstractionObserver]: Analyzing ICFG fibo_2calls_4-2.c [2022-01-10 06:38:39,900 INFO L204 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2022-01-10 06:38:39,900 INFO L163 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2022-01-10 06:38:39,929 INFO L338 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2022-01-10 06:38:39,934 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 06:38:39,934 INFO L340 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2022-01-10 06:38:39,944 INFO L276 IsEmpty]: Start isEmpty. Operand has 27 states, 18 states have (on average 1.3333333333333333) internal successors, (24), 19 states have internal predecessors, (24), 5 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) [2022-01-10 06:38:39,947 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 11 [2022-01-10 06:38:39,948 INFO L506 BasicCegarLoop]: Found error trace [2022-01-10 06:38:39,948 INFO L514 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-01-10 06:38:39,948 INFO L402 AbstractCegarLoop]: === Iteration 1 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-01-10 06:38:39,952 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-01-10 06:38:39,952 INFO L85 PathProgramCache]: Analyzing trace with hash 1014607960, now seen corresponding path program 1 times [2022-01-10 06:38:39,960 INFO L121 FreeRefinementEngine]: Executing refinement strategy WOLF [2022-01-10 06:38:39,960 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleMathsat [1524703681] [2022-01-10 06:38:39,960 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-01-10 06:38:39,961 INFO L168 SolverBuilder]: Constructing external solver with command: mathsat -unsat_core_generation=3 [2022-01-10 06:38:39,961 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat [2022-01-10 06:38:39,963 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 06:38:39,999 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 06:38:40,027 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-10 06:38:40,029 INFO L263 TraceCheckSpWp]: Trace formula consists of 26 conjuncts, 4 conjunts are in the unsatisfiable core [2022-01-10 06:38:40,032 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-01-10 06:38:40,109 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-01-10 06:38:40,109 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-01-10 06:38:40,110 INFO L139 FreeRefinementEngine]: Strategy WOLF found an infeasible trace [2022-01-10 06:38:40,110 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleMathsat [1524703681] [2022-01-10 06:38:40,111 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleMathsat [1524703681] provided 1 perfect and 0 imperfect interpolant sequences [2022-01-10 06:38:40,111 INFO L186 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-01-10 06:38:40,111 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-01-10 06:38:40,113 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [350863782] [2022-01-10 06:38:40,113 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-01-10 06:38:40,116 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-01-10 06:38:40,123 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy WOLF [2022-01-10 06:38:40,152 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-01-10 06:38:40,153 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-01-10 06:38:40,154 INFO L87 Difference]: Start difference. First operand has 27 states, 18 states have (on average 1.3333333333333333) internal successors, (24), 19 states have internal predecessors, (24), 5 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) Second operand has 5 states, 4 states have (on average 2.0) internal successors, (8), 5 states have internal predecessors, (8), 1 states have call successors, (1), 1 states have call predecessors, (1), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-01-10 06:38:40,223 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-01-10 06:38:40,223 INFO L93 Difference]: Finished difference Result 37 states and 46 transitions. [2022-01-10 06:38:40,226 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-01-10 06:38:40,226 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 4 states have (on average 2.0) internal successors, (8), 5 states have internal predecessors, (8), 1 states have call successors, (1), 1 states have call predecessors, (1), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 10 [2022-01-10 06:38:40,227 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-01-10 06:38:40,231 INFO L225 Difference]: With dead ends: 37 [2022-01-10 06:38:40,231 INFO L226 Difference]: Without dead ends: 25 [2022-01-10 06:38:40,233 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 10 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2022-01-10 06:38:40,236 INFO L933 BasicCegarLoop]: 26 mSDtfsCounter, 14 mSDsluCounter, 56 mSDsCounter, 0 mSdLazyCounter, 31 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 17 SdHoareTripleChecker+Valid, 82 SdHoareTripleChecker+Invalid, 31 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 31 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-01-10 06:38:40,236 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [17 Valid, 82 Invalid, 31 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 31 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-01-10 06:38:40,247 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 25 states. [2022-01-10 06:38:40,258 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 25 to 25. [2022-01-10 06:38:40,259 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 25 states, 16 states have (on average 1.25) internal successors, (20), 17 states have internal predecessors, (20), 5 states have call successors, (5), 2 states have call predecessors, (5), 3 states have return successors, (7), 5 states have call predecessors, (7), 5 states have call successors, (7) [2022-01-10 06:38:40,260 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 25 states to 25 states and 32 transitions. [2022-01-10 06:38:40,261 INFO L78 Accepts]: Start accepts. Automaton has 25 states and 32 transitions. Word has length 10 [2022-01-10 06:38:40,261 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-01-10 06:38:40,261 INFO L470 AbstractCegarLoop]: Abstraction has 25 states and 32 transitions. [2022-01-10 06:38:40,261 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 4 states have (on average 2.0) internal successors, (8), 5 states have internal predecessors, (8), 1 states have call successors, (1), 1 states have call predecessors, (1), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-01-10 06:38:40,261 INFO L276 IsEmpty]: Start isEmpty. Operand 25 states and 32 transitions. [2022-01-10 06:38:40,262 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 12 [2022-01-10 06:38:40,262 INFO L506 BasicCegarLoop]: Found error trace [2022-01-10 06:38:40,262 INFO L514 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-01-10 06:38:40,268 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 06:38:40,467 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 06:38:40,468 INFO L402 AbstractCegarLoop]: === Iteration 2 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-01-10 06:38:40,468 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-01-10 06:38:40,468 INFO L85 PathProgramCache]: Analyzing trace with hash 2131805067, now seen corresponding path program 1 times [2022-01-10 06:38:40,469 INFO L121 FreeRefinementEngine]: Executing refinement strategy WOLF [2022-01-10 06:38:40,469 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleMathsat [628116569] [2022-01-10 06:38:40,469 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-01-10 06:38:40,469 INFO L168 SolverBuilder]: Constructing external solver with command: mathsat -unsat_core_generation=3 [2022-01-10 06:38:40,469 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat [2022-01-10 06:38:40,472 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 06:38:40,474 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 06:38:40,492 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-10 06:38:40,495 INFO L263 TraceCheckSpWp]: Trace formula consists of 27 conjuncts, 4 conjunts are in the unsatisfiable core [2022-01-10 06:38:40,496 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-01-10 06:38:40,554 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-01-10 06:38:40,554 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-01-10 06:38:40,559 INFO L139 FreeRefinementEngine]: Strategy WOLF found an infeasible trace [2022-01-10 06:38:40,559 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleMathsat [628116569] [2022-01-10 06:38:40,559 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleMathsat [628116569] provided 1 perfect and 0 imperfect interpolant sequences [2022-01-10 06:38:40,560 INFO L186 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-01-10 06:38:40,560 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-01-10 06:38:40,560 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2056285262] [2022-01-10 06:38:40,560 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-01-10 06:38:40,561 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-01-10 06:38:40,561 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy WOLF [2022-01-10 06:38:40,561 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-01-10 06:38:40,561 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-01-10 06:38:40,562 INFO L87 Difference]: Start difference. First operand 25 states and 32 transitions. Second operand has 5 states, 4 states have (on average 2.25) internal successors, (9), 5 states have internal predecessors, (9), 1 states have call successors, (1), 1 states have call predecessors, (1), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-01-10 06:38:40,621 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-01-10 06:38:40,621 INFO L93 Difference]: Finished difference Result 31 states and 39 transitions. [2022-01-10 06:38:40,622 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-01-10 06:38:40,622 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 4 states have (on average 2.25) internal successors, (9), 5 states have internal predecessors, (9), 1 states have call successors, (1), 1 states have call predecessors, (1), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 11 [2022-01-10 06:38:40,622 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-01-10 06:38:40,623 INFO L225 Difference]: With dead ends: 31 [2022-01-10 06:38:40,623 INFO L226 Difference]: Without dead ends: 27 [2022-01-10 06:38:40,623 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 11 GetRequests, 7 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2022-01-10 06:38:40,624 INFO L933 BasicCegarLoop]: 23 mSDtfsCounter, 8 mSDsluCounter, 49 mSDsCounter, 0 mSdLazyCounter, 39 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 11 SdHoareTripleChecker+Valid, 72 SdHoareTripleChecker+Invalid, 39 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 39 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-01-10 06:38:40,625 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [11 Valid, 72 Invalid, 39 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 39 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-01-10 06:38:40,625 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 27 states. [2022-01-10 06:38:40,629 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 27 to 25. [2022-01-10 06:38:40,629 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 25 states, 16 states have (on average 1.25) internal successors, (20), 17 states have internal predecessors, (20), 5 states have call successors, (5), 2 states have call predecessors, (5), 3 states have return successors, (7), 5 states have call predecessors, (7), 5 states have call successors, (7) [2022-01-10 06:38:40,630 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 25 states to 25 states and 32 transitions. [2022-01-10 06:38:40,630 INFO L78 Accepts]: Start accepts. Automaton has 25 states and 32 transitions. Word has length 11 [2022-01-10 06:38:40,630 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-01-10 06:38:40,630 INFO L470 AbstractCegarLoop]: Abstraction has 25 states and 32 transitions. [2022-01-10 06:38:40,630 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 4 states have (on average 2.25) internal successors, (9), 5 states have internal predecessors, (9), 1 states have call successors, (1), 1 states have call predecessors, (1), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-01-10 06:38:40,631 INFO L276 IsEmpty]: Start isEmpty. Operand 25 states and 32 transitions. [2022-01-10 06:38:40,631 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 23 [2022-01-10 06:38:40,631 INFO L506 BasicCegarLoop]: Found error trace [2022-01-10 06:38:40,631 INFO L514 BasicCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-01-10 06:38:40,640 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 06:38:40,832 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 06:38:40,832 INFO L402 AbstractCegarLoop]: === Iteration 3 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-01-10 06:38:40,833 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-01-10 06:38:40,833 INFO L85 PathProgramCache]: Analyzing trace with hash -1494555912, now seen corresponding path program 1 times [2022-01-10 06:38:40,833 INFO L121 FreeRefinementEngine]: Executing refinement strategy WOLF [2022-01-10 06:38:40,834 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleMathsat [1710952856] [2022-01-10 06:38:40,834 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-01-10 06:38:40,834 INFO L168 SolverBuilder]: Constructing external solver with command: mathsat -unsat_core_generation=3 [2022-01-10 06:38:40,834 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat [2022-01-10 06:38:40,835 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 06:38:40,837 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 06:38:40,858 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-10 06:38:40,859 INFO L263 TraceCheckSpWp]: Trace formula consists of 43 conjuncts, 6 conjunts are in the unsatisfiable core [2022-01-10 06:38:40,860 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-01-10 06:38:41,010 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2022-01-10 06:38:41,010 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-01-10 06:38:41,285 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2022-01-10 06:38:41,286 INFO L139 FreeRefinementEngine]: Strategy WOLF found an infeasible trace [2022-01-10 06:38:41,286 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleMathsat [1710952856] [2022-01-10 06:38:41,286 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleMathsat [1710952856] provided 0 perfect and 2 imperfect interpolant sequences [2022-01-10 06:38:41,286 INFO L186 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-01-10 06:38:41,286 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7] total 10 [2022-01-10 06:38:41,286 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1449126610] [2022-01-10 06:38:41,286 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-01-10 06:38:41,287 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2022-01-10 06:38:41,287 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy WOLF [2022-01-10 06:38:41,287 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2022-01-10 06:38:41,289 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=22, Invalid=68, Unknown=0, NotChecked=0, Total=90 [2022-01-10 06:38:41,289 INFO L87 Difference]: Start difference. First operand 25 states and 32 transitions. Second operand has 10 states, 8 states have (on average 2.75) internal successors, (22), 10 states have internal predecessors, (22), 5 states have call successors, (5), 1 states have call predecessors, (5), 3 states have return successors, (5), 2 states have call predecessors, (5), 5 states have call successors, (5) [2022-01-10 06:38:41,468 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-01-10 06:38:41,468 INFO L93 Difference]: Finished difference Result 37 states and 49 transitions. [2022-01-10 06:38:41,469 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2022-01-10 06:38:41,470 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 8 states have (on average 2.75) internal successors, (22), 10 states have internal predecessors, (22), 5 states have call successors, (5), 1 states have call predecessors, (5), 3 states have return successors, (5), 2 states have call predecessors, (5), 5 states have call successors, (5) Word has length 22 [2022-01-10 06:38:41,470 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-01-10 06:38:41,471 INFO L225 Difference]: With dead ends: 37 [2022-01-10 06:38:41,471 INFO L226 Difference]: Without dead ends: 33 [2022-01-10 06:38:41,471 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 44 GetRequests, 34 SyntacticMatches, 0 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=32, Invalid=100, Unknown=0, NotChecked=0, Total=132 [2022-01-10 06:38:41,472 INFO L933 BasicCegarLoop]: 18 mSDtfsCounter, 24 mSDsluCounter, 78 mSDsCounter, 0 mSdLazyCounter, 104 mSolverCounterSat, 11 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 31 SdHoareTripleChecker+Valid, 96 SdHoareTripleChecker+Invalid, 115 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 11 IncrementalHoareTripleChecker+Valid, 104 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-01-10 06:38:41,473 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [31 Valid, 96 Invalid, 115 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [11 Valid, 104 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-01-10 06:38:41,473 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 33 states. [2022-01-10 06:38:41,478 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 33 to 29. [2022-01-10 06:38:41,478 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 29 states, 18 states have (on average 1.2222222222222223) internal successors, (22), 19 states have internal predecessors, (22), 6 states have call successors, (6), 2 states have call predecessors, (6), 4 states have return successors, (11), 7 states have call predecessors, (11), 6 states have call successors, (11) [2022-01-10 06:38:41,479 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 29 states to 29 states and 39 transitions. [2022-01-10 06:38:41,479 INFO L78 Accepts]: Start accepts. Automaton has 29 states and 39 transitions. Word has length 22 [2022-01-10 06:38:41,479 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-01-10 06:38:41,479 INFO L470 AbstractCegarLoop]: Abstraction has 29 states and 39 transitions. [2022-01-10 06:38:41,480 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 8 states have (on average 2.75) internal successors, (22), 10 states have internal predecessors, (22), 5 states have call successors, (5), 1 states have call predecessors, (5), 3 states have return successors, (5), 2 states have call predecessors, (5), 5 states have call successors, (5) [2022-01-10 06:38:41,480 INFO L276 IsEmpty]: Start isEmpty. Operand 29 states and 39 transitions. [2022-01-10 06:38:41,481 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 24 [2022-01-10 06:38:41,481 INFO L506 BasicCegarLoop]: Found error trace [2022-01-10 06:38:41,481 INFO L514 BasicCegarLoop]: trace histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-01-10 06:38:41,497 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (4)] Forceful destruction successful, exit code 0 [2022-01-10 06:38:41,687 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 06:38:41,688 INFO L402 AbstractCegarLoop]: === Iteration 4 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-01-10 06:38:41,690 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-01-10 06:38:41,690 INFO L85 PathProgramCache]: Analyzing trace with hash 814571350, now seen corresponding path program 1 times [2022-01-10 06:38:41,690 INFO L121 FreeRefinementEngine]: Executing refinement strategy WOLF [2022-01-10 06:38:41,690 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleMathsat [386136263] [2022-01-10 06:38:41,690 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-01-10 06:38:41,690 INFO L168 SolverBuilder]: Constructing external solver with command: mathsat -unsat_core_generation=3 [2022-01-10 06:38:41,691 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat [2022-01-10 06:38:41,692 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 06:38:41,692 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 06:38:41,717 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-10 06:38:41,718 INFO L263 TraceCheckSpWp]: Trace formula consists of 44 conjuncts, 6 conjunts are in the unsatisfiable core [2022-01-10 06:38:41,720 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-01-10 06:38:41,798 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2022-01-10 06:38:41,798 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-01-10 06:38:41,963 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2022-01-10 06:38:41,963 INFO L139 FreeRefinementEngine]: Strategy WOLF found an infeasible trace [2022-01-10 06:38:41,964 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleMathsat [386136263] [2022-01-10 06:38:41,964 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleMathsat [386136263] provided 0 perfect and 2 imperfect interpolant sequences [2022-01-10 06:38:41,964 INFO L186 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-01-10 06:38:41,964 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7] total 10 [2022-01-10 06:38:41,964 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1591102264] [2022-01-10 06:38:41,964 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-01-10 06:38:41,965 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2022-01-10 06:38:41,965 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy WOLF [2022-01-10 06:38:41,965 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2022-01-10 06:38:41,965 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=22, Invalid=68, Unknown=0, NotChecked=0, Total=90 [2022-01-10 06:38:41,966 INFO L87 Difference]: Start difference. First operand 29 states and 39 transitions. Second operand has 10 states, 8 states have (on average 3.0) internal successors, (24), 10 states have internal predecessors, (24), 5 states have call successors, (5), 1 states have call predecessors, (5), 3 states have return successors, (5), 2 states have call predecessors, (5), 5 states have call successors, (5) [2022-01-10 06:38:42,103 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-01-10 06:38:42,103 INFO L93 Difference]: Finished difference Result 61 states and 96 transitions. [2022-01-10 06:38:42,104 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2022-01-10 06:38:42,104 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 8 states have (on average 3.0) internal successors, (24), 10 states have internal predecessors, (24), 5 states have call successors, (5), 1 states have call predecessors, (5), 3 states have return successors, (5), 2 states have call predecessors, (5), 5 states have call successors, (5) Word has length 23 [2022-01-10 06:38:42,104 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-01-10 06:38:42,105 INFO L225 Difference]: With dead ends: 61 [2022-01-10 06:38:42,105 INFO L226 Difference]: Without dead ends: 35 [2022-01-10 06:38:42,110 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 47 GetRequests, 37 SyntacticMatches, 0 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=32, Invalid=100, Unknown=0, NotChecked=0, Total=132 [2022-01-10 06:38:42,110 INFO L933 BasicCegarLoop]: 20 mSDtfsCounter, 15 mSDsluCounter, 95 mSDsCounter, 0 mSdLazyCounter, 126 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 20 SdHoareTripleChecker+Valid, 115 SdHoareTripleChecker+Invalid, 129 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 126 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-01-10 06:38:42,111 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [20 Valid, 115 Invalid, 129 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 126 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-01-10 06:38:42,111 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 35 states. [2022-01-10 06:38:42,117 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 35 to 32. [2022-01-10 06:38:42,117 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 32 states, 19 states have (on average 1.2105263157894737) internal successors, (23), 21 states have internal predecessors, (23), 7 states have call successors, (7), 2 states have call predecessors, (7), 5 states have return successors, (16), 8 states have call predecessors, (16), 7 states have call successors, (16) [2022-01-10 06:38:42,118 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 32 states to 32 states and 46 transitions. [2022-01-10 06:38:42,118 INFO L78 Accepts]: Start accepts. Automaton has 32 states and 46 transitions. Word has length 23 [2022-01-10 06:38:42,118 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-01-10 06:38:42,118 INFO L470 AbstractCegarLoop]: Abstraction has 32 states and 46 transitions. [2022-01-10 06:38:42,119 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 8 states have (on average 3.0) internal successors, (24), 10 states have internal predecessors, (24), 5 states have call successors, (5), 1 states have call predecessors, (5), 3 states have return successors, (5), 2 states have call predecessors, (5), 5 states have call successors, (5) [2022-01-10 06:38:42,119 INFO L276 IsEmpty]: Start isEmpty. Operand 32 states and 46 transitions. [2022-01-10 06:38:42,121 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 35 [2022-01-10 06:38:42,121 INFO L506 BasicCegarLoop]: Found error trace [2022-01-10 06:38:42,121 INFO L514 BasicCegarLoop]: trace histogram [3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-01-10 06:38:42,127 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (5)] Forceful destruction successful, exit code 0 [2022-01-10 06:38:42,322 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 06:38:42,322 INFO L402 AbstractCegarLoop]: === Iteration 5 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-01-10 06:38:42,323 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-01-10 06:38:42,323 INFO L85 PathProgramCache]: Analyzing trace with hash 1581983960, now seen corresponding path program 1 times [2022-01-10 06:38:42,323 INFO L121 FreeRefinementEngine]: Executing refinement strategy WOLF [2022-01-10 06:38:42,323 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleMathsat [1380722145] [2022-01-10 06:38:42,324 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-01-10 06:38:42,324 INFO L168 SolverBuilder]: Constructing external solver with command: mathsat -unsat_core_generation=3 [2022-01-10 06:38:42,324 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat [2022-01-10 06:38:42,327 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 06:38:42,328 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 06:38:42,354 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-10 06:38:42,359 INFO L263 TraceCheckSpWp]: Trace formula consists of 60 conjuncts, 8 conjunts are in the unsatisfiable core [2022-01-10 06:38:42,361 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-01-10 06:38:42,481 INFO L134 CoverageAnalysis]: Checked inductivity of 16 backedges. 2 proven. 9 refuted. 0 times theorem prover too weak. 5 trivial. 0 not checked. [2022-01-10 06:38:42,481 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-01-10 06:38:42,840 INFO L134 CoverageAnalysis]: Checked inductivity of 16 backedges. 2 proven. 10 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2022-01-10 06:38:42,841 INFO L139 FreeRefinementEngine]: Strategy WOLF found an infeasible trace [2022-01-10 06:38:42,841 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleMathsat [1380722145] [2022-01-10 06:38:42,841 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleMathsat [1380722145] provided 0 perfect and 2 imperfect interpolant sequences [2022-01-10 06:38:42,841 INFO L186 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-01-10 06:38:42,841 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 9] total 12 [2022-01-10 06:38:42,841 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [592761364] [2022-01-10 06:38:42,841 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-01-10 06:38:42,842 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2022-01-10 06:38:42,842 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy WOLF [2022-01-10 06:38:42,842 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2022-01-10 06:38:42,842 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=28, Invalid=104, Unknown=0, NotChecked=0, Total=132 [2022-01-10 06:38:42,842 INFO L87 Difference]: Start difference. First operand 32 states and 46 transitions. Second operand has 12 states, 10 states have (on average 3.2) internal successors, (32), 12 states have internal predecessors, (32), 8 states have call successors, (8), 1 states have call predecessors, (8), 4 states have return successors, (8), 3 states have call predecessors, (8), 8 states have call successors, (8) [2022-01-10 06:38:43,047 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-01-10 06:38:43,047 INFO L93 Difference]: Finished difference Result 49 states and 78 transitions. [2022-01-10 06:38:43,048 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2022-01-10 06:38:43,048 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 10 states have (on average 3.2) internal successors, (32), 12 states have internal predecessors, (32), 8 states have call successors, (8), 1 states have call predecessors, (8), 4 states have return successors, (8), 3 states have call predecessors, (8), 8 states have call successors, (8) Word has length 34 [2022-01-10 06:38:43,048 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-01-10 06:38:43,049 INFO L225 Difference]: With dead ends: 49 [2022-01-10 06:38:43,049 INFO L226 Difference]: Without dead ends: 45 [2022-01-10 06:38:43,049 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 71 GetRequests, 58 SyntacticMatches, 0 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 9 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=45, Invalid=165, Unknown=0, NotChecked=0, Total=210 [2022-01-10 06:38:43,050 INFO L933 BasicCegarLoop]: 21 mSDtfsCounter, 18 mSDsluCounter, 132 mSDsCounter, 0 mSdLazyCounter, 184 mSolverCounterSat, 14 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 26 SdHoareTripleChecker+Valid, 153 SdHoareTripleChecker+Invalid, 198 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 14 IncrementalHoareTripleChecker+Valid, 184 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2022-01-10 06:38:43,050 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [26 Valid, 153 Invalid, 198 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [14 Valid, 184 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2022-01-10 06:38:43,051 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 45 states. [2022-01-10 06:38:43,057 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 45 to 36. [2022-01-10 06:38:43,058 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 36 states, 21 states have (on average 1.1904761904761905) internal successors, (25), 23 states have internal predecessors, (25), 8 states have call successors, (8), 2 states have call predecessors, (8), 6 states have return successors, (21), 10 states have call predecessors, (21), 8 states have call successors, (21) [2022-01-10 06:38:43,058 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 36 states to 36 states and 54 transitions. [2022-01-10 06:38:43,058 INFO L78 Accepts]: Start accepts. Automaton has 36 states and 54 transitions. Word has length 34 [2022-01-10 06:38:43,059 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-01-10 06:38:43,059 INFO L470 AbstractCegarLoop]: Abstraction has 36 states and 54 transitions. [2022-01-10 06:38:43,059 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 10 states have (on average 3.2) internal successors, (32), 12 states have internal predecessors, (32), 8 states have call successors, (8), 1 states have call predecessors, (8), 4 states have return successors, (8), 3 states have call predecessors, (8), 8 states have call successors, (8) [2022-01-10 06:38:43,059 INFO L276 IsEmpty]: Start isEmpty. Operand 36 states and 54 transitions. [2022-01-10 06:38:43,060 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 36 [2022-01-10 06:38:43,060 INFO L506 BasicCegarLoop]: Found error trace [2022-01-10 06:38:43,060 INFO L514 BasicCegarLoop]: trace histogram [3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-01-10 06:38:43,072 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 06:38:43,268 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 06:38:43,270 INFO L402 AbstractCegarLoop]: === Iteration 6 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-01-10 06:38:43,271 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-01-10 06:38:43,271 INFO L85 PathProgramCache]: Analyzing trace with hash 1656487097, now seen corresponding path program 1 times [2022-01-10 06:38:43,271 INFO L121 FreeRefinementEngine]: Executing refinement strategy WOLF [2022-01-10 06:38:43,271 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleMathsat [402326989] [2022-01-10 06:38:43,271 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-01-10 06:38:43,271 INFO L168 SolverBuilder]: Constructing external solver with command: mathsat -unsat_core_generation=3 [2022-01-10 06:38:43,271 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat [2022-01-10 06:38:43,272 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 06:38:43,273 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 06:38:43,297 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-10 06:38:43,298 INFO L263 TraceCheckSpWp]: Trace formula consists of 61 conjuncts, 8 conjunts are in the unsatisfiable core [2022-01-10 06:38:43,300 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-01-10 06:38:43,373 INFO L134 CoverageAnalysis]: Checked inductivity of 17 backedges. 2 proven. 9 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2022-01-10 06:38:43,374 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-01-10 06:38:43,617 INFO L134 CoverageAnalysis]: Checked inductivity of 17 backedges. 2 proven. 11 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2022-01-10 06:38:43,617 INFO L139 FreeRefinementEngine]: Strategy WOLF found an infeasible trace [2022-01-10 06:38:43,617 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleMathsat [402326989] [2022-01-10 06:38:43,617 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleMathsat [402326989] provided 0 perfect and 2 imperfect interpolant sequences [2022-01-10 06:38:43,618 INFO L186 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-01-10 06:38:43,618 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 9] total 12 [2022-01-10 06:38:43,618 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [215793546] [2022-01-10 06:38:43,618 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-01-10 06:38:43,619 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2022-01-10 06:38:43,619 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy WOLF [2022-01-10 06:38:43,620 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2022-01-10 06:38:43,620 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=28, Invalid=104, Unknown=0, NotChecked=0, Total=132 [2022-01-10 06:38:43,620 INFO L87 Difference]: Start difference. First operand 36 states and 54 transitions. Second operand has 12 states, 10 states have (on average 3.3) internal successors, (33), 12 states have internal predecessors, (33), 8 states have call successors, (8), 1 states have call predecessors, (8), 4 states have return successors, (8), 3 states have call predecessors, (8), 8 states have call successors, (8) [2022-01-10 06:38:43,803 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-01-10 06:38:43,803 INFO L93 Difference]: Finished difference Result 79 states and 150 transitions. [2022-01-10 06:38:43,803 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2022-01-10 06:38:43,804 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 10 states have (on average 3.3) internal successors, (33), 12 states have internal predecessors, (33), 8 states have call successors, (8), 1 states have call predecessors, (8), 4 states have return successors, (8), 3 states have call predecessors, (8), 8 states have call successors, (8) Word has length 35 [2022-01-10 06:38:43,804 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-01-10 06:38:43,805 INFO L225 Difference]: With dead ends: 79 [2022-01-10 06:38:43,805 INFO L226 Difference]: Without dead ends: 46 [2022-01-10 06:38:43,806 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 74 GetRequests, 61 SyntacticMatches, 0 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 9 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=45, Invalid=165, Unknown=0, NotChecked=0, Total=210 [2022-01-10 06:38:43,806 INFO L933 BasicCegarLoop]: 23 mSDtfsCounter, 16 mSDsluCounter, 129 mSDsCounter, 0 mSdLazyCounter, 178 mSolverCounterSat, 8 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 21 SdHoareTripleChecker+Valid, 152 SdHoareTripleChecker+Invalid, 186 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 8 IncrementalHoareTripleChecker+Valid, 178 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-01-10 06:38:43,806 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [21 Valid, 152 Invalid, 186 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [8 Valid, 178 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-01-10 06:38:43,807 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 46 states. [2022-01-10 06:38:43,817 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 46 to 46. [2022-01-10 06:38:43,818 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 46 states, 26 states have (on average 1.1538461538461537) internal successors, (30), 29 states have internal predecessors, (30), 10 states have call successors, (10), 2 states have call predecessors, (10), 9 states have return successors, (37), 14 states have call predecessors, (37), 10 states have call successors, (37) [2022-01-10 06:38:43,819 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 46 states to 46 states and 77 transitions. [2022-01-10 06:38:43,819 INFO L78 Accepts]: Start accepts. Automaton has 46 states and 77 transitions. Word has length 35 [2022-01-10 06:38:43,819 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-01-10 06:38:43,819 INFO L470 AbstractCegarLoop]: Abstraction has 46 states and 77 transitions. [2022-01-10 06:38:43,819 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 10 states have (on average 3.3) internal successors, (33), 12 states have internal predecessors, (33), 8 states have call successors, (8), 1 states have call predecessors, (8), 4 states have return successors, (8), 3 states have call predecessors, (8), 8 states have call successors, (8) [2022-01-10 06:38:43,820 INFO L276 IsEmpty]: Start isEmpty. Operand 46 states and 77 transitions. [2022-01-10 06:38:43,821 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 47 [2022-01-10 06:38:43,821 INFO L506 BasicCegarLoop]: Found error trace [2022-01-10 06:38:43,821 INFO L514 BasicCegarLoop]: trace histogram [4, 4, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-01-10 06:38:43,829 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 06:38:44,027 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 06:38:44,028 INFO L402 AbstractCegarLoop]: === Iteration 7 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-01-10 06:38:44,028 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-01-10 06:38:44,028 INFO L85 PathProgramCache]: Analyzing trace with hash 600804856, now seen corresponding path program 2 times [2022-01-10 06:38:44,029 INFO L121 FreeRefinementEngine]: Executing refinement strategy WOLF [2022-01-10 06:38:44,029 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleMathsat [1267575858] [2022-01-10 06:38:44,029 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-01-10 06:38:44,029 INFO L168 SolverBuilder]: Constructing external solver with command: mathsat -unsat_core_generation=3 [2022-01-10 06:38:44,029 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat [2022-01-10 06:38:44,030 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 06:38:44,032 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 06:38:44,063 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-01-10 06:38:44,063 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-01-10 06:38:44,065 INFO L263 TraceCheckSpWp]: Trace formula consists of 77 conjuncts, 10 conjunts are in the unsatisfiable core [2022-01-10 06:38:44,071 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-01-10 06:38:44,225 INFO L134 CoverageAnalysis]: Checked inductivity of 40 backedges. 4 proven. 20 refuted. 0 times theorem prover too weak. 16 trivial. 0 not checked. [2022-01-10 06:38:44,225 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-01-10 06:38:44,731 INFO L134 CoverageAnalysis]: Checked inductivity of 40 backedges. 4 proven. 24 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2022-01-10 06:38:44,731 INFO L139 FreeRefinementEngine]: Strategy WOLF found an infeasible trace [2022-01-10 06:38:44,731 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleMathsat [1267575858] [2022-01-10 06:38:44,731 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleMathsat [1267575858] provided 0 perfect and 2 imperfect interpolant sequences [2022-01-10 06:38:44,731 INFO L186 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-01-10 06:38:44,731 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 11] total 14 [2022-01-10 06:38:44,732 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [749154635] [2022-01-10 06:38:44,732 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-01-10 06:38:44,732 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2022-01-10 06:38:44,732 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy WOLF [2022-01-10 06:38:44,732 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2022-01-10 06:38:44,733 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=34, Invalid=148, Unknown=0, NotChecked=0, Total=182 [2022-01-10 06:38:44,733 INFO L87 Difference]: Start difference. First operand 46 states and 77 transitions. Second operand has 14 states, 12 states have (on average 3.0833333333333335) internal successors, (37), 14 states have internal predecessors, (37), 10 states have call successors, (10), 1 states have call predecessors, (10), 5 states have return successors, (11), 4 states have call predecessors, (11), 10 states have call successors, (11) [2022-01-10 06:38:45,039 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-01-10 06:38:45,039 INFO L93 Difference]: Finished difference Result 70 states and 142 transitions. [2022-01-10 06:38:45,039 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2022-01-10 06:38:45,040 INFO L78 Accepts]: Start accepts. Automaton has has 14 states, 12 states have (on average 3.0833333333333335) internal successors, (37), 14 states have internal predecessors, (37), 10 states have call successors, (10), 1 states have call predecessors, (10), 5 states have return successors, (11), 4 states have call predecessors, (11), 10 states have call successors, (11) Word has length 46 [2022-01-10 06:38:45,040 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-01-10 06:38:45,041 INFO L225 Difference]: With dead ends: 70 [2022-01-10 06:38:45,041 INFO L226 Difference]: Without dead ends: 66 [2022-01-10 06:38:45,042 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 99 GetRequests, 82 SyntacticMatches, 0 SemanticMatches, 17 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 20 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=67, Invalid=275, Unknown=0, NotChecked=0, Total=342 [2022-01-10 06:38:45,043 INFO L933 BasicCegarLoop]: 23 mSDtfsCounter, 34 mSDsluCounter, 133 mSDsCounter, 0 mSdLazyCounter, 209 mSolverCounterSat, 34 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 43 SdHoareTripleChecker+Valid, 156 SdHoareTripleChecker+Invalid, 243 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 34 IncrementalHoareTripleChecker+Valid, 209 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2022-01-10 06:38:45,043 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [43 Valid, 156 Invalid, 243 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [34 Valid, 209 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2022-01-10 06:38:45,043 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 66 states. [2022-01-10 06:38:45,056 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 66 to 50. [2022-01-10 06:38:45,056 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 50 states, 28 states have (on average 1.1428571428571428) internal successors, (32), 31 states have internal predecessors, (32), 11 states have call successors, (11), 2 states have call predecessors, (11), 10 states have return successors, (47), 16 states have call predecessors, (47), 11 states have call successors, (47) [2022-01-10 06:38:45,057 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 50 states to 50 states and 90 transitions. [2022-01-10 06:38:45,057 INFO L78 Accepts]: Start accepts. Automaton has 50 states and 90 transitions. Word has length 46 [2022-01-10 06:38:45,058 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-01-10 06:38:45,058 INFO L470 AbstractCegarLoop]: Abstraction has 50 states and 90 transitions. [2022-01-10 06:38:45,058 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 14 states, 12 states have (on average 3.0833333333333335) internal successors, (37), 14 states have internal predecessors, (37), 10 states have call successors, (10), 1 states have call predecessors, (10), 5 states have return successors, (11), 4 states have call predecessors, (11), 10 states have call successors, (11) [2022-01-10 06:38:45,058 INFO L276 IsEmpty]: Start isEmpty. Operand 50 states and 90 transitions. [2022-01-10 06:38:45,060 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 48 [2022-01-10 06:38:45,060 INFO L506 BasicCegarLoop]: Found error trace [2022-01-10 06:38:45,060 INFO L514 BasicCegarLoop]: trace histogram [4, 4, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-01-10 06:38:45,083 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (8)] Ended with exit code 0 [2022-01-10 06:38:45,269 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 06:38:45,270 INFO L402 AbstractCegarLoop]: === Iteration 8 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-01-10 06:38:45,270 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-01-10 06:38:45,270 INFO L85 PathProgramCache]: Analyzing trace with hash 1482129412, now seen corresponding path program 1 times [2022-01-10 06:38:45,270 INFO L121 FreeRefinementEngine]: Executing refinement strategy WOLF [2022-01-10 06:38:45,270 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleMathsat [2146123410] [2022-01-10 06:38:45,271 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-01-10 06:38:45,271 INFO L168 SolverBuilder]: Constructing external solver with command: mathsat -unsat_core_generation=3 [2022-01-10 06:38:45,271 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat [2022-01-10 06:38:45,272 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 06:38:45,273 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 06:38:45,330 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-10 06:38:45,332 INFO L263 TraceCheckSpWp]: Trace formula consists of 78 conjuncts, 8 conjunts are in the unsatisfiable core [2022-01-10 06:38:45,333 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-01-10 06:38:45,458 INFO L134 CoverageAnalysis]: Checked inductivity of 41 backedges. 11 proven. 11 refuted. 0 times theorem prover too weak. 19 trivial. 0 not checked. [2022-01-10 06:38:45,458 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-01-10 06:38:45,789 INFO L134 CoverageAnalysis]: Checked inductivity of 41 backedges. 11 proven. 12 refuted. 0 times theorem prover too weak. 18 trivial. 0 not checked. [2022-01-10 06:38:45,790 INFO L139 FreeRefinementEngine]: Strategy WOLF found an infeasible trace [2022-01-10 06:38:45,790 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleMathsat [2146123410] [2022-01-10 06:38:45,790 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleMathsat [2146123410] provided 0 perfect and 2 imperfect interpolant sequences [2022-01-10 06:38:45,790 INFO L186 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-01-10 06:38:45,790 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 9] total 12 [2022-01-10 06:38:45,790 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1027612040] [2022-01-10 06:38:45,790 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-01-10 06:38:45,791 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2022-01-10 06:38:45,791 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy WOLF [2022-01-10 06:38:45,791 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2022-01-10 06:38:45,791 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=28, Invalid=104, Unknown=0, NotChecked=0, Total=132 [2022-01-10 06:38:45,791 INFO L87 Difference]: Start difference. First operand 50 states and 90 transitions. Second operand has 12 states, 10 states have (on average 3.6) internal successors, (36), 12 states have internal predecessors, (36), 8 states have call successors, (11), 1 states have call predecessors, (11), 4 states have return successors, (11), 6 states have call predecessors, (11), 8 states have call successors, (11) [2022-01-10 06:38:45,983 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-01-10 06:38:45,983 INFO L93 Difference]: Finished difference Result 77 states and 164 transitions. [2022-01-10 06:38:45,984 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2022-01-10 06:38:45,984 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 10 states have (on average 3.6) internal successors, (36), 12 states have internal predecessors, (36), 8 states have call successors, (11), 1 states have call predecessors, (11), 4 states have return successors, (11), 6 states have call predecessors, (11), 8 states have call successors, (11) Word has length 47 [2022-01-10 06:38:45,985 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-01-10 06:38:45,985 INFO L225 Difference]: With dead ends: 77 [2022-01-10 06:38:45,986 INFO L226 Difference]: Without dead ends: 73 [2022-01-10 06:38:45,986 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 98 GetRequests, 85 SyntacticMatches, 0 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 9 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=45, Invalid=165, Unknown=0, NotChecked=0, Total=210 [2022-01-10 06:38:45,987 INFO L933 BasicCegarLoop]: 19 mSDtfsCounter, 17 mSDsluCounter, 108 mSDsCounter, 0 mSdLazyCounter, 157 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 23 SdHoareTripleChecker+Valid, 127 SdHoareTripleChecker+Invalid, 160 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 157 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-01-10 06:38:45,987 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [23 Valid, 127 Invalid, 160 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 157 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-01-10 06:38:45,987 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 73 states. [2022-01-10 06:38:46,008 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 73 to 52. [2022-01-10 06:38:46,009 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 52 states, 29 states have (on average 1.1379310344827587) internal successors, (33), 33 states have internal predecessors, (33), 11 states have call successors, (11), 2 states have call predecessors, (11), 11 states have return successors, (51), 16 states have call predecessors, (51), 11 states have call successors, (51) [2022-01-10 06:38:46,010 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 52 states to 52 states and 95 transitions. [2022-01-10 06:38:46,010 INFO L78 Accepts]: Start accepts. Automaton has 52 states and 95 transitions. Word has length 47 [2022-01-10 06:38:46,010 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-01-10 06:38:46,011 INFO L470 AbstractCegarLoop]: Abstraction has 52 states and 95 transitions. [2022-01-10 06:38:46,011 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 10 states have (on average 3.6) internal successors, (36), 12 states have internal predecessors, (36), 8 states have call successors, (11), 1 states have call predecessors, (11), 4 states have return successors, (11), 6 states have call predecessors, (11), 8 states have call successors, (11) [2022-01-10 06:38:46,011 INFO L276 IsEmpty]: Start isEmpty. Operand 52 states and 95 transitions. [2022-01-10 06:38:46,015 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 49 [2022-01-10 06:38:46,015 INFO L506 BasicCegarLoop]: Found error trace [2022-01-10 06:38:46,015 INFO L514 BasicCegarLoop]: trace histogram [4, 4, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-01-10 06:38:46,026 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (9)] Forceful destruction successful, exit code 0 [2022-01-10 06:38:46,216 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 06:38:46,216 INFO L402 AbstractCegarLoop]: === Iteration 9 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-01-10 06:38:46,217 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-01-10 06:38:46,217 INFO L85 PathProgramCache]: Analyzing trace with hash -951466503, now seen corresponding path program 1 times [2022-01-10 06:38:46,217 INFO L121 FreeRefinementEngine]: Executing refinement strategy WOLF [2022-01-10 06:38:46,217 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleMathsat [1788791406] [2022-01-10 06:38:46,217 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-01-10 06:38:46,217 INFO L168 SolverBuilder]: Constructing external solver with command: mathsat -unsat_core_generation=3 [2022-01-10 06:38:46,218 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat [2022-01-10 06:38:46,218 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 06:38:46,219 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 06:38:46,248 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-10 06:38:46,259 INFO L263 TraceCheckSpWp]: Trace formula consists of 79 conjuncts, 6 conjunts are in the unsatisfiable core [2022-01-10 06:38:46,260 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-01-10 06:38:46,352 INFO L134 CoverageAnalysis]: Checked inductivity of 43 backedges. 15 proven. 5 refuted. 0 times theorem prover too weak. 23 trivial. 0 not checked. [2022-01-10 06:38:46,352 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-01-10 06:38:46,577 INFO L134 CoverageAnalysis]: Checked inductivity of 43 backedges. 15 proven. 5 refuted. 0 times theorem prover too weak. 23 trivial. 0 not checked. [2022-01-10 06:38:46,578 INFO L139 FreeRefinementEngine]: Strategy WOLF found an infeasible trace [2022-01-10 06:38:46,578 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleMathsat [1788791406] [2022-01-10 06:38:46,578 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleMathsat [1788791406] provided 0 perfect and 2 imperfect interpolant sequences [2022-01-10 06:38:46,578 INFO L186 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-01-10 06:38:46,578 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7] total 10 [2022-01-10 06:38:46,578 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1942558435] [2022-01-10 06:38:46,578 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-01-10 06:38:46,579 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2022-01-10 06:38:46,579 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy WOLF [2022-01-10 06:38:46,579 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2022-01-10 06:38:46,579 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=22, Invalid=68, Unknown=0, NotChecked=0, Total=90 [2022-01-10 06:38:46,580 INFO L87 Difference]: Start difference. First operand 52 states and 95 transitions. Second operand has 10 states, 8 states have (on average 4.0) internal successors, (32), 10 states have internal predecessors, (32), 5 states have call successors, (10), 1 states have call predecessors, (10), 3 states have return successors, (10), 5 states have call predecessors, (10), 5 states have call successors, (10) [2022-01-10 06:38:46,683 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-01-10 06:38:46,684 INFO L93 Difference]: Finished difference Result 68 states and 122 transitions. [2022-01-10 06:38:46,684 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2022-01-10 06:38:46,684 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 8 states have (on average 4.0) internal successors, (32), 10 states have internal predecessors, (32), 5 states have call successors, (10), 1 states have call predecessors, (10), 3 states have return successors, (10), 5 states have call predecessors, (10), 5 states have call successors, (10) Word has length 48 [2022-01-10 06:38:46,685 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-01-10 06:38:46,685 INFO L225 Difference]: With dead ends: 68 [2022-01-10 06:38:46,685 INFO L226 Difference]: Without dead ends: 64 [2022-01-10 06:38:46,686 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 96 GetRequests, 86 SyntacticMatches, 0 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=32, Invalid=100, Unknown=0, NotChecked=0, Total=132 [2022-01-10 06:38:46,686 INFO L933 BasicCegarLoop]: 17 mSDtfsCounter, 29 mSDsluCounter, 61 mSDsCounter, 0 mSdLazyCounter, 85 mSolverCounterSat, 6 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 34 SdHoareTripleChecker+Valid, 78 SdHoareTripleChecker+Invalid, 91 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 6 IncrementalHoareTripleChecker+Valid, 85 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-01-10 06:38:46,686 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [34 Valid, 78 Invalid, 91 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [6 Valid, 85 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-01-10 06:38:46,687 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 64 states. [2022-01-10 06:38:46,693 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 64 to 52. [2022-01-10 06:38:46,693 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 52 states, 29 states have (on average 1.1379310344827587) internal successors, (33), 33 states have internal predecessors, (33), 11 states have call successors, (11), 2 states have call predecessors, (11), 11 states have return successors, (51), 16 states have call predecessors, (51), 11 states have call successors, (51) [2022-01-10 06:38:46,694 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 52 states to 52 states and 95 transitions. [2022-01-10 06:38:46,694 INFO L78 Accepts]: Start accepts. Automaton has 52 states and 95 transitions. Word has length 48 [2022-01-10 06:38:46,694 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-01-10 06:38:46,694 INFO L470 AbstractCegarLoop]: Abstraction has 52 states and 95 transitions. [2022-01-10 06:38:46,694 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 8 states have (on average 4.0) internal successors, (32), 10 states have internal predecessors, (32), 5 states have call successors, (10), 1 states have call predecessors, (10), 3 states have return successors, (10), 5 states have call predecessors, (10), 5 states have call successors, (10) [2022-01-10 06:38:46,694 INFO L276 IsEmpty]: Start isEmpty. Operand 52 states and 95 transitions. [2022-01-10 06:38:46,695 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 50 [2022-01-10 06:38:46,695 INFO L506 BasicCegarLoop]: Found error trace [2022-01-10 06:38:46,695 INFO L514 BasicCegarLoop]: trace histogram [4, 4, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-01-10 06:38:46,702 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 06:38:46,902 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 06:38:46,902 INFO L402 AbstractCegarLoop]: === Iteration 10 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-01-10 06:38:46,903 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-01-10 06:38:46,903 INFO L85 PathProgramCache]: Analyzing trace with hash 533549857, now seen corresponding path program 2 times [2022-01-10 06:38:46,903 INFO L121 FreeRefinementEngine]: Executing refinement strategy WOLF [2022-01-10 06:38:46,903 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleMathsat [516573798] [2022-01-10 06:38:46,903 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-01-10 06:38:46,903 INFO L168 SolverBuilder]: Constructing external solver with command: mathsat -unsat_core_generation=3 [2022-01-10 06:38:46,904 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat [2022-01-10 06:38:46,905 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 06:38:46,910 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 06:38:46,935 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-01-10 06:38:46,935 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-01-10 06:38:46,937 INFO L263 TraceCheckSpWp]: Trace formula consists of 80 conjuncts, 6 conjunts are in the unsatisfiable core [2022-01-10 06:38:46,938 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-01-10 06:38:47,034 INFO L134 CoverageAnalysis]: Checked inductivity of 45 backedges. 17 proven. 5 refuted. 0 times theorem prover too weak. 23 trivial. 0 not checked. [2022-01-10 06:38:47,035 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-01-10 06:38:47,228 INFO L134 CoverageAnalysis]: Checked inductivity of 45 backedges. 17 proven. 5 refuted. 0 times theorem prover too weak. 23 trivial. 0 not checked. [2022-01-10 06:38:47,228 INFO L139 FreeRefinementEngine]: Strategy WOLF found an infeasible trace [2022-01-10 06:38:47,228 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleMathsat [516573798] [2022-01-10 06:38:47,228 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleMathsat [516573798] provided 0 perfect and 2 imperfect interpolant sequences [2022-01-10 06:38:47,229 INFO L186 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-01-10 06:38:47,229 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7] total 10 [2022-01-10 06:38:47,229 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [961707801] [2022-01-10 06:38:47,229 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-01-10 06:38:47,229 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2022-01-10 06:38:47,229 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy WOLF [2022-01-10 06:38:47,230 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2022-01-10 06:38:47,230 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=22, Invalid=68, Unknown=0, NotChecked=0, Total=90 [2022-01-10 06:38:47,230 INFO L87 Difference]: Start difference. First operand 52 states and 95 transitions. Second operand has 10 states, 8 states have (on average 4.25) internal successors, (34), 10 states have internal predecessors, (34), 5 states have call successors, (10), 1 states have call predecessors, (10), 3 states have return successors, (10), 5 states have call predecessors, (10), 5 states have call successors, (10) [2022-01-10 06:38:47,309 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-01-10 06:38:47,309 INFO L93 Difference]: Finished difference Result 68 states and 122 transitions. [2022-01-10 06:38:47,309 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2022-01-10 06:38:47,310 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 8 states have (on average 4.25) internal successors, (34), 10 states have internal predecessors, (34), 5 states have call successors, (10), 1 states have call predecessors, (10), 3 states have return successors, (10), 5 states have call predecessors, (10), 5 states have call successors, (10) Word has length 49 [2022-01-10 06:38:47,310 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-01-10 06:38:47,311 INFO L225 Difference]: With dead ends: 68 [2022-01-10 06:38:47,311 INFO L226 Difference]: Without dead ends: 64 [2022-01-10 06:38:47,311 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 98 GetRequests, 88 SyntacticMatches, 0 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=32, Invalid=100, Unknown=0, NotChecked=0, Total=132 [2022-01-10 06:38:47,312 INFO L933 BasicCegarLoop]: 19 mSDtfsCounter, 20 mSDsluCounter, 78 mSDsCounter, 0 mSdLazyCounter, 107 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 24 SdHoareTripleChecker+Valid, 97 SdHoareTripleChecker+Invalid, 110 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 107 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-01-10 06:38:47,312 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [24 Valid, 97 Invalid, 110 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 107 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-01-10 06:38:47,313 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 64 states. [2022-01-10 06:38:47,318 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 64 to 52. [2022-01-10 06:38:47,319 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 52 states, 29 states have (on average 1.1379310344827587) internal successors, (33), 33 states have internal predecessors, (33), 11 states have call successors, (11), 2 states have call predecessors, (11), 11 states have return successors, (51), 16 states have call predecessors, (51), 11 states have call successors, (51) [2022-01-10 06:38:47,320 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 52 states to 52 states and 95 transitions. [2022-01-10 06:38:47,320 INFO L78 Accepts]: Start accepts. Automaton has 52 states and 95 transitions. Word has length 49 [2022-01-10 06:38:47,320 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-01-10 06:38:47,320 INFO L470 AbstractCegarLoop]: Abstraction has 52 states and 95 transitions. [2022-01-10 06:38:47,320 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 8 states have (on average 4.25) internal successors, (34), 10 states have internal predecessors, (34), 5 states have call successors, (10), 1 states have call predecessors, (10), 3 states have return successors, (10), 5 states have call predecessors, (10), 5 states have call successors, (10) [2022-01-10 06:38:47,321 INFO L276 IsEmpty]: Start isEmpty. Operand 52 states and 95 transitions. [2022-01-10 06:38:47,321 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 62 [2022-01-10 06:38:47,321 INFO L506 BasicCegarLoop]: Found error trace [2022-01-10 06:38:47,322 INFO L514 BasicCegarLoop]: trace histogram [5, 5, 4, 4, 4, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-01-10 06:38:47,331 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 06:38:47,528 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 06:38:47,528 INFO L402 AbstractCegarLoop]: === Iteration 11 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-01-10 06:38:47,529 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-01-10 06:38:47,529 INFO L85 PathProgramCache]: Analyzing trace with hash -175386786, now seen corresponding path program 1 times [2022-01-10 06:38:47,529 INFO L121 FreeRefinementEngine]: Executing refinement strategy WOLF [2022-01-10 06:38:47,529 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleMathsat [1673191836] [2022-01-10 06:38:47,529 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-01-10 06:38:47,529 INFO L168 SolverBuilder]: Constructing external solver with command: mathsat -unsat_core_generation=3 [2022-01-10 06:38:47,529 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat [2022-01-10 06:38:47,530 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 06:38:47,531 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 06:38:47,561 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2022-01-10 06:38:47,561 INFO L352 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2022-01-10 06:38:47,582 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2022-01-10 06:38:47,604 INFO L133 FreeRefinementEngine]: Strategy WOLF found a feasible trace [2022-01-10 06:38:47,604 INFO L628 BasicCegarLoop]: Counterexample is feasible [2022-01-10 06:38:47,605 INFO L764 garLoopResultBuilder]: Registering result UNSAFE for location ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION (0 of 1 remaining) [2022-01-10 06:38:47,641 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 06:38:47,806 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 06:38:47,809 INFO L732 BasicCegarLoop]: Path program histogram: [2, 2, 1, 1, 1, 1, 1, 1, 1] [2022-01-10 06:38:47,811 INFO L179 ceAbstractionStarter]: Computing trace abstraction results [2022-01-10 06:38:47,833 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 10.01 06:38:47 BoogieIcfgContainer [2022-01-10 06:38:47,834 INFO L132 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2022-01-10 06:38:47,834 INFO L158 Benchmark]: Toolchain (without parser) took 8447.29ms. Allocated memory was 183.5MB in the beginning and 238.0MB in the end (delta: 54.5MB). Free memory was 132.8MB in the beginning and 195.7MB in the end (delta: -63.0MB). There was no memory consumed. Max. memory is 8.0GB. [2022-01-10 06:38:47,834 INFO L158 Benchmark]: CDTParser took 0.12ms. Allocated memory is still 183.5MB. Free memory is still 149.1MB. There was no memory consumed. Max. memory is 8.0GB. [2022-01-10 06:38:47,834 INFO L158 Benchmark]: CACSL2BoogieTranslator took 203.29ms. Allocated memory is still 183.5MB. Free memory was 132.5MB in the beginning and 159.6MB in the end (delta: -27.2MB). Peak memory consumption was 11.5MB. Max. memory is 8.0GB. [2022-01-10 06:38:47,834 INFO L158 Benchmark]: Boogie Procedure Inliner took 20.20ms. Allocated memory is still 183.5MB. Free memory was 159.6MB in the beginning and 158.6MB in the end (delta: 1.0MB). Peak memory consumption was 1.0MB. Max. memory is 8.0GB. [2022-01-10 06:38:47,835 INFO L158 Benchmark]: Boogie Preprocessor took 27.54ms. Allocated memory is still 183.5MB. Free memory was 158.6MB in the beginning and 157.4MB in the end (delta: 1.2MB). Peak memory consumption was 1.0MB. Max. memory is 8.0GB. [2022-01-10 06:38:47,835 INFO L158 Benchmark]: RCFGBuilder took 250.15ms. Allocated memory is still 183.5MB. Free memory was 157.0MB in the beginning and 148.1MB in the end (delta: 8.9MB). Peak memory consumption was 9.4MB. Max. memory is 8.0GB. [2022-01-10 06:38:47,835 INFO L158 Benchmark]: TraceAbstraction took 7941.32ms. Allocated memory was 183.5MB in the beginning and 238.0MB in the end (delta: 54.5MB). Free memory was 147.6MB in the beginning and 195.7MB in the end (delta: -48.1MB). Peak memory consumption was 7.4MB. Max. memory is 8.0GB. [2022-01-10 06:38:47,836 INFO L339 ainManager$Toolchain]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * CDTParser took 0.12ms. Allocated memory is still 183.5MB. Free memory is still 149.1MB. There was no memory consumed. Max. memory is 8.0GB. * CACSL2BoogieTranslator took 203.29ms. Allocated memory is still 183.5MB. Free memory was 132.5MB in the beginning and 159.6MB in the end (delta: -27.2MB). Peak memory consumption was 11.5MB. Max. memory is 8.0GB. * Boogie Procedure Inliner took 20.20ms. Allocated memory is still 183.5MB. Free memory was 159.6MB in the beginning and 158.6MB in the end (delta: 1.0MB). Peak memory consumption was 1.0MB. Max. memory is 8.0GB. * Boogie Preprocessor took 27.54ms. Allocated memory is still 183.5MB. Free memory was 158.6MB in the beginning and 157.4MB in the end (delta: 1.2MB). Peak memory consumption was 1.0MB. Max. memory is 8.0GB. * RCFGBuilder took 250.15ms. Allocated memory is still 183.5MB. Free memory was 157.0MB in the beginning and 148.1MB in the end (delta: 8.9MB). Peak memory consumption was 9.4MB. Max. memory is 8.0GB. * TraceAbstraction took 7941.32ms. Allocated memory was 183.5MB in the beginning and 238.0MB in the end (delta: 54.5MB). Free memory was 147.6MB in the beginning and 195.7MB in the end (delta: -48.1MB). Peak memory consumption was 7.4MB. Max. memory is 8.0GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - StatisticsResult: ErrorAutomatonStatistics NumberErrorTraces: 0, NumberStatementsAllTraces: 0, NumberRelevantStatements: 0, 0.0s ErrorAutomatonConstructionTimeTotal, 0.0s FaulLocalizationTime, NumberStatementsFirstTrace: -1, TraceLengthAvg: 0, 0.0s ErrorAutomatonConstructionTimeAvg, 0.0s ErrorAutomatonDifferenceTimeAvg, 0.0s ErrorAutomatonDifferenceTimeTotal, NumberOfNoEnhancement: 0, NumberOfFiniteEnhancement: 0, NumberOfInfiniteEnhancement: 0 - CounterExampleResult [Line: 41]: a call to reach_error is reachable a call to reach_error is reachable We found a FailurePath: [L38] int x = 4; VAL [x=4] [L39] CALL, EXPR fibo1(x) VAL [\old(n)=4] [L10] COND FALSE !(n < 1) VAL [\old(n)=4, n=4] [L12] COND FALSE !(n == 1) VAL [\old(n)=4, n=4] [L15] CALL, EXPR fibo2(n-1) VAL [\old(n)=3] [L20] COND FALSE !(n < 1) VAL [\old(n)=3, n=3] [L22] COND FALSE !(n == 1) VAL [\old(n)=3, n=3] [L25] CALL, EXPR fibo1(n-1) VAL [\old(n)=2] [L10] COND FALSE !(n < 1) VAL [\old(n)=2, n=2] [L12] COND FALSE !(n == 1) VAL [\old(n)=2, n=2] [L15] CALL, EXPR fibo2(n-1) VAL [\old(n)=1] [L20] COND FALSE !(n < 1) VAL [\old(n)=1, n=1] [L22] COND TRUE n == 1 [L23] return 1; VAL [\old(n)=1, \result=1, n=1] [L15] RET, EXPR fibo2(n-1) VAL [\old(n)=2, fibo2(n-1)=1, n=2] [L15] CALL, EXPR fibo2(n-2) VAL [\old(n)=0] [L20] COND TRUE n < 1 [L21] return 0; VAL [\old(n)=0, \result=0, n=0] [L15] RET, EXPR fibo2(n-2) VAL [\old(n)=2, fibo2(n-1)=1, fibo2(n-2)=0, n=2] [L15] return fibo2(n-1) + fibo2(n-2); [L25] RET, EXPR fibo1(n-1) VAL [\old(n)=3, fibo1(n-1)=1, n=3] [L25] CALL, EXPR fibo1(n-2) VAL [\old(n)=1] [L10] COND FALSE !(n < 1) VAL [\old(n)=1, n=1] [L12] COND TRUE n == 1 [L13] return 1; VAL [\old(n)=1, \result=1, n=1] [L25] RET, EXPR fibo1(n-2) VAL [\old(n)=3, fibo1(n-1)=1, fibo1(n-2)=1, n=3] [L25] return fibo1(n-1) + fibo1(n-2); [L15] RET, EXPR fibo2(n-1) VAL [\old(n)=4, fibo2(n-1)=2, n=4] [L15] CALL, EXPR fibo2(n-2) VAL [\old(n)=2] [L20] COND FALSE !(n < 1) VAL [\old(n)=2, n=2] [L22] COND FALSE !(n == 1) VAL [\old(n)=2, n=2] [L25] CALL, EXPR fibo1(n-1) VAL [\old(n)=1] [L10] COND FALSE !(n < 1) VAL [\old(n)=1, n=1] [L12] COND TRUE n == 1 [L13] return 1; VAL [\old(n)=1, \result=1, n=1] [L25] RET, EXPR fibo1(n-1) VAL [\old(n)=2, fibo1(n-1)=1, n=2] [L25] CALL, EXPR fibo1(n-2) VAL [\old(n)=0] [L10] COND TRUE n < 1 [L11] return 0; VAL [\old(n)=0, \result=0, n=0] [L25] RET, EXPR fibo1(n-2) VAL [\old(n)=2, fibo1(n-1)=1, fibo1(n-2)=0, n=2] [L25] return fibo1(n-1) + fibo1(n-2); [L15] RET, EXPR fibo2(n-2) VAL [\old(n)=4, fibo2(n-1)=2, fibo2(n-2)=1, n=4] [L15] return fibo2(n-1) + fibo2(n-2); [L39] RET, EXPR fibo1(x) VAL [fibo1(x)=3, x=4] [L39] int result = fibo1(x); [L40] COND TRUE result == 3 VAL [result=3, x=4] [L41] reach_error() VAL [result=3, x=4] - StatisticsResult: Ultimate Automizer benchmark data CFG has 3 procedures, 27 locations, 1 error locations. Started 1 CEGAR loops. OverallTime: 7.9s, OverallIterations: 11, TraceHistogramMax: 5, PathProgramHistogramMax: 2, EmptinessCheckTime: 0.0s, AutomataDifference: 1.6s, DeadEndRemovalTime: 0.0s, HoareAnnotationTime: 0.0s, InitialAbstractionConstructionTime: 0.0s, PartialOrderReductionTime: 0.0s, HoareTripleCheckerStatistics: 0 mSolverCounterUnknown, 250 SdHoareTripleChecker+Valid, 1.1s IncrementalHoareTripleChecker+Time, 0 mSdLazyCounter, 195 mSDsluCounter, 1128 SdHoareTripleChecker+Invalid, 0.9s Time, 0 mProtectedAction, 0 SdHoareTripleChecker+Unchecked, 0 IncrementalHoareTripleChecker+Unchecked, 919 mSDsCounter, 82 IncrementalHoareTripleChecker+Valid, 0 mProtectedPredicate, 1220 IncrementalHoareTripleChecker+Invalid, 1302 SdHoareTripleChecker+Unknown, 0 mSolverCounterNotChecked, 82 mSolverCounterUnsat, 209 mSDtfsCounter, 1220 mSolverCounterSat, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Unknown, PredicateUnifierStatistics: 0 DeclaredPredicates, 648 GetRequests, 544 SyntacticMatches, 0 SemanticMatches, 104 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 63 ImplicationChecksByTransitivity, 0.9s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=52occurred in iteration=8, InterpolantAutomatonStates: 72, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 0.0s DumpTime, AutomataMinimizationStatistics: 0.1s AutomataMinimizationTime, 10 MinimizatonAttempts, 79 StatesRemovedByMinimization, 8 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TRACE_CHECK: 0.1s SsaConstructionTime, 0.1s SatisfiabilityAnalysisTime, 3.4s InterpolantComputationTime, 386 NumberOfCodeBlocks, 386 NumberOfCodeBlocksAsserted, 13 NumberOfCheckSat, 611 ConstructedInterpolants, 0 QuantifiedInterpolants, 1694 SizeOfPredicates, 29 NumberOfNonLiveVariables, 575 ConjunctsInSsa, 66 ConjunctsInUnsatCore, 18 InterpolantComputations, 2 PerfectInterpolantSequences, 282/420 InterpolantCoveringCapability, INVARIANT_SYNTHESIS: No data available, INTERPOLANT_CONSOLIDATION: No data available, ABSTRACT_INTERPRETATION: No data available, PDR: No data available, ACCELERATED_INTERPOLATION: No data available, SIFA: No data available, ReuseStatistics: No data available RESULT: Ultimate proved your program to be incorrect! [2022-01-10 06:38:47,863 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Forceful destruction successful, exit code 0 Received shutdown request...