./Ultimate.py --spec ../sv-benchmarks/c/properties/unreach-call.prp --file ../sv-benchmarks/c/recursive-simple/fibo_2calls_4-2.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version 798a7b37 Calling Ultimate with: /root/.sdkman/candidates/java/21.0.5-tem/bin/java -Dosgi.configuration.area=/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/config -Xmx15G -Xms4m -jar /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/org.eclipse.equinox.launcher_1.6.800.v20240513-1750.jar -data @noDefault -ultimatedata /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data -tc /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/AutomizerReach.xml -i ../sv-benchmarks/c/recursive-simple/fibo_2calls_4-2.c -s /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf --cacsl2boogietranslator.entry.function main --witnessprinter.witness.directory /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux --witnessprinter.witness.filename witness --witnessprinter.write.witness.besides.input.file false --witnessprinter.graph.data.specification CHECK( init(main()), LTL(G ! call(reach_error())) ) --witnessprinter.graph.data.producer Automizer --witnessprinter.graph.data.architecture 32bit --witnessprinter.graph.data.programhash 22d9a6832a4080412e38f5d573b63985f3b10b3c2009b6559595c7c0bbda414f --- Real Ultimate output --- This is Ultimate 0.3.0-?-798a7b3-m [2025-03-03 14:34:31,125 INFO L188 SettingsManager]: Resetting all preferences to default values... [2025-03-03 14:34:31,176 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf [2025-03-03 14:34:31,181 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2025-03-03 14:34:31,181 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2025-03-03 14:34:31,203 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2025-03-03 14:34:31,206 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2025-03-03 14:34:31,206 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2025-03-03 14:34:31,206 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2025-03-03 14:34:31,206 INFO L153 SettingsManager]: * Use memory slicer=true [2025-03-03 14:34:31,206 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2025-03-03 14:34:31,207 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2025-03-03 14:34:31,207 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2025-03-03 14:34:31,207 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2025-03-03 14:34:31,207 INFO L153 SettingsManager]: * Use SBE=true [2025-03-03 14:34:31,207 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2025-03-03 14:34:31,208 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2025-03-03 14:34:31,208 INFO L153 SettingsManager]: * sizeof long=4 [2025-03-03 14:34:31,209 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2025-03-03 14:34:31,209 INFO L153 SettingsManager]: * sizeof POINTER=4 [2025-03-03 14:34:31,209 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2025-03-03 14:34:31,209 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2025-03-03 14:34:31,209 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2025-03-03 14:34:31,209 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2025-03-03 14:34:31,209 INFO L153 SettingsManager]: * sizeof long double=12 [2025-03-03 14:34:31,209 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2025-03-03 14:34:31,209 INFO L153 SettingsManager]: * Behaviour of calls to undefined functions=OVERAPPROXIMATE_BEHAVIOUR [2025-03-03 14:34:31,209 INFO L153 SettingsManager]: * Use constant arrays=true [2025-03-03 14:34:31,209 INFO L151 SettingsManager]: Preferences of IcfgBuilder differ from their defaults: [2025-03-03 14:34:31,209 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2025-03-03 14:34:31,210 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2025-03-03 14:34:31,210 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2025-03-03 14:34:31,210 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2025-03-03 14:34:31,210 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2025-03-03 14:34:31,210 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2025-03-03 14:34:31,210 INFO L153 SettingsManager]: * Compute procedure contracts=false [2025-03-03 14:34:31,210 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2025-03-03 14:34:31,210 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2025-03-03 14:34:31,210 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2025-03-03 14:34:31,210 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2025-03-03 14:34:31,210 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2025-03-03 14:34:31,210 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2025-03-03 14:34:31,210 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2025-03-03 14:34:31,210 INFO L153 SettingsManager]: * Looper check in Petri net analysis=SEMANTIC Applying setting for plugin de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator: Entry function -> main Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Witness directory -> /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Witness filename -> witness Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Write witness besides input file -> false Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data specification -> CHECK( init(main()), LTL(G ! call(reach_error())) ) Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data producer -> Automizer Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data architecture -> 32bit Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data programhash -> 22d9a6832a4080412e38f5d573b63985f3b10b3c2009b6559595c7c0bbda414f [2025-03-03 14:34:31,406 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2025-03-03 14:34:31,413 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2025-03-03 14:34:31,416 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2025-03-03 14:34:31,416 INFO L270 PluginConnector]: Initializing CDTParser... [2025-03-03 14:34:31,417 INFO L274 PluginConnector]: CDTParser initialized [2025-03-03 14:34:31,418 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/recursive-simple/fibo_2calls_4-2.c [2025-03-03 14:34:32,577 INFO L533 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/b5c680b98/0850e9d6a25b4d90a0271ce0fd4da5f4/FLAG2f971e974 [2025-03-03 14:34:32,802 INFO L384 CDTParser]: Found 1 translation units. [2025-03-03 14:34:32,804 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/recursive-simple/fibo_2calls_4-2.c [2025-03-03 14:34:32,809 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/b5c680b98/0850e9d6a25b4d90a0271ce0fd4da5f4/FLAG2f971e974 [2025-03-03 14:34:33,164 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/b5c680b98/0850e9d6a25b4d90a0271ce0fd4da5f4 [2025-03-03 14:34:33,166 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2025-03-03 14:34:33,166 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2025-03-03 14:34:33,167 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2025-03-03 14:34:33,167 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2025-03-03 14:34:33,170 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2025-03-03 14:34:33,170 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 03.03 02:34:33" (1/1) ... [2025-03-03 14:34:33,171 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@4388bb49 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 02:34:33, skipping insertion in model container [2025-03-03 14:34:33,171 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 03.03 02:34:33" (1/1) ... [2025-03-03 14:34:33,183 INFO L175 MainTranslator]: Built tables and reachable declarations [2025-03-03 14:34:33,276 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/recursive-simple/fibo_2calls_4-2.c[946,959] [2025-03-03 14:34:33,280 INFO L210 PostProcessor]: Analyzing one entry point: main [2025-03-03 14:34:33,285 INFO L200 MainTranslator]: Completed pre-run [2025-03-03 14:34:33,297 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/recursive-simple/fibo_2calls_4-2.c[946,959] [2025-03-03 14:34:33,297 INFO L210 PostProcessor]: Analyzing one entry point: main [2025-03-03 14:34:33,307 INFO L204 MainTranslator]: Completed translation [2025-03-03 14:34:33,308 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 02:34:33 WrapperNode [2025-03-03 14:34:33,309 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2025-03-03 14:34:33,310 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2025-03-03 14:34:33,310 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2025-03-03 14:34:33,310 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2025-03-03 14:34:33,314 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 02:34:33" (1/1) ... [2025-03-03 14:34:33,318 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 02:34:33" (1/1) ... [2025-03-03 14:34:33,327 INFO L138 Inliner]: procedures = 14, calls = 12, calls flagged for inlining = 2, calls inlined = 2, statements flattened = 20 [2025-03-03 14:34:33,328 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2025-03-03 14:34:33,328 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2025-03-03 14:34:33,329 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2025-03-03 14:34:33,329 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2025-03-03 14:34:33,333 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 02:34:33" (1/1) ... [2025-03-03 14:34:33,333 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 02:34:33" (1/1) ... [2025-03-03 14:34:33,334 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 02:34:33" (1/1) ... [2025-03-03 14:34:33,344 INFO L175 MemorySlicer]: Split 2 memory accesses to 1 slices as follows [2]. 100 percent of accesses are in the largest equivalence class. The 2 initializations are split as follows [2]. The 0 writes are split as follows [0]. [2025-03-03 14:34:33,345 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 02:34:33" (1/1) ... [2025-03-03 14:34:33,345 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 02:34:33" (1/1) ... [2025-03-03 14:34:33,347 INFO L184 PluginConnector]: Executing the observer ReplaceArrayAssignments from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 02:34:33" (1/1) ... [2025-03-03 14:34:33,350 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 02:34:33" (1/1) ... [2025-03-03 14:34:33,350 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 02:34:33" (1/1) ... [2025-03-03 14:34:33,350 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 02:34:33" (1/1) ... [2025-03-03 14:34:33,351 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2025-03-03 14:34:33,352 INFO L112 PluginConnector]: ------------------------IcfgBuilder---------------------------- [2025-03-03 14:34:33,352 INFO L270 PluginConnector]: Initializing IcfgBuilder... [2025-03-03 14:34:33,352 INFO L274 PluginConnector]: IcfgBuilder initialized [2025-03-03 14:34:33,354 INFO L184 PluginConnector]: Executing the observer IcfgBuilderObserver from plugin IcfgBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 02:34:33" (1/1) ... [2025-03-03 14:34:33,358 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2025-03-03 14:34:33,368 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 14:34:33,380 INFO L229 MonitoredProcess]: Starting monitored process 1 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (exit command is (exit), workingDir is null) [2025-03-03 14:34:33,383 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (1)] Waiting until timeout for monitored process [2025-03-03 14:34:33,400 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2025-03-03 14:34:33,400 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2025-03-03 14:34:33,400 INFO L130 BoogieDeclarations]: Found specification of procedure fibo2 [2025-03-03 14:34:33,400 INFO L138 BoogieDeclarations]: Found implementation of procedure fibo2 [2025-03-03 14:34:33,401 INFO L130 BoogieDeclarations]: Found specification of procedure fibo1 [2025-03-03 14:34:33,401 INFO L138 BoogieDeclarations]: Found implementation of procedure fibo1 [2025-03-03 14:34:33,401 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2025-03-03 14:34:33,401 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2025-03-03 14:34:33,439 INFO L256 CfgBuilder]: Building ICFG [2025-03-03 14:34:33,440 INFO L286 CfgBuilder]: Building CFG for each procedure with an implementation [2025-03-03 14:34:33,506 INFO L1325 $ProcedureCfgBuilder]: dead code at ProgramPoint L25: havoc #t~ret6;havoc #t~ret7; [2025-03-03 14:34:33,525 INFO L1325 $ProcedureCfgBuilder]: dead code at ProgramPoint L15: havoc #t~ret4;havoc #t~ret5; [2025-03-03 14:34:33,534 INFO L? ?]: Removed 8 outVars from TransFormulas that were not future-live. [2025-03-03 14:34:33,534 INFO L307 CfgBuilder]: Performing block encoding [2025-03-03 14:34:33,541 INFO L331 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2025-03-03 14:34:33,542 INFO L336 CfgBuilder]: Removed 0 assume(true) statements. [2025-03-03 14:34:33,542 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 03.03 02:34:33 BoogieIcfgContainer [2025-03-03 14:34:33,542 INFO L131 PluginConnector]: ------------------------ END IcfgBuilder---------------------------- [2025-03-03 14:34:33,543 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2025-03-03 14:34:33,543 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2025-03-03 14:34:33,547 INFO L274 PluginConnector]: TraceAbstraction initialized [2025-03-03 14:34:33,547 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 03.03 02:34:33" (1/3) ... [2025-03-03 14:34:33,547 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@6b28bac4 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 03.03 02:34:33, skipping insertion in model container [2025-03-03 14:34:33,548 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 02:34:33" (2/3) ... [2025-03-03 14:34:33,548 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@6b28bac4 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 03.03 02:34:33, skipping insertion in model container [2025-03-03 14:34:33,548 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 03.03 02:34:33" (3/3) ... [2025-03-03 14:34:33,549 INFO L128 eAbstractionObserver]: Analyzing ICFG fibo_2calls_4-2.c [2025-03-03 14:34:33,558 INFO L216 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2025-03-03 14:34:33,560 INFO L151 ceAbstractionStarter]: Applying trace abstraction to ICFG fibo_2calls_4-2.c that has 3 procedures, 29 locations, 1 initial locations, 0 loop locations, and 1 error locations. [2025-03-03 14:34:33,592 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2025-03-03 14:34:33,599 INFO L333 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, mAutomataTypeConcurrency=PETRI_NET, mHoareTripleChecks=INCREMENTAL, mHoareAnnotationPositions=LoopHeads, 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, mPorIndependenceSettings=[Lde.uni_freiburg.informatik.ultimate.lib.tracecheckerutils.partialorder.independence.IndependenceSettings;@5cef0afd, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2025-03-03 14:34:33,599 INFO L334 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2025-03-03 14:34:33,604 INFO L276 IsEmpty]: Start isEmpty. Operand has 29 states, 20 states have (on average 1.3) internal successors, (26), 21 states have internal predecessors, (26), 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) [2025-03-03 14:34:33,609 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 11 [2025-03-03 14:34:33,610 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 14:34:33,610 INFO L218 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-03 14:34:33,610 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 14:34:33,613 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 14:34:33,614 INFO L85 PathProgramCache]: Analyzing trace with hash -402987893, now seen corresponding path program 1 times [2025-03-03 14:34:33,618 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 14:34:33,618 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2097594863] [2025-03-03 14:34:33,618 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 14:34:33,619 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 14:34:33,660 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 10 statements into 1 equivalence classes. [2025-03-03 14:34:33,677 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 10 of 10 statements. [2025-03-03 14:34:33,677 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 14:34:33,677 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 14:34:33,776 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-03 14:34:33,777 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-03 14:34:33,778 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2097594863] [2025-03-03 14:34:33,778 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2097594863] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-03 14:34:33,778 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-03 14:34:33,779 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2025-03-03 14:34:33,780 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [585497040] [2025-03-03 14:34:33,780 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-03 14:34:33,783 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2025-03-03 14:34:33,783 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-03 14:34:33,797 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2025-03-03 14:34:33,798 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2025-03-03 14:34:33,799 INFO L87 Difference]: Start difference. First operand has 29 states, 20 states have (on average 1.3) internal successors, (26), 21 states have internal predecessors, (26), 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, 5 states have (on average 1.6) internal successors, (8), 4 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) [2025-03-03 14:34:33,835 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 14:34:33,836 INFO L93 Difference]: Finished difference Result 39 states and 48 transitions. [2025-03-03 14:34:33,836 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2025-03-03 14:34:33,837 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 1.6) internal successors, (8), 4 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 [2025-03-03 14:34:33,837 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 14:34:33,841 INFO L225 Difference]: With dead ends: 39 [2025-03-03 14:34:33,841 INFO L226 Difference]: Without dead ends: 27 [2025-03-03 14:34:33,843 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 5 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2025-03-03 14:34:33,845 INFO L435 NwaCegarLoop]: 33 mSDtfsCounter, 0 mSDsluCounter, 91 mSDsCounter, 0 mSdLazyCounter, 15 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 124 SdHoareTripleChecker+Invalid, 15 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 15 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-03-03 14:34:33,845 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 124 Invalid, 15 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 15 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-03-03 14:34:33,856 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 27 states. [2025-03-03 14:34:33,865 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 27 to 27. [2025-03-03 14:34:33,866 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 27 states, 18 states have (on average 1.2222222222222223) internal successors, (22), 19 states have internal predecessors, (22), 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) [2025-03-03 14:34:33,868 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 27 states to 27 states and 34 transitions. [2025-03-03 14:34:33,869 INFO L78 Accepts]: Start accepts. Automaton has 27 states and 34 transitions. Word has length 10 [2025-03-03 14:34:33,869 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 14:34:33,869 INFO L471 AbstractCegarLoop]: Abstraction has 27 states and 34 transitions. [2025-03-03 14:34:33,869 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 1.6) internal successors, (8), 4 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) [2025-03-03 14:34:33,869 INFO L276 IsEmpty]: Start isEmpty. Operand 27 states and 34 transitions. [2025-03-03 14:34:33,870 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 12 [2025-03-03 14:34:33,870 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 14:34:33,870 INFO L218 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-03 14:34:33,870 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2025-03-03 14:34:33,870 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 14:34:33,871 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 14:34:33,871 INFO L85 PathProgramCache]: Analyzing trace with hash -1356301235, now seen corresponding path program 1 times [2025-03-03 14:34:33,871 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 14:34:33,871 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1464542571] [2025-03-03 14:34:33,871 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 14:34:33,871 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 14:34:33,875 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 11 statements into 1 equivalence classes. [2025-03-03 14:34:33,880 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 11 of 11 statements. [2025-03-03 14:34:33,880 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 14:34:33,880 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 14:34:33,950 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-03 14:34:33,951 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-03 14:34:33,952 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1464542571] [2025-03-03 14:34:33,952 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1464542571] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-03 14:34:33,952 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-03 14:34:33,952 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2025-03-03 14:34:33,952 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [689968123] [2025-03-03 14:34:33,952 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-03 14:34:33,953 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2025-03-03 14:34:33,953 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-03 14:34:33,954 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2025-03-03 14:34:33,954 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2025-03-03 14:34:33,954 INFO L87 Difference]: Start difference. First operand 27 states and 34 transitions. Second operand has 5 states, 5 states have (on average 1.8) internal successors, (9), 4 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) [2025-03-03 14:34:33,970 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 14:34:33,971 INFO L93 Difference]: Finished difference Result 33 states and 41 transitions. [2025-03-03 14:34:33,971 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2025-03-03 14:34:33,971 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 1.8) internal successors, (9), 4 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 [2025-03-03 14:34:33,971 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 14:34:33,972 INFO L225 Difference]: With dead ends: 33 [2025-03-03 14:34:33,972 INFO L226 Difference]: Without dead ends: 29 [2025-03-03 14:34:33,972 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 5 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2025-03-03 14:34:33,973 INFO L435 NwaCegarLoop]: 33 mSDtfsCounter, 0 mSDsluCounter, 92 mSDsCounter, 0 mSdLazyCounter, 9 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 125 SdHoareTripleChecker+Invalid, 9 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 9 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-03-03 14:34:33,973 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 125 Invalid, 9 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 9 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-03-03 14:34:33,973 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 29 states. [2025-03-03 14:34:33,976 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 29 to 27. [2025-03-03 14:34:33,976 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 27 states, 18 states have (on average 1.2222222222222223) internal successors, (22), 19 states have internal predecessors, (22), 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) [2025-03-03 14:34:33,976 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 27 states to 27 states and 34 transitions. [2025-03-03 14:34:33,977 INFO L78 Accepts]: Start accepts. Automaton has 27 states and 34 transitions. Word has length 11 [2025-03-03 14:34:33,977 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 14:34:33,977 INFO L471 AbstractCegarLoop]: Abstraction has 27 states and 34 transitions. [2025-03-03 14:34:33,977 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 1.8) internal successors, (9), 4 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) [2025-03-03 14:34:33,977 INFO L276 IsEmpty]: Start isEmpty. Operand 27 states and 34 transitions. [2025-03-03 14:34:33,978 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 24 [2025-03-03 14:34:33,978 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 14:34:33,978 INFO L218 NwaCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-03 14:34:33,978 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2025-03-03 14:34:33,978 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 14:34:33,978 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 14:34:33,978 INFO L85 PathProgramCache]: Analyzing trace with hash 1190707769, now seen corresponding path program 1 times [2025-03-03 14:34:33,978 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 14:34:33,979 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [572937702] [2025-03-03 14:34:33,979 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 14:34:33,979 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 14:34:33,985 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 23 statements into 1 equivalence classes. [2025-03-03 14:34:33,996 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 23 of 23 statements. [2025-03-03 14:34:33,996 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 14:34:33,996 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 14:34:34,068 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2025-03-03 14:34:34,068 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-03 14:34:34,068 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [572937702] [2025-03-03 14:34:34,068 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [572937702] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-03 14:34:34,068 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [549525295] [2025-03-03 14:34:34,068 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 14:34:34,068 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 14:34:34,068 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 14:34:34,071 INFO L229 MonitoredProcess]: Starting monitored process 2 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-03 14:34:34,072 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2025-03-03 14:34:34,106 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 23 statements into 1 equivalence classes. [2025-03-03 14:34:34,123 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 23 of 23 statements. [2025-03-03 14:34:34,123 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 14:34:34,123 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 14:34:34,125 INFO L256 TraceCheckSpWp]: Trace formula consists of 71 conjuncts, 6 conjuncts are in the unsatisfiable core [2025-03-03 14:34:34,130 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-03 14:34:34,205 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2025-03-03 14:34:34,206 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-03 14:34:34,412 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2025-03-03 14:34:34,413 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [549525295] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-03 14:34:34,413 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-03 14:34:34,414 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 7, 7] total 12 [2025-03-03 14:34:34,414 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [906329477] [2025-03-03 14:34:34,414 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-03 14:34:34,414 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2025-03-03 14:34:34,414 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-03 14:34:34,416 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2025-03-03 14:34:34,416 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=28, Invalid=104, Unknown=0, NotChecked=0, Total=132 [2025-03-03 14:34:34,416 INFO L87 Difference]: Start difference. First operand 27 states and 34 transitions. Second operand has 12 states, 9 states have (on average 3.3333333333333335) internal successors, (30), 12 states have internal predecessors, (30), 8 states have call successors, (8), 1 states have call predecessors, (8), 4 states have return successors, (8), 2 states have call predecessors, (8), 8 states have call successors, (8) [2025-03-03 14:34:34,518 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 14:34:34,518 INFO L93 Difference]: Finished difference Result 55 states and 75 transitions. [2025-03-03 14:34:34,518 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2025-03-03 14:34:34,519 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 9 states have (on average 3.3333333333333335) internal successors, (30), 12 states have internal predecessors, (30), 8 states have call successors, (8), 1 states have call predecessors, (8), 4 states have return successors, (8), 2 states have call predecessors, (8), 8 states have call successors, (8) Word has length 23 [2025-03-03 14:34:34,519 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 14:34:34,520 INFO L225 Difference]: With dead ends: 55 [2025-03-03 14:34:34,520 INFO L226 Difference]: Without dead ends: 31 [2025-03-03 14:34:34,521 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 53 GetRequests, 39 SyntacticMatches, 2 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 15 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=40, Invalid=142, Unknown=0, NotChecked=0, Total=182 [2025-03-03 14:34:34,522 INFO L435 NwaCegarLoop]: 21 mSDtfsCounter, 22 mSDsluCounter, 84 mSDsCounter, 0 mSdLazyCounter, 96 mSolverCounterSat, 15 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 27 SdHoareTripleChecker+Valid, 105 SdHoareTripleChecker+Invalid, 111 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 15 IncrementalHoareTripleChecker+Valid, 96 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-03 14:34:34,523 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [27 Valid, 105 Invalid, 111 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [15 Valid, 96 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-03 14:34:34,523 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 31 states. [2025-03-03 14:34:34,528 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 31 to 29. [2025-03-03 14:34:34,528 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 29 states, 19 states have (on average 1.2105263157894737) internal successors, (23), 21 states have internal predecessors, (23), 5 states have call successors, (5), 2 states have call predecessors, (5), 4 states have return successors, (8), 5 states have call predecessors, (8), 5 states have call successors, (8) [2025-03-03 14:34:34,528 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 29 states to 29 states and 36 transitions. [2025-03-03 14:34:34,530 INFO L78 Accepts]: Start accepts. Automaton has 29 states and 36 transitions. Word has length 23 [2025-03-03 14:34:34,530 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 14:34:34,530 INFO L471 AbstractCegarLoop]: Abstraction has 29 states and 36 transitions. [2025-03-03 14:34:34,530 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 9 states have (on average 3.3333333333333335) internal successors, (30), 12 states have internal predecessors, (30), 8 states have call successors, (8), 1 states have call predecessors, (8), 4 states have return successors, (8), 2 states have call predecessors, (8), 8 states have call successors, (8) [2025-03-03 14:34:34,530 INFO L276 IsEmpty]: Start isEmpty. Operand 29 states and 36 transitions. [2025-03-03 14:34:34,531 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 25 [2025-03-03 14:34:34,531 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 14:34:34,531 INFO L218 NwaCegarLoop]: trace histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-03 14:34:34,537 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Ended with exit code 0 [2025-03-03 14:34:34,731 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2,2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 14:34:34,732 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 14:34:34,732 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 14:34:34,732 INFO L85 PathProgramCache]: Analyzing trace with hash -1027112458, now seen corresponding path program 1 times [2025-03-03 14:34:34,732 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 14:34:34,732 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [74667089] [2025-03-03 14:34:34,732 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 14:34:34,733 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 14:34:34,738 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 24 statements into 1 equivalence classes. [2025-03-03 14:34:34,747 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 24 of 24 statements. [2025-03-03 14:34:34,748 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 14:34:34,748 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 14:34:34,845 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2025-03-03 14:34:34,845 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-03 14:34:34,845 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [74667089] [2025-03-03 14:34:34,845 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [74667089] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-03 14:34:34,846 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [65838284] [2025-03-03 14:34:34,846 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 14:34:34,846 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 14:34:34,846 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 14:34:34,848 INFO L229 MonitoredProcess]: Starting monitored process 3 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-03 14:34:34,848 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2025-03-03 14:34:34,871 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 24 statements into 1 equivalence classes. [2025-03-03 14:34:34,882 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 24 of 24 statements. [2025-03-03 14:34:34,882 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 14:34:34,882 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 14:34:34,882 INFO L256 TraceCheckSpWp]: Trace formula consists of 73 conjuncts, 6 conjuncts are in the unsatisfiable core [2025-03-03 14:34:34,883 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-03 14:34:34,915 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2025-03-03 14:34:34,916 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-03 14:34:35,071 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2025-03-03 14:34:35,071 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [65838284] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-03 14:34:35,071 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-03 14:34:35,071 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7, 7] total 10 [2025-03-03 14:34:35,072 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1167955384] [2025-03-03 14:34:35,072 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-03 14:34:35,072 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2025-03-03 14:34:35,072 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-03 14:34:35,072 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2025-03-03 14:34:35,072 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=22, Invalid=68, Unknown=0, NotChecked=0, Total=90 [2025-03-03 14:34:35,073 INFO L87 Difference]: Start difference. First operand 29 states and 36 transitions. Second operand has 10 states, 8 states have (on average 3.125) internal successors, (25), 10 states have internal predecessors, (25), 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) [2025-03-03 14:34:35,175 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 14:34:35,175 INFO L93 Difference]: Finished difference Result 40 states and 52 transitions. [2025-03-03 14:34:35,176 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2025-03-03 14:34:35,176 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 8 states have (on average 3.125) internal successors, (25), 10 states have internal predecessors, (25), 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 24 [2025-03-03 14:34:35,176 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 14:34:35,177 INFO L225 Difference]: With dead ends: 40 [2025-03-03 14:34:35,177 INFO L226 Difference]: Without dead ends: 36 [2025-03-03 14:34:35,177 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 54 GetRequests, 43 SyntacticMatches, 2 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 6 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=27, Invalid=83, Unknown=0, NotChecked=0, Total=110 [2025-03-03 14:34:35,178 INFO L435 NwaCegarLoop]: 20 mSDtfsCounter, 13 mSDsluCounter, 115 mSDsCounter, 0 mSdLazyCounter, 142 mSolverCounterSat, 5 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 22 SdHoareTripleChecker+Valid, 135 SdHoareTripleChecker+Invalid, 147 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 5 IncrementalHoareTripleChecker+Valid, 142 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-03 14:34:35,178 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [22 Valid, 135 Invalid, 147 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [5 Valid, 142 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-03 14:34:35,178 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 36 states. [2025-03-03 14:34:35,182 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 36 to 34. [2025-03-03 14:34:35,183 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 34 states, 22 states have (on average 1.1818181818181819) internal successors, (26), 24 states have internal predecessors, (26), 6 states have call successors, (6), 2 states have call predecessors, (6), 5 states have return successors, (13), 7 states have call predecessors, (13), 6 states have call successors, (13) [2025-03-03 14:34:35,183 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 34 states to 34 states and 45 transitions. [2025-03-03 14:34:35,183 INFO L78 Accepts]: Start accepts. Automaton has 34 states and 45 transitions. Word has length 24 [2025-03-03 14:34:35,184 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 14:34:35,184 INFO L471 AbstractCegarLoop]: Abstraction has 34 states and 45 transitions. [2025-03-03 14:34:35,184 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 8 states have (on average 3.125) internal successors, (25), 10 states have internal predecessors, (25), 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) [2025-03-03 14:34:35,184 INFO L276 IsEmpty]: Start isEmpty. Operand 34 states and 45 transitions. [2025-03-03 14:34:35,184 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 37 [2025-03-03 14:34:35,184 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 14:34:35,184 INFO L218 NwaCegarLoop]: 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, 1] [2025-03-03 14:34:35,191 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Ended with exit code 0 [2025-03-03 14:34:35,385 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 3 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable3 [2025-03-03 14:34:35,385 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 14:34:35,385 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 14:34:35,386 INFO L85 PathProgramCache]: Analyzing trace with hash 1200844378, now seen corresponding path program 1 times [2025-03-03 14:34:35,386 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 14:34:35,386 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2108675337] [2025-03-03 14:34:35,386 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 14:34:35,386 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 14:34:35,389 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 36 statements into 1 equivalence classes. [2025-03-03 14:34:35,393 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 36 of 36 statements. [2025-03-03 14:34:35,394 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 14:34:35,394 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 14:34:35,457 INFO L134 CoverageAnalysis]: Checked inductivity of 16 backedges. 5 proven. 5 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2025-03-03 14:34:35,458 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-03 14:34:35,458 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2108675337] [2025-03-03 14:34:35,458 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2108675337] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-03 14:34:35,458 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1809119055] [2025-03-03 14:34:35,458 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 14:34:35,458 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 14:34:35,458 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 14:34:35,461 INFO L229 MonitoredProcess]: Starting monitored process 4 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-03 14:34:35,463 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2025-03-03 14:34:35,488 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 36 statements into 1 equivalence classes. [2025-03-03 14:34:35,499 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 36 of 36 statements. [2025-03-03 14:34:35,499 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 14:34:35,499 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 14:34:35,500 INFO L256 TraceCheckSpWp]: Trace formula consists of 100 conjuncts, 8 conjuncts are in the unsatisfiable core [2025-03-03 14:34:35,501 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-03 14:34:35,564 INFO L134 CoverageAnalysis]: Checked inductivity of 16 backedges. 2 proven. 9 refuted. 0 times theorem prover too weak. 5 trivial. 0 not checked. [2025-03-03 14:34:35,564 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-03 14:34:35,825 INFO L134 CoverageAnalysis]: Checked inductivity of 16 backedges. 2 proven. 10 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2025-03-03 14:34:35,825 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1809119055] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-03 14:34:35,826 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-03 14:34:35,826 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 8, 9] total 14 [2025-03-03 14:34:35,826 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [780400213] [2025-03-03 14:34:35,826 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-03 14:34:35,826 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2025-03-03 14:34:35,826 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-03 14:34:35,827 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2025-03-03 14:34:35,827 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=36, Invalid=146, Unknown=0, NotChecked=0, Total=182 [2025-03-03 14:34:35,827 INFO L87 Difference]: Start difference. First operand 34 states and 45 transitions. Second operand has 14 states, 11 states have (on average 4.090909090909091) internal successors, (45), 14 states have internal predecessors, (45), 11 states have call successors, (13), 1 states have call predecessors, (13), 5 states have return successors, (13), 3 states have call predecessors, (13), 11 states have call successors, (13) [2025-03-03 14:34:35,966 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 14:34:35,966 INFO L93 Difference]: Finished difference Result 69 states and 100 transitions. [2025-03-03 14:34:35,967 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2025-03-03 14:34:35,967 INFO L78 Accepts]: Start accepts. Automaton has has 14 states, 11 states have (on average 4.090909090909091) internal successors, (45), 14 states have internal predecessors, (45), 11 states have call successors, (13), 1 states have call predecessors, (13), 5 states have return successors, (13), 3 states have call predecessors, (13), 11 states have call successors, (13) Word has length 36 [2025-03-03 14:34:35,967 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 14:34:35,968 INFO L225 Difference]: With dead ends: 69 [2025-03-03 14:34:35,968 INFO L226 Difference]: Without dead ends: 38 [2025-03-03 14:34:35,969 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 82 GetRequests, 64 SyntacticMatches, 3 SemanticMatches, 15 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 32 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=54, Invalid=218, Unknown=0, NotChecked=0, Total=272 [2025-03-03 14:34:35,969 INFO L435 NwaCegarLoop]: 20 mSDtfsCounter, 18 mSDsluCounter, 126 mSDsCounter, 0 mSdLazyCounter, 147 mSolverCounterSat, 21 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 23 SdHoareTripleChecker+Valid, 146 SdHoareTripleChecker+Invalid, 168 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 21 IncrementalHoareTripleChecker+Valid, 147 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-03 14:34:35,969 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [23 Valid, 146 Invalid, 168 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [21 Valid, 147 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-03 14:34:35,970 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 38 states. [2025-03-03 14:34:35,975 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 38 to 36. [2025-03-03 14:34:35,976 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 36 states, 23 states have (on average 1.173913043478261) internal successors, (27), 26 states have internal predecessors, (27), 6 states have call successors, (6), 2 states have call predecessors, (6), 6 states have return successors, (14), 7 states have call predecessors, (14), 6 states have call successors, (14) [2025-03-03 14:34:35,977 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 36 states to 36 states and 47 transitions. [2025-03-03 14:34:35,978 INFO L78 Accepts]: Start accepts. Automaton has 36 states and 47 transitions. Word has length 36 [2025-03-03 14:34:35,978 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 14:34:35,978 INFO L471 AbstractCegarLoop]: Abstraction has 36 states and 47 transitions. [2025-03-03 14:34:35,978 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 14 states, 11 states have (on average 4.090909090909091) internal successors, (45), 14 states have internal predecessors, (45), 11 states have call successors, (13), 1 states have call predecessors, (13), 5 states have return successors, (13), 3 states have call predecessors, (13), 11 states have call successors, (13) [2025-03-03 14:34:35,978 INFO L276 IsEmpty]: Start isEmpty. Operand 36 states and 47 transitions. [2025-03-03 14:34:35,979 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 38 [2025-03-03 14:34:35,980 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 14:34:35,980 INFO L218 NwaCegarLoop]: 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, 1, 1] [2025-03-03 14:34:35,986 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Forceful destruction successful, exit code 0 [2025-03-03 14:34:36,181 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 14:34:36,181 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 14:34:36,182 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 14:34:36,182 INFO L85 PathProgramCache]: Analyzing trace with hash -255039370, now seen corresponding path program 1 times [2025-03-03 14:34:36,182 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 14:34:36,182 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1290976519] [2025-03-03 14:34:36,182 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 14:34:36,182 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 14:34:36,185 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 37 statements into 1 equivalence classes. [2025-03-03 14:34:36,189 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 37 of 37 statements. [2025-03-03 14:34:36,189 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 14:34:36,189 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 14:34:36,287 INFO L134 CoverageAnalysis]: Checked inductivity of 17 backedges. 4 proven. 3 refuted. 0 times theorem prover too weak. 10 trivial. 0 not checked. [2025-03-03 14:34:36,287 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-03 14:34:36,287 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1290976519] [2025-03-03 14:34:36,288 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1290976519] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-03 14:34:36,288 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [477424973] [2025-03-03 14:34:36,288 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 14:34:36,288 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 14:34:36,288 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 14:34:36,290 INFO L229 MonitoredProcess]: Starting monitored process 5 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-03 14:34:36,291 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2025-03-03 14:34:36,310 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 37 statements into 1 equivalence classes. [2025-03-03 14:34:36,318 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 37 of 37 statements. [2025-03-03 14:34:36,319 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 14:34:36,319 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 14:34:36,319 INFO L256 TraceCheckSpWp]: Trace formula consists of 102 conjuncts, 8 conjuncts are in the unsatisfiable core [2025-03-03 14:34:36,320 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-03 14:34:36,397 INFO L134 CoverageAnalysis]: Checked inductivity of 17 backedges. 2 proven. 9 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2025-03-03 14:34:36,398 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-03 14:34:36,636 INFO L134 CoverageAnalysis]: Checked inductivity of 17 backedges. 2 proven. 11 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2025-03-03 14:34:36,636 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [477424973] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-03 14:34:36,636 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-03 14:34:36,636 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 8, 9] total 17 [2025-03-03 14:34:36,636 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [458959592] [2025-03-03 14:34:36,636 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-03 14:34:36,637 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 17 states [2025-03-03 14:34:36,637 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-03 14:34:36,637 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2025-03-03 14:34:36,638 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=46, Invalid=226, Unknown=0, NotChecked=0, Total=272 [2025-03-03 14:34:36,638 INFO L87 Difference]: Start difference. First operand 36 states and 47 transitions. Second operand has 17 states, 16 states have (on average 3.0625) internal successors, (49), 17 states have internal predecessors, (49), 10 states have call successors, (12), 1 states have call predecessors, (12), 7 states have return successors, (12), 6 states have call predecessors, (12), 10 states have call successors, (12) [2025-03-03 14:34:36,888 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 14:34:36,888 INFO L93 Difference]: Finished difference Result 101 states and 161 transitions. [2025-03-03 14:34:36,889 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2025-03-03 14:34:36,889 INFO L78 Accepts]: Start accepts. Automaton has has 17 states, 16 states have (on average 3.0625) internal successors, (49), 17 states have internal predecessors, (49), 10 states have call successors, (12), 1 states have call predecessors, (12), 7 states have return successors, (12), 6 states have call predecessors, (12), 10 states have call successors, (12) Word has length 37 [2025-03-03 14:34:36,889 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 14:34:36,890 INFO L225 Difference]: With dead ends: 101 [2025-03-03 14:34:36,890 INFO L226 Difference]: Without dead ends: 68 [2025-03-03 14:34:36,891 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 97 GetRequests, 69 SyntacticMatches, 4 SemanticMatches, 24 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 99 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=121, Invalid=529, Unknown=0, NotChecked=0, Total=650 [2025-03-03 14:34:36,891 INFO L435 NwaCegarLoop]: 33 mSDtfsCounter, 40 mSDsluCounter, 196 mSDsCounter, 0 mSdLazyCounter, 282 mSolverCounterSat, 50 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 43 SdHoareTripleChecker+Valid, 229 SdHoareTripleChecker+Invalid, 332 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 50 IncrementalHoareTripleChecker+Valid, 282 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2025-03-03 14:34:36,891 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [43 Valid, 229 Invalid, 332 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [50 Valid, 282 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2025-03-03 14:34:36,891 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 68 states. [2025-03-03 14:34:36,898 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 68 to 56. [2025-03-03 14:34:36,898 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 56 states, 35 states have (on average 1.1714285714285715) internal successors, (41), 39 states have internal predecessors, (41), 11 states have call successors, (11), 3 states have call predecessors, (11), 9 states have return successors, (34), 13 states have call predecessors, (34), 11 states have call successors, (34) [2025-03-03 14:34:36,899 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 56 states to 56 states and 86 transitions. [2025-03-03 14:34:36,899 INFO L78 Accepts]: Start accepts. Automaton has 56 states and 86 transitions. Word has length 37 [2025-03-03 14:34:36,899 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 14:34:36,900 INFO L471 AbstractCegarLoop]: Abstraction has 56 states and 86 transitions. [2025-03-03 14:34:36,900 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 17 states, 16 states have (on average 3.0625) internal successors, (49), 17 states have internal predecessors, (49), 10 states have call successors, (12), 1 states have call predecessors, (12), 7 states have return successors, (12), 6 states have call predecessors, (12), 10 states have call successors, (12) [2025-03-03 14:34:36,900 INFO L276 IsEmpty]: Start isEmpty. Operand 56 states and 86 transitions. [2025-03-03 14:34:36,901 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 52 [2025-03-03 14:34:36,901 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 14:34:36,901 INFO L218 NwaCegarLoop]: trace histogram [4, 4, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-03 14:34:36,907 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Forceful destruction successful, exit code 0 [2025-03-03 14:34:37,102 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 14:34:37,102 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 14:34:37,103 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 14:34:37,103 INFO L85 PathProgramCache]: Analyzing trace with hash -1862824006, now seen corresponding path program 1 times [2025-03-03 14:34:37,103 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 14:34:37,103 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1209425173] [2025-03-03 14:34:37,103 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 14:34:37,103 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 14:34:37,107 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 51 statements into 1 equivalence classes. [2025-03-03 14:34:37,115 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 51 of 51 statements. [2025-03-03 14:34:37,115 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 14:34:37,115 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 14:34:37,196 INFO L134 CoverageAnalysis]: Checked inductivity of 44 backedges. 12 proven. 12 refuted. 0 times theorem prover too weak. 20 trivial. 0 not checked. [2025-03-03 14:34:37,197 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-03 14:34:37,198 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1209425173] [2025-03-03 14:34:37,198 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1209425173] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-03 14:34:37,198 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [305062533] [2025-03-03 14:34:37,198 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 14:34:37,198 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 14:34:37,198 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 14:34:37,202 INFO L229 MonitoredProcess]: Starting monitored process 6 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-03 14:34:37,204 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2025-03-03 14:34:37,227 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 51 statements into 1 equivalence classes. [2025-03-03 14:34:37,256 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 51 of 51 statements. [2025-03-03 14:34:37,256 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 14:34:37,256 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 14:34:37,257 INFO L256 TraceCheckSpWp]: Trace formula consists of 133 conjuncts, 8 conjuncts are in the unsatisfiable core [2025-03-03 14:34:37,258 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-03 14:34:37,287 INFO L134 CoverageAnalysis]: Checked inductivity of 44 backedges. 12 proven. 12 refuted. 0 times theorem prover too weak. 20 trivial. 0 not checked. [2025-03-03 14:34:37,288 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-03 14:34:37,564 INFO L134 CoverageAnalysis]: Checked inductivity of 44 backedges. 12 proven. 13 refuted. 0 times theorem prover too weak. 19 trivial. 0 not checked. [2025-03-03 14:34:37,564 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [305062533] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-03 14:34:37,565 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-03 14:34:37,565 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8, 9] total 11 [2025-03-03 14:34:37,565 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1898807697] [2025-03-03 14:34:37,565 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-03 14:34:37,566 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 11 states [2025-03-03 14:34:37,566 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-03 14:34:37,566 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2025-03-03 14:34:37,567 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=27, Invalid=83, Unknown=0, NotChecked=0, Total=110 [2025-03-03 14:34:37,567 INFO L87 Difference]: Start difference. First operand 56 states and 86 transitions. Second operand has 11 states, 10 states have (on average 3.9) internal successors, (39), 11 states have internal predecessors, (39), 7 states have call successors, (10), 1 states have call predecessors, (10), 4 states have return successors, (10), 6 states have call predecessors, (10), 7 states have call successors, (10) [2025-03-03 14:34:37,667 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 14:34:37,667 INFO L93 Difference]: Finished difference Result 81 states and 140 transitions. [2025-03-03 14:34:37,668 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2025-03-03 14:34:37,668 INFO L78 Accepts]: Start accepts. Automaton has has 11 states, 10 states have (on average 3.9) internal successors, (39), 11 states have internal predecessors, (39), 7 states have call successors, (10), 1 states have call predecessors, (10), 4 states have return successors, (10), 6 states have call predecessors, (10), 7 states have call successors, (10) Word has length 51 [2025-03-03 14:34:37,669 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 14:34:37,669 INFO L225 Difference]: With dead ends: 81 [2025-03-03 14:34:37,671 INFO L226 Difference]: Without dead ends: 77 [2025-03-03 14:34:37,672 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 112 GetRequests, 97 SyntacticMatches, 4 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 11 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=38, Invalid=118, Unknown=0, NotChecked=0, Total=156 [2025-03-03 14:34:37,672 INFO L435 NwaCegarLoop]: 20 mSDtfsCounter, 19 mSDsluCounter, 91 mSDsCounter, 0 mSdLazyCounter, 111 mSolverCounterSat, 12 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 27 SdHoareTripleChecker+Valid, 111 SdHoareTripleChecker+Invalid, 123 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 12 IncrementalHoareTripleChecker+Valid, 111 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-03 14:34:37,672 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [27 Valid, 111 Invalid, 123 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [12 Valid, 111 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-03 14:34:37,673 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 77 states. [2025-03-03 14:34:37,685 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 77 to 56. [2025-03-03 14:34:37,687 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 56 states, 35 states have (on average 1.1714285714285715) internal successors, (41), 39 states have internal predecessors, (41), 11 states have call successors, (11), 3 states have call predecessors, (11), 9 states have return successors, (34), 13 states have call predecessors, (34), 11 states have call successors, (34) [2025-03-03 14:34:37,689 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 56 states to 56 states and 86 transitions. [2025-03-03 14:34:37,690 INFO L78 Accepts]: Start accepts. Automaton has 56 states and 86 transitions. Word has length 51 [2025-03-03 14:34:37,691 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 14:34:37,691 INFO L471 AbstractCegarLoop]: Abstraction has 56 states and 86 transitions. [2025-03-03 14:34:37,691 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 11 states, 10 states have (on average 3.9) internal successors, (39), 11 states have internal predecessors, (39), 7 states have call successors, (10), 1 states have call predecessors, (10), 4 states have return successors, (10), 6 states have call predecessors, (10), 7 states have call successors, (10) [2025-03-03 14:34:37,691 INFO L276 IsEmpty]: Start isEmpty. Operand 56 states and 86 transitions. [2025-03-03 14:34:37,692 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 53 [2025-03-03 14:34:37,692 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 14:34:37,692 INFO L218 NwaCegarLoop]: trace histogram [4, 4, 3, 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, 1] [2025-03-03 14:34:37,698 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Forceful destruction successful, exit code 0 [2025-03-03 14:34:37,892 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 14:34:37,893 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 14:34:37,893 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 14:34:37,893 INFO L85 PathProgramCache]: Analyzing trace with hash -424745804, now seen corresponding path program 1 times [2025-03-03 14:34:37,893 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 14:34:37,893 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [261323535] [2025-03-03 14:34:37,893 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 14:34:37,894 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 14:34:37,896 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 52 statements into 1 equivalence classes. [2025-03-03 14:34:37,900 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 52 of 52 statements. [2025-03-03 14:34:37,900 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 14:34:37,900 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 14:34:37,952 INFO L134 CoverageAnalysis]: Checked inductivity of 46 backedges. 18 proven. 5 refuted. 0 times theorem prover too weak. 23 trivial. 0 not checked. [2025-03-03 14:34:37,953 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-03 14:34:37,953 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [261323535] [2025-03-03 14:34:37,953 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [261323535] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-03 14:34:37,953 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1261274850] [2025-03-03 14:34:37,953 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 14:34:37,953 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 14:34:37,953 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 14:34:37,955 INFO L229 MonitoredProcess]: Starting monitored process 7 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-03 14:34:37,956 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2025-03-03 14:34:37,980 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 52 statements into 1 equivalence classes. [2025-03-03 14:34:37,996 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 52 of 52 statements. [2025-03-03 14:34:37,996 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 14:34:37,996 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 14:34:37,996 INFO L256 TraceCheckSpWp]: Trace formula consists of 135 conjuncts, 6 conjuncts are in the unsatisfiable core [2025-03-03 14:34:37,997 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-03 14:34:38,020 INFO L134 CoverageAnalysis]: Checked inductivity of 46 backedges. 18 proven. 5 refuted. 0 times theorem prover too weak. 23 trivial. 0 not checked. [2025-03-03 14:34:38,020 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-03 14:34:38,159 INFO L134 CoverageAnalysis]: Checked inductivity of 46 backedges. 18 proven. 5 refuted. 0 times theorem prover too weak. 23 trivial. 0 not checked. [2025-03-03 14:34:38,159 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1261274850] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-03 14:34:38,159 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-03 14:34:38,159 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7, 7] total 9 [2025-03-03 14:34:38,159 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1756516788] [2025-03-03 14:34:38,159 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-03 14:34:38,160 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2025-03-03 14:34:38,160 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-03 14:34:38,160 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2025-03-03 14:34:38,160 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=19, Invalid=53, Unknown=0, NotChecked=0, Total=72 [2025-03-03 14:34:38,160 INFO L87 Difference]: Start difference. First operand 56 states and 86 transitions. Second operand has 9 states, 8 states have (on average 4.625) internal successors, (37), 9 states have internal predecessors, (37), 4 states have call successors, (9), 1 states have call predecessors, (9), 3 states have return successors, (9), 5 states have call predecessors, (9), 4 states have call successors, (9) [2025-03-03 14:34:38,215 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 14:34:38,215 INFO L93 Difference]: Finished difference Result 69 states and 101 transitions. [2025-03-03 14:34:38,215 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2025-03-03 14:34:38,215 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 8 states have (on average 4.625) internal successors, (37), 9 states have internal predecessors, (37), 4 states have call successors, (9), 1 states have call predecessors, (9), 3 states have return successors, (9), 5 states have call predecessors, (9), 4 states have call successors, (9) Word has length 52 [2025-03-03 14:34:38,215 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 14:34:38,216 INFO L225 Difference]: With dead ends: 69 [2025-03-03 14:34:38,216 INFO L226 Difference]: Without dead ends: 65 [2025-03-03 14:34:38,216 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 110 GetRequests, 99 SyntacticMatches, 3 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=24, Invalid=66, Unknown=0, NotChecked=0, Total=90 [2025-03-03 14:34:38,217 INFO L435 NwaCegarLoop]: 20 mSDtfsCounter, 18 mSDsluCounter, 49 mSDsCounter, 0 mSdLazyCounter, 72 mSolverCounterSat, 16 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 25 SdHoareTripleChecker+Valid, 69 SdHoareTripleChecker+Invalid, 88 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 16 IncrementalHoareTripleChecker+Valid, 72 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-03-03 14:34:38,217 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [25 Valid, 69 Invalid, 88 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [16 Valid, 72 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-03-03 14:34:38,217 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 65 states. [2025-03-03 14:34:38,222 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 65 to 56. [2025-03-03 14:34:38,222 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 56 states, 35 states have (on average 1.1714285714285715) internal successors, (41), 39 states have internal predecessors, (41), 11 states have call successors, (11), 3 states have call predecessors, (11), 9 states have return successors, (34), 13 states have call predecessors, (34), 11 states have call successors, (34) [2025-03-03 14:34:38,223 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 56 states to 56 states and 86 transitions. [2025-03-03 14:34:38,223 INFO L78 Accepts]: Start accepts. Automaton has 56 states and 86 transitions. Word has length 52 [2025-03-03 14:34:38,223 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 14:34:38,223 INFO L471 AbstractCegarLoop]: Abstraction has 56 states and 86 transitions. [2025-03-03 14:34:38,223 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 8 states have (on average 4.625) internal successors, (37), 9 states have internal predecessors, (37), 4 states have call successors, (9), 1 states have call predecessors, (9), 3 states have return successors, (9), 5 states have call predecessors, (9), 4 states have call successors, (9) [2025-03-03 14:34:38,223 INFO L276 IsEmpty]: Start isEmpty. Operand 56 states and 86 transitions. [2025-03-03 14:34:38,225 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 66 [2025-03-03 14:34:38,225 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 14:34:38,225 INFO L218 NwaCegarLoop]: trace histogram [5, 5, 4, 4, 4, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-03 14:34:38,230 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Ended with exit code 0 [2025-03-03 14:34:38,425 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 14:34:38,425 INFO L396 AbstractCegarLoop]: === Iteration 9 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 14:34:38,426 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 14:34:38,426 INFO L85 PathProgramCache]: Analyzing trace with hash 1805494280, now seen corresponding path program 1 times [2025-03-03 14:34:38,426 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 14:34:38,426 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1919632874] [2025-03-03 14:34:38,426 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 14:34:38,426 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 14:34:38,429 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 65 statements into 1 equivalence classes. [2025-03-03 14:34:38,440 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 65 of 65 statements. [2025-03-03 14:34:38,440 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 14:34:38,440 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-03 14:34:38,440 INFO L348 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2025-03-03 14:34:38,442 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 65 statements into 1 equivalence classes. [2025-03-03 14:34:38,451 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 65 of 65 statements. [2025-03-03 14:34:38,452 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 14:34:38,452 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-03 14:34:38,467 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2025-03-03 14:34:38,467 INFO L340 BasicCegarLoop]: Counterexample is feasible [2025-03-03 14:34:38,468 INFO L782 garLoopResultBuilder]: Registering result UNSAFE for location ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION (0 of 1 remaining) [2025-03-03 14:34:38,469 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8 [2025-03-03 14:34:38,471 INFO L422 BasicCegarLoop]: Path program histogram: [1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-03 14:34:38,487 INFO L170 ceAbstractionStarter]: Computing trace abstraction results [2025-03-03 14:34:38,488 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 03.03 02:34:38 BoogieIcfgContainer [2025-03-03 14:34:38,488 INFO L131 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2025-03-03 14:34:38,489 INFO L112 PluginConnector]: ------------------------Witness Printer---------------------------- [2025-03-03 14:34:38,489 INFO L270 PluginConnector]: Initializing Witness Printer... [2025-03-03 14:34:38,489 INFO L274 PluginConnector]: Witness Printer initialized [2025-03-03 14:34:38,490 INFO L184 PluginConnector]: Executing the observer RCFGCatcher from plugin Witness Printer for "de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 03.03 02:34:33" (3/4) ... [2025-03-03 14:34:38,490 INFO L140 WitnessPrinter]: Generating witness for reachability counterexample [2025-03-03 14:34:38,526 INFO L127 tionWitnessGenerator]: Generated YAML witness of length 36. [2025-03-03 14:34:38,578 INFO L149 WitnessManager]: Wrote witness to /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/witness.graphml [2025-03-03 14:34:38,578 INFO L149 WitnessManager]: Wrote witness to /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/witness.yml [2025-03-03 14:34:38,582 INFO L131 PluginConnector]: ------------------------ END Witness Printer---------------------------- [2025-03-03 14:34:38,583 INFO L158 Benchmark]: Toolchain (without parser) took 5416.43ms. Allocated memory is still 142.6MB. Free memory was 106.6MB in the beginning and 78.6MB in the end (delta: 28.0MB). Peak memory consumption was 25.4MB. Max. memory is 16.1GB. [2025-03-03 14:34:38,583 INFO L158 Benchmark]: CDTParser took 0.23ms. Allocated memory is still 201.3MB. Free memory is still 127.3MB. There was no memory consumed. Max. memory is 16.1GB. [2025-03-03 14:34:38,583 INFO L158 Benchmark]: CACSL2BoogieTranslator took 141.97ms. Allocated memory is still 142.6MB. Free memory was 105.6MB in the beginning and 95.0MB in the end (delta: 10.7MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. [2025-03-03 14:34:38,583 INFO L158 Benchmark]: Boogie Procedure Inliner took 18.33ms. Allocated memory is still 142.6MB. Free memory was 95.0MB in the beginning and 93.9MB in the end (delta: 1.0MB). There was no memory consumed. Max. memory is 16.1GB. [2025-03-03 14:34:38,583 INFO L158 Benchmark]: Boogie Preprocessor took 22.72ms. Allocated memory is still 142.6MB. Free memory was 93.9MB in the beginning and 92.8MB in the end (delta: 1.1MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. [2025-03-03 14:34:38,584 INFO L158 Benchmark]: IcfgBuilder took 190.27ms. Allocated memory is still 142.6MB. Free memory was 92.8MB in the beginning and 82.3MB in the end (delta: 10.5MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. [2025-03-03 14:34:38,584 INFO L158 Benchmark]: TraceAbstraction took 4945.14ms. Allocated memory is still 142.6MB. Free memory was 82.3MB in the beginning and 85.2MB in the end (delta: -2.9MB). There was no memory consumed. Max. memory is 16.1GB. [2025-03-03 14:34:38,584 INFO L158 Benchmark]: Witness Printer took 93.49ms. Allocated memory is still 142.6MB. Free memory was 85.2MB in the beginning and 78.6MB in the end (delta: 6.6MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. [2025-03-03 14:34:38,585 INFO L338 ainManager$Toolchain]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * CDTParser took 0.23ms. Allocated memory is still 201.3MB. Free memory is still 127.3MB. There was no memory consumed. Max. memory is 16.1GB. * CACSL2BoogieTranslator took 141.97ms. Allocated memory is still 142.6MB. Free memory was 105.6MB in the beginning and 95.0MB in the end (delta: 10.7MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. * Boogie Procedure Inliner took 18.33ms. Allocated memory is still 142.6MB. Free memory was 95.0MB in the beginning and 93.9MB in the end (delta: 1.0MB). There was no memory consumed. Max. memory is 16.1GB. * Boogie Preprocessor took 22.72ms. Allocated memory is still 142.6MB. Free memory was 93.9MB in the beginning and 92.8MB in the end (delta: 1.1MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. * IcfgBuilder took 190.27ms. Allocated memory is still 142.6MB. Free memory was 92.8MB in the beginning and 82.3MB in the end (delta: 10.5MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. * TraceAbstraction took 4945.14ms. Allocated memory is still 142.6MB. Free memory was 82.3MB in the beginning and 85.2MB in the end (delta: -2.9MB). There was no memory consumed. Max. memory is 16.1GB. * Witness Printer took 93.49ms. Allocated memory is still 142.6MB. Free memory was 85.2MB in the beginning and 78.6MB in the end (delta: 6.6MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. * 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] [L15] RET, EXPR fibo2(n-1) VAL [\old(n)=2, 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] [L15] RET, EXPR fibo2(n-2) VAL [\old(n)=2, n=2] [L15] return fibo2(n-1) + fibo2(n-2); [L25] RET, EXPR fibo1(n-1) VAL [\old(n)=3, 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] [L25] RET, EXPR fibo1(n-2) VAL [\old(n)=3, n=3] [L25] return fibo1(n-1) + fibo1(n-2); [L15] RET, EXPR fibo2(n-1) VAL [\old(n)=4, 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] [L25] RET, EXPR fibo1(n-1) VAL [\old(n)=2, 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] [L25] RET, EXPR fibo1(n-2) VAL [\old(n)=2, n=2] [L25] return fibo1(n-1) + fibo1(n-2); [L15] RET, EXPR fibo2(n-2) VAL [\old(n)=4, n=4] [L15] return fibo2(n-1) + fibo2(n-2); [L39] RET, EXPR fibo1(x) VAL [x=4] [L39] int result = fibo1(x); [L40] COND TRUE result == 3 VAL [x=4] [L41] reach_error() VAL [x=4] - StatisticsResult: Ultimate Automizer benchmark data CFG has 3 procedures, 29 locations, 1 error locations. Started 1 CEGAR loops. OverallTime: 4.9s, OverallIterations: 9, TraceHistogramMax: 5, PathProgramHistogramMax: 1, EmptinessCheckTime: 0.0s, AutomataDifference: 0.9s, DeadEndRemovalTime: 0.0s, HoareAnnotationTime: 0.0s, InitialAbstractionConstructionTime: 0.0s, HoareTripleCheckerStatistics: 0 mSolverCounterUnknown, 167 SdHoareTripleChecker+Valid, 0.6s IncrementalHoareTripleChecker+Time, 0 mSdLazyCounter, 130 mSDsluCounter, 1044 SdHoareTripleChecker+Invalid, 0.5s Time, 0 mProtectedAction, 0 SdHoareTripleChecker+Unchecked, 0 IncrementalHoareTripleChecker+Unchecked, 844 mSDsCounter, 119 IncrementalHoareTripleChecker+Valid, 0 mProtectedPredicate, 874 IncrementalHoareTripleChecker+Invalid, 993 SdHoareTripleChecker+Unknown, 0 mSolverCounterNotChecked, 119 mSolverCounterUnsat, 200 mSDtfsCounter, 874 mSolverCounterSat, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Unknown, PredicateUnifierStatistics: 0 DeclaredPredicates, 518 GetRequests, 415 SyntacticMatches, 18 SemanticMatches, 85 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 165 ImplicationChecksByTransitivity, 0.6s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=56occurred in iteration=6, 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, 8 MinimizatonAttempts, 50 StatesRemovedByMinimization, 7 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TRACE_CHECK: 0.0s SsaConstructionTime, 0.2s SatisfiabilityAnalysisTime, 2.2s InterpolantComputationTime, 532 NumberOfCodeBlocks, 532 NumberOfCodeBlocksAsserted, 15 NumberOfCheckSat, 670 ConstructedInterpolants, 0 QuantifiedInterpolants, 1408 SizeOfPredicates, 9 NumberOfNonLiveVariables, 614 ConjunctsInSsa, 42 ConjunctsInUnsatCore, 20 InterpolantComputations, 2 PerfectInterpolantSequences, 276/393 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, ConComCheckerStatistics: No data available RESULT: Ultimate proved your program to be incorrect! [2025-03-03 14:34:38,598 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (1)] Forceful destruction successful, exit code 0 Received shutdown request... --- End real Ultimate output --- Execution finished normally Writing output log to file Ultimate.log Writing human readable error path to file UltimateCounterExample.errorpath Result: FALSE