./Ultimate.py --spec ../sv-benchmarks/c/properties/unreach-call.prp --file ../sv-benchmarks/c/nla-digbench-scaling/prodbin-ll_valuebound10.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version 798a7b37 Calling Ultimate with: /root/.sdkman/candidates/java/21.0.5-tem/bin/java -Dosgi.configuration.area=/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/config -Xmx15G -Xms4m -jar /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/org.eclipse.equinox.launcher_1.6.800.v20240513-1750.jar -data @noDefault -ultimatedata /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data -tc /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/AutomizerReach.xml -i ../sv-benchmarks/c/nla-digbench-scaling/prodbin-ll_valuebound10.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 ca6b6f09277139d829682a6458fdcdacf72411331aa404fd46248e3dcb9a9e7f --- Real Ultimate output --- This is Ultimate 0.3.0-?-798a7b3-m [2025-03-03 14:07:42,852 INFO L188 SettingsManager]: Resetting all preferences to default values... [2025-03-03 14:07:42,908 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf [2025-03-03 14:07:42,913 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2025-03-03 14:07:42,915 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2025-03-03 14:07:42,927 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2025-03-03 14:07:42,927 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2025-03-03 14:07:42,927 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2025-03-03 14:07:42,927 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2025-03-03 14:07:42,927 INFO L153 SettingsManager]: * Use memory slicer=true [2025-03-03 14:07:42,928 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2025-03-03 14:07:42,928 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2025-03-03 14:07:42,928 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2025-03-03 14:07:42,928 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2025-03-03 14:07:42,928 INFO L153 SettingsManager]: * Use SBE=true [2025-03-03 14:07:42,928 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2025-03-03 14:07:42,928 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2025-03-03 14:07:42,928 INFO L153 SettingsManager]: * sizeof long=4 [2025-03-03 14:07:42,928 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2025-03-03 14:07:42,929 INFO L153 SettingsManager]: * sizeof POINTER=4 [2025-03-03 14:07:42,929 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2025-03-03 14:07:42,929 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2025-03-03 14:07:42,929 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2025-03-03 14:07:42,929 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2025-03-03 14:07:42,929 INFO L153 SettingsManager]: * sizeof long double=12 [2025-03-03 14:07:42,929 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2025-03-03 14:07:42,929 INFO L153 SettingsManager]: * Behaviour of calls to undefined functions=OVERAPPROXIMATE_BEHAVIOUR [2025-03-03 14:07:42,929 INFO L153 SettingsManager]: * Use constant arrays=true [2025-03-03 14:07:42,929 INFO L151 SettingsManager]: Preferences of IcfgBuilder differ from their defaults: [2025-03-03 14:07:42,929 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2025-03-03 14:07:42,929 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2025-03-03 14:07:42,930 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2025-03-03 14:07:42,930 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2025-03-03 14:07:42,930 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2025-03-03 14:07:42,930 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2025-03-03 14:07:42,930 INFO L153 SettingsManager]: * Compute procedure contracts=false [2025-03-03 14:07:42,930 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2025-03-03 14:07:42,930 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2025-03-03 14:07:42,930 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2025-03-03 14:07:42,930 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2025-03-03 14:07:42,930 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2025-03-03 14:07:42,930 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2025-03-03 14:07:42,930 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2025-03-03 14:07:42,930 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 -> ca6b6f09277139d829682a6458fdcdacf72411331aa404fd46248e3dcb9a9e7f [2025-03-03 14:07:43,127 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2025-03-03 14:07:43,132 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2025-03-03 14:07:43,134 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2025-03-03 14:07:43,134 INFO L270 PluginConnector]: Initializing CDTParser... [2025-03-03 14:07:43,135 INFO L274 PluginConnector]: CDTParser initialized [2025-03-03 14:07:43,135 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/nla-digbench-scaling/prodbin-ll_valuebound10.c [2025-03-03 14:07:44,272 INFO L533 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/9b32329f6/a5bbe1378d994a39bee1b17cca761d9e/FLAG59981b7e0 [2025-03-03 14:07:44,494 INFO L384 CDTParser]: Found 1 translation units. [2025-03-03 14:07:44,494 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/prodbin-ll_valuebound10.c [2025-03-03 14:07:44,498 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/9b32329f6/a5bbe1378d994a39bee1b17cca761d9e/FLAG59981b7e0 [2025-03-03 14:07:44,508 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/9b32329f6/a5bbe1378d994a39bee1b17cca761d9e [2025-03-03 14:07:44,510 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2025-03-03 14:07:44,511 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2025-03-03 14:07:44,512 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2025-03-03 14:07:44,512 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2025-03-03 14:07:44,515 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2025-03-03 14:07:44,515 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 03.03 02:07:44" (1/1) ... [2025-03-03 14:07:44,516 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@1bec93e1 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 02:07:44, skipping insertion in model container [2025-03-03 14:07:44,516 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 03.03 02:07:44" (1/1) ... [2025-03-03 14:07:44,526 INFO L175 MainTranslator]: Built tables and reachable declarations [2025-03-03 14:07:44,623 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/prodbin-ll_valuebound10.c[537,550] [2025-03-03 14:07:44,637 INFO L210 PostProcessor]: Analyzing one entry point: main [2025-03-03 14:07:44,644 INFO L200 MainTranslator]: Completed pre-run [2025-03-03 14:07:44,651 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/prodbin-ll_valuebound10.c[537,550] [2025-03-03 14:07:44,654 INFO L210 PostProcessor]: Analyzing one entry point: main [2025-03-03 14:07:44,665 INFO L204 MainTranslator]: Completed translation [2025-03-03 14:07:44,665 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 02:07:44 WrapperNode [2025-03-03 14:07:44,665 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2025-03-03 14:07:44,667 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2025-03-03 14:07:44,667 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2025-03-03 14:07:44,667 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2025-03-03 14:07:44,673 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 02:07:44" (1/1) ... [2025-03-03 14:07:44,678 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 02:07:44" (1/1) ... [2025-03-03 14:07:44,690 INFO L138 Inliner]: procedures = 14, calls = 12, calls flagged for inlining = 2, calls inlined = 2, statements flattened = 40 [2025-03-03 14:07:44,691 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2025-03-03 14:07:44,692 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2025-03-03 14:07:44,693 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2025-03-03 14:07:44,693 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2025-03-03 14:07:44,698 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 02:07:44" (1/1) ... [2025-03-03 14:07:44,698 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 02:07:44" (1/1) ... [2025-03-03 14:07:44,699 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 02:07:44" (1/1) ... [2025-03-03 14:07:44,708 INFO L175 MemorySlicer]: Split 2 memory accesses to 1 slices as follows [2]. 100 percent of accesses are in the largest equivalence class. The 2 initializations are split as follows [2]. The 0 writes are split as follows [0]. [2025-03-03 14:07:44,709 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 02:07:44" (1/1) ... [2025-03-03 14:07:44,709 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 02:07:44" (1/1) ... [2025-03-03 14:07:44,711 INFO L184 PluginConnector]: Executing the observer ReplaceArrayAssignments from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 02:07:44" (1/1) ... [2025-03-03 14:07:44,715 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 02:07:44" (1/1) ... [2025-03-03 14:07:44,716 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 02:07:44" (1/1) ... [2025-03-03 14:07:44,716 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 02:07:44" (1/1) ... [2025-03-03 14:07:44,717 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2025-03-03 14:07:44,719 INFO L112 PluginConnector]: ------------------------IcfgBuilder---------------------------- [2025-03-03 14:07:44,719 INFO L270 PluginConnector]: Initializing IcfgBuilder... [2025-03-03 14:07:44,719 INFO L274 PluginConnector]: IcfgBuilder initialized [2025-03-03 14:07:44,720 INFO L184 PluginConnector]: Executing the observer IcfgBuilderObserver from plugin IcfgBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 02:07:44" (1/1) ... [2025-03-03 14:07:44,725 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2025-03-03 14:07:44,739 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 14:07:44,752 INFO L229 MonitoredProcess]: Starting monitored process 1 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (exit command is (exit), workingDir is null) [2025-03-03 14:07:44,755 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (1)] Waiting until timeout for monitored process [2025-03-03 14:07:44,774 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2025-03-03 14:07:44,774 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2025-03-03 14:07:44,774 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2025-03-03 14:07:44,774 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2025-03-03 14:07:44,775 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2025-03-03 14:07:44,775 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2025-03-03 14:07:44,775 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2025-03-03 14:07:44,775 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2025-03-03 14:07:44,811 INFO L256 CfgBuilder]: Building ICFG [2025-03-03 14:07:44,812 INFO L286 CfgBuilder]: Building CFG for each procedure with an implementation [2025-03-03 14:07:44,907 INFO L? ?]: Removed 6 outVars from TransFormulas that were not future-live. [2025-03-03 14:07:44,907 INFO L307 CfgBuilder]: Performing block encoding [2025-03-03 14:07:44,913 INFO L331 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2025-03-03 14:07:44,914 INFO L336 CfgBuilder]: Removed 0 assume(true) statements. [2025-03-03 14:07:44,914 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 03.03 02:07:44 BoogieIcfgContainer [2025-03-03 14:07:44,914 INFO L131 PluginConnector]: ------------------------ END IcfgBuilder---------------------------- [2025-03-03 14:07:44,917 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2025-03-03 14:07:44,917 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2025-03-03 14:07:44,921 INFO L274 PluginConnector]: TraceAbstraction initialized [2025-03-03 14:07:44,921 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 03.03 02:07:44" (1/3) ... [2025-03-03 14:07:44,922 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@2878de7 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 03.03 02:07:44, skipping insertion in model container [2025-03-03 14:07:44,922 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 02:07:44" (2/3) ... [2025-03-03 14:07:44,922 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@2878de7 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 03.03 02:07:44, skipping insertion in model container [2025-03-03 14:07:44,922 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 03.03 02:07:44" (3/3) ... [2025-03-03 14:07:44,923 INFO L128 eAbstractionObserver]: Analyzing ICFG prodbin-ll_valuebound10.c [2025-03-03 14:07:44,933 INFO L216 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2025-03-03 14:07:44,935 INFO L151 ceAbstractionStarter]: Applying trace abstraction to ICFG prodbin-ll_valuebound10.c that has 3 procedures, 26 locations, 1 initial locations, 1 loop locations, and 1 error locations. [2025-03-03 14:07:44,980 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2025-03-03 14:07:44,991 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;@4c15200, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2025-03-03 14:07:44,992 INFO L334 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2025-03-03 14:07:44,995 INFO L276 IsEmpty]: Start isEmpty. Operand has 26 states, 18 states have (on average 1.2777777777777777) internal successors, (23), 18 states have internal predecessors, (23), 5 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) [2025-03-03 14:07:44,999 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 24 [2025-03-03 14:07:44,999 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 14:07:45,000 INFO L218 NwaCegarLoop]: trace histogram [3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-03 14:07:45,000 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 14:07:45,007 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 14:07:45,007 INFO L85 PathProgramCache]: Analyzing trace with hash -603682929, now seen corresponding path program 1 times [2025-03-03 14:07:45,013 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 14:07:45,014 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2075530690] [2025-03-03 14:07:45,014 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 14:07:45,014 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 14:07:45,067 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 23 statements into 1 equivalence classes. [2025-03-03 14:07:45,080 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 23 of 23 statements. [2025-03-03 14:07:45,082 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 14:07:45,082 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 14:07:45,127 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 8 trivial. 0 not checked. [2025-03-03 14:07:45,128 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-03 14:07:45,128 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2075530690] [2025-03-03 14:07:45,130 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2075530690] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-03 14:07:45,130 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [564073237] [2025-03-03 14:07:45,130 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 14:07:45,130 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 14:07:45,130 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 14:07:45,133 INFO L229 MonitoredProcess]: Starting monitored process 2 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-03 14:07:45,135 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2025-03-03 14:07:45,167 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 23 statements into 1 equivalence classes. [2025-03-03 14:07:45,191 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 23 of 23 statements. [2025-03-03 14:07:45,191 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 14:07:45,191 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 14:07:45,192 INFO L256 TraceCheckSpWp]: Trace formula consists of 67 conjuncts, 1 conjuncts are in the unsatisfiable core [2025-03-03 14:07:45,195 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-03 14:07:45,203 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 8 trivial. 0 not checked. [2025-03-03 14:07:45,203 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2025-03-03 14:07:45,203 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [564073237] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-03 14:07:45,203 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2025-03-03 14:07:45,203 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [2] total 2 [2025-03-03 14:07:45,207 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1490547084] [2025-03-03 14:07:45,207 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-03 14:07:45,209 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2025-03-03 14:07:45,210 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-03 14:07:45,222 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2025-03-03 14:07:45,222 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2025-03-03 14:07:45,224 INFO L87 Difference]: Start difference. First operand has 26 states, 18 states have (on average 1.2777777777777777) internal successors, (23), 18 states have internal predecessors, (23), 5 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) Second operand has 2 states, 2 states have (on average 6.0) internal successors, (12), 2 states have internal predecessors, (12), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 1 states have call predecessors, (3), 2 states have call successors, (3) [2025-03-03 14:07:45,236 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 14:07:45,238 INFO L93 Difference]: Finished difference Result 49 states and 67 transitions. [2025-03-03 14:07:45,239 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2025-03-03 14:07:45,240 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 6.0) internal successors, (12), 2 states have internal predecessors, (12), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 1 states have call predecessors, (3), 2 states have call successors, (3) Word has length 23 [2025-03-03 14:07:45,241 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 14:07:45,245 INFO L225 Difference]: With dead ends: 49 [2025-03-03 14:07:45,245 INFO L226 Difference]: Without dead ends: 22 [2025-03-03 14:07:45,249 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 24 GetRequests, 24 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-03 14:07:45,251 INFO L435 NwaCegarLoop]: 30 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, 30 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-03 14:07:45,253 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 30 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 0 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-03-03 14:07:45,263 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 22 states. [2025-03-03 14:07:45,274 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 22 to 22. [2025-03-03 14:07:45,276 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 22 states, 14 states have (on average 1.2142857142857142) internal successors, (17), 15 states have internal predecessors, (17), 5 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) [2025-03-03 14:07:45,278 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 22 states to 22 states and 26 transitions. [2025-03-03 14:07:45,281 INFO L78 Accepts]: Start accepts. Automaton has 22 states and 26 transitions. Word has length 23 [2025-03-03 14:07:45,281 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 14:07:45,281 INFO L471 AbstractCegarLoop]: Abstraction has 22 states and 26 transitions. [2025-03-03 14:07:45,282 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 2 states have (on average 6.0) internal successors, (12), 2 states have internal predecessors, (12), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 1 states have call predecessors, (3), 2 states have call successors, (3) [2025-03-03 14:07:45,282 INFO L276 IsEmpty]: Start isEmpty. Operand 22 states and 26 transitions. [2025-03-03 14:07:45,283 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 24 [2025-03-03 14:07:45,283 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 14:07:45,283 INFO L218 NwaCegarLoop]: trace histogram [3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-03 14:07:45,289 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Ended with exit code 0 [2025-03-03 14:07:45,484 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable0 [2025-03-03 14:07:45,484 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 14:07:45,485 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 14:07:45,485 INFO L85 PathProgramCache]: Analyzing trace with hash 1252528, now seen corresponding path program 1 times [2025-03-03 14:07:45,485 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 14:07:45,485 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [216546724] [2025-03-03 14:07:45,485 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 14:07:45,485 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 14:07:45,491 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 23 statements into 1 equivalence classes. [2025-03-03 14:07:45,517 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 23 of 23 statements. [2025-03-03 14:07:45,519 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 14:07:45,519 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-03 14:07:45,523 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [189207816] [2025-03-03 14:07:45,523 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 14:07:45,523 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 14:07:45,523 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 14:07:45,525 INFO L229 MonitoredProcess]: Starting monitored process 3 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-03 14:07:45,526 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2025-03-03 14:07:45,552 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 23 statements into 1 equivalence classes. [2025-03-03 14:07:45,567 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 23 of 23 statements. [2025-03-03 14:07:45,567 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 14:07:45,567 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 14:07:45,568 INFO L256 TraceCheckSpWp]: Trace formula consists of 67 conjuncts, 19 conjuncts are in the unsatisfiable core [2025-03-03 14:07:45,570 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-03 14:07:45,729 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 3 proven. 3 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2025-03-03 14:07:45,729 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-03 14:07:45,805 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2025-03-03 14:07:45,805 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-03 14:07:45,805 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [216546724] [2025-03-03 14:07:45,806 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-03 14:07:45,806 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [189207816] [2025-03-03 14:07:45,806 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [189207816] provided 1 perfect and 1 imperfect interpolant sequences [2025-03-03 14:07:45,806 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2025-03-03 14:07:45,806 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [9] total 10 [2025-03-03 14:07:45,807 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1415467071] [2025-03-03 14:07:45,807 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-03 14:07:45,807 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2025-03-03 14:07:45,807 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-03 14:07:45,808 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2025-03-03 14:07:45,808 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=21, Invalid=69, Unknown=0, NotChecked=0, Total=90 [2025-03-03 14:07:45,808 INFO L87 Difference]: Start difference. First operand 22 states and 26 transitions. Second operand has 5 states, 4 states have (on average 2.5) internal successors, (10), 4 states have internal predecessors, (10), 2 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-03 14:07:45,856 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 14:07:45,856 INFO L93 Difference]: Finished difference Result 32 states and 38 transitions. [2025-03-03 14:07:45,857 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2025-03-03 14:07:45,857 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), 2 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 23 [2025-03-03 14:07:45,857 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 14:07:45,858 INFO L225 Difference]: With dead ends: 32 [2025-03-03 14:07:45,858 INFO L226 Difference]: Without dead ends: 30 [2025-03-03 14:07:45,858 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 45 GetRequests, 34 SyntacticMatches, 2 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 12 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=25, Invalid=85, Unknown=0, NotChecked=0, Total=110 [2025-03-03 14:07:45,859 INFO L435 NwaCegarLoop]: 18 mSDtfsCounter, 5 mSDsluCounter, 50 mSDsCounter, 0 mSdLazyCounter, 35 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 6 SdHoareTripleChecker+Valid, 68 SdHoareTripleChecker+Invalid, 36 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 35 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-03-03 14:07:45,859 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [6 Valid, 68 Invalid, 36 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 35 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-03-03 14:07:45,859 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 30 states. [2025-03-03 14:07:45,864 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 30 to 27. [2025-03-03 14:07:45,864 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 27 states, 17 states have (on average 1.1764705882352942) internal successors, (20), 19 states have internal predecessors, (20), 6 states have call successors, (6), 3 states have call predecessors, (6), 3 states have return successors, (5), 4 states have call predecessors, (5), 5 states have call successors, (5) [2025-03-03 14:07:45,865 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 27 states to 27 states and 31 transitions. [2025-03-03 14:07:45,865 INFO L78 Accepts]: Start accepts. Automaton has 27 states and 31 transitions. Word has length 23 [2025-03-03 14:07:45,866 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 14:07:45,867 INFO L471 AbstractCegarLoop]: Abstraction has 27 states and 31 transitions. [2025-03-03 14:07:45,867 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), 2 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-03 14:07:45,867 INFO L276 IsEmpty]: Start isEmpty. Operand 27 states and 31 transitions. [2025-03-03 14:07:45,870 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 30 [2025-03-03 14:07:45,870 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 14:07:45,870 INFO L218 NwaCegarLoop]: trace histogram [3, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-03 14:07:45,875 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Ended with exit code 0 [2025-03-03 14:07:46,070 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 3 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable1 [2025-03-03 14:07:46,071 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 14:07:46,071 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 14:07:46,071 INFO L85 PathProgramCache]: Analyzing trace with hash 1696350775, now seen corresponding path program 1 times [2025-03-03 14:07:46,071 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 14:07:46,071 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [57503988] [2025-03-03 14:07:46,071 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 14:07:46,071 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 14:07:46,075 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 29 statements into 1 equivalence classes. [2025-03-03 14:07:46,088 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 29 of 29 statements. [2025-03-03 14:07:46,089 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 14:07:46,089 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 14:07:46,225 INFO L134 CoverageAnalysis]: Checked inductivity of 14 backedges. 8 proven. 0 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2025-03-03 14:07:46,226 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-03 14:07:46,226 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [57503988] [2025-03-03 14:07:46,226 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [57503988] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-03 14:07:46,226 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-03 14:07:46,226 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2025-03-03 14:07:46,226 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1398503113] [2025-03-03 14:07:46,226 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-03 14:07:46,226 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2025-03-03 14:07:46,226 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-03 14:07:46,227 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2025-03-03 14:07:46,227 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=10, Invalid=20, Unknown=0, NotChecked=0, Total=30 [2025-03-03 14:07:46,227 INFO L87 Difference]: Start difference. First operand 27 states and 31 transitions. Second operand has 6 states, 6 states have (on average 2.8333333333333335) internal successors, (17), 5 states have internal predecessors, (17), 3 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (4), 3 states have call predecessors, (4), 2 states have call successors, (4) [2025-03-03 14:07:46,285 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 14:07:46,286 INFO L93 Difference]: Finished difference Result 37 states and 42 transitions. [2025-03-03 14:07:46,286 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2025-03-03 14:07:46,286 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 2.8333333333333335) internal successors, (17), 5 states have internal predecessors, (17), 3 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (4), 3 states have call predecessors, (4), 2 states have call successors, (4) Word has length 29 [2025-03-03 14:07:46,286 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 14:07:46,287 INFO L225 Difference]: With dead ends: 37 [2025-03-03 14:07:46,287 INFO L226 Difference]: Without dead ends: 30 [2025-03-03 14:07:46,287 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 6 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=10, Invalid=20, Unknown=0, NotChecked=0, Total=30 [2025-03-03 14:07:46,287 INFO L435 NwaCegarLoop]: 18 mSDtfsCounter, 10 mSDsluCounter, 40 mSDsCounter, 0 mSdLazyCounter, 46 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 11 SdHoareTripleChecker+Valid, 58 SdHoareTripleChecker+Invalid, 46 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 46 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-03 14:07:46,288 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [11 Valid, 58 Invalid, 46 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 46 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-03 14:07:46,288 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 30 states. [2025-03-03 14:07:46,291 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 30 to 28. [2025-03-03 14:07:46,291 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 28 states, 18 states have (on average 1.1666666666666667) internal successors, (21), 19 states have internal predecessors, (21), 6 states have call successors, (6), 3 states have call predecessors, (6), 3 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) [2025-03-03 14:07:46,291 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 28 states to 28 states and 32 transitions. [2025-03-03 14:07:46,292 INFO L78 Accepts]: Start accepts. Automaton has 28 states and 32 transitions. Word has length 29 [2025-03-03 14:07:46,292 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 14:07:46,292 INFO L471 AbstractCegarLoop]: Abstraction has 28 states and 32 transitions. [2025-03-03 14:07:46,292 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 2.8333333333333335) internal successors, (17), 5 states have internal predecessors, (17), 3 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (4), 3 states have call predecessors, (4), 2 states have call successors, (4) [2025-03-03 14:07:46,292 INFO L276 IsEmpty]: Start isEmpty. Operand 28 states and 32 transitions. [2025-03-03 14:07:46,293 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 32 [2025-03-03 14:07:46,294 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 14:07:46,294 INFO L218 NwaCegarLoop]: trace histogram [3, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-03 14:07:46,294 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2 [2025-03-03 14:07:46,294 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 14:07:46,294 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 14:07:46,294 INFO L85 PathProgramCache]: Analyzing trace with hash -1715132203, now seen corresponding path program 1 times [2025-03-03 14:07:46,295 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 14:07:46,295 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1369553069] [2025-03-03 14:07:46,295 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 14:07:46,295 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 14:07:46,302 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 31 statements into 1 equivalence classes. [2025-03-03 14:07:46,329 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 31 of 31 statements. [2025-03-03 14:07:46,331 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 14:07:46,331 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-03 14:07:46,332 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2032245917] [2025-03-03 14:07:46,332 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 14:07:46,332 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 14:07:46,333 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 14:07:46,338 INFO L229 MonitoredProcess]: Starting monitored process 4 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-03 14:07:46,343 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2025-03-03 14:07:46,358 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 31 statements into 1 equivalence classes. [2025-03-03 14:07:46,373 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 31 of 31 statements. [2025-03-03 14:07:46,373 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 14:07:46,373 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 14:07:46,375 INFO L256 TraceCheckSpWp]: Trace formula consists of 87 conjuncts, 22 conjuncts are in the unsatisfiable core [2025-03-03 14:07:46,377 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-03 14:07:46,632 INFO L134 CoverageAnalysis]: Checked inductivity of 15 backedges. 1 proven. 2 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2025-03-03 14:07:46,632 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-03 14:07:47,874 INFO L134 CoverageAnalysis]: Checked inductivity of 15 backedges. 2 proven. 1 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2025-03-03 14:07:47,874 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-03 14:07:47,874 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1369553069] [2025-03-03 14:07:47,874 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-03 14:07:47,874 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2032245917] [2025-03-03 14:07:47,874 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2032245917] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-03 14:07:47,874 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-03-03 14:07:47,874 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 9] total 15 [2025-03-03 14:07:47,874 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1736987919] [2025-03-03 14:07:47,874 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-03-03 14:07:47,875 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 15 states [2025-03-03 14:07:47,875 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-03 14:07:47,875 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2025-03-03 14:07:47,875 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=44, Invalid=166, Unknown=0, NotChecked=0, Total=210 [2025-03-03 14:07:47,875 INFO L87 Difference]: Start difference. First operand 28 states and 32 transitions. Second operand has 15 states, 12 states have (on average 1.8333333333333333) internal successors, (22), 13 states have internal predecessors, (22), 4 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (5), 3 states have call predecessors, (5), 2 states have call successors, (5) [2025-03-03 14:07:49,027 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 14:07:49,028 INFO L93 Difference]: Finished difference Result 43 states and 51 transitions. [2025-03-03 14:07:49,028 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2025-03-03 14:07:49,028 INFO L78 Accepts]: Start accepts. Automaton has has 15 states, 12 states have (on average 1.8333333333333333) internal successors, (22), 13 states have internal predecessors, (22), 4 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (5), 3 states have call predecessors, (5), 2 states have call successors, (5) Word has length 31 [2025-03-03 14:07:49,028 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 14:07:49,030 INFO L225 Difference]: With dead ends: 43 [2025-03-03 14:07:49,030 INFO L226 Difference]: Without dead ends: 41 [2025-03-03 14:07:49,030 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 63 GetRequests, 45 SyntacticMatches, 2 SemanticMatches, 16 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 43 ImplicationChecksByTransitivity, 1.2s TimeCoverageRelationStatistics Valid=64, Invalid=242, Unknown=0, NotChecked=0, Total=306 [2025-03-03 14:07:49,030 INFO L435 NwaCegarLoop]: 18 mSDtfsCounter, 8 mSDsluCounter, 167 mSDsCounter, 0 mSdLazyCounter, 178 mSolverCounterSat, 6 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 9 SdHoareTripleChecker+Valid, 185 SdHoareTripleChecker+Invalid, 184 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 6 IncrementalHoareTripleChecker+Valid, 178 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.1s IncrementalHoareTripleChecker+Time [2025-03-03 14:07:49,031 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [9 Valid, 185 Invalid, 184 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [6 Valid, 178 Invalid, 0 Unknown, 0 Unchecked, 1.1s Time] [2025-03-03 14:07:49,031 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 41 states. [2025-03-03 14:07:49,034 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 41 to 39. [2025-03-03 14:07:49,035 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 39 states, 26 states have (on average 1.2307692307692308) internal successors, (32), 28 states have internal predecessors, (32), 8 states have call successors, (8), 4 states have call predecessors, (8), 4 states have return successors, (7), 6 states have call predecessors, (7), 7 states have call successors, (7) [2025-03-03 14:07:49,035 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 39 states to 39 states and 47 transitions. [2025-03-03 14:07:49,035 INFO L78 Accepts]: Start accepts. Automaton has 39 states and 47 transitions. Word has length 31 [2025-03-03 14:07:49,035 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 14:07:49,035 INFO L471 AbstractCegarLoop]: Abstraction has 39 states and 47 transitions. [2025-03-03 14:07:49,036 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 15 states, 12 states have (on average 1.8333333333333333) internal successors, (22), 13 states have internal predecessors, (22), 4 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (5), 3 states have call predecessors, (5), 2 states have call successors, (5) [2025-03-03 14:07:49,036 INFO L276 IsEmpty]: Start isEmpty. Operand 39 states and 47 transitions. [2025-03-03 14:07:49,036 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 32 [2025-03-03 14:07:49,036 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 14:07:49,036 INFO L218 NwaCegarLoop]: trace histogram [3, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-03 14:07:49,042 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Forceful destruction successful, exit code 0 [2025-03-03 14:07:49,237 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 14:07:49,237 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 14:07:49,237 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 14:07:49,238 INFO L85 PathProgramCache]: Analyzing trace with hash -1686503052, now seen corresponding path program 1 times [2025-03-03 14:07:49,238 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 14:07:49,238 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1852361494] [2025-03-03 14:07:49,238 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 14:07:49,238 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 14:07:49,241 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 31 statements into 1 equivalence classes. [2025-03-03 14:07:49,250 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 31 of 31 statements. [2025-03-03 14:07:49,250 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 14:07:49,251 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-03 14:07:49,251 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2135990726] [2025-03-03 14:07:49,251 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 14:07:49,251 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 14:07:49,252 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 14:07:49,253 INFO L229 MonitoredProcess]: Starting monitored process 5 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-03 14:07:49,255 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2025-03-03 14:07:49,276 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 31 statements into 1 equivalence classes. [2025-03-03 14:07:49,285 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 31 of 31 statements. [2025-03-03 14:07:49,286 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 14:07:49,286 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 14:07:49,286 INFO L256 TraceCheckSpWp]: Trace formula consists of 82 conjuncts, 22 conjuncts are in the unsatisfiable core [2025-03-03 14:07:49,288 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-03 14:07:49,450 INFO L134 CoverageAnalysis]: Checked inductivity of 15 backedges. 7 proven. 2 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2025-03-03 14:07:49,450 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-03 14:07:49,802 INFO L134 CoverageAnalysis]: Checked inductivity of 15 backedges. 7 proven. 2 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2025-03-03 14:07:49,802 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-03 14:07:49,802 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1852361494] [2025-03-03 14:07:49,802 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-03 14:07:49,802 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2135990726] [2025-03-03 14:07:49,802 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2135990726] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-03 14:07:49,803 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-03-03 14:07:49,803 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 13] total 20 [2025-03-03 14:07:49,803 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1696103076] [2025-03-03 14:07:49,803 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-03-03 14:07:49,803 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 20 states [2025-03-03 14:07:49,803 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-03 14:07:49,804 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 20 interpolants. [2025-03-03 14:07:49,804 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=67, Invalid=313, Unknown=0, NotChecked=0, Total=380 [2025-03-03 14:07:49,804 INFO L87 Difference]: Start difference. First operand 39 states and 47 transitions. Second operand has 20 states, 16 states have (on average 1.6875) internal successors, (27), 17 states have internal predecessors, (27), 5 states have call successors, (7), 2 states have call predecessors, (7), 3 states have return successors, (6), 5 states have call predecessors, (6), 3 states have call successors, (6) [2025-03-03 14:07:50,207 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 14:07:50,208 INFO L93 Difference]: Finished difference Result 66 states and 80 transitions. [2025-03-03 14:07:50,208 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 17 states. [2025-03-03 14:07:50,208 INFO L78 Accepts]: Start accepts. Automaton has has 20 states, 16 states have (on average 1.6875) internal successors, (27), 17 states have internal predecessors, (27), 5 states have call successors, (7), 2 states have call predecessors, (7), 3 states have return successors, (6), 5 states have call predecessors, (6), 3 states have call successors, (6) Word has length 31 [2025-03-03 14:07:50,209 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 14:07:50,209 INFO L225 Difference]: With dead ends: 66 [2025-03-03 14:07:50,209 INFO L226 Difference]: Without dead ends: 59 [2025-03-03 14:07:50,210 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 65 GetRequests, 40 SyntacticMatches, 2 SemanticMatches, 23 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 106 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=116, Invalid=484, Unknown=0, NotChecked=0, Total=600 [2025-03-03 14:07:50,210 INFO L435 NwaCegarLoop]: 13 mSDtfsCounter, 26 mSDsluCounter, 107 mSDsCounter, 0 mSdLazyCounter, 228 mSolverCounterSat, 19 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 28 SdHoareTripleChecker+Valid, 120 SdHoareTripleChecker+Invalid, 247 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 19 IncrementalHoareTripleChecker+Valid, 228 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2025-03-03 14:07:50,210 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [28 Valid, 120 Invalid, 247 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [19 Valid, 228 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2025-03-03 14:07:50,211 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 59 states. [2025-03-03 14:07:50,220 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 59 to 59. [2025-03-03 14:07:50,221 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 59 states, 40 states have (on average 1.225) internal successors, (49), 44 states have internal predecessors, (49), 12 states have call successors, (12), 6 states have call predecessors, (12), 6 states have return successors, (11), 8 states have call predecessors, (11), 11 states have call successors, (11) [2025-03-03 14:07:50,222 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 59 states to 59 states and 72 transitions. [2025-03-03 14:07:50,223 INFO L78 Accepts]: Start accepts. Automaton has 59 states and 72 transitions. Word has length 31 [2025-03-03 14:07:50,223 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 14:07:50,224 INFO L471 AbstractCegarLoop]: Abstraction has 59 states and 72 transitions. [2025-03-03 14:07:50,224 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 20 states, 16 states have (on average 1.6875) internal successors, (27), 17 states have internal predecessors, (27), 5 states have call successors, (7), 2 states have call predecessors, (7), 3 states have return successors, (6), 5 states have call predecessors, (6), 3 states have call successors, (6) [2025-03-03 14:07:50,224 INFO L276 IsEmpty]: Start isEmpty. Operand 59 states and 72 transitions. [2025-03-03 14:07:50,224 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 38 [2025-03-03 14:07:50,225 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 14:07:50,225 INFO L218 NwaCegarLoop]: trace histogram [3, 3, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-03 14:07:50,232 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-03 14:07:50,425 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 14:07:50,426 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 14:07:50,426 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 14:07:50,426 INFO L85 PathProgramCache]: Analyzing trace with hash -514072932, now seen corresponding path program 1 times [2025-03-03 14:07:50,426 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 14:07:50,426 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [123417765] [2025-03-03 14:07:50,426 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 14:07:50,426 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 14:07:50,429 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 37 statements into 1 equivalence classes. [2025-03-03 14:07:50,440 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 37 of 37 statements. [2025-03-03 14:07:50,440 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 14:07:50,440 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-03 14:07:50,443 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1307264544] [2025-03-03 14:07:50,444 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 14:07:50,444 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 14:07:50,444 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 14:07:50,446 INFO L229 MonitoredProcess]: Starting monitored process 6 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-03 14:07:50,448 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2025-03-03 14:07:50,467 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 37 statements into 1 equivalence classes. [2025-03-03 14:07:50,477 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 37 of 37 statements. [2025-03-03 14:07:50,477 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 14:07:50,477 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 14:07:50,478 INFO L256 TraceCheckSpWp]: Trace formula consists of 98 conjuncts, 10 conjuncts are in the unsatisfiable core [2025-03-03 14:07:50,479 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-03 14:07:50,521 INFO L134 CoverageAnalysis]: Checked inductivity of 22 backedges. 7 proven. 1 refuted. 0 times theorem prover too weak. 14 trivial. 0 not checked. [2025-03-03 14:07:50,521 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-03 14:07:50,598 INFO L134 CoverageAnalysis]: Checked inductivity of 22 backedges. 7 proven. 1 refuted. 0 times theorem prover too weak. 14 trivial. 0 not checked. [2025-03-03 14:07:50,598 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-03 14:07:50,598 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [123417765] [2025-03-03 14:07:50,598 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-03 14:07:50,598 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1307264544] [2025-03-03 14:07:50,598 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1307264544] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-03 14:07:50,598 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-03-03 14:07:50,598 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 10 [2025-03-03 14:07:50,598 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1790724167] [2025-03-03 14:07:50,598 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-03-03 14:07:50,598 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2025-03-03 14:07:50,598 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-03 14:07:50,599 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2025-03-03 14:07:50,599 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=24, Invalid=66, Unknown=0, NotChecked=0, Total=90 [2025-03-03 14:07:50,599 INFO L87 Difference]: Start difference. First operand 59 states and 72 transitions. Second operand has 10 states, 9 states have (on average 2.5555555555555554) internal successors, (23), 7 states have internal predecessors, (23), 2 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (6), 3 states have call predecessors, (6), 1 states have call successors, (6) [2025-03-03 14:07:50,692 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 14:07:50,693 INFO L93 Difference]: Finished difference Result 65 states and 77 transitions. [2025-03-03 14:07:50,693 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2025-03-03 14:07:50,693 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 9 states have (on average 2.5555555555555554) internal successors, (23), 7 states have internal predecessors, (23), 2 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (6), 3 states have call predecessors, (6), 1 states have call successors, (6) Word has length 37 [2025-03-03 14:07:50,693 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 14:07:50,694 INFO L225 Difference]: With dead ends: 65 [2025-03-03 14:07:50,694 INFO L226 Difference]: Without dead ends: 58 [2025-03-03 14:07:50,695 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 73 GetRequests, 62 SyntacticMatches, 2 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 14 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=31, Invalid=79, Unknown=0, NotChecked=0, Total=110 [2025-03-03 14:07:50,695 INFO L435 NwaCegarLoop]: 20 mSDtfsCounter, 5 mSDsluCounter, 114 mSDsCounter, 0 mSdLazyCounter, 80 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 5 SdHoareTripleChecker+Valid, 134 SdHoareTripleChecker+Invalid, 81 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 80 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-03 14:07:50,695 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [5 Valid, 134 Invalid, 81 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 80 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-03 14:07:50,696 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 58 states. [2025-03-03 14:07:50,706 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 58 to 58. [2025-03-03 14:07:50,706 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 58 states, 40 states have (on average 1.15) internal successors, (46), 43 states have internal predecessors, (46), 11 states have call successors, (11), 6 states have call predecessors, (11), 6 states have return successors, (11), 8 states have call predecessors, (11), 11 states have call successors, (11) [2025-03-03 14:07:50,708 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 58 states to 58 states and 68 transitions. [2025-03-03 14:07:50,708 INFO L78 Accepts]: Start accepts. Automaton has 58 states and 68 transitions. Word has length 37 [2025-03-03 14:07:50,708 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 14:07:50,708 INFO L471 AbstractCegarLoop]: Abstraction has 58 states and 68 transitions. [2025-03-03 14:07:50,708 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 9 states have (on average 2.5555555555555554) internal successors, (23), 7 states have internal predecessors, (23), 2 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (6), 3 states have call predecessors, (6), 1 states have call successors, (6) [2025-03-03 14:07:50,708 INFO L276 IsEmpty]: Start isEmpty. Operand 58 states and 68 transitions. [2025-03-03 14:07:50,709 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 48 [2025-03-03 14:07:50,709 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 14:07:50,709 INFO L218 NwaCegarLoop]: trace histogram [4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-03 14:07:50,716 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Forceful destruction successful, exit code 0 [2025-03-03 14:07:50,914 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 14:07:50,914 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 14:07:50,914 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 14:07:50,914 INFO L85 PathProgramCache]: Analyzing trace with hash -1695860034, now seen corresponding path program 1 times [2025-03-03 14:07:50,914 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 14:07:50,914 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [986666302] [2025-03-03 14:07:50,914 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 14:07:50,915 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 14:07:50,921 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 47 statements into 1 equivalence classes. [2025-03-03 14:07:50,970 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 47 of 47 statements. [2025-03-03 14:07:50,970 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 14:07:50,970 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 14:07:51,482 INFO L134 CoverageAnalysis]: Checked inductivity of 45 backedges. 15 proven. 12 refuted. 0 times theorem prover too weak. 18 trivial. 0 not checked. [2025-03-03 14:07:51,482 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-03 14:07:51,482 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [986666302] [2025-03-03 14:07:51,482 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [986666302] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-03 14:07:51,483 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [789358035] [2025-03-03 14:07:51,483 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 14:07:51,483 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 14:07:51,483 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 14:07:51,484 INFO L229 MonitoredProcess]: Starting monitored process 7 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-03 14:07:51,486 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2025-03-03 14:07:51,510 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 47 statements into 1 equivalence classes. [2025-03-03 14:07:51,528 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 47 of 47 statements. [2025-03-03 14:07:51,528 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 14:07:51,528 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 14:07:51,529 INFO L256 TraceCheckSpWp]: Trace formula consists of 122 conjuncts, 19 conjuncts are in the unsatisfiable core [2025-03-03 14:07:51,531 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-03 14:07:51,723 INFO L134 CoverageAnalysis]: Checked inductivity of 45 backedges. 24 proven. 3 refuted. 0 times theorem prover too weak. 18 trivial. 0 not checked. [2025-03-03 14:07:51,723 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-03 14:07:51,996 INFO L134 CoverageAnalysis]: Checked inductivity of 45 backedges. 14 proven. 13 refuted. 0 times theorem prover too weak. 18 trivial. 0 not checked. [2025-03-03 14:07:51,996 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [789358035] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-03 14:07:51,996 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-03 14:07:51,996 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 13, 11] total 23 [2025-03-03 14:07:51,997 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [836757089] [2025-03-03 14:07:51,997 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-03 14:07:51,997 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 23 states [2025-03-03 14:07:51,998 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-03 14:07:51,999 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 23 interpolants. [2025-03-03 14:07:51,999 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=110, Invalid=396, Unknown=0, NotChecked=0, Total=506 [2025-03-03 14:07:51,999 INFO L87 Difference]: Start difference. First operand 58 states and 68 transitions. Second operand has 23 states, 23 states have (on average 1.8695652173913044) internal successors, (43), 21 states have internal predecessors, (43), 11 states have call successors, (12), 2 states have call predecessors, (12), 2 states have return successors, (12), 10 states have call predecessors, (12), 10 states have call successors, (12) [2025-03-03 14:07:52,299 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 14:07:52,300 INFO L93 Difference]: Finished difference Result 81 states and 95 transitions. [2025-03-03 14:07:52,300 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 18 states. [2025-03-03 14:07:52,300 INFO L78 Accepts]: Start accepts. Automaton has has 23 states, 23 states have (on average 1.8695652173913044) internal successors, (43), 21 states have internal predecessors, (43), 11 states have call successors, (12), 2 states have call predecessors, (12), 2 states have return successors, (12), 10 states have call predecessors, (12), 10 states have call successors, (12) Word has length 47 [2025-03-03 14:07:52,300 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 14:07:52,301 INFO L225 Difference]: With dead ends: 81 [2025-03-03 14:07:52,301 INFO L226 Difference]: Without dead ends: 58 [2025-03-03 14:07:52,301 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 117 GetRequests, 81 SyntacticMatches, 2 SemanticMatches, 34 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 222 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=296, Invalid=964, Unknown=0, NotChecked=0, Total=1260 [2025-03-03 14:07:52,302 INFO L435 NwaCegarLoop]: 21 mSDtfsCounter, 18 mSDsluCounter, 160 mSDsCounter, 0 mSdLazyCounter, 198 mSolverCounterSat, 15 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 18 SdHoareTripleChecker+Valid, 181 SdHoareTripleChecker+Invalid, 213 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 15 IncrementalHoareTripleChecker+Valid, 198 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-03 14:07:52,302 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [18 Valid, 181 Invalid, 213 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [15 Valid, 198 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-03 14:07:52,302 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 58 states. [2025-03-03 14:07:52,309 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 58 to 58. [2025-03-03 14:07:52,310 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 58 states, 40 states have (on average 1.075) internal successors, (43), 43 states have internal predecessors, (43), 11 states have call successors, (11), 6 states have call predecessors, (11), 6 states have return successors, (11), 8 states have call predecessors, (11), 11 states have call successors, (11) [2025-03-03 14:07:52,310 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 58 states to 58 states and 65 transitions. [2025-03-03 14:07:52,311 INFO L78 Accepts]: Start accepts. Automaton has 58 states and 65 transitions. Word has length 47 [2025-03-03 14:07:52,312 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 14:07:52,312 INFO L471 AbstractCegarLoop]: Abstraction has 58 states and 65 transitions. [2025-03-03 14:07:52,312 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 23 states, 23 states have (on average 1.8695652173913044) internal successors, (43), 21 states have internal predecessors, (43), 11 states have call successors, (12), 2 states have call predecessors, (12), 2 states have return successors, (12), 10 states have call predecessors, (12), 10 states have call successors, (12) [2025-03-03 14:07:52,312 INFO L276 IsEmpty]: Start isEmpty. Operand 58 states and 65 transitions. [2025-03-03 14:07:52,313 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 48 [2025-03-03 14:07:52,314 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 14:07:52,314 INFO L218 NwaCegarLoop]: trace histogram [4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-03 14:07:52,320 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-03 14:07:52,519 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 14:07:52,519 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 14:07:52,520 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 14:07:52,520 INFO L85 PathProgramCache]: Analyzing trace with hash 2093548637, now seen corresponding path program 2 times [2025-03-03 14:07:52,520 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 14:07:52,520 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [573833904] [2025-03-03 14:07:52,520 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-03 14:07:52,521 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 14:07:52,525 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 47 statements into 2 equivalence classes. [2025-03-03 14:07:52,545 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 47 of 47 statements. [2025-03-03 14:07:52,545 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-03 14:07:52,545 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-03 14:07:52,546 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1797142103] [2025-03-03 14:07:52,546 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-03 14:07:52,546 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 14:07:52,546 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 14:07:52,549 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-03 14:07:52,551 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-03 14:07:52,569 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 47 statements into 2 equivalence classes. [2025-03-03 14:07:52,582 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 47 of 47 statements. [2025-03-03 14:07:52,582 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-03 14:07:52,582 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 14:07:52,583 INFO L256 TraceCheckSpWp]: Trace formula consists of 117 conjuncts, 30 conjuncts are in the unsatisfiable core [2025-03-03 14:07:52,588 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-03 14:07:53,142 INFO L134 CoverageAnalysis]: Checked inductivity of 45 backedges. 5 proven. 22 refuted. 0 times theorem prover too weak. 18 trivial. 0 not checked. [2025-03-03 14:07:53,142 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-03 14:08:08,738 INFO L134 CoverageAnalysis]: Checked inductivity of 45 backedges. 8 proven. 19 refuted. 0 times theorem prover too weak. 18 trivial. 0 not checked. [2025-03-03 14:08:08,738 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-03 14:08:08,738 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [573833904] [2025-03-03 14:08:08,738 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-03 14:08:08,738 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1797142103] [2025-03-03 14:08:08,738 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1797142103] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-03 14:08:08,738 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-03-03 14:08:08,738 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [15, 13] total 23 [2025-03-03 14:08:08,738 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [555729495] [2025-03-03 14:08:08,738 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-03-03 14:08:08,739 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 23 states [2025-03-03 14:08:08,739 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-03 14:08:08,739 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 23 interpolants. [2025-03-03 14:08:08,740 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=94, Invalid=412, Unknown=0, NotChecked=0, Total=506 [2025-03-03 14:08:08,740 INFO L87 Difference]: Start difference. First operand 58 states and 65 transitions. Second operand has 23 states, 20 states have (on average 1.85) internal successors, (37), 21 states have internal predecessors, (37), 8 states have call successors, (11), 2 states have call predecessors, (11), 2 states have return successors, (9), 7 states have call predecessors, (9), 6 states have call successors, (9) [2025-03-03 14:08:17,485 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 14:08:17,485 INFO L93 Difference]: Finished difference Result 80 states and 90 transitions. [2025-03-03 14:08:17,485 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 21 states. [2025-03-03 14:08:17,485 INFO L78 Accepts]: Start accepts. Automaton has has 23 states, 20 states have (on average 1.85) internal successors, (37), 21 states have internal predecessors, (37), 8 states have call successors, (11), 2 states have call predecessors, (11), 2 states have return successors, (9), 7 states have call predecessors, (9), 6 states have call successors, (9) Word has length 47 [2025-03-03 14:08:17,485 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 14:08:17,486 INFO L225 Difference]: With dead ends: 80 [2025-03-03 14:08:17,486 INFO L226 Difference]: Without dead ends: 78 [2025-03-03 14:08:17,487 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 99 GetRequests, 69 SyntacticMatches, 2 SemanticMatches, 28 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 185 ImplicationChecksByTransitivity, 20.4s TimeCoverageRelationStatistics Valid=180, Invalid=690, Unknown=0, NotChecked=0, Total=870 [2025-03-03 14:08:17,487 INFO L435 NwaCegarLoop]: 19 mSDtfsCounter, 10 mSDsluCounter, 164 mSDsCounter, 0 mSdLazyCounter, 237 mSolverCounterSat, 8 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.9s Time, 0 mProtectedPredicate, 0 mProtectedAction, 11 SdHoareTripleChecker+Valid, 183 SdHoareTripleChecker+Invalid, 245 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 8 IncrementalHoareTripleChecker+Valid, 237 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.9s IncrementalHoareTripleChecker+Time [2025-03-03 14:08:17,487 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [11 Valid, 183 Invalid, 245 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [8 Valid, 237 Invalid, 0 Unknown, 0 Unchecked, 1.9s Time] [2025-03-03 14:08:17,488 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 78 states. [2025-03-03 14:08:17,493 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 78 to 78. [2025-03-03 14:08:17,494 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 78 states, 55 states have (on average 1.0545454545454545) internal successors, (58), 58 states have internal predecessors, (58), 15 states have call successors, (15), 7 states have call predecessors, (15), 7 states have return successors, (15), 12 states have call predecessors, (15), 15 states have call successors, (15) [2025-03-03 14:08:17,494 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 78 states to 78 states and 88 transitions. [2025-03-03 14:08:17,494 INFO L78 Accepts]: Start accepts. Automaton has 78 states and 88 transitions. Word has length 47 [2025-03-03 14:08:17,494 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 14:08:17,494 INFO L471 AbstractCegarLoop]: Abstraction has 78 states and 88 transitions. [2025-03-03 14:08:17,495 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 23 states, 20 states have (on average 1.85) internal successors, (37), 21 states have internal predecessors, (37), 8 states have call successors, (11), 2 states have call predecessors, (11), 2 states have return successors, (9), 7 states have call predecessors, (9), 6 states have call successors, (9) [2025-03-03 14:08:17,495 INFO L276 IsEmpty]: Start isEmpty. Operand 78 states and 88 transitions. [2025-03-03 14:08:17,496 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 56 [2025-03-03 14:08:17,497 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 14:08:17,497 INFO L218 NwaCegarLoop]: trace histogram [5, 5, 4, 4, 4, 4, 4, 4, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-03 14:08:17,503 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Ended with exit code 0 [2025-03-03 14:08:17,697 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 14:08:17,698 INFO L396 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 14:08:17,698 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 14:08:17,698 INFO L85 PathProgramCache]: Analyzing trace with hash -2042325056, now seen corresponding path program 2 times [2025-03-03 14:08:17,698 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 14:08:17,698 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1978614050] [2025-03-03 14:08:17,698 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-03 14:08:17,698 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 14:08:17,701 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 55 statements into 2 equivalence classes. [2025-03-03 14:08:17,726 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 55 of 55 statements. [2025-03-03 14:08:17,727 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-03 14:08:17,727 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 14:08:18,178 INFO L134 CoverageAnalysis]: Checked inductivity of 72 backedges. 31 proven. 11 refuted. 0 times theorem prover too weak. 30 trivial. 0 not checked. [2025-03-03 14:08:18,179 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-03 14:08:18,179 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1978614050] [2025-03-03 14:08:18,179 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1978614050] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-03 14:08:18,179 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [771446113] [2025-03-03 14:08:18,179 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-03 14:08:18,179 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 14:08:18,179 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 14:08:18,181 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-03 14:08:18,182 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-03 14:08:18,202 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 55 statements into 2 equivalence classes. [2025-03-03 14:08:18,215 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 55 of 55 statements. [2025-03-03 14:08:18,216 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-03 14:08:18,216 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 14:08:18,217 INFO L256 TraceCheckSpWp]: Trace formula consists of 127 conjuncts, 20 conjuncts are in the unsatisfiable core [2025-03-03 14:08:18,218 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-03 14:08:18,369 INFO L134 CoverageAnalysis]: Checked inductivity of 72 backedges. 39 proven. 3 refuted. 0 times theorem prover too weak. 30 trivial. 0 not checked. [2025-03-03 14:08:18,369 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-03 14:08:18,839 INFO L134 CoverageAnalysis]: Checked inductivity of 72 backedges. 39 proven. 3 refuted. 0 times theorem prover too weak. 30 trivial. 0 not checked. [2025-03-03 14:08:18,839 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [771446113] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-03 14:08:18,840 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-03 14:08:18,840 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 13, 13] total 31 [2025-03-03 14:08:18,841 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [435472834] [2025-03-03 14:08:18,841 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-03 14:08:18,841 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 31 states [2025-03-03 14:08:18,841 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-03 14:08:18,842 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 31 interpolants. [2025-03-03 14:08:18,842 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=177, Invalid=753, Unknown=0, NotChecked=0, Total=930 [2025-03-03 14:08:18,842 INFO L87 Difference]: Start difference. First operand 78 states and 88 transitions. Second operand has 31 states, 30 states have (on average 1.7666666666666666) internal successors, (53), 27 states have internal predecessors, (53), 17 states have call successors, (18), 2 states have call predecessors, (18), 2 states have return successors, (19), 17 states have call predecessors, (19), 16 states have call successors, (19) [2025-03-03 14:08:19,062 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 14:08:19,062 INFO L93 Difference]: Finished difference Result 90 states and 100 transitions. [2025-03-03 14:08:19,062 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2025-03-03 14:08:19,062 INFO L78 Accepts]: Start accepts. Automaton has has 31 states, 30 states have (on average 1.7666666666666666) internal successors, (53), 27 states have internal predecessors, (53), 17 states have call successors, (18), 2 states have call predecessors, (18), 2 states have return successors, (19), 17 states have call predecessors, (19), 16 states have call successors, (19) Word has length 55 [2025-03-03 14:08:19,062 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 14:08:19,063 INFO L225 Difference]: With dead ends: 90 [2025-03-03 14:08:19,063 INFO L226 Difference]: Without dead ends: 0 [2025-03-03 14:08:19,063 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 134 GetRequests, 95 SyntacticMatches, 1 SemanticMatches, 38 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 401 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=334, Invalid=1226, Unknown=0, NotChecked=0, Total=1560 [2025-03-03 14:08:19,063 INFO L435 NwaCegarLoop]: 21 mSDtfsCounter, 11 mSDsluCounter, 193 mSDsCounter, 0 mSdLazyCounter, 242 mSolverCounterSat, 9 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 11 SdHoareTripleChecker+Valid, 214 SdHoareTripleChecker+Invalid, 251 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 9 IncrementalHoareTripleChecker+Valid, 242 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-03 14:08:19,064 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [11 Valid, 214 Invalid, 251 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [9 Valid, 242 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-03 14:08:19,064 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 0 states. [2025-03-03 14:08:19,064 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 0 to 0. [2025-03-03 14:08:19,064 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-03 14:08:19,064 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 0 states to 0 states and 0 transitions. [2025-03-03 14:08:19,064 INFO L78 Accepts]: Start accepts. Automaton has 0 states and 0 transitions. Word has length 55 [2025-03-03 14:08:19,064 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 14:08:19,064 INFO L471 AbstractCegarLoop]: Abstraction has 0 states and 0 transitions. [2025-03-03 14:08:19,064 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 31 states, 30 states have (on average 1.7666666666666666) internal successors, (53), 27 states have internal predecessors, (53), 17 states have call successors, (18), 2 states have call predecessors, (18), 2 states have return successors, (19), 17 states have call predecessors, (19), 16 states have call successors, (19) [2025-03-03 14:08:19,064 INFO L276 IsEmpty]: Start isEmpty. Operand 0 states and 0 transitions. [2025-03-03 14:08:19,064 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2025-03-03 14:08:19,066 INFO L782 garLoopResultBuilder]: Registering result SAFE for location __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION (0 of 1 remaining) [2025-03-03 14:08:19,072 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-03 14:08:19,267 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,SelfDestructingSolverStorable8 [2025-03-03 14:08:19,269 INFO L422 BasicCegarLoop]: Path program histogram: [2, 2, 1, 1, 1, 1, 1] [2025-03-03 14:08:19,270 INFO L343 DoubleDeckerVisitor]: Before removal of dead ends 0 states and 0 transitions. [2025-03-03 14:08:19,442 INFO L170 ceAbstractionStarter]: Computing trace abstraction results [2025-03-03 14:08:19,457 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 03.03 02:08:19 BoogieIcfgContainer [2025-03-03 14:08:19,461 INFO L131 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2025-03-03 14:08:19,461 INFO L112 PluginConnector]: ------------------------Witness Printer---------------------------- [2025-03-03 14:08:19,461 INFO L270 PluginConnector]: Initializing Witness Printer... [2025-03-03 14:08:19,462 INFO L274 PluginConnector]: Witness Printer initialized [2025-03-03 14:08:19,462 INFO L184 PluginConnector]: Executing the observer RCFGCatcher from plugin Witness Printer for "de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 03.03 02:07:44" (3/4) ... [2025-03-03 14:08:19,464 INFO L146 WitnessPrinter]: Generating witness for correct program [2025-03-03 14:08:19,469 INFO L385 IcfgBacktranslator]: Ignoring RootEdge to procedure assume_abort_if_not [2025-03-03 14:08:19,469 INFO L385 IcfgBacktranslator]: Ignoring RootEdge to procedure __VERIFIER_assert [2025-03-03 14:08:19,475 INFO L919 BoogieBacktranslator]: Reduced CFG by removing 13 nodes and edges [2025-03-03 14:08:19,475 INFO L919 BoogieBacktranslator]: Reduced CFG by removing 4 nodes and edges [2025-03-03 14:08:19,475 INFO L919 BoogieBacktranslator]: Reduced CFG by removing 3 nodes and edges [2025-03-03 14:08:19,475 INFO L919 BoogieBacktranslator]: Reduced CFG by removing 1 nodes and edges [2025-03-03 14:08:19,536 INFO L149 WitnessManager]: Wrote witness to /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/witness.graphml [2025-03-03 14:08:19,537 INFO L149 WitnessManager]: Wrote witness to /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/witness.yml [2025-03-03 14:08:19,537 INFO L131 PluginConnector]: ------------------------ END Witness Printer---------------------------- [2025-03-03 14:08:19,538 INFO L158 Benchmark]: Toolchain (without parser) took 35026.45ms. Allocated memory was 167.8MB in the beginning and 369.1MB in the end (delta: 201.3MB). Free memory was 122.9MB in the beginning and 184.6MB in the end (delta: -61.7MB). Peak memory consumption was 136.0MB. Max. memory is 16.1GB. [2025-03-03 14:08:19,538 INFO L158 Benchmark]: CDTParser took 0.21ms. Allocated memory is still 201.3MB. Free memory is still 116.4MB. There was no memory consumed. Max. memory is 16.1GB. [2025-03-03 14:08:19,538 INFO L158 Benchmark]: CACSL2BoogieTranslator took 154.22ms. Allocated memory is still 167.8MB. Free memory was 122.0MB in the beginning and 111.7MB in the end (delta: 10.3MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. [2025-03-03 14:08:19,539 INFO L158 Benchmark]: Boogie Procedure Inliner took 24.61ms. Allocated memory is still 167.8MB. Free memory was 111.7MB in the beginning and 109.9MB in the end (delta: 1.7MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. [2025-03-03 14:08:19,539 INFO L158 Benchmark]: Boogie Preprocessor took 26.25ms. Allocated memory is still 167.8MB. Free memory was 109.9MB in the beginning and 109.0MB in the end (delta: 914.3kB). There was no memory consumed. Max. memory is 16.1GB. [2025-03-03 14:08:19,539 INFO L158 Benchmark]: IcfgBuilder took 195.83ms. Allocated memory is still 167.8MB. Free memory was 109.0MB in the beginning and 97.9MB in the end (delta: 11.1MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. [2025-03-03 14:08:19,540 INFO L158 Benchmark]: TraceAbstraction took 34543.83ms. Allocated memory was 167.8MB in the beginning and 369.1MB in the end (delta: 201.3MB). Free memory was 97.0MB in the beginning and 192.8MB in the end (delta: -95.9MB). Peak memory consumption was 110.9MB. Max. memory is 16.1GB. [2025-03-03 14:08:19,540 INFO L158 Benchmark]: Witness Printer took 75.55ms. Allocated memory is still 369.1MB. Free memory was 192.8MB in the beginning and 184.6MB in the end (delta: 8.3MB). There was no memory consumed. Max. memory is 16.1GB. [2025-03-03 14:08:19,541 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.21ms. Allocated memory is still 201.3MB. Free memory is still 116.4MB. There was no memory consumed. Max. memory is 16.1GB. * CACSL2BoogieTranslator took 154.22ms. Allocated memory is still 167.8MB. Free memory was 122.0MB in the beginning and 111.7MB in the end (delta: 10.3MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. * Boogie Procedure Inliner took 24.61ms. Allocated memory is still 167.8MB. Free memory was 111.7MB in the beginning and 109.9MB in the end (delta: 1.7MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. * Boogie Preprocessor took 26.25ms. Allocated memory is still 167.8MB. Free memory was 109.9MB in the beginning and 109.0MB in the end (delta: 914.3kB). There was no memory consumed. Max. memory is 16.1GB. * IcfgBuilder took 195.83ms. Allocated memory is still 167.8MB. Free memory was 109.0MB in the beginning and 97.9MB in the end (delta: 11.1MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. * TraceAbstraction took 34543.83ms. Allocated memory was 167.8MB in the beginning and 369.1MB in the end (delta: 201.3MB). Free memory was 97.0MB in the beginning and 192.8MB in the end (delta: -95.9MB). Peak memory consumption was 110.9MB. Max. memory is 16.1GB. * Witness Printer took 75.55ms. Allocated memory is still 369.1MB. Free memory was 192.8MB in the beginning and 184.6MB in the end (delta: 8.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: 15]: 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 3 procedures, 26 locations, 1 error locations. Started 1 CEGAR loops. OverallTime: 34.3s, OverallIterations: 9, TraceHistogramMax: 5, PathProgramHistogramMax: 2, EmptinessCheckTime: 0.0s, AutomataDifference: 11.1s, DeadEndRemovalTime: 0.0s, HoareAnnotationTime: 0.0s, InitialAbstractionConstructionTime: 0.0s, HoareTripleCheckerStatistics: 0 mSolverCounterUnknown, 99 SdHoareTripleChecker+Valid, 3.6s IncrementalHoareTripleChecker+Time, 0 mSdLazyCounter, 93 mSDsluCounter, 1173 SdHoareTripleChecker+Invalid, 3.4s Time, 0 mProtectedAction, 0 SdHoareTripleChecker+Unchecked, 0 IncrementalHoareTripleChecker+Unchecked, 995 mSDsCounter, 59 IncrementalHoareTripleChecker+Valid, 0 mProtectedPredicate, 1244 IncrementalHoareTripleChecker+Invalid, 1303 SdHoareTripleChecker+Unknown, 0 mSolverCounterNotChecked, 59 mSolverCounterUnsat, 178 mSDtfsCounter, 1244 mSolverCounterSat, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Unknown, PredicateUnifierStatistics: 0 DeclaredPredicates, 626 GetRequests, 452 SyntacticMatches, 13 SemanticMatches, 161 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 983 ImplicationChecksByTransitivity, 23.1s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=78occurred in iteration=8, InterpolantAutomatonStates: 106, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 0.0s DumpTime, AutomataMinimizationStatistics: 0.1s AutomataMinimizationTime, 9 MinimizatonAttempts, 7 StatesRemovedByMinimization, 3 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TRACE_CHECK: 0.0s SsaConstructionTime, 0.3s SatisfiabilityAnalysisTime, 20.8s InterpolantComputationTime, 617 NumberOfCodeBlocks, 617 NumberOfCodeBlocksAsserted, 21 NumberOfCheckSat, 700 ConstructedInterpolants, 7 QuantifiedInterpolants, 4260 SizeOfPredicates, 16 NumberOfNonLiveVariables, 767 ConjunctsInSsa, 143 ConjunctsInUnsatCore, 19 InterpolantComputations, 3 PerfectInterpolantSequences, 505/607 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: (((((((((0 <= y) && (1 <= b)) && ((z + ((__int128) x * y)) == ((long long) a * b))) && (b <= 10)) && (y <= 1)) || ((((((y == ((b >= 0) ? (b / 2) : ((b / 2) - 1))) && (1 <= b)) && (b <= 10)) && (x == ((long long) 2 * a))) && (z == 0)) && (((b >= 0) ? (b % 2) : ((b % 2) + 2)) != 1))) || (((((y <= 2) && (1 <= y)) && (1 <= b)) && ((z + ((__int128) x * y)) == ((long long) a * b))) && (b <= 10))) || (((((b == y) && (1 <= b)) && ((z + ((__int128) x * y)) == ((long long) a * b))) && (b <= 10)) && (a == x))) || ((((((1 <= ((b >= 0) ? (b % 2) : ((b % 2) + 2))) && (((((long long) -1 + b) >= 0) ? (((long long) -1 + b) / 2) : ((((long long) -1 + b) / 2) - 1)) == y)) && (1 <= b)) && (b <= 10)) && (x == ((long long) 2 * a))) && ((z + (((__int128) a * y) * 2)) == ((long long) a * b)))) RESULT: Ultimate proved your program to be correct! [2025-03-03 14:08:19,583 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