./Ultimate.py --spec ../sv-benchmarks/c/properties/unreach-call.prp --file ../sv-benchmarks/c/nla-digbench-scaling/hard2_valuebound100.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version e2fb8bed 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/nla-digbench-scaling/hard2_valuebound100.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 c39f3d25be406fa166da46a61b4a36c0a90262202dfdee83ae8e5211f182a6f7 --- Real Ultimate output --- This is Ultimate 0.3.0-?-e2fb8be-m [2025-03-08 05:12:28,146 INFO L188 SettingsManager]: Resetting all preferences to default values... [2025-03-08 05:12:28,198 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf [2025-03-08 05:12:28,204 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2025-03-08 05:12:28,204 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2025-03-08 05:12:28,220 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2025-03-08 05:12:28,220 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2025-03-08 05:12:28,220 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2025-03-08 05:12:28,220 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2025-03-08 05:12:28,220 INFO L153 SettingsManager]: * Use memory slicer=true [2025-03-08 05:12:28,220 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2025-03-08 05:12:28,220 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2025-03-08 05:12:28,220 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2025-03-08 05:12:28,221 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2025-03-08 05:12:28,221 INFO L153 SettingsManager]: * Use SBE=true [2025-03-08 05:12:28,221 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2025-03-08 05:12:28,221 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2025-03-08 05:12:28,221 INFO L153 SettingsManager]: * sizeof long=4 [2025-03-08 05:12:28,221 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2025-03-08 05:12:28,221 INFO L153 SettingsManager]: * sizeof POINTER=4 [2025-03-08 05:12:28,221 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2025-03-08 05:12:28,221 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2025-03-08 05:12:28,221 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2025-03-08 05:12:28,221 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2025-03-08 05:12:28,221 INFO L153 SettingsManager]: * sizeof long double=12 [2025-03-08 05:12:28,221 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2025-03-08 05:12:28,221 INFO L153 SettingsManager]: * Behaviour of calls to undefined functions=OVERAPPROXIMATE_BEHAVIOUR [2025-03-08 05:12:28,221 INFO L153 SettingsManager]: * Use constant arrays=true [2025-03-08 05:12:28,221 INFO L151 SettingsManager]: Preferences of IcfgBuilder differ from their defaults: [2025-03-08 05:12:28,221 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2025-03-08 05:12:28,221 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2025-03-08 05:12:28,221 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2025-03-08 05:12:28,221 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2025-03-08 05:12:28,222 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2025-03-08 05:12:28,222 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2025-03-08 05:12:28,222 INFO L153 SettingsManager]: * Compute procedure contracts=false [2025-03-08 05:12:28,222 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2025-03-08 05:12:28,222 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2025-03-08 05:12:28,222 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2025-03-08 05:12:28,222 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2025-03-08 05:12:28,222 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2025-03-08 05:12:28,222 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2025-03-08 05:12:28,222 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2025-03-08 05:12:28,222 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 -> c39f3d25be406fa166da46a61b4a36c0a90262202dfdee83ae8e5211f182a6f7 [2025-03-08 05:12:28,441 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2025-03-08 05:12:28,449 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2025-03-08 05:12:28,450 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2025-03-08 05:12:28,451 INFO L270 PluginConnector]: Initializing CDTParser... [2025-03-08 05:12:28,451 INFO L274 PluginConnector]: CDTParser initialized [2025-03-08 05:12:28,452 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/nla-digbench-scaling/hard2_valuebound100.c [2025-03-08 05:12:29,520 INFO L533 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/27bd9f8aa/da91f637f91d4e52b06e120757459044/FLAG943346557 [2025-03-08 05:12:29,699 INFO L384 CDTParser]: Found 1 translation units. [2025-03-08 05:12:29,700 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/hard2_valuebound100.c [2025-03-08 05:12:29,707 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/27bd9f8aa/da91f637f91d4e52b06e120757459044/FLAG943346557 [2025-03-08 05:12:29,731 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/27bd9f8aa/da91f637f91d4e52b06e120757459044 [2025-03-08 05:12:29,733 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2025-03-08 05:12:29,734 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2025-03-08 05:12:29,735 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2025-03-08 05:12:29,735 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2025-03-08 05:12:29,738 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2025-03-08 05:12:29,738 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 08.03 05:12:29" (1/1) ... [2025-03-08 05:12:29,739 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@a536f4 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.03 05:12:29, skipping insertion in model container [2025-03-08 05:12:29,739 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 08.03 05:12:29" (1/1) ... [2025-03-08 05:12:29,749 INFO L175 MainTranslator]: Built tables and reachable declarations [2025-03-08 05:12:29,842 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/nla-digbench-scaling/hard2_valuebound100.c[526,539] [2025-03-08 05:12:29,855 INFO L210 PostProcessor]: Analyzing one entry point: main [2025-03-08 05:12:29,862 INFO L200 MainTranslator]: Completed pre-run [2025-03-08 05:12:29,870 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/nla-digbench-scaling/hard2_valuebound100.c[526,539] [2025-03-08 05:12:29,875 INFO L210 PostProcessor]: Analyzing one entry point: main [2025-03-08 05:12:29,887 INFO L204 MainTranslator]: Completed translation [2025-03-08 05:12:29,888 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.03 05:12:29 WrapperNode [2025-03-08 05:12:29,888 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2025-03-08 05:12:29,889 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2025-03-08 05:12:29,889 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2025-03-08 05:12:29,889 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2025-03-08 05:12:29,894 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.03 05:12:29" (1/1) ... [2025-03-08 05:12:29,899 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.03 05:12:29" (1/1) ... [2025-03-08 05:12:29,913 INFO L138 Inliner]: procedures = 14, calls = 23, calls flagged for inlining = 3, calls inlined = 3, statements flattened = 58 [2025-03-08 05:12:29,913 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2025-03-08 05:12:29,914 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2025-03-08 05:12:29,914 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2025-03-08 05:12:29,914 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2025-03-08 05:12:29,920 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.03 05:12:29" (1/1) ... [2025-03-08 05:12:29,921 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.03 05:12:29" (1/1) ... [2025-03-08 05:12:29,921 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.03 05:12:29" (1/1) ... [2025-03-08 05:12:29,935 INFO L175 MemorySlicer]: Split 10 memory accesses to 2 slices as follows [2, 8]. 80 percent of accesses are in the largest equivalence class. The 10 initializations are split as follows [2, 8]. The 0 writes are split as follows [0, 0]. [2025-03-08 05:12:29,936 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.03 05:12:29" (1/1) ... [2025-03-08 05:12:29,936 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.03 05:12:29" (1/1) ... [2025-03-08 05:12:29,938 INFO L184 PluginConnector]: Executing the observer ReplaceArrayAssignments from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.03 05:12:29" (1/1) ... [2025-03-08 05:12:29,939 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.03 05:12:29" (1/1) ... [2025-03-08 05:12:29,939 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.03 05:12:29" (1/1) ... [2025-03-08 05:12:29,940 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.03 05:12:29" (1/1) ... [2025-03-08 05:12:29,942 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2025-03-08 05:12:29,943 INFO L112 PluginConnector]: ------------------------IcfgBuilder---------------------------- [2025-03-08 05:12:29,943 INFO L270 PluginConnector]: Initializing IcfgBuilder... [2025-03-08 05:12:29,943 INFO L274 PluginConnector]: IcfgBuilder initialized [2025-03-08 05:12:29,944 INFO L184 PluginConnector]: Executing the observer IcfgBuilderObserver from plugin IcfgBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.03 05:12:29" (1/1) ... [2025-03-08 05:12:29,947 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2025-03-08 05:12:29,955 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-08 05:12:29,966 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-08 05:12:29,968 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-08 05:12:29,985 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2025-03-08 05:12:29,985 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2025-03-08 05:12:29,985 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#1 [2025-03-08 05:12:29,985 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2025-03-08 05:12:29,985 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2025-03-08 05:12:29,985 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2025-03-08 05:12:29,985 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2025-03-08 05:12:30,026 INFO L256 CfgBuilder]: Building ICFG [2025-03-08 05:12:30,028 INFO L286 CfgBuilder]: Building CFG for each procedure with an implementation [2025-03-08 05:12:30,149 INFO L? ?]: Removed 7 outVars from TransFormulas that were not future-live. [2025-03-08 05:12:30,150 INFO L307 CfgBuilder]: Performing block encoding [2025-03-08 05:12:30,156 INFO L331 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2025-03-08 05:12:30,157 INFO L336 CfgBuilder]: Removed 0 assume(true) statements. [2025-03-08 05:12:30,157 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 08.03 05:12:30 BoogieIcfgContainer [2025-03-08 05:12:30,157 INFO L131 PluginConnector]: ------------------------ END IcfgBuilder---------------------------- [2025-03-08 05:12:30,160 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2025-03-08 05:12:30,160 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2025-03-08 05:12:30,163 INFO L274 PluginConnector]: TraceAbstraction initialized [2025-03-08 05:12:30,164 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 08.03 05:12:29" (1/3) ... [2025-03-08 05:12:30,164 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@418895b and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 08.03 05:12:30, skipping insertion in model container [2025-03-08 05:12:30,165 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.03 05:12:29" (2/3) ... [2025-03-08 05:12:30,165 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@418895b and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 08.03 05:12:30, skipping insertion in model container [2025-03-08 05:12:30,165 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 08.03 05:12:30" (3/3) ... [2025-03-08 05:12:30,166 INFO L128 eAbstractionObserver]: Analyzing ICFG hard2_valuebound100.c [2025-03-08 05:12:30,177 INFO L216 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2025-03-08 05:12:30,178 INFO L151 ceAbstractionStarter]: Applying trace abstraction to ICFG hard2_valuebound100.c that has 2 procedures, 24 locations, 1 initial locations, 2 loop locations, and 1 error locations. [2025-03-08 05:12:30,220 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2025-03-08 05:12:30,230 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;@68d6f84e, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2025-03-08 05:12:30,230 INFO L334 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2025-03-08 05:12:30,234 INFO L276 IsEmpty]: Start isEmpty. Operand has 24 states, 16 states have (on average 1.375) internal successors, (22), 15 states have internal predecessors, (22), 7 states have call successors, (7), 1 states have call predecessors, (7), 1 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2025-03-08 05:12:30,237 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 9 [2025-03-08 05:12:30,237 INFO L210 NwaCegarLoop]: Found error trace [2025-03-08 05:12:30,237 INFO L218 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1] [2025-03-08 05:12:30,238 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-08 05:12:30,241 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-08 05:12:30,241 INFO L85 PathProgramCache]: Analyzing trace with hash 1948886864, now seen corresponding path program 1 times [2025-03-08 05:12:30,246 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-08 05:12:30,246 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1775877215] [2025-03-08 05:12:30,246 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 05:12:30,247 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-08 05:12:30,294 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 8 statements into 1 equivalence classes. [2025-03-08 05:12:30,308 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 8 of 8 statements. [2025-03-08 05:12:30,308 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 05:12:30,308 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 05:12:30,345 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-08 05:12:30,345 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-08 05:12:30,346 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1775877215] [2025-03-08 05:12:30,346 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1775877215] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-08 05:12:30,346 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-08 05:12:30,347 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2025-03-08 05:12:30,347 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1627382868] [2025-03-08 05:12:30,348 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-08 05:12:30,350 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2025-03-08 05:12:30,350 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-08 05:12:30,361 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2025-03-08 05:12:30,362 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2025-03-08 05:12:30,363 INFO L87 Difference]: Start difference. First operand has 24 states, 16 states have (on average 1.375) internal successors, (22), 15 states have internal predecessors, (22), 7 states have call successors, (7), 1 states have call predecessors, (7), 1 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) Second operand has 2 states, 2 states have (on average 3.5) internal successors, (7), 2 states have internal predecessors, (7), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2025-03-08 05:12:30,372 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-08 05:12:30,372 INFO L93 Difference]: Finished difference Result 45 states and 75 transitions. [2025-03-08 05:12:30,373 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2025-03-08 05:12:30,374 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 3.5) internal successors, (7), 2 states have internal predecessors, (7), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 8 [2025-03-08 05:12:30,374 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-08 05:12:30,377 INFO L225 Difference]: With dead ends: 45 [2025-03-08 05:12:30,377 INFO L226 Difference]: Without dead ends: 20 [2025-03-08 05:12:30,379 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 2 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 0 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2025-03-08 05:12:30,381 INFO L435 NwaCegarLoop]: 32 mSDtfsCounter, 0 mSDsluCounter, 0 mSDsCounter, 0 mSdLazyCounter, 0 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 32 SdHoareTripleChecker+Invalid, 0 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 0 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-03-08 05:12:30,381 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 32 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 0 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-03-08 05:12:30,389 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 20 states. [2025-03-08 05:12:30,399 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 20 to 20. [2025-03-08 05:12:30,400 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 20 states, 11 states have (on average 1.3636363636363635) internal successors, (15), 12 states have internal predecessors, (15), 7 states have call successors, (7), 1 states have call predecessors, (7), 1 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2025-03-08 05:12:30,403 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 20 states to 20 states and 28 transitions. [2025-03-08 05:12:30,405 INFO L78 Accepts]: Start accepts. Automaton has 20 states and 28 transitions. Word has length 8 [2025-03-08 05:12:30,405 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-08 05:12:30,405 INFO L471 AbstractCegarLoop]: Abstraction has 20 states and 28 transitions. [2025-03-08 05:12:30,406 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 2 states have (on average 3.5) internal successors, (7), 2 states have internal predecessors, (7), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2025-03-08 05:12:30,406 INFO L276 IsEmpty]: Start isEmpty. Operand 20 states and 28 transitions. [2025-03-08 05:12:30,406 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 9 [2025-03-08 05:12:30,406 INFO L210 NwaCegarLoop]: Found error trace [2025-03-08 05:12:30,406 INFO L218 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1] [2025-03-08 05:12:30,407 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2025-03-08 05:12:30,407 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-08 05:12:30,408 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-08 05:12:30,408 INFO L85 PathProgramCache]: Analyzing trace with hash 1977516015, now seen corresponding path program 1 times [2025-03-08 05:12:30,408 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-08 05:12:30,408 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [431397978] [2025-03-08 05:12:30,408 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 05:12:30,408 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-08 05:12:30,416 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 8 statements into 1 equivalence classes. [2025-03-08 05:12:30,429 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 8 of 8 statements. [2025-03-08 05:12:30,430 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 05:12:30,430 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 05:12:30,533 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-08 05:12:30,533 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-08 05:12:30,533 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [431397978] [2025-03-08 05:12:30,533 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [431397978] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-08 05:12:30,533 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-08 05:12:30,533 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2025-03-08 05:12:30,533 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [673117733] [2025-03-08 05:12:30,533 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-08 05:12:30,534 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2025-03-08 05:12:30,534 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-08 05:12:30,534 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2025-03-08 05:12:30,534 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2025-03-08 05:12:30,534 INFO L87 Difference]: Start difference. First operand 20 states and 28 transitions. Second operand has 5 states, 4 states have (on average 1.75) internal successors, (7), 4 states have internal predecessors, (7), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2025-03-08 05:12:30,580 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-08 05:12:30,580 INFO L93 Difference]: Finished difference Result 32 states and 44 transitions. [2025-03-08 05:12:30,580 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2025-03-08 05:12:30,580 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 4 states have (on average 1.75) internal successors, (7), 4 states have internal predecessors, (7), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 8 [2025-03-08 05:12:30,580 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-08 05:12:30,581 INFO L225 Difference]: With dead ends: 32 [2025-03-08 05:12:30,581 INFO L226 Difference]: Without dead ends: 30 [2025-03-08 05:12:30,581 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 6 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2025-03-08 05:12:30,581 INFO L435 NwaCegarLoop]: 24 mSDtfsCounter, 8 mSDsluCounter, 59 mSDsCounter, 0 mSdLazyCounter, 22 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 14 SdHoareTripleChecker+Valid, 83 SdHoareTripleChecker+Invalid, 22 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 22 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-03-08 05:12:30,581 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [14 Valid, 83 Invalid, 22 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 22 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-03-08 05:12:30,582 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 30 states. [2025-03-08 05:12:30,585 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 30 to 24. [2025-03-08 05:12:30,585 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 24 states, 14 states have (on average 1.2857142857142858) internal successors, (18), 15 states have internal predecessors, (18), 7 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2025-03-08 05:12:30,586 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 24 states to 24 states and 31 transitions. [2025-03-08 05:12:30,586 INFO L78 Accepts]: Start accepts. Automaton has 24 states and 31 transitions. Word has length 8 [2025-03-08 05:12:30,586 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-08 05:12:30,586 INFO L471 AbstractCegarLoop]: Abstraction has 24 states and 31 transitions. [2025-03-08 05:12:30,586 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 4 states have (on average 1.75) internal successors, (7), 4 states have internal predecessors, (7), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2025-03-08 05:12:30,586 INFO L276 IsEmpty]: Start isEmpty. Operand 24 states and 31 transitions. [2025-03-08 05:12:30,586 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 14 [2025-03-08 05:12:30,586 INFO L210 NwaCegarLoop]: Found error trace [2025-03-08 05:12:30,586 INFO L218 NwaCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-08 05:12:30,586 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2025-03-08 05:12:30,586 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-08 05:12:30,587 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-08 05:12:30,587 INFO L85 PathProgramCache]: Analyzing trace with hash 311658512, now seen corresponding path program 1 times [2025-03-08 05:12:30,587 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-08 05:12:30,587 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1947654172] [2025-03-08 05:12:30,587 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 05:12:30,587 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-08 05:12:30,593 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 13 statements into 1 equivalence classes. [2025-03-08 05:12:30,600 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 13 of 13 statements. [2025-03-08 05:12:30,600 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 05:12:30,600 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 05:12:30,671 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-08 05:12:30,671 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-08 05:12:30,671 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1947654172] [2025-03-08 05:12:30,672 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1947654172] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-08 05:12:30,672 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-08 05:12:30,672 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2025-03-08 05:12:30,672 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1893664680] [2025-03-08 05:12:30,672 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-08 05:12:30,672 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2025-03-08 05:12:30,672 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-08 05:12:30,674 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2025-03-08 05:12:30,674 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2025-03-08 05:12:30,674 INFO L87 Difference]: Start difference. First operand 24 states and 31 transitions. Second operand has 5 states, 4 states have (on average 2.5) internal successors, (10), 4 states have internal predecessors, (10), 1 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2025-03-08 05:12:30,723 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-08 05:12:30,723 INFO L93 Difference]: Finished difference Result 36 states and 47 transitions. [2025-03-08 05:12:30,725 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2025-03-08 05:12:30,725 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 4 states have (on average 2.5) internal successors, (10), 4 states have internal predecessors, (10), 1 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 13 [2025-03-08 05:12:30,725 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-08 05:12:30,725 INFO L225 Difference]: With dead ends: 36 [2025-03-08 05:12:30,725 INFO L226 Difference]: Without dead ends: 34 [2025-03-08 05:12:30,726 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 6 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2025-03-08 05:12:30,728 INFO L435 NwaCegarLoop]: 24 mSDtfsCounter, 8 mSDsluCounter, 56 mSDsCounter, 0 mSdLazyCounter, 33 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 13 SdHoareTripleChecker+Valid, 80 SdHoareTripleChecker+Invalid, 33 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 33 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-03-08 05:12:30,728 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [13 Valid, 80 Invalid, 33 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 33 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-03-08 05:12:30,729 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 34 states. [2025-03-08 05:12:30,735 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 34 to 28. [2025-03-08 05:12:30,735 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 28 states, 17 states have (on average 1.2352941176470589) internal successors, (21), 18 states have internal predecessors, (21), 7 states have call successors, (7), 3 states have call predecessors, (7), 3 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2025-03-08 05:12:30,736 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 28 states to 28 states and 34 transitions. [2025-03-08 05:12:30,736 INFO L78 Accepts]: Start accepts. Automaton has 28 states and 34 transitions. Word has length 13 [2025-03-08 05:12:30,736 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-08 05:12:30,736 INFO L471 AbstractCegarLoop]: Abstraction has 28 states and 34 transitions. [2025-03-08 05:12:30,736 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 4 states have (on average 2.5) internal successors, (10), 4 states have internal predecessors, (10), 1 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2025-03-08 05:12:30,736 INFO L276 IsEmpty]: Start isEmpty. Operand 28 states and 34 transitions. [2025-03-08 05:12:30,737 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 19 [2025-03-08 05:12:30,737 INFO L210 NwaCegarLoop]: Found error trace [2025-03-08 05:12:30,737 INFO L218 NwaCegarLoop]: trace histogram [3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-08 05:12:30,737 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2 [2025-03-08 05:12:30,738 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-08 05:12:30,738 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-08 05:12:30,738 INFO L85 PathProgramCache]: Analyzing trace with hash -34188081, now seen corresponding path program 1 times [2025-03-08 05:12:30,738 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-08 05:12:30,738 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [10766243] [2025-03-08 05:12:30,738 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 05:12:30,738 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-08 05:12:30,743 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 18 statements into 1 equivalence classes. [2025-03-08 05:12:30,748 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 18 of 18 statements. [2025-03-08 05:12:30,748 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 05:12:30,748 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-08 05:12:30,752 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [126075636] [2025-03-08 05:12:30,752 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 05:12:30,752 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-08 05:12:30,752 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-08 05:12:30,756 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-08 05:12:30,757 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-08 05:12:30,786 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 18 statements into 1 equivalence classes. [2025-03-08 05:12:30,798 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 18 of 18 statements. [2025-03-08 05:12:30,798 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 05:12:30,798 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 05:12:30,801 INFO L256 TraceCheckSpWp]: Trace formula consists of 81 conjuncts, 9 conjuncts are in the unsatisfiable core [2025-03-08 05:12:30,805 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-08 05:12:30,879 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2025-03-08 05:12:30,879 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2025-03-08 05:12:30,880 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-08 05:12:30,880 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [10766243] [2025-03-08 05:12:30,880 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-08 05:12:30,880 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [126075636] [2025-03-08 05:12:30,880 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [126075636] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-08 05:12:30,881 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-08 05:12:30,881 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2025-03-08 05:12:30,881 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [214199140] [2025-03-08 05:12:30,881 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-08 05:12:30,881 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2025-03-08 05:12:30,881 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-08 05:12:30,881 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2025-03-08 05:12:30,881 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2025-03-08 05:12:30,882 INFO L87 Difference]: Start difference. First operand 28 states and 34 transitions. Second operand has 5 states, 4 states have (on average 2.5) internal successors, (10), 4 states have internal predecessors, (10), 1 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2025-03-08 05:12:30,930 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-08 05:12:30,930 INFO L93 Difference]: Finished difference Result 51 states and 68 transitions. [2025-03-08 05:12:30,930 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2025-03-08 05:12:30,930 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 4 states have (on average 2.5) internal successors, (10), 4 states have internal predecessors, (10), 1 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) Word has length 18 [2025-03-08 05:12:30,930 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-08 05:12:30,931 INFO L225 Difference]: With dead ends: 51 [2025-03-08 05:12:30,931 INFO L226 Difference]: Without dead ends: 39 [2025-03-08 05:12:30,931 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 18 GetRequests, 14 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2025-03-08 05:12:30,931 INFO L435 NwaCegarLoop]: 24 mSDtfsCounter, 4 mSDsluCounter, 57 mSDsCounter, 0 mSdLazyCounter, 38 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 7 SdHoareTripleChecker+Valid, 81 SdHoareTripleChecker+Invalid, 40 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 38 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-03-08 05:12:30,932 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [7 Valid, 81 Invalid, 40 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 38 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-03-08 05:12:30,932 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 39 states. [2025-03-08 05:12:30,936 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 39 to 39. [2025-03-08 05:12:30,936 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 39 states, 22 states have (on average 1.2272727272727273) internal successors, (27), 23 states have internal predecessors, (27), 12 states have call successors, (12), 4 states have call predecessors, (12), 4 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2025-03-08 05:12:30,937 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 39 states to 39 states and 50 transitions. [2025-03-08 05:12:30,937 INFO L78 Accepts]: Start accepts. Automaton has 39 states and 50 transitions. Word has length 18 [2025-03-08 05:12:30,937 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-08 05:12:30,937 INFO L471 AbstractCegarLoop]: Abstraction has 39 states and 50 transitions. [2025-03-08 05:12:30,937 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 4 states have (on average 2.5) internal successors, (10), 4 states have internal predecessors, (10), 1 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2025-03-08 05:12:30,937 INFO L276 IsEmpty]: Start isEmpty. Operand 39 states and 50 transitions. [2025-03-08 05:12:30,938 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 25 [2025-03-08 05:12:30,938 INFO L210 NwaCegarLoop]: Found error trace [2025-03-08 05:12:30,938 INFO L218 NwaCegarLoop]: trace histogram [4, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-08 05:12:30,943 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-08 05:12:31,138 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-08 05:12:31,138 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-08 05:12:31,139 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-08 05:12:31,139 INFO L85 PathProgramCache]: Analyzing trace with hash 80856429, now seen corresponding path program 1 times [2025-03-08 05:12:31,139 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-08 05:12:31,139 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [939985021] [2025-03-08 05:12:31,139 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 05:12:31,139 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-08 05:12:31,143 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 24 statements into 1 equivalence classes. [2025-03-08 05:12:31,153 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 24 of 24 statements. [2025-03-08 05:12:31,153 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 05:12:31,153 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-08 05:12:31,154 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1827543539] [2025-03-08 05:12:31,154 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 05:12:31,154 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-08 05:12:31,154 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-08 05:12:31,159 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-08 05:12:31,159 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-08 05:12:31,183 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 24 statements into 1 equivalence classes. [2025-03-08 05:12:31,200 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 24 of 24 statements. [2025-03-08 05:12:31,200 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 05:12:31,200 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 05:12:31,202 INFO L256 TraceCheckSpWp]: Trace formula consists of 91 conjuncts, 7 conjuncts are in the unsatisfiable core [2025-03-08 05:12:31,203 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-08 05:12:31,254 INFO L134 CoverageAnalysis]: Checked inductivity of 18 backedges. 6 proven. 0 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2025-03-08 05:12:31,254 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2025-03-08 05:12:31,254 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-08 05:12:31,254 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [939985021] [2025-03-08 05:12:31,254 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-08 05:12:31,254 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1827543539] [2025-03-08 05:12:31,254 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1827543539] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-08 05:12:31,254 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-08 05:12:31,254 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2025-03-08 05:12:31,254 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [82128931] [2025-03-08 05:12:31,254 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-08 05:12:31,254 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2025-03-08 05:12:31,254 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-08 05:12:31,255 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2025-03-08 05:12:31,255 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2025-03-08 05:12:31,255 INFO L87 Difference]: Start difference. First operand 39 states and 50 transitions. Second operand has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 1 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) [2025-03-08 05:12:31,299 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-08 05:12:31,299 INFO L93 Difference]: Finished difference Result 51 states and 66 transitions. [2025-03-08 05:12:31,299 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2025-03-08 05:12:31,299 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 1 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) Word has length 24 [2025-03-08 05:12:31,299 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-08 05:12:31,300 INFO L225 Difference]: With dead ends: 51 [2025-03-08 05:12:31,300 INFO L226 Difference]: Without dead ends: 49 [2025-03-08 05:12:31,300 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 24 GetRequests, 20 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2025-03-08 05:12:31,301 INFO L435 NwaCegarLoop]: 18 mSDtfsCounter, 7 mSDsluCounter, 46 mSDsCounter, 0 mSdLazyCounter, 40 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 10 SdHoareTripleChecker+Valid, 64 SdHoareTripleChecker+Invalid, 43 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 40 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-03-08 05:12:31,301 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [10 Valid, 64 Invalid, 43 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 40 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-03-08 05:12:31,301 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 49 states. [2025-03-08 05:12:31,305 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 49 to 48. [2025-03-08 05:12:31,305 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 48 states, 27 states have (on average 1.2592592592592593) internal successors, (34), 29 states have internal predecessors, (34), 15 states have call successors, (15), 5 states have call predecessors, (15), 5 states have return successors, (14), 13 states have call predecessors, (14), 14 states have call successors, (14) [2025-03-08 05:12:31,306 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 48 states to 48 states and 63 transitions. [2025-03-08 05:12:31,306 INFO L78 Accepts]: Start accepts. Automaton has 48 states and 63 transitions. Word has length 24 [2025-03-08 05:12:31,306 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-08 05:12:31,306 INFO L471 AbstractCegarLoop]: Abstraction has 48 states and 63 transitions. [2025-03-08 05:12:31,306 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 1 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) [2025-03-08 05:12:31,306 INFO L276 IsEmpty]: Start isEmpty. Operand 48 states and 63 transitions. [2025-03-08 05:12:31,307 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 35 [2025-03-08 05:12:31,307 INFO L210 NwaCegarLoop]: Found error trace [2025-03-08 05:12:31,307 INFO L218 NwaCegarLoop]: trace histogram [6, 5, 5, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-08 05:12:31,313 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2025-03-08 05:12:31,507 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,3 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-08 05:12:31,507 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-08 05:12:31,508 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-08 05:12:31,508 INFO L85 PathProgramCache]: Analyzing trace with hash -1529814263, now seen corresponding path program 1 times [2025-03-08 05:12:31,508 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-08 05:12:31,508 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [320978722] [2025-03-08 05:12:31,508 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 05:12:31,508 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-08 05:12:31,512 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 34 statements into 1 equivalence classes. [2025-03-08 05:12:31,522 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 34 of 34 statements. [2025-03-08 05:12:31,524 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 05:12:31,524 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-08 05:12:31,524 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1756526449] [2025-03-08 05:12:31,524 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 05:12:31,524 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-08 05:12:31,527 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-08 05:12:31,528 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-08 05:12:31,530 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-08 05:12:31,554 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 34 statements into 1 equivalence classes. [2025-03-08 05:12:31,569 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 34 of 34 statements. [2025-03-08 05:12:31,569 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 05:12:31,569 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 05:12:31,569 INFO L256 TraceCheckSpWp]: Trace formula consists of 113 conjuncts, 13 conjuncts are in the unsatisfiable core [2025-03-08 05:12:31,571 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-08 05:12:31,648 INFO L134 CoverageAnalysis]: Checked inductivity of 53 backedges. 10 proven. 3 refuted. 0 times theorem prover too weak. 40 trivial. 0 not checked. [2025-03-08 05:12:31,648 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-08 05:12:31,710 INFO L134 CoverageAnalysis]: Checked inductivity of 53 backedges. 10 proven. 0 refuted. 0 times theorem prover too weak. 43 trivial. 0 not checked. [2025-03-08 05:12:31,710 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-08 05:12:31,710 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [320978722] [2025-03-08 05:12:31,710 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-08 05:12:31,710 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1756526449] [2025-03-08 05:12:31,710 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1756526449] provided 1 perfect and 1 imperfect interpolant sequences [2025-03-08 05:12:31,710 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2025-03-08 05:12:31,710 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [6] total 7 [2025-03-08 05:12:31,710 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [837148544] [2025-03-08 05:12:31,710 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-08 05:12:31,711 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2025-03-08 05:12:31,711 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-08 05:12:31,711 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2025-03-08 05:12:31,711 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=29, Unknown=0, NotChecked=0, Total=42 [2025-03-08 05:12:31,711 INFO L87 Difference]: Start difference. First operand 48 states and 63 transitions. Second operand has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 1 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) [2025-03-08 05:12:32,827 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.08s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2025-03-08 05:12:32,838 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-08 05:12:32,838 INFO L93 Difference]: Finished difference Result 57 states and 74 transitions. [2025-03-08 05:12:32,838 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2025-03-08 05:12:32,838 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 1 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) Word has length 34 [2025-03-08 05:12:32,839 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-08 05:12:32,840 INFO L225 Difference]: With dead ends: 57 [2025-03-08 05:12:32,840 INFO L226 Difference]: Without dead ends: 55 [2025-03-08 05:12:32,840 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 67 GetRequests, 59 SyntacticMatches, 2 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=17, Invalid=39, Unknown=0, NotChecked=0, Total=56 [2025-03-08 05:12:32,840 INFO L435 NwaCegarLoop]: 23 mSDtfsCounter, 4 mSDsluCounter, 52 mSDsCounter, 0 mSdLazyCounter, 38 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 6 SdHoareTripleChecker+Valid, 75 SdHoareTripleChecker+Invalid, 39 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 38 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.1s IncrementalHoareTripleChecker+Time [2025-03-08 05:12:32,840 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [6 Valid, 75 Invalid, 39 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 38 Invalid, 0 Unknown, 0 Unchecked, 1.1s Time] [2025-03-08 05:12:32,841 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 55 states. [2025-03-08 05:12:32,848 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 55 to 54. [2025-03-08 05:12:32,850 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 54 states, 30 states have (on average 1.2333333333333334) internal successors, (37), 33 states have internal predecessors, (37), 17 states have call successors, (17), 6 states have call predecessors, (17), 6 states have return successors, (16), 14 states have call predecessors, (16), 16 states have call successors, (16) [2025-03-08 05:12:32,852 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 54 states to 54 states and 70 transitions. [2025-03-08 05:12:32,852 INFO L78 Accepts]: Start accepts. Automaton has 54 states and 70 transitions. Word has length 34 [2025-03-08 05:12:32,852 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-08 05:12:32,852 INFO L471 AbstractCegarLoop]: Abstraction has 54 states and 70 transitions. [2025-03-08 05:12:32,852 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 1 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) [2025-03-08 05:12:32,852 INFO L276 IsEmpty]: Start isEmpty. Operand 54 states and 70 transitions. [2025-03-08 05:12:32,853 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 41 [2025-03-08 05:12:32,853 INFO L210 NwaCegarLoop]: Found error trace [2025-03-08 05:12:32,853 INFO L218 NwaCegarLoop]: trace histogram [7, 6, 6, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-08 05:12:32,858 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Ended with exit code 0 [2025-03-08 05:12:33,053 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-08 05:12:33,053 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-08 05:12:33,054 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-08 05:12:33,054 INFO L85 PathProgramCache]: Analyzing trace with hash -1244483954, now seen corresponding path program 1 times [2025-03-08 05:12:33,054 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-08 05:12:33,054 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [607449950] [2025-03-08 05:12:33,054 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 05:12:33,054 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-08 05:12:33,058 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 40 statements into 1 equivalence classes. [2025-03-08 05:12:33,062 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 40 of 40 statements. [2025-03-08 05:12:33,062 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 05:12:33,062 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 05:12:33,137 INFO L134 CoverageAnalysis]: Checked inductivity of 72 backedges. 12 proven. 0 refuted. 0 times theorem prover too weak. 60 trivial. 0 not checked. [2025-03-08 05:12:33,137 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-08 05:12:33,138 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [607449950] [2025-03-08 05:12:33,138 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [607449950] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-08 05:12:33,138 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-08 05:12:33,138 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2025-03-08 05:12:33,138 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [771482747] [2025-03-08 05:12:33,138 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-08 05:12:33,138 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2025-03-08 05:12:33,138 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-08 05:12:33,139 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2025-03-08 05:12:33,139 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2025-03-08 05:12:33,139 INFO L87 Difference]: Start difference. First operand 54 states and 70 transitions. Second operand has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 1 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 1 states have call predecessors, (6), 1 states have call successors, (6) [2025-03-08 05:12:33,176 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-08 05:12:33,177 INFO L93 Difference]: Finished difference Result 62 states and 78 transitions. [2025-03-08 05:12:33,177 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2025-03-08 05:12:33,177 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 1 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 1 states have call predecessors, (6), 1 states have call successors, (6) Word has length 40 [2025-03-08 05:12:33,177 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-08 05:12:33,178 INFO L225 Difference]: With dead ends: 62 [2025-03-08 05:12:33,178 INFO L226 Difference]: Without dead ends: 51 [2025-03-08 05:12:33,178 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 6 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2025-03-08 05:12:33,179 INFO L435 NwaCegarLoop]: 27 mSDtfsCounter, 3 mSDsluCounter, 64 mSDsCounter, 0 mSdLazyCounter, 28 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 3 SdHoareTripleChecker+Valid, 91 SdHoareTripleChecker+Invalid, 28 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 28 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-03-08 05:12:33,179 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [3 Valid, 91 Invalid, 28 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 28 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-03-08 05:12:33,179 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 51 states. [2025-03-08 05:12:33,186 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 51 to 51. [2025-03-08 05:12:33,186 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 51 states, 29 states have (on average 1.206896551724138) internal successors, (35), 32 states have internal predecessors, (35), 15 states have call successors, (15), 6 states have call predecessors, (15), 6 states have return successors, (14), 12 states have call predecessors, (14), 14 states have call successors, (14) [2025-03-08 05:12:33,187 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 51 states to 51 states and 64 transitions. [2025-03-08 05:12:33,187 INFO L78 Accepts]: Start accepts. Automaton has 51 states and 64 transitions. Word has length 40 [2025-03-08 05:12:33,187 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-08 05:12:33,187 INFO L471 AbstractCegarLoop]: Abstraction has 51 states and 64 transitions. [2025-03-08 05:12:33,187 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 1 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 1 states have call predecessors, (6), 1 states have call successors, (6) [2025-03-08 05:12:33,187 INFO L276 IsEmpty]: Start isEmpty. Operand 51 states and 64 transitions. [2025-03-08 05:12:33,188 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 53 [2025-03-08 05:12:33,188 INFO L210 NwaCegarLoop]: Found error trace [2025-03-08 05:12:33,188 INFO L218 NwaCegarLoop]: trace histogram [9, 8, 8, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-08 05:12:33,188 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6 [2025-03-08 05:12:33,188 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-08 05:12:33,188 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-08 05:12:33,188 INFO L85 PathProgramCache]: Analyzing trace with hash 664019262, now seen corresponding path program 1 times [2025-03-08 05:12:33,188 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-08 05:12:33,188 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1386640156] [2025-03-08 05:12:33,188 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 05:12:33,188 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-08 05:12:33,195 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 52 statements into 1 equivalence classes. [2025-03-08 05:12:33,217 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 52 of 52 statements. [2025-03-08 05:12:33,217 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 05:12:33,217 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-08 05:12:33,218 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [311330384] [2025-03-08 05:12:33,218 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 05:12:33,218 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-08 05:12:33,218 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-08 05:12:33,222 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-08 05:12:33,222 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-08 05:12:33,245 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 52 statements into 1 equivalence classes. [2025-03-08 05:12:33,259 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 52 of 52 statements. [2025-03-08 05:12:33,259 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 05:12:33,260 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 05:12:33,260 INFO L256 TraceCheckSpWp]: Trace formula consists of 151 conjuncts, 33 conjuncts are in the unsatisfiable core [2025-03-08 05:12:33,262 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-08 05:12:33,452 INFO L134 CoverageAnalysis]: Checked inductivity of 133 backedges. 15 proven. 27 refuted. 0 times theorem prover too weak. 91 trivial. 0 not checked. [2025-03-08 05:12:33,452 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-08 05:12:34,270 INFO L134 CoverageAnalysis]: Checked inductivity of 133 backedges. 15 proven. 27 refuted. 0 times theorem prover too weak. 91 trivial. 0 not checked. [2025-03-08 05:12:34,270 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-08 05:12:34,270 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1386640156] [2025-03-08 05:12:34,270 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-08 05:12:34,270 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [311330384] [2025-03-08 05:12:34,270 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [311330384] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-08 05:12:34,270 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-03-08 05:12:34,270 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9] total 15 [2025-03-08 05:12:34,271 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [846255472] [2025-03-08 05:12:34,271 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-03-08 05:12:34,271 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 15 states [2025-03-08 05:12:34,271 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-08 05:12:34,271 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2025-03-08 05:12:34,272 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=43, Invalid=167, Unknown=0, NotChecked=0, Total=210 [2025-03-08 05:12:34,272 INFO L87 Difference]: Start difference. First operand 51 states and 64 transitions. Second operand has 15 states, 12 states have (on average 2.1666666666666665) internal successors, (26), 14 states have internal predecessors, (26), 7 states have call successors, (18), 3 states have call predecessors, (18), 2 states have return successors, (16), 4 states have call predecessors, (16), 5 states have call successors, (16) [2025-03-08 05:12:34,718 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-08 05:12:34,718 INFO L93 Difference]: Finished difference Result 116 states and 161 transitions. [2025-03-08 05:12:34,719 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2025-03-08 05:12:34,719 INFO L78 Accepts]: Start accepts. Automaton has has 15 states, 12 states have (on average 2.1666666666666665) internal successors, (26), 14 states have internal predecessors, (26), 7 states have call successors, (18), 3 states have call predecessors, (18), 2 states have return successors, (16), 4 states have call predecessors, (16), 5 states have call successors, (16) Word has length 52 [2025-03-08 05:12:34,719 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-08 05:12:34,720 INFO L225 Difference]: With dead ends: 116 [2025-03-08 05:12:34,720 INFO L226 Difference]: Without dead ends: 95 [2025-03-08 05:12:34,720 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 106 GetRequests, 89 SyntacticMatches, 0 SemanticMatches, 17 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 28 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=76, Invalid=266, Unknown=0, NotChecked=0, Total=342 [2025-03-08 05:12:34,721 INFO L435 NwaCegarLoop]: 20 mSDtfsCounter, 27 mSDsluCounter, 134 mSDsCounter, 0 mSdLazyCounter, 303 mSolverCounterSat, 59 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 32 SdHoareTripleChecker+Valid, 154 SdHoareTripleChecker+Invalid, 362 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 59 IncrementalHoareTripleChecker+Valid, 303 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2025-03-08 05:12:34,721 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [32 Valid, 154 Invalid, 362 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [59 Valid, 303 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2025-03-08 05:12:34,721 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 95 states. [2025-03-08 05:12:34,745 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 95 to 93. [2025-03-08 05:12:34,746 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 93 states, 51 states have (on average 1.2745098039215685) internal successors, (65), 56 states have internal predecessors, (65), 31 states have call successors, (31), 10 states have call predecessors, (31), 10 states have return successors, (30), 26 states have call predecessors, (30), 30 states have call successors, (30) [2025-03-08 05:12:34,747 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 93 states to 93 states and 126 transitions. [2025-03-08 05:12:34,747 INFO L78 Accepts]: Start accepts. Automaton has 93 states and 126 transitions. Word has length 52 [2025-03-08 05:12:34,747 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-08 05:12:34,747 INFO L471 AbstractCegarLoop]: Abstraction has 93 states and 126 transitions. [2025-03-08 05:12:34,747 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 15 states, 12 states have (on average 2.1666666666666665) internal successors, (26), 14 states have internal predecessors, (26), 7 states have call successors, (18), 3 states have call predecessors, (18), 2 states have return successors, (16), 4 states have call predecessors, (16), 5 states have call successors, (16) [2025-03-08 05:12:34,747 INFO L276 IsEmpty]: Start isEmpty. Operand 93 states and 126 transitions. [2025-03-08 05:12:34,748 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 64 [2025-03-08 05:12:34,748 INFO L210 NwaCegarLoop]: Found error trace [2025-03-08 05:12:34,748 INFO L218 NwaCegarLoop]: trace histogram [11, 10, 10, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-08 05:12:34,756 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Ended with exit code 0 [2025-03-08 05:12:34,948 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-08 05:12:34,949 INFO L396 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-08 05:12:34,950 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-08 05:12:34,950 INFO L85 PathProgramCache]: Analyzing trace with hash 832756608, now seen corresponding path program 1 times [2025-03-08 05:12:34,950 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-08 05:12:34,950 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [643817271] [2025-03-08 05:12:34,950 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 05:12:34,950 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-08 05:12:34,956 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 63 statements into 1 equivalence classes. [2025-03-08 05:12:34,978 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 63 of 63 statements. [2025-03-08 05:12:34,979 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 05:12:34,979 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-08 05:12:34,980 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1931033517] [2025-03-08 05:12:34,981 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 05:12:34,981 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-08 05:12:34,981 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-08 05:12:34,983 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-08 05:12:34,984 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-08 05:12:35,008 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 63 statements into 1 equivalence classes. [2025-03-08 05:12:35,029 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 63 of 63 statements. [2025-03-08 05:12:35,030 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 05:12:35,030 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 05:12:35,031 INFO L256 TraceCheckSpWp]: Trace formula consists of 171 conjuncts, 35 conjuncts are in the unsatisfiable core [2025-03-08 05:12:35,033 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-08 05:12:35,210 INFO L134 CoverageAnalysis]: Checked inductivity of 207 backedges. 19 proven. 35 refuted. 0 times theorem prover too weak. 153 trivial. 0 not checked. [2025-03-08 05:12:35,211 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-08 05:12:35,610 INFO L134 CoverageAnalysis]: Checked inductivity of 207 backedges. 19 proven. 35 refuted. 0 times theorem prover too weak. 153 trivial. 0 not checked. [2025-03-08 05:12:35,611 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-08 05:12:35,611 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [643817271] [2025-03-08 05:12:35,611 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-08 05:12:35,611 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1931033517] [2025-03-08 05:12:35,611 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1931033517] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-08 05:12:35,611 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-03-08 05:12:35,611 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 9] total 16 [2025-03-08 05:12:35,611 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [29535294] [2025-03-08 05:12:35,611 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-03-08 05:12:35,612 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2025-03-08 05:12:35,612 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-08 05:12:35,612 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2025-03-08 05:12:35,614 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=53, Invalid=187, Unknown=0, NotChecked=0, Total=240 [2025-03-08 05:12:35,614 INFO L87 Difference]: Start difference. First operand 93 states and 126 transitions. Second operand has 16 states, 13 states have (on average 2.1538461538461537) internal successors, (28), 15 states have internal predecessors, (28), 8 states have call successors, (22), 3 states have call predecessors, (22), 2 states have return successors, (20), 5 states have call predecessors, (20), 6 states have call successors, (20) [2025-03-08 05:12:35,925 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-08 05:12:35,925 INFO L93 Difference]: Finished difference Result 142 states and 195 transitions. [2025-03-08 05:12:35,925 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2025-03-08 05:12:35,925 INFO L78 Accepts]: Start accepts. Automaton has has 16 states, 13 states have (on average 2.1538461538461537) internal successors, (28), 15 states have internal predecessors, (28), 8 states have call successors, (22), 3 states have call predecessors, (22), 2 states have return successors, (20), 5 states have call predecessors, (20), 6 states have call successors, (20) Word has length 63 [2025-03-08 05:12:35,926 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-08 05:12:35,927 INFO L225 Difference]: With dead ends: 142 [2025-03-08 05:12:35,929 INFO L226 Difference]: Without dead ends: 115 [2025-03-08 05:12:35,930 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 127 GetRequests, 110 SyntacticMatches, 0 SemanticMatches, 17 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 28 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=79, Invalid=263, Unknown=0, NotChecked=0, Total=342 [2025-03-08 05:12:35,930 INFO L435 NwaCegarLoop]: 24 mSDtfsCounter, 12 mSDsluCounter, 143 mSDsCounter, 0 mSdLazyCounter, 254 mSolverCounterSat, 36 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 17 SdHoareTripleChecker+Valid, 167 SdHoareTripleChecker+Invalid, 290 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 36 IncrementalHoareTripleChecker+Valid, 254 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2025-03-08 05:12:35,930 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [17 Valid, 167 Invalid, 290 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [36 Valid, 254 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2025-03-08 05:12:35,931 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 115 states. [2025-03-08 05:12:35,958 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 115 to 91. [2025-03-08 05:12:35,959 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 91 states, 51 states have (on average 1.2156862745098038) internal successors, (62), 56 states have internal predecessors, (62), 28 states have call successors, (28), 11 states have call predecessors, (28), 11 states have return successors, (27), 23 states have call predecessors, (27), 27 states have call successors, (27) [2025-03-08 05:12:35,960 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 91 states to 91 states and 117 transitions. [2025-03-08 05:12:35,961 INFO L78 Accepts]: Start accepts. Automaton has 91 states and 117 transitions. Word has length 63 [2025-03-08 05:12:35,962 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-08 05:12:35,963 INFO L471 AbstractCegarLoop]: Abstraction has 91 states and 117 transitions. [2025-03-08 05:12:35,963 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 16 states, 13 states have (on average 2.1538461538461537) internal successors, (28), 15 states have internal predecessors, (28), 8 states have call successors, (22), 3 states have call predecessors, (22), 2 states have return successors, (20), 5 states have call predecessors, (20), 6 states have call successors, (20) [2025-03-08 05:12:35,963 INFO L276 IsEmpty]: Start isEmpty. Operand 91 states and 117 transitions. [2025-03-08 05:12:35,967 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 69 [2025-03-08 05:12:35,967 INFO L210 NwaCegarLoop]: Found error trace [2025-03-08 05:12:35,967 INFO L218 NwaCegarLoop]: trace histogram [12, 11, 11, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-08 05:12:35,974 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-08 05:12:36,167 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-08 05:12:36,168 INFO L396 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-08 05:12:36,168 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-08 05:12:36,168 INFO L85 PathProgramCache]: Analyzing trace with hash 1361922143, now seen corresponding path program 1 times [2025-03-08 05:12:36,168 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-08 05:12:36,168 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [20142440] [2025-03-08 05:12:36,168 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 05:12:36,168 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-08 05:12:36,173 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 68 statements into 1 equivalence classes. [2025-03-08 05:12:36,186 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 68 of 68 statements. [2025-03-08 05:12:36,186 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 05:12:36,186 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 05:12:36,439 INFO L134 CoverageAnalysis]: Checked inductivity of 249 backedges. 22 proven. 7 refuted. 0 times theorem prover too weak. 220 trivial. 0 not checked. [2025-03-08 05:12:36,439 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-08 05:12:36,439 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [20142440] [2025-03-08 05:12:36,439 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [20142440] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-08 05:12:36,439 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1358686829] [2025-03-08 05:12:36,439 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 05:12:36,439 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-08 05:12:36,440 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-08 05:12:36,441 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-08 05:12:36,443 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-08 05:12:36,465 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 68 statements into 1 equivalence classes. [2025-03-08 05:12:36,482 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 68 of 68 statements. [2025-03-08 05:12:36,482 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 05:12:36,482 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 05:12:36,483 INFO L256 TraceCheckSpWp]: Trace formula consists of 180 conjuncts, 19 conjuncts are in the unsatisfiable core [2025-03-08 05:12:36,485 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-08 05:12:36,599 INFO L134 CoverageAnalysis]: Checked inductivity of 249 backedges. 22 proven. 7 refuted. 0 times theorem prover too weak. 220 trivial. 0 not checked. [2025-03-08 05:12:36,599 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-08 05:12:36,851 INFO L134 CoverageAnalysis]: Checked inductivity of 249 backedges. 22 proven. 7 refuted. 0 times theorem prover too weak. 220 trivial. 0 not checked. [2025-03-08 05:12:36,852 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1358686829] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-08 05:12:36,852 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-08 05:12:36,852 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7, 7] total 13 [2025-03-08 05:12:36,852 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [65040155] [2025-03-08 05:12:36,852 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-08 05:12:36,852 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 13 states [2025-03-08 05:12:36,852 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-08 05:12:36,853 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2025-03-08 05:12:36,853 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=36, Invalid=120, Unknown=0, NotChecked=0, Total=156 [2025-03-08 05:12:36,853 INFO L87 Difference]: Start difference. First operand 91 states and 117 transitions. Second operand has 13 states, 13 states have (on average 2.230769230769231) internal successors, (29), 11 states have internal predecessors, (29), 7 states have call successors, (35), 3 states have call predecessors, (35), 1 states have return successors, (32), 7 states have call predecessors, (32), 7 states have call successors, (32) [2025-03-08 05:12:36,998 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-08 05:12:36,998 INFO L93 Difference]: Finished difference Result 110 states and 136 transitions. [2025-03-08 05:12:36,999 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2025-03-08 05:12:36,999 INFO L78 Accepts]: Start accepts. Automaton has has 13 states, 13 states have (on average 2.230769230769231) internal successors, (29), 11 states have internal predecessors, (29), 7 states have call successors, (35), 3 states have call predecessors, (35), 1 states have return successors, (32), 7 states have call predecessors, (32), 7 states have call successors, (32) Word has length 68 [2025-03-08 05:12:36,999 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-08 05:12:37,000 INFO L225 Difference]: With dead ends: 110 [2025-03-08 05:12:37,000 INFO L226 Difference]: Without dead ends: 84 [2025-03-08 05:12:37,000 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 143 GetRequests, 128 SyntacticMatches, 2 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 40 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=48, Invalid=162, Unknown=0, NotChecked=0, Total=210 [2025-03-08 05:12:37,001 INFO L435 NwaCegarLoop]: 29 mSDtfsCounter, 9 mSDsluCounter, 124 mSDsCounter, 0 mSdLazyCounter, 125 mSolverCounterSat, 10 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 9 SdHoareTripleChecker+Valid, 153 SdHoareTripleChecker+Invalid, 135 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 10 IncrementalHoareTripleChecker+Valid, 125 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-08 05:12:37,001 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [9 Valid, 153 Invalid, 135 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [10 Valid, 125 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-08 05:12:37,001 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 84 states. [2025-03-08 05:12:37,019 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 84 to 84. [2025-03-08 05:12:37,020 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 84 states, 49 states have (on average 1.1428571428571428) internal successors, (56), 52 states have internal predecessors, (56), 23 states have call successors, (23), 11 states have call predecessors, (23), 11 states have return successors, (22), 20 states have call predecessors, (22), 22 states have call successors, (22) [2025-03-08 05:12:37,021 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 84 states to 84 states and 101 transitions. [2025-03-08 05:12:37,022 INFO L78 Accepts]: Start accepts. Automaton has 84 states and 101 transitions. Word has length 68 [2025-03-08 05:12:37,022 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-08 05:12:37,022 INFO L471 AbstractCegarLoop]: Abstraction has 84 states and 101 transitions. [2025-03-08 05:12:37,022 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 13 states, 13 states have (on average 2.230769230769231) internal successors, (29), 11 states have internal predecessors, (29), 7 states have call successors, (35), 3 states have call predecessors, (35), 1 states have return successors, (32), 7 states have call predecessors, (32), 7 states have call successors, (32) [2025-03-08 05:12:37,022 INFO L276 IsEmpty]: Start isEmpty. Operand 84 states and 101 transitions. [2025-03-08 05:12:37,023 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 81 [2025-03-08 05:12:37,023 INFO L210 NwaCegarLoop]: Found error trace [2025-03-08 05:12:37,023 INFO L218 NwaCegarLoop]: trace histogram [14, 13, 13, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1] [2025-03-08 05:12:37,029 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Forceful destruction successful, exit code 0 [2025-03-08 05:12:37,224 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable9,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-08 05:12:37,224 INFO L396 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-08 05:12:37,224 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-08 05:12:37,224 INFO L85 PathProgramCache]: Analyzing trace with hash 481284239, now seen corresponding path program 2 times [2025-03-08 05:12:37,224 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-08 05:12:37,224 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [523286896] [2025-03-08 05:12:37,224 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-08 05:12:37,225 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-08 05:12:37,229 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 80 statements into 2 equivalence classes. [2025-03-08 05:12:37,254 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 80 of 80 statements. [2025-03-08 05:12:37,254 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-08 05:12:37,254 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-08 05:12:37,256 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1941052586] [2025-03-08 05:12:37,256 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-08 05:12:37,256 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-08 05:12:37,256 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-08 05:12:37,258 INFO L229 MonitoredProcess]: Starting monitored process 8 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-08 05:12:37,259 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2025-03-08 05:12:37,283 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 80 statements into 2 equivalence classes. [2025-03-08 05:12:37,304 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 80 of 80 statements. [2025-03-08 05:12:37,304 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-08 05:12:37,304 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 05:12:37,305 INFO L256 TraceCheckSpWp]: Trace formula consists of 211 conjuncts, 45 conjuncts are in the unsatisfiable core [2025-03-08 05:12:37,307 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-08 05:12:37,554 INFO L134 CoverageAnalysis]: Checked inductivity of 356 backedges. 28 proven. 52 refuted. 0 times theorem prover too weak. 276 trivial. 0 not checked. [2025-03-08 05:12:37,554 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-08 05:12:43,650 INFO L134 CoverageAnalysis]: Checked inductivity of 356 backedges. 28 proven. 52 refuted. 0 times theorem prover too weak. 276 trivial. 0 not checked. [2025-03-08 05:12:43,650 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-08 05:12:43,650 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [523286896] [2025-03-08 05:12:43,651 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-08 05:12:43,651 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1941052586] [2025-03-08 05:12:43,651 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1941052586] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-08 05:12:43,651 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-03-08 05:12:43,651 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 12] total 21 [2025-03-08 05:12:43,652 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1943220464] [2025-03-08 05:12:43,652 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-03-08 05:12:43,652 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 21 states [2025-03-08 05:12:43,652 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-08 05:12:43,653 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2025-03-08 05:12:43,653 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=82, Invalid=338, Unknown=0, NotChecked=0, Total=420 [2025-03-08 05:12:43,653 INFO L87 Difference]: Start difference. First operand 84 states and 101 transitions. Second operand has 21 states, 18 states have (on average 1.7777777777777777) internal successors, (32), 19 states have internal predecessors, (32), 11 states have call successors, (28), 3 states have call predecessors, (28), 2 states have return successors, (26), 9 states have call predecessors, (26), 9 states have call successors, (26) [2025-03-08 05:12:49,631 WARN L286 SmtUtils]: Spent 5.76s on a formula simplification. DAG size of input: 168 DAG size of output: 83 (called from [L 388] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2025-03-08 05:12:52,639 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-08 05:12:52,639 INFO L93 Difference]: Finished difference Result 172 states and 235 transitions. [2025-03-08 05:12:52,640 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 18 states. [2025-03-08 05:12:52,640 INFO L78 Accepts]: Start accepts. Automaton has has 21 states, 18 states have (on average 1.7777777777777777) internal successors, (32), 19 states have internal predecessors, (32), 11 states have call successors, (28), 3 states have call predecessors, (28), 2 states have return successors, (26), 9 states have call predecessors, (26), 9 states have call successors, (26) Word has length 80 [2025-03-08 05:12:52,640 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-08 05:12:52,641 INFO L225 Difference]: With dead ends: 172 [2025-03-08 05:12:52,641 INFO L226 Difference]: Without dead ends: 142 [2025-03-08 05:12:52,642 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 164 GetRequests, 139 SyntacticMatches, 0 SemanticMatches, 25 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 52 ImplicationChecksByTransitivity, 7.0s TimeCoverageRelationStatistics Valid=158, Invalid=544, Unknown=0, NotChecked=0, Total=702 [2025-03-08 05:12:52,642 INFO L435 NwaCegarLoop]: 29 mSDtfsCounter, 46 mSDsluCounter, 208 mSDsCounter, 0 mSdLazyCounter, 519 mSolverCounterSat, 114 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 2.7s Time, 0 mProtectedPredicate, 0 mProtectedAction, 55 SdHoareTripleChecker+Valid, 237 SdHoareTripleChecker+Invalid, 633 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 114 IncrementalHoareTripleChecker+Valid, 519 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 2.7s IncrementalHoareTripleChecker+Time [2025-03-08 05:12:52,642 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [55 Valid, 237 Invalid, 633 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [114 Valid, 519 Invalid, 0 Unknown, 0 Unchecked, 2.7s Time] [2025-03-08 05:12:52,642 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 142 states. [2025-03-08 05:12:52,665 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 142 to 138. [2025-03-08 05:12:52,665 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 138 states, 74 states have (on average 1.2432432432432432) internal successors, (92), 82 states have internal predecessors, (92), 49 states have call successors, (49), 14 states have call predecessors, (49), 14 states have return successors, (48), 41 states have call predecessors, (48), 48 states have call successors, (48) [2025-03-08 05:12:52,666 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 138 states to 138 states and 189 transitions. [2025-03-08 05:12:52,666 INFO L78 Accepts]: Start accepts. Automaton has 138 states and 189 transitions. Word has length 80 [2025-03-08 05:12:52,666 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-08 05:12:52,666 INFO L471 AbstractCegarLoop]: Abstraction has 138 states and 189 transitions. [2025-03-08 05:12:52,667 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 21 states, 18 states have (on average 1.7777777777777777) internal successors, (32), 19 states have internal predecessors, (32), 11 states have call successors, (28), 3 states have call predecessors, (28), 2 states have return successors, (26), 9 states have call predecessors, (26), 9 states have call successors, (26) [2025-03-08 05:12:52,667 INFO L276 IsEmpty]: Start isEmpty. Operand 138 states and 189 transitions. [2025-03-08 05:12:52,669 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 92 [2025-03-08 05:12:52,669 INFO L210 NwaCegarLoop]: Found error trace [2025-03-08 05:12:52,669 INFO L218 NwaCegarLoop]: trace histogram [16, 15, 15, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-08 05:12:52,675 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Forceful destruction successful, exit code 0 [2025-03-08 05:12:52,869 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable10,8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-08 05:12:52,870 INFO L396 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-08 05:12:52,870 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-08 05:12:52,870 INFO L85 PathProgramCache]: Analyzing trace with hash 1827217295, now seen corresponding path program 2 times [2025-03-08 05:12:52,870 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-08 05:12:52,870 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1854376342] [2025-03-08 05:12:52,870 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-08 05:12:52,870 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-08 05:12:52,875 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 91 statements into 2 equivalence classes. [2025-03-08 05:12:52,899 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 91 of 91 statements. [2025-03-08 05:12:52,899 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-08 05:12:52,899 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-08 05:12:52,900 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [774567521] [2025-03-08 05:12:52,900 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-08 05:12:52,900 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-08 05:12:52,900 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-08 05:12:52,903 INFO L229 MonitoredProcess]: Starting monitored process 9 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-08 05:12:52,904 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2025-03-08 05:12:52,926 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 91 statements into 2 equivalence classes. [2025-03-08 05:12:52,946 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 91 of 91 statements. [2025-03-08 05:12:52,946 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-08 05:12:52,946 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 05:12:52,947 INFO L256 TraceCheckSpWp]: Trace formula consists of 231 conjuncts, 48 conjuncts are in the unsatisfiable core [2025-03-08 05:12:52,949 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-08 05:12:53,209 INFO L134 CoverageAnalysis]: Checked inductivity of 472 backedges. 32 proven. 62 refuted. 0 times theorem prover too weak. 378 trivial. 0 not checked. [2025-03-08 05:12:53,209 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-08 05:12:57,779 INFO L134 CoverageAnalysis]: Checked inductivity of 472 backedges. 32 proven. 62 refuted. 0 times theorem prover too weak. 378 trivial. 0 not checked. [2025-03-08 05:12:57,779 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-08 05:12:57,779 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1854376342] [2025-03-08 05:12:57,779 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-08 05:12:57,779 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [774567521] [2025-03-08 05:12:57,779 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [774567521] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-08 05:12:57,779 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-03-08 05:12:57,779 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [15, 15] total 27 [2025-03-08 05:12:57,779 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1213995447] [2025-03-08 05:12:57,779 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-03-08 05:12:57,780 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 27 states [2025-03-08 05:12:57,780 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-08 05:12:57,780 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 27 interpolants. [2025-03-08 05:12:57,781 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=147, Invalid=555, Unknown=0, NotChecked=0, Total=702 [2025-03-08 05:12:57,781 INFO L87 Difference]: Start difference. First operand 138 states and 189 transitions. Second operand has 27 states, 24 states have (on average 1.4166666666666667) internal successors, (34), 25 states have internal predecessors, (34), 15 states have call successors, (32), 3 states have call predecessors, (32), 2 states have return successors, (30), 13 states have call predecessors, (30), 13 states have call successors, (30) [2025-03-08 05:13:00,902 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-08 05:13:00,902 INFO L93 Difference]: Finished difference Result 213 states and 303 transitions. [2025-03-08 05:13:00,903 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 26 states. [2025-03-08 05:13:00,903 INFO L78 Accepts]: Start accepts. Automaton has has 27 states, 24 states have (on average 1.4166666666666667) internal successors, (34), 25 states have internal predecessors, (34), 15 states have call successors, (32), 3 states have call predecessors, (32), 2 states have return successors, (30), 13 states have call predecessors, (30), 13 states have call successors, (30) Word has length 91 [2025-03-08 05:13:00,903 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-08 05:13:00,905 INFO L225 Difference]: With dead ends: 213 [2025-03-08 05:13:00,905 INFO L226 Difference]: Without dead ends: 176 [2025-03-08 05:13:00,905 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 190 GetRequests, 155 SyntacticMatches, 0 SemanticMatches, 35 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 205 ImplicationChecksByTransitivity, 2.8s TimeCoverageRelationStatistics Valid=310, Invalid=1022, Unknown=0, NotChecked=0, Total=1332 [2025-03-08 05:13:00,906 INFO L435 NwaCegarLoop]: 31 mSDtfsCounter, 38 mSDsluCounter, 282 mSDsCounter, 0 mSdLazyCounter, 630 mSolverCounterSat, 153 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.8s Time, 0 mProtectedPredicate, 0 mProtectedAction, 46 SdHoareTripleChecker+Valid, 313 SdHoareTripleChecker+Invalid, 783 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 153 IncrementalHoareTripleChecker+Valid, 630 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.8s IncrementalHoareTripleChecker+Time [2025-03-08 05:13:00,906 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [46 Valid, 313 Invalid, 783 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [153 Valid, 630 Invalid, 0 Unknown, 0 Unchecked, 0.8s Time] [2025-03-08 05:13:00,906 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 176 states. [2025-03-08 05:13:00,938 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 176 to 144. [2025-03-08 05:13:00,938 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 144 states, 78 states have (on average 1.2435897435897436) internal successors, (97), 85 states have internal predecessors, (97), 50 states have call successors, (50), 15 states have call predecessors, (50), 15 states have return successors, (49), 43 states have call predecessors, (49), 49 states have call successors, (49) [2025-03-08 05:13:00,939 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 144 states to 144 states and 196 transitions. [2025-03-08 05:13:00,939 INFO L78 Accepts]: Start accepts. Automaton has 144 states and 196 transitions. Word has length 91 [2025-03-08 05:13:00,940 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-08 05:13:00,940 INFO L471 AbstractCegarLoop]: Abstraction has 144 states and 196 transitions. [2025-03-08 05:13:00,940 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 27 states, 24 states have (on average 1.4166666666666667) internal successors, (34), 25 states have internal predecessors, (34), 15 states have call successors, (32), 3 states have call predecessors, (32), 2 states have return successors, (30), 13 states have call predecessors, (30), 13 states have call successors, (30) [2025-03-08 05:13:00,940 INFO L276 IsEmpty]: Start isEmpty. Operand 144 states and 196 transitions. [2025-03-08 05:13:00,941 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 92 [2025-03-08 05:13:00,941 INFO L210 NwaCegarLoop]: Found error trace [2025-03-08 05:13:00,941 INFO L218 NwaCegarLoop]: trace histogram [16, 15, 15, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-08 05:13:00,947 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Ended with exit code 0 [2025-03-08 05:13:01,141 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 9 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable11 [2025-03-08 05:13:01,142 INFO L396 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-08 05:13:01,142 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-08 05:13:01,142 INFO L85 PathProgramCache]: Analyzing trace with hash 1316683118, now seen corresponding path program 1 times [2025-03-08 05:13:01,142 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-08 05:13:01,142 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [459103906] [2025-03-08 05:13:01,142 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 05:13:01,142 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-08 05:13:01,145 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 91 statements into 1 equivalence classes. [2025-03-08 05:13:01,160 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 91 of 91 statements. [2025-03-08 05:13:01,161 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 05:13:01,161 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-08 05:13:01,161 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1488777942] [2025-03-08 05:13:01,163 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 05:13:01,164 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-08 05:13:01,164 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-08 05:13:01,165 INFO L229 MonitoredProcess]: Starting monitored process 10 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-08 05:13:01,167 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Waiting until timeout for monitored process [2025-03-08 05:13:01,189 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 91 statements into 1 equivalence classes. [2025-03-08 05:13:01,208 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 91 of 91 statements. [2025-03-08 05:13:01,208 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 05:13:01,208 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 05:13:01,209 INFO L256 TraceCheckSpWp]: Trace formula consists of 227 conjuncts, 45 conjuncts are in the unsatisfiable core [2025-03-08 05:13:01,211 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-08 05:13:01,390 INFO L134 CoverageAnalysis]: Checked inductivity of 472 backedges. 29 proven. 65 refuted. 0 times theorem prover too weak. 378 trivial. 0 not checked. [2025-03-08 05:13:01,390 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-08 05:13:01,797 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-08 05:13:01,797 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [459103906] [2025-03-08 05:13:01,797 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-08 05:13:01,797 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1488777942] [2025-03-08 05:13:01,797 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1488777942] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-08 05:13:01,797 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2025-03-08 05:13:01,797 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13] total 13 [2025-03-08 05:13:01,797 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1272055433] [2025-03-08 05:13:01,798 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2025-03-08 05:13:01,798 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 13 states [2025-03-08 05:13:01,798 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-08 05:13:01,798 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2025-03-08 05:13:01,798 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=85, Invalid=295, Unknown=0, NotChecked=0, Total=380 [2025-03-08 05:13:01,798 INFO L87 Difference]: Start difference. First operand 144 states and 196 transitions. Second operand has 13 states, 12 states have (on average 1.75) internal successors, (21), 12 states have internal predecessors, (21), 6 states have call successors, (16), 2 states have call predecessors, (16), 2 states have return successors, (15), 5 states have call predecessors, (15), 5 states have call successors, (15) [2025-03-08 05:13:02,032 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-08 05:13:02,032 INFO L93 Difference]: Finished difference Result 154 states and 207 transitions. [2025-03-08 05:13:02,032 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2025-03-08 05:13:02,033 INFO L78 Accepts]: Start accepts. Automaton has has 13 states, 12 states have (on average 1.75) internal successors, (21), 12 states have internal predecessors, (21), 6 states have call successors, (16), 2 states have call predecessors, (16), 2 states have return successors, (15), 5 states have call predecessors, (15), 5 states have call successors, (15) Word has length 91 [2025-03-08 05:13:02,033 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-08 05:13:02,034 INFO L225 Difference]: With dead ends: 154 [2025-03-08 05:13:02,034 INFO L226 Difference]: Without dead ends: 152 [2025-03-08 05:13:02,034 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 121 GetRequests, 102 SyntacticMatches, 0 SemanticMatches, 19 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 40 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=92, Invalid=328, Unknown=0, NotChecked=0, Total=420 [2025-03-08 05:13:02,035 INFO L435 NwaCegarLoop]: 30 mSDtfsCounter, 5 mSDsluCounter, 213 mSDsCounter, 0 mSdLazyCounter, 471 mSolverCounterSat, 10 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 10 SdHoareTripleChecker+Valid, 243 SdHoareTripleChecker+Invalid, 481 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 10 IncrementalHoareTripleChecker+Valid, 471 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2025-03-08 05:13:02,035 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [10 Valid, 243 Invalid, 481 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [10 Valid, 471 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2025-03-08 05:13:02,035 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 152 states. [2025-03-08 05:13:02,065 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 152 to 142. [2025-03-08 05:13:02,066 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 142 states, 77 states have (on average 1.2467532467532467) internal successors, (96), 85 states have internal predecessors, (96), 49 states have call successors, (49), 15 states have call predecessors, (49), 15 states have return successors, (48), 41 states have call predecessors, (48), 48 states have call successors, (48) [2025-03-08 05:13:02,066 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 142 states to 142 states and 193 transitions. [2025-03-08 05:13:02,067 INFO L78 Accepts]: Start accepts. Automaton has 142 states and 193 transitions. Word has length 91 [2025-03-08 05:13:02,067 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-08 05:13:02,067 INFO L471 AbstractCegarLoop]: Abstraction has 142 states and 193 transitions. [2025-03-08 05:13:02,067 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 13 states, 12 states have (on average 1.75) internal successors, (21), 12 states have internal predecessors, (21), 6 states have call successors, (16), 2 states have call predecessors, (16), 2 states have return successors, (15), 5 states have call predecessors, (15), 5 states have call successors, (15) [2025-03-08 05:13:02,067 INFO L276 IsEmpty]: Start isEmpty. Operand 142 states and 193 transitions. [2025-03-08 05:13:02,068 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 97 [2025-03-08 05:13:02,068 INFO L210 NwaCegarLoop]: Found error trace [2025-03-08 05:13:02,068 INFO L218 NwaCegarLoop]: trace histogram [17, 16, 16, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-08 05:13:02,075 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Forceful destruction successful, exit code 0 [2025-03-08 05:13:02,268 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 10 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable12 [2025-03-08 05:13:02,268 INFO L396 AbstractCegarLoop]: === Iteration 14 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-08 05:13:02,269 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-08 05:13:02,269 INFO L85 PathProgramCache]: Analyzing trace with hash 1422538160, now seen corresponding path program 2 times [2025-03-08 05:13:02,269 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-08 05:13:02,269 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1704628489] [2025-03-08 05:13:02,269 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-08 05:13:02,269 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-08 05:13:02,272 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 96 statements into 2 equivalence classes. [2025-03-08 05:13:02,292 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 96 of 96 statements. [2025-03-08 05:13:02,292 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-08 05:13:02,292 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 05:13:02,542 INFO L134 CoverageAnalysis]: Checked inductivity of 534 backedges. 32 proven. 22 refuted. 0 times theorem prover too weak. 480 trivial. 0 not checked. [2025-03-08 05:13:02,542 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-08 05:13:02,542 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1704628489] [2025-03-08 05:13:02,542 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1704628489] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-08 05:13:02,542 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2043110170] [2025-03-08 05:13:02,542 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-08 05:13:02,543 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-08 05:13:02,543 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-08 05:13:02,544 INFO L229 MonitoredProcess]: Starting monitored process 11 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-08 05:13:02,546 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Waiting until timeout for monitored process [2025-03-08 05:13:02,569 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 96 statements into 2 equivalence classes. [2025-03-08 05:13:02,589 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 96 of 96 statements. [2025-03-08 05:13:02,589 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-08 05:13:02,589 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 05:13:02,590 INFO L256 TraceCheckSpWp]: Trace formula consists of 240 conjuncts, 31 conjuncts are in the unsatisfiable core [2025-03-08 05:13:02,592 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-08 05:13:02,768 INFO L134 CoverageAnalysis]: Checked inductivity of 534 backedges. 32 proven. 22 refuted. 0 times theorem prover too weak. 480 trivial. 0 not checked. [2025-03-08 05:13:02,768 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-08 05:13:03,299 INFO L134 CoverageAnalysis]: Checked inductivity of 534 backedges. 32 proven. 22 refuted. 0 times theorem prover too weak. 480 trivial. 0 not checked. [2025-03-08 05:13:03,299 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2043110170] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-08 05:13:03,299 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-08 05:13:03,299 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 10, 8] total 19 [2025-03-08 05:13:03,299 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1372876292] [2025-03-08 05:13:03,299 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-08 05:13:03,300 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 19 states [2025-03-08 05:13:03,300 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-08 05:13:03,300 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 19 interpolants. [2025-03-08 05:13:03,300 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=70, Invalid=272, Unknown=0, NotChecked=0, Total=342 [2025-03-08 05:13:03,300 INFO L87 Difference]: Start difference. First operand 142 states and 193 transitions. Second operand has 19 states, 19 states have (on average 2.0) internal successors, (38), 17 states have internal predecessors, (38), 13 states have call successors, (50), 3 states have call predecessors, (50), 1 states have return successors, (47), 13 states have call predecessors, (47), 13 states have call successors, (47) [2025-03-08 05:13:03,559 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-08 05:13:03,559 INFO L93 Difference]: Finished difference Result 200 states and 264 transitions. [2025-03-08 05:13:03,560 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2025-03-08 05:13:03,560 INFO L78 Accepts]: Start accepts. Automaton has has 19 states, 19 states have (on average 2.0) internal successors, (38), 17 states have internal predecessors, (38), 13 states have call successors, (50), 3 states have call predecessors, (50), 1 states have return successors, (47), 13 states have call predecessors, (47), 13 states have call successors, (47) Word has length 96 [2025-03-08 05:13:03,560 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-08 05:13:03,561 INFO L225 Difference]: With dead ends: 200 [2025-03-08 05:13:03,561 INFO L226 Difference]: Without dead ends: 117 [2025-03-08 05:13:03,561 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 202 GetRequests, 179 SyntacticMatches, 3 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 134 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=96, Invalid=366, Unknown=0, NotChecked=0, Total=462 [2025-03-08 05:13:03,562 INFO L435 NwaCegarLoop]: 37 mSDtfsCounter, 15 mSDsluCounter, 257 mSDsCounter, 0 mSdLazyCounter, 305 mSolverCounterSat, 13 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 19 SdHoareTripleChecker+Valid, 294 SdHoareTripleChecker+Invalid, 318 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 13 IncrementalHoareTripleChecker+Valid, 305 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-08 05:13:03,562 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [19 Valid, 294 Invalid, 318 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [13 Valid, 305 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-08 05:13:03,562 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 117 states. [2025-03-08 05:13:03,586 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 117 to 117. [2025-03-08 05:13:03,586 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 117 states, 67 states have (on average 1.1492537313432836) internal successors, (77), 72 states have internal predecessors, (77), 34 states have call successors, (34), 15 states have call predecessors, (34), 15 states have return successors, (32), 29 states have call predecessors, (32), 32 states have call successors, (32) [2025-03-08 05:13:03,587 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 117 states to 117 states and 143 transitions. [2025-03-08 05:13:03,587 INFO L78 Accepts]: Start accepts. Automaton has 117 states and 143 transitions. Word has length 96 [2025-03-08 05:13:03,587 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-08 05:13:03,587 INFO L471 AbstractCegarLoop]: Abstraction has 117 states and 143 transitions. [2025-03-08 05:13:03,587 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 19 states, 19 states have (on average 2.0) internal successors, (38), 17 states have internal predecessors, (38), 13 states have call successors, (50), 3 states have call predecessors, (50), 1 states have return successors, (47), 13 states have call predecessors, (47), 13 states have call successors, (47) [2025-03-08 05:13:03,587 INFO L276 IsEmpty]: Start isEmpty. Operand 117 states and 143 transitions. [2025-03-08 05:13:03,588 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 108 [2025-03-08 05:13:03,588 INFO L210 NwaCegarLoop]: Found error trace [2025-03-08 05:13:03,588 INFO L218 NwaCegarLoop]: trace histogram [19, 18, 18, 4, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-08 05:13:03,594 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Forceful destruction successful, exit code 0 [2025-03-08 05:13:03,788 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 11 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable13 [2025-03-08 05:13:03,789 INFO L396 AbstractCegarLoop]: === Iteration 15 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-08 05:13:03,789 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-08 05:13:03,789 INFO L85 PathProgramCache]: Analyzing trace with hash 883466356, now seen corresponding path program 2 times [2025-03-08 05:13:03,789 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-08 05:13:03,789 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [197478811] [2025-03-08 05:13:03,789 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-08 05:13:03,789 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-08 05:13:03,793 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 107 statements into 2 equivalence classes. [2025-03-08 05:13:03,804 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 107 of 107 statements. [2025-03-08 05:13:03,804 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-08 05:13:03,804 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 05:13:03,943 INFO L134 CoverageAnalysis]: Checked inductivity of 682 backedges. 48 proven. 22 refuted. 0 times theorem prover too weak. 612 trivial. 0 not checked. [2025-03-08 05:13:03,944 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-08 05:13:03,944 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [197478811] [2025-03-08 05:13:03,944 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [197478811] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-08 05:13:03,944 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1701702075] [2025-03-08 05:13:03,944 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-08 05:13:03,944 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-08 05:13:03,944 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-08 05:13:03,946 INFO L229 MonitoredProcess]: Starting monitored process 12 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-08 05:13:03,948 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Waiting until timeout for monitored process [2025-03-08 05:13:03,971 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 107 statements into 2 equivalence classes. [2025-03-08 05:13:03,992 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 107 of 107 statements. [2025-03-08 05:13:03,992 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-08 05:13:03,992 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 05:13:03,993 INFO L256 TraceCheckSpWp]: Trace formula consists of 259 conjuncts, 7 conjuncts are in the unsatisfiable core [2025-03-08 05:13:03,994 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-08 05:13:04,033 INFO L134 CoverageAnalysis]: Checked inductivity of 682 backedges. 60 proven. 10 refuted. 0 times theorem prover too weak. 612 trivial. 0 not checked. [2025-03-08 05:13:04,033 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-08 05:13:04,142 INFO L134 CoverageAnalysis]: Checked inductivity of 682 backedges. 60 proven. 10 refuted. 0 times theorem prover too weak. 612 trivial. 0 not checked. [2025-03-08 05:13:04,142 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1701702075] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-08 05:13:04,142 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-08 05:13:04,143 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 6, 6] total 9 [2025-03-08 05:13:04,143 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1107056040] [2025-03-08 05:13:04,143 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-08 05:13:04,143 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2025-03-08 05:13:04,143 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-08 05:13:04,143 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2025-03-08 05:13:04,143 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=28, Invalid=44, Unknown=0, NotChecked=0, Total=72 [2025-03-08 05:13:04,143 INFO L87 Difference]: Start difference. First operand 117 states and 143 transitions. Second operand has 9 states, 9 states have (on average 2.888888888888889) internal successors, (26), 9 states have internal predecessors, (26), 8 states have call successors, (26), 2 states have call predecessors, (26), 1 states have return successors, (25), 7 states have call predecessors, (25), 7 states have call successors, (25) [2025-03-08 05:13:04,223 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-08 05:13:04,223 INFO L93 Difference]: Finished difference Result 123 states and 148 transitions. [2025-03-08 05:13:04,224 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2025-03-08 05:13:04,224 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 9 states have (on average 2.888888888888889) internal successors, (26), 9 states have internal predecessors, (26), 8 states have call successors, (26), 2 states have call predecessors, (26), 1 states have return successors, (25), 7 states have call predecessors, (25), 7 states have call successors, (25) Word has length 107 [2025-03-08 05:13:04,224 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-08 05:13:04,225 INFO L225 Difference]: With dead ends: 123 [2025-03-08 05:13:04,225 INFO L226 Difference]: Without dead ends: 116 [2025-03-08 05:13:04,225 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 220 GetRequests, 207 SyntacticMatches, 6 SemanticMatches, 7 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 48 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=28, Invalid=44, Unknown=0, NotChecked=0, Total=72 [2025-03-08 05:13:04,225 INFO L435 NwaCegarLoop]: 42 mSDtfsCounter, 6 mSDsluCounter, 78 mSDsCounter, 0 mSdLazyCounter, 74 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 8 SdHoareTripleChecker+Valid, 120 SdHoareTripleChecker+Invalid, 76 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 74 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-08 05:13:04,225 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [8 Valid, 120 Invalid, 76 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 74 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-08 05:13:04,226 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 116 states. [2025-03-08 05:13:04,250 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 116 to 113. [2025-03-08 05:13:04,251 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 113 states, 66 states have (on average 1.1363636363636365) internal successors, (75), 70 states have internal predecessors, (75), 31 states have call successors, (31), 15 states have call predecessors, (31), 15 states have return successors, (30), 27 states have call predecessors, (30), 30 states have call successors, (30) [2025-03-08 05:13:04,251 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 113 states to 113 states and 136 transitions. [2025-03-08 05:13:04,252 INFO L78 Accepts]: Start accepts. Automaton has 113 states and 136 transitions. Word has length 107 [2025-03-08 05:13:04,253 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-08 05:13:04,253 INFO L471 AbstractCegarLoop]: Abstraction has 113 states and 136 transitions. [2025-03-08 05:13:04,253 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 9 states have (on average 2.888888888888889) internal successors, (26), 9 states have internal predecessors, (26), 8 states have call successors, (26), 2 states have call predecessors, (26), 1 states have return successors, (25), 7 states have call predecessors, (25), 7 states have call successors, (25) [2025-03-08 05:13:04,253 INFO L276 IsEmpty]: Start isEmpty. Operand 113 states and 136 transitions. [2025-03-08 05:13:04,254 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 109 [2025-03-08 05:13:04,254 INFO L210 NwaCegarLoop]: Found error trace [2025-03-08 05:13:04,254 INFO L218 NwaCegarLoop]: trace histogram [19, 18, 18, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1] [2025-03-08 05:13:04,260 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Forceful destruction successful, exit code 0 [2025-03-08 05:13:04,454 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 12 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable14 [2025-03-08 05:13:04,455 INFO L396 AbstractCegarLoop]: === Iteration 16 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-08 05:13:04,455 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-08 05:13:04,455 INFO L85 PathProgramCache]: Analyzing trace with hash 293213024, now seen corresponding path program 3 times [2025-03-08 05:13:04,455 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-08 05:13:04,456 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1566674479] [2025-03-08 05:13:04,456 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-03-08 05:13:04,456 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-08 05:13:04,461 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 108 statements into 10 equivalence classes. [2025-03-08 05:13:04,510 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 10 check-sat command(s) and asserted 108 of 108 statements. [2025-03-08 05:13:04,510 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 10 check-sat command(s) [2025-03-08 05:13:04,510 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-08 05:13:04,511 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1174268000] [2025-03-08 05:13:04,511 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-03-08 05:13:04,511 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-08 05:13:04,511 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-08 05:13:04,513 INFO L229 MonitoredProcess]: Starting monitored process 13 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-08 05:13:04,514 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Waiting until timeout for monitored process [2025-03-08 05:13:04,539 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 108 statements into 10 equivalence classes. [2025-03-08 05:13:04,565 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) and asserted 43 of 108 statements. [2025-03-08 05:13:04,565 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2025-03-08 05:13:04,566 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 05:13:04,566 INFO L256 TraceCheckSpWp]: Trace formula consists of 142 conjuncts, 35 conjuncts are in the unsatisfiable core [2025-03-08 05:13:04,568 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-08 05:13:04,678 INFO L134 CoverageAnalysis]: Checked inductivity of 687 backedges. 153 proven. 41 refuted. 0 times theorem prover too weak. 493 trivial. 0 not checked. [2025-03-08 05:13:04,679 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-08 05:13:05,293 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-08 05:13:05,293 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1566674479] [2025-03-08 05:13:05,293 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-08 05:13:05,293 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1174268000] [2025-03-08 05:13:05,293 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1174268000] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-08 05:13:05,293 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2025-03-08 05:13:05,293 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10] total 10 [2025-03-08 05:13:05,293 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1387438786] [2025-03-08 05:13:05,293 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2025-03-08 05:13:05,293 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2025-03-08 05:13:05,293 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-08 05:13:05,294 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2025-03-08 05:13:05,294 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=40, Invalid=170, Unknown=0, NotChecked=0, Total=210 [2025-03-08 05:13:05,294 INFO L87 Difference]: Start difference. First operand 113 states and 136 transitions. Second operand has 10 states, 9 states have (on average 2.2222222222222223) internal successors, (20), 9 states have internal predecessors, (20), 3 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (11), 4 states have call predecessors, (11), 3 states have call successors, (11) [2025-03-08 05:13:05,403 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-08 05:13:05,403 INFO L93 Difference]: Finished difference Result 120 states and 142 transitions. [2025-03-08 05:13:05,403 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2025-03-08 05:13:05,403 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 9 states have (on average 2.2222222222222223) internal successors, (20), 9 states have internal predecessors, (20), 3 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (11), 4 states have call predecessors, (11), 3 states have call successors, (11) Word has length 108 [2025-03-08 05:13:05,403 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-08 05:13:05,404 INFO L225 Difference]: With dead ends: 120 [2025-03-08 05:13:05,404 INFO L226 Difference]: Without dead ends: 118 [2025-03-08 05:13:05,404 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 117 GetRequests, 101 SyntacticMatches, 0 SemanticMatches, 16 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 45 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=65, Invalid=241, Unknown=0, NotChecked=0, Total=306 [2025-03-08 05:13:05,405 INFO L435 NwaCegarLoop]: 15 mSDtfsCounter, 19 mSDsluCounter, 40 mSDsCounter, 0 mSdLazyCounter, 94 mSolverCounterSat, 28 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 21 SdHoareTripleChecker+Valid, 55 SdHoareTripleChecker+Invalid, 122 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 28 IncrementalHoareTripleChecker+Valid, 94 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-08 05:13:05,405 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [21 Valid, 55 Invalid, 122 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [28 Valid, 94 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-08 05:13:05,405 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 118 states. [2025-03-08 05:13:05,429 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 118 to 117. [2025-03-08 05:13:05,429 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 117 states, 69 states have (on average 1.1304347826086956) internal successors, (78), 73 states have internal predecessors, (78), 31 states have call successors, (31), 16 states have call predecessors, (31), 16 states have return successors, (30), 27 states have call predecessors, (30), 30 states have call successors, (30) [2025-03-08 05:13:05,430 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 117 states to 117 states and 139 transitions. [2025-03-08 05:13:05,430 INFO L78 Accepts]: Start accepts. Automaton has 117 states and 139 transitions. Word has length 108 [2025-03-08 05:13:05,430 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-08 05:13:05,430 INFO L471 AbstractCegarLoop]: Abstraction has 117 states and 139 transitions. [2025-03-08 05:13:05,430 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 9 states have (on average 2.2222222222222223) internal successors, (20), 9 states have internal predecessors, (20), 3 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (11), 4 states have call predecessors, (11), 3 states have call successors, (11) [2025-03-08 05:13:05,430 INFO L276 IsEmpty]: Start isEmpty. Operand 117 states and 139 transitions. [2025-03-08 05:13:05,431 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 120 [2025-03-08 05:13:05,431 INFO L210 NwaCegarLoop]: Found error trace [2025-03-08 05:13:05,431 INFO L218 NwaCegarLoop]: trace histogram [21, 20, 20, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-08 05:13:05,437 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Forceful destruction successful, exit code 0 [2025-03-08 05:13:05,635 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 13 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable15 [2025-03-08 05:13:05,635 INFO L396 AbstractCegarLoop]: === Iteration 17 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-08 05:13:05,636 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-08 05:13:05,636 INFO L85 PathProgramCache]: Analyzing trace with hash -1970692066, now seen corresponding path program 3 times [2025-03-08 05:13:05,636 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-08 05:13:05,636 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1317754603] [2025-03-08 05:13:05,636 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-03-08 05:13:05,636 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-08 05:13:05,641 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 119 statements into 12 equivalence classes. [2025-03-08 05:13:05,674 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 12 check-sat command(s) and asserted 119 of 119 statements. [2025-03-08 05:13:05,674 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 12 check-sat command(s) [2025-03-08 05:13:05,674 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-08 05:13:05,675 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1907133151] [2025-03-08 05:13:05,675 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-03-08 05:13:05,675 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-08 05:13:05,675 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-08 05:13:05,678 INFO L229 MonitoredProcess]: Starting monitored process 14 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-08 05:13:05,680 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Waiting until timeout for monitored process [2025-03-08 05:13:05,706 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 119 statements into 12 equivalence classes. [2025-03-08 05:13:05,720 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) and asserted 42 of 119 statements. [2025-03-08 05:13:05,720 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2025-03-08 05:13:05,720 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 05:13:05,720 INFO L256 TraceCheckSpWp]: Trace formula consists of 134 conjuncts, 29 conjuncts are in the unsatisfiable core [2025-03-08 05:13:05,722 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-08 05:13:05,826 INFO L134 CoverageAnalysis]: Checked inductivity of 845 backedges. 163 proven. 50 refuted. 0 times theorem prover too weak. 632 trivial. 0 not checked. [2025-03-08 05:13:05,826 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-08 05:13:05,934 INFO L134 CoverageAnalysis]: Checked inductivity of 845 backedges. 152 proven. 2 refuted. 0 times theorem prover too weak. 691 trivial. 0 not checked. [2025-03-08 05:13:05,934 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-08 05:13:05,934 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1317754603] [2025-03-08 05:13:05,934 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-08 05:13:05,934 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1907133151] [2025-03-08 05:13:05,934 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1907133151] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-08 05:13:05,934 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-03-08 05:13:05,934 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 8] total 16 [2025-03-08 05:13:05,934 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1306712585] [2025-03-08 05:13:05,934 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-03-08 05:13:05,934 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2025-03-08 05:13:05,934 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-08 05:13:05,935 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2025-03-08 05:13:05,935 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=41, Invalid=199, Unknown=0, NotChecked=0, Total=240 [2025-03-08 05:13:05,935 INFO L87 Difference]: Start difference. First operand 117 states and 139 transitions. Second operand has 16 states, 12 states have (on average 2.4166666666666665) internal successors, (29), 11 states have internal predecessors, (29), 7 states have call successors, (17), 3 states have call predecessors, (17), 2 states have return successors, (18), 7 states have call predecessors, (18), 5 states have call successors, (18) [2025-03-08 05:13:06,078 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-08 05:13:06,078 INFO L93 Difference]: Finished difference Result 118 states and 140 transitions. [2025-03-08 05:13:06,079 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2025-03-08 05:13:06,079 INFO L78 Accepts]: Start accepts. Automaton has has 16 states, 12 states have (on average 2.4166666666666665) internal successors, (29), 11 states have internal predecessors, (29), 7 states have call successors, (17), 3 states have call predecessors, (17), 2 states have return successors, (18), 7 states have call predecessors, (18), 5 states have call successors, (18) Word has length 119 [2025-03-08 05:13:06,079 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-08 05:13:06,079 INFO L225 Difference]: With dead ends: 118 [2025-03-08 05:13:06,079 INFO L226 Difference]: Without dead ends: 0 [2025-03-08 05:13:06,080 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 244 GetRequests, 224 SyntacticMatches, 0 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 55 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=98, Invalid=364, Unknown=0, NotChecked=0, Total=462 [2025-03-08 05:13:06,080 INFO L435 NwaCegarLoop]: 14 mSDtfsCounter, 24 mSDsluCounter, 85 mSDsCounter, 0 mSdLazyCounter, 121 mSolverCounterSat, 86 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 24 SdHoareTripleChecker+Valid, 99 SdHoareTripleChecker+Invalid, 207 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 86 IncrementalHoareTripleChecker+Valid, 121 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-08 05:13:06,080 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [24 Valid, 99 Invalid, 207 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [86 Valid, 121 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-08 05:13:06,080 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 0 states. [2025-03-08 05:13:06,080 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 0 to 0. [2025-03-08 05:13:06,080 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 0 states, 0 states have (on average 0.0) internal successors, (0), 0 states have internal predecessors, (0), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2025-03-08 05:13:06,080 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 0 states to 0 states and 0 transitions. [2025-03-08 05:13:06,080 INFO L78 Accepts]: Start accepts. Automaton has 0 states and 0 transitions. Word has length 119 [2025-03-08 05:13:06,080 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-08 05:13:06,080 INFO L471 AbstractCegarLoop]: Abstraction has 0 states and 0 transitions. [2025-03-08 05:13:06,081 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 16 states, 12 states have (on average 2.4166666666666665) internal successors, (29), 11 states have internal predecessors, (29), 7 states have call successors, (17), 3 states have call predecessors, (17), 2 states have return successors, (18), 7 states have call predecessors, (18), 5 states have call successors, (18) [2025-03-08 05:13:06,081 INFO L276 IsEmpty]: Start isEmpty. Operand 0 states and 0 transitions. [2025-03-08 05:13:06,081 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2025-03-08 05:13:06,082 INFO L782 garLoopResultBuilder]: Registering result SAFE for location __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION (0 of 1 remaining) [2025-03-08 05:13:06,088 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Ended with exit code 0 [2025-03-08 05:13:06,287 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 14 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable16 [2025-03-08 05:13:06,289 INFO L422 BasicCegarLoop]: Path program histogram: [3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1] [2025-03-08 05:13:06,290 INFO L343 DoubleDeckerVisitor]: Before removal of dead ends 0 states and 0 transitions. [2025-03-08 05:13:07,839 INFO L170 ceAbstractionStarter]: Computing trace abstraction results [2025-03-08 05:13:07,847 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 08.03 05:13:07 BoogieIcfgContainer [2025-03-08 05:13:07,848 INFO L131 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2025-03-08 05:13:07,848 INFO L112 PluginConnector]: ------------------------Witness Printer---------------------------- [2025-03-08 05:13:07,848 INFO L270 PluginConnector]: Initializing Witness Printer... [2025-03-08 05:13:07,848 INFO L274 PluginConnector]: Witness Printer initialized [2025-03-08 05:13:07,848 INFO L184 PluginConnector]: Executing the observer RCFGCatcher from plugin Witness Printer for "de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 08.03 05:12:30" (3/4) ... [2025-03-08 05:13:07,850 INFO L146 WitnessPrinter]: Generating witness for correct program [2025-03-08 05:13:07,854 INFO L385 IcfgBacktranslator]: Ignoring RootEdge to procedure __VERIFIER_assert [2025-03-08 05:13:07,856 INFO L919 BoogieBacktranslator]: Reduced CFG by removing 16 nodes and edges [2025-03-08 05:13:07,856 INFO L919 BoogieBacktranslator]: Reduced CFG by removing 6 nodes and edges [2025-03-08 05:13:07,856 INFO L919 BoogieBacktranslator]: Reduced CFG by removing 4 nodes and edges [2025-03-08 05:13:07,856 INFO L919 BoogieBacktranslator]: Reduced CFG by removing 1 nodes and edges [2025-03-08 05:13:07,856 INFO L919 BoogieBacktranslator]: Reduced CFG by removing 1 nodes and edges [2025-03-08 05:13:07,909 INFO L149 WitnessManager]: Wrote witness to /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/witness.graphml [2025-03-08 05:13:07,909 INFO L149 WitnessManager]: Wrote witness to /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/witness.yml [2025-03-08 05:13:07,909 INFO L131 PluginConnector]: ------------------------ END Witness Printer---------------------------- [2025-03-08 05:13:07,909 INFO L158 Benchmark]: Toolchain (without parser) took 38175.34ms. Allocated memory was 167.8MB in the beginning and 503.3MB in the end (delta: 335.5MB). Free memory was 124.7MB in the beginning and 273.0MB in the end (delta: -148.3MB). Peak memory consumption was 186.4MB. Max. memory is 16.1GB. [2025-03-08 05:13:07,910 INFO L158 Benchmark]: CDTParser took 0.17ms. Allocated memory is still 201.3MB. Free memory is still 117.4MB. There was no memory consumed. Max. memory is 16.1GB. [2025-03-08 05:13:07,910 INFO L158 Benchmark]: CACSL2BoogieTranslator took 153.82ms. Allocated memory is still 167.8MB. Free memory was 124.7MB in the beginning and 113.2MB in the end (delta: 11.5MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. [2025-03-08 05:13:07,911 INFO L158 Benchmark]: Boogie Procedure Inliner took 24.22ms. Allocated memory is still 167.8MB. Free memory was 113.2MB in the beginning and 112.4MB in the end (delta: 821.3kB). There was no memory consumed. Max. memory is 16.1GB. [2025-03-08 05:13:07,911 INFO L158 Benchmark]: Boogie Preprocessor took 28.94ms. Allocated memory is still 167.8MB. Free memory was 112.4MB in the beginning and 111.4MB in the end (delta: 988.9kB). There was no memory consumed. Max. memory is 16.1GB. [2025-03-08 05:13:07,911 INFO L158 Benchmark]: IcfgBuilder took 214.19ms. Allocated memory is still 167.8MB. Free memory was 111.4MB in the beginning and 98.8MB in the end (delta: 12.6MB). Peak memory consumption was 16.8MB. Max. memory is 16.1GB. [2025-03-08 05:13:07,912 INFO L158 Benchmark]: TraceAbstraction took 37687.76ms. Allocated memory was 167.8MB in the beginning and 503.3MB in the end (delta: 335.5MB). Free memory was 98.8MB in the beginning and 277.3MB in the end (delta: -178.5MB). Peak memory consumption was 263.7MB. Max. memory is 16.1GB. [2025-03-08 05:13:07,912 INFO L158 Benchmark]: Witness Printer took 60.82ms. Allocated memory is still 503.3MB. Free memory was 277.3MB in the beginning and 273.0MB in the end (delta: 4.3MB). There was no memory consumed. Max. memory is 16.1GB. [2025-03-08 05:13:07,913 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.17ms. Allocated memory is still 201.3MB. Free memory is still 117.4MB. There was no memory consumed. Max. memory is 16.1GB. * CACSL2BoogieTranslator took 153.82ms. Allocated memory is still 167.8MB. Free memory was 124.7MB in the beginning and 113.2MB in the end (delta: 11.5MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. * Boogie Procedure Inliner took 24.22ms. Allocated memory is still 167.8MB. Free memory was 113.2MB in the beginning and 112.4MB in the end (delta: 821.3kB). There was no memory consumed. Max. memory is 16.1GB. * Boogie Preprocessor took 28.94ms. Allocated memory is still 167.8MB. Free memory was 112.4MB in the beginning and 111.4MB in the end (delta: 988.9kB). There was no memory consumed. Max. memory is 16.1GB. * IcfgBuilder took 214.19ms. Allocated memory is still 167.8MB. Free memory was 111.4MB in the beginning and 98.8MB in the end (delta: 12.6MB). Peak memory consumption was 16.8MB. Max. memory is 16.1GB. * TraceAbstraction took 37687.76ms. Allocated memory was 167.8MB in the beginning and 503.3MB in the end (delta: 335.5MB). Free memory was 98.8MB in the beginning and 277.3MB in the end (delta: -178.5MB). Peak memory consumption was 263.7MB. Max. memory is 16.1GB. * Witness Printer took 60.82ms. Allocated memory is still 503.3MB. Free memory was 277.3MB in the beginning and 273.0MB in the end (delta: 4.3MB). There was no memory consumed. 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 - PositiveResult [Line: 17]: a call to reach_error is unreachable For all program executions holds that a call to reach_error is unreachable at this location - StatisticsResult: Ultimate Automizer benchmark data CFG has 2 procedures, 24 locations, 43 edges, 1 error locations. Started 1 CEGAR loops. OverallTime: 36.1s, OverallIterations: 17, TraceHistogramMax: 21, PathProgramHistogramMax: 3, EmptinessCheckTime: 0.0s, AutomataDifference: 15.3s, DeadEndRemovalTime: 0.0s, HoareAnnotationTime: 0.0s, InitialAbstractionConstructionTime: 0.0s, HoareTripleCheckerStatistics: 0 mSolverCounterUnknown, 294 SdHoareTripleChecker+Valid, 5.9s IncrementalHoareTripleChecker+Time, 0 mSdLazyCounter, 235 mSDsluCounter, 2341 SdHoareTripleChecker+Invalid, 5.5s Time, 0 mProtectedAction, 0 SdHoareTripleChecker+Unchecked, 0 IncrementalHoareTripleChecker+Unchecked, 1898 mSDsCounter, 517 IncrementalHoareTripleChecker+Valid, 0 mProtectedPredicate, 3095 IncrementalHoareTripleChecker+Invalid, 3612 SdHoareTripleChecker+Unknown, 0 mSolverCounterNotChecked, 517 mSolverCounterUnsat, 443 mSDtfsCounter, 3095 mSolverCounterSat, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Unknown, PredicateUnifierStatistics: 0 DeclaredPredicates, 1763 GetRequests, 1535 SyntacticMatches, 13 SemanticMatches, 215 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 675 ImplicationChecksByTransitivity, 11.5s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=144occurred in iteration=12, InterpolantAutomatonStates: 167, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 0.0s DumpTime, AutomataMinimizationStatistics: 0.3s AutomataMinimizationTime, 17 MinimizatonAttempts, 90 StatesRemovedByMinimization, 11 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TRACE_CHECK: 0.1s SsaConstructionTime, 0.6s SatisfiabilityAnalysisTime, 16.7s InterpolantComputationTime, 1971 NumberOfCodeBlocks, 1829 NumberOfCodeBlocksAsserted, 64 NumberOfCheckSat, 1972 ConstructedInterpolants, 0 QuantifiedInterpolants, 17726 SizeOfPredicates, 29 NumberOfNonLiveVariables, 2231 ConjunctsInSsa, 356 ConjunctsInUnsatCore, 29 InterpolantComputations, 7 PerfectInterpolantSequences, 9144/9786 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 - AllSpecificationsHoldResult: All specifications hold 1 specifications checked. All of them hold - InvariantResult [Line: 34]: Location Invariant Derived location invariant: ((((((((d == 1) && (p == 1)) && (q == 0)) && (A == r)) && (B == 1)) || (((((2 == p) && (q == 0)) && (A == r)) && (B == 1)) && (2 == d))) || (((((p == 4) && (q == 0)) && (A == r)) && (d == 4)) && (B == 1))) || (((((8 <= p) && (q == 0)) && (A == r)) && (d == p)) && (B == 1))) - InvariantResult [Line: 22]: Location Invariant Derived location invariant: ((((1 <= p) && (A == ((long long) q + r))) && (d == p)) && (B == 1)) RESULT: Ultimate proved your program to be correct! [2025-03-08 05:13:07,966 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 Result: TRUE