./Ultimate.py --spec ../sv-benchmarks/c/properties/unreach-call.prp --file ../sv-benchmarks/c/nla-digbench/egcd2-ll.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/egcd2-ll.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 ed6536c9cb0e4b2be9a327fc4a25c6bfba6e98b1dfb78e314dd25bca8cbdb087 --- Real Ultimate output --- This is Ultimate 0.3.0-?-798a7b3-m [2025-03-03 13:41:46,419 INFO L188 SettingsManager]: Resetting all preferences to default values... [2025-03-03 13:41:46,475 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf [2025-03-03 13:41:46,481 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2025-03-03 13:41:46,483 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2025-03-03 13:41:46,500 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2025-03-03 13:41:46,501 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2025-03-03 13:41:46,502 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2025-03-03 13:41:46,502 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2025-03-03 13:41:46,502 INFO L153 SettingsManager]: * Use memory slicer=true [2025-03-03 13:41:46,502 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2025-03-03 13:41:46,502 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2025-03-03 13:41:46,503 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2025-03-03 13:41:46,503 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2025-03-03 13:41:46,503 INFO L153 SettingsManager]: * Use SBE=true [2025-03-03 13:41:46,503 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2025-03-03 13:41:46,504 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2025-03-03 13:41:46,504 INFO L153 SettingsManager]: * sizeof long=4 [2025-03-03 13:41:46,504 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2025-03-03 13:41:46,504 INFO L153 SettingsManager]: * sizeof POINTER=4 [2025-03-03 13:41:46,504 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2025-03-03 13:41:46,504 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2025-03-03 13:41:46,505 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2025-03-03 13:41:46,505 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2025-03-03 13:41:46,505 INFO L153 SettingsManager]: * sizeof long double=12 [2025-03-03 13:41:46,505 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2025-03-03 13:41:46,505 INFO L153 SettingsManager]: * Behaviour of calls to undefined functions=OVERAPPROXIMATE_BEHAVIOUR [2025-03-03 13:41:46,505 INFO L153 SettingsManager]: * Use constant arrays=true [2025-03-03 13:41:46,505 INFO L151 SettingsManager]: Preferences of IcfgBuilder differ from their defaults: [2025-03-03 13:41:46,505 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2025-03-03 13:41:46,505 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2025-03-03 13:41:46,505 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2025-03-03 13:41:46,505 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2025-03-03 13:41:46,506 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2025-03-03 13:41:46,506 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2025-03-03 13:41:46,506 INFO L153 SettingsManager]: * Compute procedure contracts=false [2025-03-03 13:41:46,506 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2025-03-03 13:41:46,506 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2025-03-03 13:41:46,506 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2025-03-03 13:41:46,506 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2025-03-03 13:41:46,506 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2025-03-03 13:41:46,506 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2025-03-03 13:41:46,506 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2025-03-03 13:41:46,506 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 -> ed6536c9cb0e4b2be9a327fc4a25c6bfba6e98b1dfb78e314dd25bca8cbdb087 [2025-03-03 13:41:46,730 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2025-03-03 13:41:46,737 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2025-03-03 13:41:46,740 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2025-03-03 13:41:46,740 INFO L270 PluginConnector]: Initializing CDTParser... [2025-03-03 13:41:46,741 INFO L274 PluginConnector]: CDTParser initialized [2025-03-03 13:41:46,742 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/nla-digbench/egcd2-ll.c [2025-03-03 13:41:47,890 INFO L533 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/06184b1b9/33e8000df68948a1a29ccf4beb86863c/FLAG80a27c1e7 [2025-03-03 13:41:48,111 INFO L384 CDTParser]: Found 1 translation units. [2025-03-03 13:41:48,112 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench/egcd2-ll.c [2025-03-03 13:41:48,122 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/06184b1b9/33e8000df68948a1a29ccf4beb86863c/FLAG80a27c1e7 [2025-03-03 13:41:48,454 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/06184b1b9/33e8000df68948a1a29ccf4beb86863c [2025-03-03 13:41:48,457 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2025-03-03 13:41:48,458 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2025-03-03 13:41:48,459 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2025-03-03 13:41:48,460 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2025-03-03 13:41:48,463 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2025-03-03 13:41:48,464 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 03.03 01:41:48" (1/1) ... [2025-03-03 13:41:48,465 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@5179053f and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 01:41:48, skipping insertion in model container [2025-03-03 13:41:48,465 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 03.03 01:41:48" (1/1) ... [2025-03-03 13:41:48,475 INFO L175 MainTranslator]: Built tables and reachable declarations [2025-03-03 13:41:48,567 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/egcd2-ll.c[490,503] [2025-03-03 13:41:48,587 INFO L210 PostProcessor]: Analyzing one entry point: main [2025-03-03 13:41:48,594 INFO L200 MainTranslator]: Completed pre-run [2025-03-03 13:41:48,603 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/egcd2-ll.c[490,503] [2025-03-03 13:41:48,612 INFO L210 PostProcessor]: Analyzing one entry point: main [2025-03-03 13:41:48,627 INFO L204 MainTranslator]: Completed translation [2025-03-03 13:41:48,627 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 01:41:48 WrapperNode [2025-03-03 13:41:48,628 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2025-03-03 13:41:48,629 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2025-03-03 13:41:48,629 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2025-03-03 13:41:48,629 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2025-03-03 13:41:48,634 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 01:41:48" (1/1) ... [2025-03-03 13:41:48,639 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 01:41:48" (1/1) ... [2025-03-03 13:41:48,653 INFO L138 Inliner]: procedures = 14, calls = 17, calls flagged for inlining = 2, calls inlined = 2, statements flattened = 71 [2025-03-03 13:41:48,654 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2025-03-03 13:41:48,654 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2025-03-03 13:41:48,655 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2025-03-03 13:41:48,655 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2025-03-03 13:41:48,661 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 01:41:48" (1/1) ... [2025-03-03 13:41:48,662 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 01:41:48" (1/1) ... [2025-03-03 13:41:48,662 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 01:41:48" (1/1) ... [2025-03-03 13:41:48,676 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 13:41:48,677 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 01:41:48" (1/1) ... [2025-03-03 13:41:48,677 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 01:41:48" (1/1) ... [2025-03-03 13:41:48,679 INFO L184 PluginConnector]: Executing the observer ReplaceArrayAssignments from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 01:41:48" (1/1) ... [2025-03-03 13:41:48,679 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 01:41:48" (1/1) ... [2025-03-03 13:41:48,680 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 01:41:48" (1/1) ... [2025-03-03 13:41:48,680 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 01:41:48" (1/1) ... [2025-03-03 13:41:48,681 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2025-03-03 13:41:48,683 INFO L112 PluginConnector]: ------------------------IcfgBuilder---------------------------- [2025-03-03 13:41:48,683 INFO L270 PluginConnector]: Initializing IcfgBuilder... [2025-03-03 13:41:48,683 INFO L274 PluginConnector]: IcfgBuilder initialized [2025-03-03 13:41:48,684 INFO L184 PluginConnector]: Executing the observer IcfgBuilderObserver from plugin IcfgBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 01:41:48" (1/1) ... [2025-03-03 13:41:48,687 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2025-03-03 13:41:48,697 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 13:41:48,710 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 13:41:48,715 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 13:41:48,733 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2025-03-03 13:41:48,733 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2025-03-03 13:41:48,733 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2025-03-03 13:41:48,733 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2025-03-03 13:41:48,733 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2025-03-03 13:41:48,734 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2025-03-03 13:41:48,734 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2025-03-03 13:41:48,734 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2025-03-03 13:41:48,783 INFO L256 CfgBuilder]: Building ICFG [2025-03-03 13:41:48,785 INFO L286 CfgBuilder]: Building CFG for each procedure with an implementation [2025-03-03 13:41:48,919 INFO L? ?]: Removed 11 outVars from TransFormulas that were not future-live. [2025-03-03 13:41:48,919 INFO L307 CfgBuilder]: Performing block encoding [2025-03-03 13:41:48,926 INFO L331 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2025-03-03 13:41:48,927 INFO L336 CfgBuilder]: Removed 0 assume(true) statements. [2025-03-03 13:41:48,927 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 03.03 01:41:48 BoogieIcfgContainer [2025-03-03 13:41:48,927 INFO L131 PluginConnector]: ------------------------ END IcfgBuilder---------------------------- [2025-03-03 13:41:48,929 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2025-03-03 13:41:48,929 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2025-03-03 13:41:48,932 INFO L274 PluginConnector]: TraceAbstraction initialized [2025-03-03 13:41:48,933 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 03.03 01:41:48" (1/3) ... [2025-03-03 13:41:48,933 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@645d5350 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 03.03 01:41:48, skipping insertion in model container [2025-03-03 13:41:48,933 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 01:41:48" (2/3) ... [2025-03-03 13:41:48,933 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@645d5350 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 03.03 01:41:48, skipping insertion in model container [2025-03-03 13:41:48,933 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 03.03 01:41:48" (3/3) ... [2025-03-03 13:41:48,935 INFO L128 eAbstractionObserver]: Analyzing ICFG egcd2-ll.c [2025-03-03 13:41:48,945 INFO L216 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2025-03-03 13:41:48,946 INFO L151 ceAbstractionStarter]: Applying trace abstraction to ICFG egcd2-ll.c that has 3 procedures, 30 locations, 1 initial locations, 2 loop locations, and 1 error locations. [2025-03-03 13:41:48,984 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2025-03-03 13:41:48,993 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;@689d7111, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2025-03-03 13:41:48,993 INFO L334 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2025-03-03 13:41:48,995 INFO L276 IsEmpty]: Start isEmpty. Operand has 30 states, 17 states have (on average 1.3529411764705883) internal successors, (23), 18 states have internal predecessors, (23), 10 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2025-03-03 13:41:48,999 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 29 [2025-03-03 13:41:48,999 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 13:41:48,999 INFO L218 NwaCegarLoop]: trace histogram [4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-03 13:41:48,999 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 13:41:49,002 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 13:41:49,002 INFO L85 PathProgramCache]: Analyzing trace with hash 818312437, now seen corresponding path program 1 times [2025-03-03 13:41:49,006 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 13:41:49,007 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [210358422] [2025-03-03 13:41:49,007 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 13:41:49,007 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 13:41:49,055 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 28 statements into 1 equivalence classes. [2025-03-03 13:41:49,068 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 28 of 28 statements. [2025-03-03 13:41:49,068 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 13:41:49,069 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 13:41:49,118 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 18 trivial. 0 not checked. [2025-03-03 13:41:49,118 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-03 13:41:49,119 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [210358422] [2025-03-03 13:41:49,119 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [210358422] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-03 13:41:49,119 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [192718238] [2025-03-03 13:41:49,120 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 13:41:49,120 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 13:41:49,120 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 13:41:49,122 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 13:41:49,124 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 13:41:49,155 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 28 statements into 1 equivalence classes. [2025-03-03 13:41:49,177 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 28 of 28 statements. [2025-03-03 13:41:49,178 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 13:41:49,178 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 13:41:49,179 INFO L256 TraceCheckSpWp]: Trace formula consists of 92 conjuncts, 1 conjuncts are in the unsatisfiable core [2025-03-03 13:41:49,182 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-03 13:41:49,189 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 6 proven. 0 refuted. 0 times theorem prover too weak. 18 trivial. 0 not checked. [2025-03-03 13:41:49,189 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2025-03-03 13:41:49,189 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [192718238] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-03 13:41:49,189 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2025-03-03 13:41:49,190 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [2] total 2 [2025-03-03 13:41:49,191 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [257017958] [2025-03-03 13:41:49,191 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-03 13:41:49,194 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2025-03-03 13:41:49,194 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-03 13:41:49,207 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2025-03-03 13:41:49,207 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2025-03-03 13:41:49,209 INFO L87 Difference]: Start difference. First operand has 30 states, 17 states have (on average 1.3529411764705883) internal successors, (23), 18 states have internal predecessors, (23), 10 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) 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, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 2 states have call successors, (4) [2025-03-03 13:41:49,225 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 13:41:49,225 INFO L93 Difference]: Finished difference Result 57 states and 92 transitions. [2025-03-03 13:41:49,226 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2025-03-03 13:41:49,227 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, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 2 states have call successors, (4) Word has length 28 [2025-03-03 13:41:49,228 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 13:41:49,232 INFO L225 Difference]: With dead ends: 57 [2025-03-03 13:41:49,232 INFO L226 Difference]: Without dead ends: 26 [2025-03-03 13:41:49,234 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 29 GetRequests, 29 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 13:41:49,238 INFO L435 NwaCegarLoop]: 39 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, 39 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 13:41:49,240 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 39 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 0 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-03-03 13:41:49,249 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 26 states. [2025-03-03 13:41:49,261 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 26 to 26. [2025-03-03 13:41:49,263 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 26 states, 13 states have (on average 1.2307692307692308) internal successors, (16), 15 states have internal predecessors, (16), 10 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2025-03-03 13:41:49,266 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 26 states to 26 states and 35 transitions. [2025-03-03 13:41:49,269 INFO L78 Accepts]: Start accepts. Automaton has 26 states and 35 transitions. Word has length 28 [2025-03-03 13:41:49,269 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 13:41:49,269 INFO L471 AbstractCegarLoop]: Abstraction has 26 states and 35 transitions. [2025-03-03 13:41:49,269 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, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 2 states have call successors, (4) [2025-03-03 13:41:49,270 INFO L276 IsEmpty]: Start isEmpty. Operand 26 states and 35 transitions. [2025-03-03 13:41:49,271 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 29 [2025-03-03 13:41:49,271 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 13:41:49,272 INFO L218 NwaCegarLoop]: trace histogram [4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-03 13:41:49,280 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 13:41:49,472 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 13:41:49,473 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 13:41:49,473 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 13:41:49,473 INFO L85 PathProgramCache]: Analyzing trace with hash 1356241141, now seen corresponding path program 1 times [2025-03-03 13:41:49,473 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 13:41:49,473 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [840415193] [2025-03-03 13:41:49,473 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 13:41:49,473 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 13:41:49,480 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 28 statements into 1 equivalence classes. [2025-03-03 13:41:49,501 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 28 of 28 statements. [2025-03-03 13:41:49,501 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 13:41:49,501 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 13:41:49,676 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 3 proven. 6 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2025-03-03 13:41:49,676 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-03 13:41:49,676 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [840415193] [2025-03-03 13:41:49,678 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [840415193] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-03 13:41:49,678 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1770336165] [2025-03-03 13:41:49,678 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 13:41:49,678 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 13:41:49,678 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 13:41:49,680 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 13:41:49,681 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 13:41:49,712 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 28 statements into 1 equivalence classes. [2025-03-03 13:41:49,726 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 28 of 28 statements. [2025-03-03 13:41:49,726 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 13:41:49,726 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 13:41:49,727 INFO L256 TraceCheckSpWp]: Trace formula consists of 92 conjuncts, 11 conjuncts are in the unsatisfiable core [2025-03-03 13:41:49,728 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-03 13:41:49,846 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2025-03-03 13:41:49,847 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2025-03-03 13:41:49,847 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1770336165] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-03 13:41:49,847 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2025-03-03 13:41:49,847 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [6] total 10 [2025-03-03 13:41:49,847 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [802289342] [2025-03-03 13:41:49,847 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-03 13:41:49,848 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2025-03-03 13:41:49,848 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-03 13:41:49,848 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2025-03-03 13:41:49,848 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=18, Invalid=72, Unknown=0, NotChecked=0, Total=90 [2025-03-03 13:41:49,848 INFO L87 Difference]: Start difference. First operand 26 states and 35 transitions. Second operand has 6 states, 5 states have (on average 2.0) internal successors, (10), 5 states have internal predecessors, (10), 3 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2025-03-03 13:41:49,941 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 13:41:49,941 INFO L93 Difference]: Finished difference Result 41 states and 56 transitions. [2025-03-03 13:41:49,942 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2025-03-03 13:41:49,942 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 5 states have (on average 2.0) internal successors, (10), 5 states have internal predecessors, (10), 3 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) Word has length 28 [2025-03-03 13:41:49,942 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 13:41:49,943 INFO L225 Difference]: With dead ends: 41 [2025-03-03 13:41:49,944 INFO L226 Difference]: Without dead ends: 39 [2025-03-03 13:41:49,944 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 34 GetRequests, 25 SyntacticMatches, 0 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 5 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=22, Invalid=88, Unknown=0, NotChecked=0, Total=110 [2025-03-03 13:41:49,944 INFO L435 NwaCegarLoop]: 26 mSDtfsCounter, 6 mSDsluCounter, 90 mSDsCounter, 0 mSdLazyCounter, 56 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 11 SdHoareTripleChecker+Valid, 116 SdHoareTripleChecker+Invalid, 57 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 56 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-03 13:41:49,945 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [11 Valid, 116 Invalid, 57 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 56 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-03 13:41:49,945 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 39 states. [2025-03-03 13:41:49,956 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 39 to 37. [2025-03-03 13:41:49,957 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 37 states, 18 states have (on average 1.2777777777777777) internal successors, (23), 20 states have internal predecessors, (23), 15 states have call successors, (15), 3 states have call predecessors, (15), 3 states have return successors, (14), 13 states have call predecessors, (14), 14 states have call successors, (14) [2025-03-03 13:41:49,957 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 37 states to 37 states and 52 transitions. [2025-03-03 13:41:49,958 INFO L78 Accepts]: Start accepts. Automaton has 37 states and 52 transitions. Word has length 28 [2025-03-03 13:41:49,958 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 13:41:49,958 INFO L471 AbstractCegarLoop]: Abstraction has 37 states and 52 transitions. [2025-03-03 13:41:49,958 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 5 states have (on average 2.0) internal successors, (10), 5 states have internal predecessors, (10), 3 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2025-03-03 13:41:49,958 INFO L276 IsEmpty]: Start isEmpty. Operand 37 states and 52 transitions. [2025-03-03 13:41:49,958 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 29 [2025-03-03 13:41:49,958 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 13:41:49,958 INFO L218 NwaCegarLoop]: trace histogram [4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-03 13:41:49,965 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2025-03-03 13:41:50,159 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 13:41:50,159 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 13:41:50,159 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 13:41:50,159 INFO L85 PathProgramCache]: Analyzing trace with hash 1358326511, now seen corresponding path program 1 times [2025-03-03 13:41:50,160 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 13:41:50,160 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [698184382] [2025-03-03 13:41:50,160 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 13:41:50,160 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 13:41:50,168 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 28 statements into 1 equivalence classes. [2025-03-03 13:41:50,178 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 28 of 28 statements. [2025-03-03 13:41:50,180 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 13:41:50,180 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-03 13:41:50,182 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1223031254] [2025-03-03 13:41:50,182 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 13:41:50,182 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 13:41:50,182 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 13:41:50,184 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 13:41:50,185 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 13:41:50,208 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 28 statements into 1 equivalence classes. [2025-03-03 13:41:50,220 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 28 of 28 statements. [2025-03-03 13:41:50,220 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 13:41:50,220 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 13:41:50,221 INFO L256 TraceCheckSpWp]: Trace formula consists of 95 conjuncts, 7 conjuncts are in the unsatisfiable core [2025-03-03 13:41:50,222 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-03 13:41:50,252 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2025-03-03 13:41:50,253 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2025-03-03 13:41:50,253 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-03 13:41:50,253 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [698184382] [2025-03-03 13:41:50,254 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-03 13:41:50,254 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1223031254] [2025-03-03 13:41:50,254 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1223031254] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-03 13:41:50,254 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-03 13:41:50,254 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2025-03-03 13:41:50,254 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2115646837] [2025-03-03 13:41:50,254 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-03 13:41:50,254 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2025-03-03 13:41:50,254 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-03 13:41:50,255 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2025-03-03 13:41:50,255 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2025-03-03 13:41:50,255 INFO L87 Difference]: Start difference. First operand 37 states and 52 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, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2025-03-03 13:41:50,301 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 13:41:50,301 INFO L93 Difference]: Finished difference Result 54 states and 78 transitions. [2025-03-03 13:41:50,301 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2025-03-03 13:41:50,301 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, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) Word has length 28 [2025-03-03 13:41:50,302 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 13:41:50,303 INFO L225 Difference]: With dead ends: 54 [2025-03-03 13:41:50,303 INFO L226 Difference]: Without dead ends: 52 [2025-03-03 13:41:50,303 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 28 GetRequests, 24 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2025-03-03 13:41:50,304 INFO L435 NwaCegarLoop]: 32 mSDtfsCounter, 4 mSDsluCounter, 83 mSDsCounter, 0 mSdLazyCounter, 32 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 8 SdHoareTripleChecker+Valid, 115 SdHoareTripleChecker+Invalid, 32 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 32 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-03-03 13:41:50,304 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [8 Valid, 115 Invalid, 32 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 32 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-03-03 13:41:50,304 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 52 states. [2025-03-03 13:41:50,314 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 52 to 43. [2025-03-03 13:41:50,315 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 43 states, 21 states have (on average 1.2380952380952381) internal successors, (26), 25 states have internal predecessors, (26), 17 states have call successors, (17), 4 states have call predecessors, (17), 4 states have return successors, (16), 13 states have call predecessors, (16), 16 states have call successors, (16) [2025-03-03 13:41:50,316 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 43 states to 43 states and 59 transitions. [2025-03-03 13:41:50,316 INFO L78 Accepts]: Start accepts. Automaton has 43 states and 59 transitions. Word has length 28 [2025-03-03 13:41:50,316 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 13:41:50,316 INFO L471 AbstractCegarLoop]: Abstraction has 43 states and 59 transitions. [2025-03-03 13:41:50,316 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, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2025-03-03 13:41:50,319 INFO L276 IsEmpty]: Start isEmpty. Operand 43 states and 59 transitions. [2025-03-03 13:41:50,319 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 34 [2025-03-03 13:41:50,319 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 13:41:50,319 INFO L218 NwaCegarLoop]: trace histogram [4, 4, 4, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-03 13:41:50,325 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Ended with exit code 0 [2025-03-03 13:41:50,520 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 13:41:50,520 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 13:41:50,520 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 13:41:50,520 INFO L85 PathProgramCache]: Analyzing trace with hash 94956302, now seen corresponding path program 1 times [2025-03-03 13:41:50,520 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 13:41:50,520 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [391775264] [2025-03-03 13:41:50,520 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 13:41:50,520 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 13:41:50,526 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 33 statements into 1 equivalence classes. [2025-03-03 13:41:50,534 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 33 of 33 statements. [2025-03-03 13:41:50,538 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 13:41:50,538 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 13:41:50,643 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 5 proven. 6 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2025-03-03 13:41:50,643 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-03 13:41:50,643 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [391775264] [2025-03-03 13:41:50,643 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [391775264] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-03 13:41:50,643 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1104892597] [2025-03-03 13:41:50,643 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 13:41:50,643 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 13:41:50,643 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 13:41:50,645 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 13:41:50,647 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 13:41:50,675 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 33 statements into 1 equivalence classes. [2025-03-03 13:41:50,686 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 33 of 33 statements. [2025-03-03 13:41:50,686 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 13:41:50,686 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 13:41:50,687 INFO L256 TraceCheckSpWp]: Trace formula consists of 101 conjuncts, 9 conjuncts are in the unsatisfiable core [2025-03-03 13:41:50,688 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-03 13:41:50,752 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2025-03-03 13:41:50,752 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2025-03-03 13:41:50,752 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1104892597] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-03 13:41:50,752 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2025-03-03 13:41:50,752 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [6] total 9 [2025-03-03 13:41:50,752 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [188543273] [2025-03-03 13:41:50,752 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-03 13:41:50,752 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2025-03-03 13:41:50,752 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-03 13:41:50,753 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2025-03-03 13:41:50,753 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=16, Invalid=56, Unknown=0, NotChecked=0, Total=72 [2025-03-03 13:41:50,753 INFO L87 Difference]: Start difference. First operand 43 states and 59 transitions. Second operand has 5 states, 5 states have (on average 2.6) internal successors, (13), 4 states have internal predecessors, (13), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2025-03-03 13:41:50,794 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 13:41:50,794 INFO L93 Difference]: Finished difference Result 51 states and 66 transitions. [2025-03-03 13:41:50,795 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2025-03-03 13:41:50,795 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.6) internal successors, (13), 4 states have internal predecessors, (13), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) Word has length 33 [2025-03-03 13:41:50,796 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 13:41:50,796 INFO L225 Difference]: With dead ends: 51 [2025-03-03 13:41:50,796 INFO L226 Difference]: Without dead ends: 47 [2025-03-03 13:41:50,796 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 39 GetRequests, 31 SyntacticMatches, 0 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=20, Invalid=70, Unknown=0, NotChecked=0, Total=90 [2025-03-03 13:41:50,797 INFO L435 NwaCegarLoop]: 33 mSDtfsCounter, 6 mSDsluCounter, 85 mSDsCounter, 0 mSdLazyCounter, 27 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 10 SdHoareTripleChecker+Valid, 118 SdHoareTripleChecker+Invalid, 28 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 27 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-03-03 13:41:50,797 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [10 Valid, 118 Invalid, 28 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 27 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-03-03 13:41:50,797 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 47 states. [2025-03-03 13:41:50,803 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 47 to 46. [2025-03-03 13:41:50,804 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 46 states, 24 states have (on average 1.1666666666666667) internal successors, (28), 27 states have internal predecessors, (28), 16 states have call successors, (16), 5 states have call predecessors, (16), 5 states have return successors, (15), 13 states have call predecessors, (15), 15 states have call successors, (15) [2025-03-03 13:41:50,804 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 46 states to 46 states and 59 transitions. [2025-03-03 13:41:50,804 INFO L78 Accepts]: Start accepts. Automaton has 46 states and 59 transitions. Word has length 33 [2025-03-03 13:41:50,804 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 13:41:50,805 INFO L471 AbstractCegarLoop]: Abstraction has 46 states and 59 transitions. [2025-03-03 13:41:50,805 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.6) internal successors, (13), 4 states have internal predecessors, (13), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2025-03-03 13:41:50,805 INFO L276 IsEmpty]: Start isEmpty. Operand 46 states and 59 transitions. [2025-03-03 13:41:50,805 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 44 [2025-03-03 13:41:50,805 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 13:41:50,805 INFO L218 NwaCegarLoop]: trace histogram [4, 4, 4, 4, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-03 13:41:50,811 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Forceful destruction successful, exit code 0 [2025-03-03 13:41:51,006 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 13:41:51,006 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 13:41:51,007 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 13:41:51,007 INFO L85 PathProgramCache]: Analyzing trace with hash 200937844, now seen corresponding path program 1 times [2025-03-03 13:41:51,007 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 13:41:51,007 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1680790257] [2025-03-03 13:41:51,007 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 13:41:51,007 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 13:41:51,012 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 43 statements into 1 equivalence classes. [2025-03-03 13:41:51,020 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 43 of 43 statements. [2025-03-03 13:41:51,021 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 13:41:51,021 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-03 13:41:51,021 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1645540192] [2025-03-03 13:41:51,022 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 13:41:51,022 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 13:41:51,022 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 13:41:51,023 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 13:41:51,025 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 13:41:51,050 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 43 statements into 1 equivalence classes. [2025-03-03 13:41:51,064 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 43 of 43 statements. [2025-03-03 13:41:51,064 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 13:41:51,064 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 13:41:51,065 INFO L256 TraceCheckSpWp]: Trace formula consists of 122 conjuncts, 11 conjuncts are in the unsatisfiable core [2025-03-03 13:41:51,066 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-03 13:41:51,210 INFO L134 CoverageAnalysis]: Checked inductivity of 42 backedges. 6 proven. 0 refuted. 0 times theorem prover too weak. 36 trivial. 0 not checked. [2025-03-03 13:41:51,210 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2025-03-03 13:41:51,210 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-03 13:41:51,210 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1680790257] [2025-03-03 13:41:51,210 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-03 13:41:51,210 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1645540192] [2025-03-03 13:41:51,210 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1645540192] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-03 13:41:51,210 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-03 13:41:51,211 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2025-03-03 13:41:51,211 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1003928625] [2025-03-03 13:41:51,211 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-03 13:41:51,211 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2025-03-03 13:41:51,211 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-03 13:41:51,211 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2025-03-03 13:41:51,211 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2025-03-03 13:41:51,211 INFO L87 Difference]: Start difference. First operand 46 states and 59 transitions. Second operand has 5 states, 5 states have (on average 2.6) internal successors, (13), 4 states have internal predecessors, (13), 2 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2025-03-03 13:41:51,262 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 13:41:51,262 INFO L93 Difference]: Finished difference Result 53 states and 65 transitions. [2025-03-03 13:41:51,262 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2025-03-03 13:41:51,262 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.6) internal successors, (13), 4 states have internal predecessors, (13), 2 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) Word has length 43 [2025-03-03 13:41:51,263 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 13:41:51,263 INFO L225 Difference]: With dead ends: 53 [2025-03-03 13:41:51,263 INFO L226 Difference]: Without dead ends: 51 [2025-03-03 13:41:51,263 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 43 GetRequests, 39 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2025-03-03 13:41:51,264 INFO L435 NwaCegarLoop]: 30 mSDtfsCounter, 5 mSDsluCounter, 76 mSDsCounter, 0 mSdLazyCounter, 39 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 6 SdHoareTripleChecker+Valid, 106 SdHoareTripleChecker+Invalid, 40 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 39 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-03-03 13:41:51,264 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [6 Valid, 106 Invalid, 40 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 39 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-03-03 13:41:51,265 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 51 states. [2025-03-03 13:41:51,274 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 51 to 50. [2025-03-03 13:41:51,275 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 50 states, 27 states have (on average 1.1481481481481481) internal successors, (31), 30 states have internal predecessors, (31), 16 states have call successors, (16), 6 states have call predecessors, (16), 6 states have return successors, (15), 13 states have call predecessors, (15), 15 states have call successors, (15) [2025-03-03 13:41:51,277 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 50 states to 50 states and 62 transitions. [2025-03-03 13:41:51,278 INFO L78 Accepts]: Start accepts. Automaton has 50 states and 62 transitions. Word has length 43 [2025-03-03 13:41:51,278 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 13:41:51,278 INFO L471 AbstractCegarLoop]: Abstraction has 50 states and 62 transitions. [2025-03-03 13:41:51,278 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.6) internal successors, (13), 4 states have internal predecessors, (13), 2 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2025-03-03 13:41:51,278 INFO L276 IsEmpty]: Start isEmpty. Operand 50 states and 62 transitions. [2025-03-03 13:41:51,279 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 50 [2025-03-03 13:41:51,279 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 13:41:51,279 INFO L218 NwaCegarLoop]: trace histogram [5, 4, 4, 4, 4, 4, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-03 13:41:51,285 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 13:41:51,479 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 13:41:51,480 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 13:41:51,480 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 13:41:51,480 INFO L85 PathProgramCache]: Analyzing trace with hash 1881921480, now seen corresponding path program 1 times [2025-03-03 13:41:51,480 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 13:41:51,480 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1045800490] [2025-03-03 13:41:51,480 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 13:41:51,480 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 13:41:51,486 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 49 statements into 1 equivalence classes. [2025-03-03 13:41:51,499 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 49 of 49 statements. [2025-03-03 13:41:51,499 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 13:41:51,499 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-03 13:41:51,500 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1652796050] [2025-03-03 13:41:51,500 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 13:41:51,500 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 13:41:51,500 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 13:41:51,503 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 13:41:51,504 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 13:41:51,528 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 49 statements into 1 equivalence classes. [2025-03-03 13:41:51,543 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 49 of 49 statements. [2025-03-03 13:41:51,543 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 13:41:51,543 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 13:41:51,544 INFO L256 TraceCheckSpWp]: Trace formula consists of 136 conjuncts, 15 conjuncts are in the unsatisfiable core [2025-03-03 13:41:51,545 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-03 13:41:51,602 INFO L134 CoverageAnalysis]: Checked inductivity of 57 backedges. 8 proven. 1 refuted. 0 times theorem prover too weak. 48 trivial. 0 not checked. [2025-03-03 13:41:51,602 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-03 13:41:51,679 INFO L134 CoverageAnalysis]: Checked inductivity of 57 backedges. 8 proven. 0 refuted. 0 times theorem prover too weak. 49 trivial. 0 not checked. [2025-03-03 13:41:51,679 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-03 13:41:51,679 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1045800490] [2025-03-03 13:41:51,679 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-03 13:41:51,679 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1652796050] [2025-03-03 13:41:51,679 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1652796050] provided 1 perfect and 1 imperfect interpolant sequences [2025-03-03 13:41:51,679 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2025-03-03 13:41:51,679 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [6] total 7 [2025-03-03 13:41:51,679 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1707607511] [2025-03-03 13:41:51,679 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-03 13:41:51,679 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2025-03-03 13:41:51,679 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-03 13:41:51,680 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2025-03-03 13:41:51,680 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=29, Unknown=0, NotChecked=0, Total=42 [2025-03-03 13:41:51,680 INFO L87 Difference]: Start difference. First operand 50 states and 62 transitions. Second operand has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (8), 2 states have call predecessors, (8), 2 states have call successors, (8) [2025-03-03 13:41:51,723 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 13:41:51,723 INFO L93 Difference]: Finished difference Result 56 states and 67 transitions. [2025-03-03 13:41:51,724 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2025-03-03 13:41:51,724 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (8), 2 states have call predecessors, (8), 2 states have call successors, (8) Word has length 49 [2025-03-03 13:41:51,724 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 13:41:51,725 INFO L225 Difference]: With dead ends: 56 [2025-03-03 13:41:51,725 INFO L226 Difference]: Without dead ends: 54 [2025-03-03 13:41:51,725 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 97 GetRequests, 89 SyntacticMatches, 2 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=17, Invalid=39, Unknown=0, NotChecked=0, Total=56 [2025-03-03 13:41:51,725 INFO L435 NwaCegarLoop]: 29 mSDtfsCounter, 4 mSDsluCounter, 74 mSDsCounter, 0 mSdLazyCounter, 29 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 4 SdHoareTripleChecker+Valid, 103 SdHoareTripleChecker+Invalid, 29 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 29 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-03-03 13:41:51,726 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [4 Valid, 103 Invalid, 29 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 29 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-03-03 13:41:51,726 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 54 states. [2025-03-03 13:41:51,735 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 54 to 48. [2025-03-03 13:41:51,735 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 48 states, 27 states have (on average 1.1481481481481481) internal successors, (31), 28 states have internal predecessors, (31), 14 states have call successors, (14), 6 states have call predecessors, (14), 6 states have return successors, (13), 13 states have call predecessors, (13), 13 states have call successors, (13) [2025-03-03 13:41:51,735 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 48 states to 48 states and 58 transitions. [2025-03-03 13:41:51,736 INFO L78 Accepts]: Start accepts. Automaton has 48 states and 58 transitions. Word has length 49 [2025-03-03 13:41:51,736 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 13:41:51,736 INFO L471 AbstractCegarLoop]: Abstraction has 48 states and 58 transitions. [2025-03-03 13:41:51,736 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (8), 2 states have call predecessors, (8), 2 states have call successors, (8) [2025-03-03 13:41:51,736 INFO L276 IsEmpty]: Start isEmpty. Operand 48 states and 58 transitions. [2025-03-03 13:41:51,736 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 52 [2025-03-03 13:41:51,736 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 13:41:51,736 INFO L218 NwaCegarLoop]: trace histogram [5, 4, 4, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-03 13:41:51,744 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 13:41:51,937 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 13:41:51,937 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 13:41:51,938 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 13:41:51,938 INFO L85 PathProgramCache]: Analyzing trace with hash 1615929401, now seen corresponding path program 1 times [2025-03-03 13:41:51,938 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 13:41:51,938 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [538455216] [2025-03-03 13:41:51,938 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 13:41:51,938 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 13:41:51,942 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 51 statements into 1 equivalence classes. [2025-03-03 13:41:51,948 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 51 of 51 statements. [2025-03-03 13:41:51,948 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 13:41:51,948 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 13:41:52,059 INFO L134 CoverageAnalysis]: Checked inductivity of 57 backedges. 8 proven. 10 refuted. 0 times theorem prover too weak. 39 trivial. 0 not checked. [2025-03-03 13:41:52,060 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-03 13:41:52,060 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [538455216] [2025-03-03 13:41:52,060 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [538455216] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-03 13:41:52,060 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1274722474] [2025-03-03 13:41:52,060 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 13:41:52,060 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 13:41:52,061 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 13:41:52,062 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 13:41:52,064 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 13:41:52,091 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 51 statements into 1 equivalence classes. [2025-03-03 13:41:52,109 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 51 of 51 statements. [2025-03-03 13:41:52,110 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 13:41:52,110 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 13:41:52,111 INFO L256 TraceCheckSpWp]: Trace formula consists of 146 conjuncts, 9 conjuncts are in the unsatisfiable core [2025-03-03 13:41:52,112 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-03 13:41:52,140 INFO L134 CoverageAnalysis]: Checked inductivity of 57 backedges. 8 proven. 10 refuted. 0 times theorem prover too weak. 39 trivial. 0 not checked. [2025-03-03 13:41:52,141 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-03 13:41:52,254 INFO L134 CoverageAnalysis]: Checked inductivity of 57 backedges. 8 proven. 10 refuted. 0 times theorem prover too weak. 39 trivial. 0 not checked. [2025-03-03 13:41:52,255 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1274722474] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-03 13:41:52,255 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-03 13:41:52,255 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8, 8] total 9 [2025-03-03 13:41:52,255 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1522909410] [2025-03-03 13:41:52,255 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-03 13:41:52,255 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2025-03-03 13:41:52,255 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-03 13:41:52,256 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2025-03-03 13:41:52,257 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=17, Invalid=55, Unknown=0, NotChecked=0, Total=72 [2025-03-03 13:41:52,257 INFO L87 Difference]: Start difference. First operand 48 states and 58 transitions. Second operand has 9 states, 9 states have (on average 2.3333333333333335) internal successors, (21), 8 states have internal predecessors, (21), 5 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (8), 3 states have call predecessors, (8), 4 states have call successors, (8) [2025-03-03 13:41:52,392 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 13:41:52,392 INFO L93 Difference]: Finished difference Result 88 states and 126 transitions. [2025-03-03 13:41:52,392 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2025-03-03 13:41:52,392 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 9 states have (on average 2.3333333333333335) internal successors, (21), 8 states have internal predecessors, (21), 5 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (8), 3 states have call predecessors, (8), 4 states have call successors, (8) Word has length 51 [2025-03-03 13:41:52,393 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 13:41:52,397 INFO L225 Difference]: With dead ends: 88 [2025-03-03 13:41:52,397 INFO L226 Difference]: Without dead ends: 80 [2025-03-03 13:41:52,397 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 112 GetRequests, 97 SyntacticMatches, 4 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=42, Invalid=114, Unknown=0, NotChecked=0, Total=156 [2025-03-03 13:41:52,397 INFO L435 NwaCegarLoop]: 37 mSDtfsCounter, 23 mSDsluCounter, 216 mSDsCounter, 0 mSdLazyCounter, 98 mSolverCounterSat, 30 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 28 SdHoareTripleChecker+Valid, 253 SdHoareTripleChecker+Invalid, 128 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 30 IncrementalHoareTripleChecker+Valid, 98 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-03 13:41:52,398 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [28 Valid, 253 Invalid, 128 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [30 Valid, 98 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-03 13:41:52,398 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 80 states. [2025-03-03 13:41:52,407 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 80 to 72. [2025-03-03 13:41:52,407 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 72 states, 35 states have (on average 1.2571428571428571) internal successors, (44), 36 states have internal predecessors, (44), 30 states have call successors, (30), 6 states have call predecessors, (30), 6 states have return successors, (29), 29 states have call predecessors, (29), 29 states have call successors, (29) [2025-03-03 13:41:52,408 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 72 states to 72 states and 103 transitions. [2025-03-03 13:41:52,408 INFO L78 Accepts]: Start accepts. Automaton has 72 states and 103 transitions. Word has length 51 [2025-03-03 13:41:52,408 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 13:41:52,408 INFO L471 AbstractCegarLoop]: Abstraction has 72 states and 103 transitions. [2025-03-03 13:41:52,408 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 9 states have (on average 2.3333333333333335) internal successors, (21), 8 states have internal predecessors, (21), 5 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (8), 3 states have call predecessors, (8), 4 states have call successors, (8) [2025-03-03 13:41:52,409 INFO L276 IsEmpty]: Start isEmpty. Operand 72 states and 103 transitions. [2025-03-03 13:41:52,409 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 57 [2025-03-03 13:41:52,409 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 13:41:52,409 INFO L218 NwaCegarLoop]: trace histogram [6, 5, 5, 4, 4, 4, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-03 13:41:52,415 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 13:41:52,614 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 13:41:52,614 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 13:41:52,614 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 13:41:52,614 INFO L85 PathProgramCache]: Analyzing trace with hash -270596208, now seen corresponding path program 1 times [2025-03-03 13:41:52,614 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 13:41:52,614 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1519996754] [2025-03-03 13:41:52,614 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 13:41:52,614 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 13:41:52,619 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 56 statements into 1 equivalence classes. [2025-03-03 13:41:52,629 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 56 of 56 statements. [2025-03-03 13:41:52,629 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 13:41:52,629 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-03 13:41:52,630 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1162313551] [2025-03-03 13:41:52,630 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 13:41:52,630 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 13:41:52,630 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 13:41:52,632 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 13:41:52,634 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 13:41:52,657 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 56 statements into 1 equivalence classes. [2025-03-03 13:41:52,674 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 56 of 56 statements. [2025-03-03 13:41:52,674 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 13:41:52,674 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 13:41:52,675 INFO L256 TraceCheckSpWp]: Trace formula consists of 158 conjuncts, 27 conjuncts are in the unsatisfiable core [2025-03-03 13:41:52,677 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-03 13:41:52,857 INFO L134 CoverageAnalysis]: Checked inductivity of 77 backedges. 10 proven. 15 refuted. 0 times theorem prover too weak. 52 trivial. 0 not checked. [2025-03-03 13:41:52,857 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-03 13:41:52,956 INFO L134 CoverageAnalysis]: Checked inductivity of 77 backedges. 10 proven. 3 refuted. 0 times theorem prover too weak. 64 trivial. 0 not checked. [2025-03-03 13:41:52,956 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-03 13:41:52,956 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1519996754] [2025-03-03 13:41:52,956 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-03 13:41:52,956 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1162313551] [2025-03-03 13:41:52,956 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1162313551] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-03 13:41:52,956 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-03-03 13:41:52,956 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 6] total 12 [2025-03-03 13:41:52,956 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1749885279] [2025-03-03 13:41:52,956 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-03-03 13:41:52,956 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2025-03-03 13:41:52,956 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-03 13:41:52,957 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2025-03-03 13:41:52,957 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=28, Invalid=104, Unknown=0, NotChecked=0, Total=132 [2025-03-03 13:41:52,957 INFO L87 Difference]: Start difference. First operand 72 states and 103 transitions. Second operand has 12 states, 11 states have (on average 2.1818181818181817) internal successors, (24), 9 states have internal predecessors, (24), 6 states have call successors, (19), 2 states have call predecessors, (19), 2 states have return successors, (18), 7 states have call predecessors, (18), 6 states have call successors, (18) [2025-03-03 13:41:53,112 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 13:41:53,113 INFO L93 Difference]: Finished difference Result 102 states and 149 transitions. [2025-03-03 13:41:53,113 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2025-03-03 13:41:53,114 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 11 states have (on average 2.1818181818181817) internal successors, (24), 9 states have internal predecessors, (24), 6 states have call successors, (19), 2 states have call predecessors, (19), 2 states have return successors, (18), 7 states have call predecessors, (18), 6 states have call successors, (18) Word has length 56 [2025-03-03 13:41:53,114 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 13:41:53,116 INFO L225 Difference]: With dead ends: 102 [2025-03-03 13:41:53,116 INFO L226 Difference]: Without dead ends: 99 [2025-03-03 13:41:53,116 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 112 GetRequests, 98 SyntacticMatches, 2 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 23 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=39, Invalid=143, Unknown=0, NotChecked=0, Total=182 [2025-03-03 13:41:53,118 INFO L435 NwaCegarLoop]: 33 mSDtfsCounter, 17 mSDsluCounter, 225 mSDsCounter, 0 mSdLazyCounter, 159 mSolverCounterSat, 8 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 26 SdHoareTripleChecker+Valid, 258 SdHoareTripleChecker+Invalid, 167 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 8 IncrementalHoareTripleChecker+Valid, 159 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-03 13:41:53,119 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [26 Valid, 258 Invalid, 167 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [8 Valid, 159 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-03 13:41:53,119 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 99 states. [2025-03-03 13:41:53,139 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 99 to 96. [2025-03-03 13:41:53,140 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 96 states, 45 states have (on average 1.288888888888889) internal successors, (58), 47 states have internal predecessors, (58), 43 states have call successors, (43), 7 states have call predecessors, (43), 7 states have return successors, (41), 41 states have call predecessors, (41), 41 states have call successors, (41) [2025-03-03 13:41:53,141 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 96 states to 96 states and 142 transitions. [2025-03-03 13:41:53,141 INFO L78 Accepts]: Start accepts. Automaton has 96 states and 142 transitions. Word has length 56 [2025-03-03 13:41:53,141 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 13:41:53,141 INFO L471 AbstractCegarLoop]: Abstraction has 96 states and 142 transitions. [2025-03-03 13:41:53,141 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 11 states have (on average 2.1818181818181817) internal successors, (24), 9 states have internal predecessors, (24), 6 states have call successors, (19), 2 states have call predecessors, (19), 2 states have return successors, (18), 7 states have call predecessors, (18), 6 states have call successors, (18) [2025-03-03 13:41:53,142 INFO L276 IsEmpty]: Start isEmpty. Operand 96 states and 142 transitions. [2025-03-03 13:41:53,142 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 62 [2025-03-03 13:41:53,142 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 13:41:53,142 INFO L218 NwaCegarLoop]: trace histogram [7, 6, 6, 4, 4, 4, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-03 13:41:53,149 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Forceful destruction successful, exit code 0 [2025-03-03 13:41:53,347 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,SelfDestructingSolverStorable7 [2025-03-03 13:41:53,347 INFO L396 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 13:41:53,348 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 13:41:53,348 INFO L85 PathProgramCache]: Analyzing trace with hash 1233890451, now seen corresponding path program 2 times [2025-03-03 13:41:53,348 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 13:41:53,348 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1003489963] [2025-03-03 13:41:53,348 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-03 13:41:53,348 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 13:41:53,353 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 61 statements into 2 equivalence classes. [2025-03-03 13:41:53,369 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 61 of 61 statements. [2025-03-03 13:41:53,370 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-03 13:41:53,370 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-03 13:41:53,371 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [509584561] [2025-03-03 13:41:53,371 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-03 13:41:53,371 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 13:41:53,371 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 13:41:53,373 INFO L229 MonitoredProcess]: Starting monitored process 10 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-03 13:41:53,374 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Waiting until timeout for monitored process [2025-03-03 13:41:53,401 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 61 statements into 2 equivalence classes. [2025-03-03 13:41:53,418 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 61 of 61 statements. [2025-03-03 13:41:53,418 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-03 13:41:53,418 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 13:41:53,419 INFO L256 TraceCheckSpWp]: Trace formula consists of 167 conjuncts, 34 conjuncts are in the unsatisfiable core [2025-03-03 13:41:53,420 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-03 13:41:53,672 INFO L134 CoverageAnalysis]: Checked inductivity of 100 backedges. 12 proven. 16 refuted. 0 times theorem prover too weak. 72 trivial. 0 not checked. [2025-03-03 13:41:53,672 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-03 13:41:53,782 INFO L134 CoverageAnalysis]: Checked inductivity of 100 backedges. 12 proven. 4 refuted. 0 times theorem prover too weak. 84 trivial. 0 not checked. [2025-03-03 13:41:53,782 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-03 13:41:53,782 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1003489963] [2025-03-03 13:41:53,782 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-03 13:41:53,782 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [509584561] [2025-03-03 13:41:53,782 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [509584561] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-03 13:41:53,782 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-03-03 13:41:53,782 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 7] total 14 [2025-03-03 13:41:53,782 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1390642126] [2025-03-03 13:41:53,782 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-03-03 13:41:53,782 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2025-03-03 13:41:53,783 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-03 13:41:53,783 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2025-03-03 13:41:53,783 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=35, Invalid=147, Unknown=0, NotChecked=0, Total=182 [2025-03-03 13:41:53,783 INFO L87 Difference]: Start difference. First operand 96 states and 142 transitions. Second operand has 14 states, 13 states have (on average 1.8461538461538463) internal successors, (24), 11 states have internal predecessors, (24), 8 states have call successors, (21), 2 states have call predecessors, (21), 2 states have return successors, (20), 9 states have call predecessors, (20), 8 states have call successors, (20) [2025-03-03 13:41:54,149 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 13:41:54,150 INFO L93 Difference]: Finished difference Result 104 states and 149 transitions. [2025-03-03 13:41:54,150 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2025-03-03 13:41:54,150 INFO L78 Accepts]: Start accepts. Automaton has has 14 states, 13 states have (on average 1.8461538461538463) internal successors, (24), 11 states have internal predecessors, (24), 8 states have call successors, (21), 2 states have call predecessors, (21), 2 states have return successors, (20), 9 states have call predecessors, (20), 8 states have call successors, (20) Word has length 61 [2025-03-03 13:41:54,151 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 13:41:54,151 INFO L225 Difference]: With dead ends: 104 [2025-03-03 13:41:54,151 INFO L226 Difference]: Without dead ends: 101 [2025-03-03 13:41:54,152 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 129 GetRequests, 106 SyntacticMatches, 2 SemanticMatches, 21 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 75 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=117, Invalid=389, Unknown=0, NotChecked=0, Total=506 [2025-03-03 13:41:54,152 INFO L435 NwaCegarLoop]: 24 mSDtfsCounter, 38 mSDsluCounter, 195 mSDsCounter, 0 mSdLazyCounter, 206 mSolverCounterSat, 62 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 38 SdHoareTripleChecker+Valid, 219 SdHoareTripleChecker+Invalid, 268 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 62 IncrementalHoareTripleChecker+Valid, 206 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2025-03-03 13:41:54,153 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [38 Valid, 219 Invalid, 268 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [62 Valid, 206 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2025-03-03 13:41:54,153 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 101 states. [2025-03-03 13:41:54,177 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 101 to 98. [2025-03-03 13:41:54,177 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 98 states, 48 states have (on average 1.2708333333333333) internal successors, (61), 49 states have internal predecessors, (61), 41 states have call successors, (41), 8 states have call predecessors, (41), 8 states have return successors, (40), 40 states have call predecessors, (40), 40 states have call successors, (40) [2025-03-03 13:41:54,178 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 98 states to 98 states and 142 transitions. [2025-03-03 13:41:54,178 INFO L78 Accepts]: Start accepts. Automaton has 98 states and 142 transitions. Word has length 61 [2025-03-03 13:41:54,179 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 13:41:54,179 INFO L471 AbstractCegarLoop]: Abstraction has 98 states and 142 transitions. [2025-03-03 13:41:54,179 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 14 states, 13 states have (on average 1.8461538461538463) internal successors, (24), 11 states have internal predecessors, (24), 8 states have call successors, (21), 2 states have call predecessors, (21), 2 states have return successors, (20), 9 states have call predecessors, (20), 8 states have call successors, (20) [2025-03-03 13:41:54,179 INFO L276 IsEmpty]: Start isEmpty. Operand 98 states and 142 transitions. [2025-03-03 13:41:54,180 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 67 [2025-03-03 13:41:54,180 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 13:41:54,180 INFO L218 NwaCegarLoop]: trace histogram [8, 7, 7, 4, 4, 4, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-03 13:41:54,187 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Ended with exit code 0 [2025-03-03 13:41:54,380 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,10 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 13:41:54,380 INFO L396 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 13:41:54,381 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 13:41:54,381 INFO L85 PathProgramCache]: Analyzing trace with hash -1342203472, now seen corresponding path program 3 times [2025-03-03 13:41:54,381 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 13:41:54,381 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [33217574] [2025-03-03 13:41:54,381 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-03-03 13:41:54,381 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 13:41:54,386 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 66 statements into 5 equivalence classes. [2025-03-03 13:41:54,402 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 5 check-sat command(s) and asserted 66 of 66 statements. [2025-03-03 13:41:54,402 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 5 check-sat command(s) [2025-03-03 13:41:54,402 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-03 13:41:54,403 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [535686780] [2025-03-03 13:41:54,403 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-03-03 13:41:54,403 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 13:41:54,403 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 13:41:54,405 INFO L229 MonitoredProcess]: Starting monitored process 11 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-03 13:41:54,407 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Waiting until timeout for monitored process [2025-03-03 13:41:54,432 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 66 statements into 5 equivalence classes. [2025-03-03 13:41:54,448 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) and asserted 46 of 66 statements. [2025-03-03 13:41:54,448 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2025-03-03 13:41:54,448 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 13:41:54,449 INFO L256 TraceCheckSpWp]: Trace formula consists of 140 conjuncts, 52 conjuncts are in the unsatisfiable core [2025-03-03 13:41:54,451 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-03 13:41:54,907 INFO L134 CoverageAnalysis]: Checked inductivity of 127 backedges. 37 proven. 12 refuted. 0 times theorem prover too weak. 78 trivial. 0 not checked. [2025-03-03 13:41:54,907 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-03 13:41:55,388 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-03 13:41:55,388 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [33217574] [2025-03-03 13:41:55,388 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-03 13:41:55,388 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [535686780] [2025-03-03 13:41:55,388 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [535686780] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-03 13:41:55,388 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2025-03-03 13:41:55,388 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [15] total 15 [2025-03-03 13:41:55,389 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2059339360] [2025-03-03 13:41:55,389 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2025-03-03 13:41:55,389 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 15 states [2025-03-03 13:41:55,389 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-03 13:41:55,389 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2025-03-03 13:41:55,390 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=69, Invalid=393, Unknown=0, NotChecked=0, Total=462 [2025-03-03 13:41:55,390 INFO L87 Difference]: Start difference. First operand 98 states and 142 transitions. Second operand has 15 states, 13 states have (on average 1.6923076923076923) internal successors, (22), 12 states have internal predecessors, (22), 5 states have call successors, (12), 2 states have call predecessors, (12), 3 states have return successors, (11), 5 states have call predecessors, (11), 5 states have call successors, (11) [2025-03-03 13:41:55,654 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 13:41:55,654 INFO L93 Difference]: Finished difference Result 114 states and 155 transitions. [2025-03-03 13:41:55,654 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2025-03-03 13:41:55,654 INFO L78 Accepts]: Start accepts. Automaton has has 15 states, 13 states have (on average 1.6923076923076923) internal successors, (22), 12 states have internal predecessors, (22), 5 states have call successors, (12), 2 states have call predecessors, (12), 3 states have return successors, (11), 5 states have call predecessors, (11), 5 states have call successors, (11) Word has length 66 [2025-03-03 13:41:55,655 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 13:41:55,655 INFO L225 Difference]: With dead ends: 114 [2025-03-03 13:41:55,655 INFO L226 Difference]: Without dead ends: 112 [2025-03-03 13:41:55,656 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 91 GetRequests, 68 SyntacticMatches, 0 SemanticMatches, 23 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 118 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=95, Invalid=505, Unknown=0, NotChecked=0, Total=600 [2025-03-03 13:41:55,656 INFO L435 NwaCegarLoop]: 20 mSDtfsCounter, 23 mSDsluCounter, 179 mSDsCounter, 0 mSdLazyCounter, 289 mSolverCounterSat, 20 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 35 SdHoareTripleChecker+Valid, 199 SdHoareTripleChecker+Invalid, 309 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 20 IncrementalHoareTripleChecker+Valid, 289 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2025-03-03 13:41:55,656 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [35 Valid, 199 Invalid, 309 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [20 Valid, 289 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2025-03-03 13:41:55,657 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 112 states. [2025-03-03 13:41:55,676 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 112 to 110. [2025-03-03 13:41:55,677 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 110 states, 57 states have (on average 1.2280701754385965) internal successors, (70), 58 states have internal predecessors, (70), 41 states have call successors, (41), 11 states have call predecessors, (41), 11 states have return successors, (40), 40 states have call predecessors, (40), 40 states have call successors, (40) [2025-03-03 13:41:55,678 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 110 states to 110 states and 151 transitions. [2025-03-03 13:41:55,678 INFO L78 Accepts]: Start accepts. Automaton has 110 states and 151 transitions. Word has length 66 [2025-03-03 13:41:55,678 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 13:41:55,678 INFO L471 AbstractCegarLoop]: Abstraction has 110 states and 151 transitions. [2025-03-03 13:41:55,678 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 15 states, 13 states have (on average 1.6923076923076923) internal successors, (22), 12 states have internal predecessors, (22), 5 states have call successors, (12), 2 states have call predecessors, (12), 3 states have return successors, (11), 5 states have call predecessors, (11), 5 states have call successors, (11) [2025-03-03 13:41:55,678 INFO L276 IsEmpty]: Start isEmpty. Operand 110 states and 151 transitions. [2025-03-03 13:41:55,679 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 73 [2025-03-03 13:41:55,679 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 13:41:55,679 INFO L218 NwaCegarLoop]: trace histogram [9, 8, 8, 4, 4, 4, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-03 13:41:55,687 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Forceful destruction successful, exit code 0 [2025-03-03 13:41:55,879 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 11 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable9 [2025-03-03 13:41:55,880 INFO L396 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 13:41:55,880 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 13:41:55,880 INFO L85 PathProgramCache]: Analyzing trace with hash 991186752, now seen corresponding path program 1 times [2025-03-03 13:41:55,880 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 13:41:55,880 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [736321709] [2025-03-03 13:41:55,880 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 13:41:55,880 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 13:41:55,884 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 72 statements into 1 equivalence classes. [2025-03-03 13:41:55,892 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 72 of 72 statements. [2025-03-03 13:41:55,892 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 13:41:55,892 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-03 13:41:55,893 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1870478510] [2025-03-03 13:41:55,893 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 13:41:55,893 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 13:41:55,893 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 13:41:55,895 INFO L229 MonitoredProcess]: Starting monitored process 12 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-03 13:41:55,896 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Waiting until timeout for monitored process [2025-03-03 13:41:55,922 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 72 statements into 1 equivalence classes. [2025-03-03 13:41:55,938 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 72 of 72 statements. [2025-03-03 13:41:55,938 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 13:41:55,938 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 13:41:55,939 INFO L256 TraceCheckSpWp]: Trace formula consists of 187 conjuncts, 41 conjuncts are in the unsatisfiable core [2025-03-03 13:41:55,941 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-03 13:41:56,287 INFO L134 CoverageAnalysis]: Checked inductivity of 158 backedges. 16 proven. 15 refuted. 0 times theorem prover too weak. 127 trivial. 0 not checked. [2025-03-03 13:41:56,287 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-03 13:41:56,532 INFO L134 CoverageAnalysis]: Checked inductivity of 158 backedges. 16 proven. 6 refuted. 0 times theorem prover too weak. 136 trivial. 0 not checked. [2025-03-03 13:41:56,532 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-03 13:41:56,532 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [736321709] [2025-03-03 13:41:56,532 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-03 13:41:56,532 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1870478510] [2025-03-03 13:41:56,532 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1870478510] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-03 13:41:56,532 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-03-03 13:41:56,532 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 10] total 21 [2025-03-03 13:41:56,532 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1998458318] [2025-03-03 13:41:56,532 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-03-03 13:41:56,533 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 21 states [2025-03-03 13:41:56,533 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-03 13:41:56,533 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2025-03-03 13:41:56,533 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=64, Invalid=356, Unknown=0, NotChecked=0, Total=420 [2025-03-03 13:41:56,533 INFO L87 Difference]: Start difference. First operand 110 states and 151 transitions. Second operand has 21 states, 19 states have (on average 1.4736842105263157) internal successors, (28), 18 states have internal predecessors, (28), 10 states have call successors, (25), 3 states have call predecessors, (25), 2 states have return successors, (24), 8 states have call predecessors, (24), 8 states have call successors, (24) [2025-03-03 13:41:57,930 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 13:41:57,930 INFO L93 Difference]: Finished difference Result 196 states and 298 transitions. [2025-03-03 13:41:57,930 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 25 states. [2025-03-03 13:41:57,931 INFO L78 Accepts]: Start accepts. Automaton has has 21 states, 19 states have (on average 1.4736842105263157) internal successors, (28), 18 states have internal predecessors, (28), 10 states have call successors, (25), 3 states have call predecessors, (25), 2 states have return successors, (24), 8 states have call predecessors, (24), 8 states have call successors, (24) Word has length 72 [2025-03-03 13:41:57,931 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 13:41:57,932 INFO L225 Difference]: With dead ends: 196 [2025-03-03 13:41:57,932 INFO L226 Difference]: Without dead ends: 188 [2025-03-03 13:41:57,933 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 159 GetRequests, 123 SyntacticMatches, 0 SemanticMatches, 36 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 206 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=255, Invalid=1151, Unknown=0, NotChecked=0, Total=1406 [2025-03-03 13:41:57,933 INFO L435 NwaCegarLoop]: 36 mSDtfsCounter, 52 mSDsluCounter, 468 mSDsCounter, 0 mSdLazyCounter, 604 mSolverCounterSat, 91 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.8s Time, 0 mProtectedPredicate, 0 mProtectedAction, 56 SdHoareTripleChecker+Valid, 504 SdHoareTripleChecker+Invalid, 695 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 91 IncrementalHoareTripleChecker+Valid, 604 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.9s IncrementalHoareTripleChecker+Time [2025-03-03 13:41:57,934 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [56 Valid, 504 Invalid, 695 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [91 Valid, 604 Invalid, 0 Unknown, 0 Unchecked, 0.9s Time] [2025-03-03 13:41:57,935 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 188 states. [2025-03-03 13:41:57,978 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 188 to 186. [2025-03-03 13:41:57,978 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 186 states, 83 states have (on average 1.3012048192771084) internal successors, (108), 84 states have internal predecessors, (108), 89 states have call successors, (89), 13 states have call predecessors, (89), 13 states have return successors, (88), 88 states have call predecessors, (88), 88 states have call successors, (88) [2025-03-03 13:41:57,979 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 186 states to 186 states and 285 transitions. [2025-03-03 13:41:57,980 INFO L78 Accepts]: Start accepts. Automaton has 186 states and 285 transitions. Word has length 72 [2025-03-03 13:41:57,980 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 13:41:57,980 INFO L471 AbstractCegarLoop]: Abstraction has 186 states and 285 transitions. [2025-03-03 13:41:57,980 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 21 states, 19 states have (on average 1.4736842105263157) internal successors, (28), 18 states have internal predecessors, (28), 10 states have call successors, (25), 3 states have call predecessors, (25), 2 states have return successors, (24), 8 states have call predecessors, (24), 8 states have call successors, (24) [2025-03-03 13:41:57,980 INFO L276 IsEmpty]: Start isEmpty. Operand 186 states and 285 transitions. [2025-03-03 13:41:57,981 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 88 [2025-03-03 13:41:57,981 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 13:41:57,981 INFO L218 NwaCegarLoop]: trace histogram [12, 11, 11, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-03 13:41:57,987 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Ended with exit code 0 [2025-03-03 13:41:58,181 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 12 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable10 [2025-03-03 13:41:58,181 INFO L396 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 13:41:58,182 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 13:41:58,182 INFO L85 PathProgramCache]: Analyzing trace with hash -1986683959, now seen corresponding path program 1 times [2025-03-03 13:41:58,182 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 13:41:58,182 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1331757185] [2025-03-03 13:41:58,182 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 13:41:58,182 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 13:41:58,185 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 87 statements into 1 equivalence classes. [2025-03-03 13:41:58,195 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 87 of 87 statements. [2025-03-03 13:41:58,195 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 13:41:58,195 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-03 13:41:58,196 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1957889495] [2025-03-03 13:41:58,196 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 13:41:58,196 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 13:41:58,196 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 13:41:58,199 INFO L229 MonitoredProcess]: Starting monitored process 13 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-03 13:41:58,201 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Waiting until timeout for monitored process [2025-03-03 13:41:58,223 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 87 statements into 1 equivalence classes. [2025-03-03 13:41:58,241 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 87 of 87 statements. [2025-03-03 13:41:58,242 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 13:41:58,242 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 13:41:58,243 INFO L256 TraceCheckSpWp]: Trace formula consists of 217 conjuncts, 54 conjuncts are in the unsatisfiable core [2025-03-03 13:41:58,244 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-03 13:41:58,763 INFO L134 CoverageAnalysis]: Checked inductivity of 280 backedges. 68 proven. 31 refuted. 0 times theorem prover too weak. 181 trivial. 0 not checked. [2025-03-03 13:41:58,763 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-03 13:42:08,258 INFO L134 CoverageAnalysis]: Checked inductivity of 280 backedges. 68 proven. 22 refuted. 0 times theorem prover too weak. 190 trivial. 0 not checked. [2025-03-03 13:42:08,258 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-03 13:42:08,258 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1331757185] [2025-03-03 13:42:08,258 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-03 13:42:08,258 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1957889495] [2025-03-03 13:42:08,258 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1957889495] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-03 13:42:08,258 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-03-03 13:42:08,258 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [15, 13] total 25 [2025-03-03 13:42:08,258 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [878666730] [2025-03-03 13:42:08,258 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-03-03 13:42:08,258 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 25 states [2025-03-03 13:42:08,258 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-03 13:42:08,259 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 25 interpolants. [2025-03-03 13:42:08,259 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=112, Invalid=488, Unknown=0, NotChecked=0, Total=600 [2025-03-03 13:42:08,259 INFO L87 Difference]: Start difference. First operand 186 states and 285 transitions. Second operand has 25 states, 21 states have (on average 1.5714285714285714) internal successors, (33), 21 states have internal predecessors, (33), 11 states have call successors, (31), 3 states have call predecessors, (31), 3 states have return successors, (30), 12 states have call predecessors, (30), 10 states have call successors, (30) [2025-03-03 13:42:19,555 WARN L286 SmtUtils]: Spent 10.75s on a formula simplification. DAG size of input: 74 DAG size of output: 73 (called from [L 388] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2025-03-03 13:43:14,840 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 46.32s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2025-03-03 13:43:19,681 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2025-03-03 13:43:30,516 WARN L286 SmtUtils]: Spent 6.24s on a formula simplification that was a NOOP. DAG size: 65 (called from [L 388] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2025-03-03 13:43:34,536 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers []