./Ultimate.py --spec ../sv-benchmarks/c/properties/unreach-call.prp --file ../sv-benchmarks/c/nla-digbench-scaling/egcd-ll_valuebound10.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version 798a7b37 Calling Ultimate with: /root/.sdkman/candidates/java/21.0.5-tem/bin/java -Dosgi.configuration.area=/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/config -Xmx15G -Xms4m -jar /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/org.eclipse.equinox.launcher_1.6.800.v20240513-1750.jar -data @noDefault -ultimatedata /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data -tc /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/AutomizerReach.xml -i ../sv-benchmarks/c/nla-digbench-scaling/egcd-ll_valuebound10.c -s /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf --cacsl2boogietranslator.entry.function main --witnessprinter.witness.directory /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux --witnessprinter.witness.filename witness --witnessprinter.write.witness.besides.input.file false --witnessprinter.graph.data.specification CHECK( init(main()), LTL(G ! call(reach_error())) ) --witnessprinter.graph.data.producer Automizer --witnessprinter.graph.data.architecture 32bit --witnessprinter.graph.data.programhash 3d9847fe213bf8df5d23c53d2bc8b53fb384c85820b87c09591484702dabefc3 --- Real Ultimate output --- This is Ultimate 0.3.0-?-798a7b3-m [2025-03-03 13:50:10,491 INFO L188 SettingsManager]: Resetting all preferences to default values... [2025-03-03 13:50:10,546 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf [2025-03-03 13:50:10,551 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2025-03-03 13:50:10,552 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2025-03-03 13:50:10,573 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2025-03-03 13:50:10,573 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2025-03-03 13:50:10,573 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2025-03-03 13:50:10,574 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2025-03-03 13:50:10,574 INFO L153 SettingsManager]: * Use memory slicer=true [2025-03-03 13:50:10,574 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2025-03-03 13:50:10,574 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2025-03-03 13:50:10,575 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2025-03-03 13:50:10,575 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2025-03-03 13:50:10,575 INFO L153 SettingsManager]: * Use SBE=true [2025-03-03 13:50:10,575 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2025-03-03 13:50:10,575 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2025-03-03 13:50:10,575 INFO L153 SettingsManager]: * sizeof long=4 [2025-03-03 13:50:10,575 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2025-03-03 13:50:10,575 INFO L153 SettingsManager]: * sizeof POINTER=4 [2025-03-03 13:50:10,576 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2025-03-03 13:50:10,576 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2025-03-03 13:50:10,576 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2025-03-03 13:50:10,576 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2025-03-03 13:50:10,576 INFO L153 SettingsManager]: * sizeof long double=12 [2025-03-03 13:50:10,576 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2025-03-03 13:50:10,576 INFO L153 SettingsManager]: * Behaviour of calls to undefined functions=OVERAPPROXIMATE_BEHAVIOUR [2025-03-03 13:50:10,576 INFO L153 SettingsManager]: * Use constant arrays=true [2025-03-03 13:50:10,576 INFO L151 SettingsManager]: Preferences of IcfgBuilder differ from their defaults: [2025-03-03 13:50:10,576 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2025-03-03 13:50:10,576 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2025-03-03 13:50:10,576 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2025-03-03 13:50:10,577 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2025-03-03 13:50:10,577 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2025-03-03 13:50:10,577 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2025-03-03 13:50:10,577 INFO L153 SettingsManager]: * Compute procedure contracts=false [2025-03-03 13:50:10,577 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2025-03-03 13:50:10,577 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2025-03-03 13:50:10,577 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2025-03-03 13:50:10,577 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2025-03-03 13:50:10,577 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2025-03-03 13:50:10,577 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2025-03-03 13:50:10,577 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2025-03-03 13:50:10,577 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 -> 3d9847fe213bf8df5d23c53d2bc8b53fb384c85820b87c09591484702dabefc3 [2025-03-03 13:50:10,757 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2025-03-03 13:50:10,762 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2025-03-03 13:50:10,765 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2025-03-03 13:50:10,766 INFO L270 PluginConnector]: Initializing CDTParser... [2025-03-03 13:50:10,766 INFO L274 PluginConnector]: CDTParser initialized [2025-03-03 13:50:10,767 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/nla-digbench-scaling/egcd-ll_valuebound10.c [2025-03-03 13:50:11,885 INFO L533 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/df9244f39/d7455c3993334224b35d90eeb29c0fcd/FLAGb9db074ce [2025-03-03 13:50:12,093 INFO L384 CDTParser]: Found 1 translation units. [2025-03-03 13:50:12,093 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/egcd-ll_valuebound10.c [2025-03-03 13:50:12,103 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/df9244f39/d7455c3993334224b35d90eeb29c0fcd/FLAGb9db074ce [2025-03-03 13:50:12,441 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/df9244f39/d7455c3993334224b35d90eeb29c0fcd [2025-03-03 13:50:12,443 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2025-03-03 13:50:12,444 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2025-03-03 13:50:12,445 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2025-03-03 13:50:12,445 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2025-03-03 13:50:12,449 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2025-03-03 13:50:12,449 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 03.03 01:50:12" (1/1) ... [2025-03-03 13:50:12,450 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@2efa1288 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 01:50:12, skipping insertion in model container [2025-03-03 13:50:12,450 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 03.03 01:50:12" (1/1) ... [2025-03-03 13:50:12,460 INFO L175 MainTranslator]: Built tables and reachable declarations [2025-03-03 13:50:12,543 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/egcd-ll_valuebound10.c[489,502] [2025-03-03 13:50:12,557 INFO L210 PostProcessor]: Analyzing one entry point: main [2025-03-03 13:50:12,564 INFO L200 MainTranslator]: Completed pre-run [2025-03-03 13:50:12,570 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/egcd-ll_valuebound10.c[489,502] [2025-03-03 13:50:12,576 INFO L210 PostProcessor]: Analyzing one entry point: main [2025-03-03 13:50:12,587 INFO L204 MainTranslator]: Completed translation [2025-03-03 13:50:12,588 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 01:50:12 WrapperNode [2025-03-03 13:50:12,588 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2025-03-03 13:50:12,589 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2025-03-03 13:50:12,589 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2025-03-03 13:50:12,589 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2025-03-03 13:50:12,593 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:50:12" (1/1) ... [2025-03-03 13:50:12,597 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:50:12" (1/1) ... [2025-03-03 13:50:12,606 INFO L138 Inliner]: procedures = 14, calls = 18, calls flagged for inlining = 2, calls inlined = 2, statements flattened = 54 [2025-03-03 13:50:12,607 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2025-03-03 13:50:12,607 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2025-03-03 13:50:12,607 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2025-03-03 13:50:12,607 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2025-03-03 13:50:12,612 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 01:50:12" (1/1) ... [2025-03-03 13:50:12,613 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 01:50:12" (1/1) ... [2025-03-03 13:50:12,613 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 01:50:12" (1/1) ... [2025-03-03 13:50:12,620 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:50:12,620 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 01:50:12" (1/1) ... [2025-03-03 13:50:12,620 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 01:50:12" (1/1) ... [2025-03-03 13:50:12,622 INFO L184 PluginConnector]: Executing the observer ReplaceArrayAssignments from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 01:50:12" (1/1) ... [2025-03-03 13:50:12,623 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 01:50:12" (1/1) ... [2025-03-03 13:50:12,624 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 01:50:12" (1/1) ... [2025-03-03 13:50:12,624 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 01:50:12" (1/1) ... [2025-03-03 13:50:12,625 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2025-03-03 13:50:12,626 INFO L112 PluginConnector]: ------------------------IcfgBuilder---------------------------- [2025-03-03 13:50:12,626 INFO L270 PluginConnector]: Initializing IcfgBuilder... [2025-03-03 13:50:12,626 INFO L274 PluginConnector]: IcfgBuilder initialized [2025-03-03 13:50:12,627 INFO L184 PluginConnector]: Executing the observer IcfgBuilderObserver from plugin IcfgBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 01:50:12" (1/1) ... [2025-03-03 13:50:12,630 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2025-03-03 13:50:12,641 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 13:50:12,651 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:50:12,653 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:50:12,669 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2025-03-03 13:50:12,669 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2025-03-03 13:50:12,669 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2025-03-03 13:50:12,669 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2025-03-03 13:50:12,670 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2025-03-03 13:50:12,670 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2025-03-03 13:50:12,670 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2025-03-03 13:50:12,670 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2025-03-03 13:50:12,704 INFO L256 CfgBuilder]: Building ICFG [2025-03-03 13:50:12,706 INFO L286 CfgBuilder]: Building CFG for each procedure with an implementation [2025-03-03 13:50:12,808 INFO L? ?]: Removed 5 outVars from TransFormulas that were not future-live. [2025-03-03 13:50:12,809 INFO L307 CfgBuilder]: Performing block encoding [2025-03-03 13:50:12,816 INFO L331 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2025-03-03 13:50:12,817 INFO L336 CfgBuilder]: Removed 0 assume(true) statements. [2025-03-03 13:50:12,817 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 03.03 01:50:12 BoogieIcfgContainer [2025-03-03 13:50:12,818 INFO L131 PluginConnector]: ------------------------ END IcfgBuilder---------------------------- [2025-03-03 13:50:12,819 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2025-03-03 13:50:12,819 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2025-03-03 13:50:12,823 INFO L274 PluginConnector]: TraceAbstraction initialized [2025-03-03 13:50:12,823 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 03.03 01:50:12" (1/3) ... [2025-03-03 13:50:12,823 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@432a475a and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 03.03 01:50:12, skipping insertion in model container [2025-03-03 13:50:12,824 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 01:50:12" (2/3) ... [2025-03-03 13:50:12,824 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@432a475a and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 03.03 01:50:12, skipping insertion in model container [2025-03-03 13:50:12,824 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 03.03 01:50:12" (3/3) ... [2025-03-03 13:50:12,825 INFO L128 eAbstractionObserver]: Analyzing ICFG egcd-ll_valuebound10.c [2025-03-03 13:50:12,835 INFO L216 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2025-03-03 13:50:12,837 INFO L151 ceAbstractionStarter]: Applying trace abstraction to ICFG egcd-ll_valuebound10.c that has 3 procedures, 31 locations, 1 initial locations, 1 loop locations, and 1 error locations. [2025-03-03 13:50:12,872 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2025-03-03 13:50:12,883 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;@f183e33, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2025-03-03 13:50:12,883 INFO L334 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2025-03-03 13:50:12,887 INFO L276 IsEmpty]: Start isEmpty. Operand has 31 states, 17 states have (on average 1.2941176470588236) internal successors, (22), 17 states have internal predecessors, (22), 11 states have call successors, (11), 2 states have call predecessors, (11), 2 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2025-03-03 13:50:12,892 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 29 [2025-03-03 13:50:12,892 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 13:50:12,893 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:50:12,893 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 13:50:12,896 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 13:50:12,897 INFO L85 PathProgramCache]: Analyzing trace with hash 296957627, now seen corresponding path program 1 times [2025-03-03 13:50:12,902 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 13:50:12,903 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1520736743] [2025-03-03 13:50:12,903 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 13:50:12,905 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 13:50:12,964 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 28 statements into 1 equivalence classes. [2025-03-03 13:50:12,979 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 28 of 28 statements. [2025-03-03 13:50:12,979 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 13:50:12,979 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 13:50:13,028 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:50:13,033 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-03 13:50:13,033 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1520736743] [2025-03-03 13:50:13,033 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1520736743] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-03 13:50:13,033 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1972370541] [2025-03-03 13:50:13,034 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 13:50:13,034 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 13:50:13,034 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 13:50:13,040 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:50:13,042 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:50:13,087 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 28 statements into 1 equivalence classes. [2025-03-03 13:50:13,110 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 28 of 28 statements. [2025-03-03 13:50:13,111 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 13:50:13,111 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 13:50:13,114 INFO L256 TraceCheckSpWp]: Trace formula consists of 82 conjuncts, 1 conjuncts are in the unsatisfiable core [2025-03-03 13:50:13,116 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-03 13:50:13,126 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:50:13,128 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2025-03-03 13:50:13,128 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1972370541] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-03 13:50:13,128 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2025-03-03 13:50:13,129 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [2] total 2 [2025-03-03 13:50:13,131 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1248904543] [2025-03-03 13:50:13,131 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-03 13:50:13,134 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2025-03-03 13:50:13,134 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-03 13:50:13,149 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2025-03-03 13:50:13,149 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2025-03-03 13:50:13,151 INFO L87 Difference]: Start difference. First operand has 31 states, 17 states have (on average 1.2941176470588236) internal successors, (22), 17 states have internal predecessors, (22), 11 states have call successors, (11), 2 states have call predecessors, (11), 2 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) 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:50:13,167 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 13:50:13,168 INFO L93 Difference]: Finished difference Result 59 states and 95 transitions. [2025-03-03 13:50:13,169 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2025-03-03 13:50:13,170 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:50:13,170 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 13:50:13,174 INFO L225 Difference]: With dead ends: 59 [2025-03-03 13:50:13,174 INFO L226 Difference]: Without dead ends: 27 [2025-03-03 13:50:13,176 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:50:13,179 INFO L435 NwaCegarLoop]: 41 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, 41 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:50:13,179 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 41 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 0 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-03-03 13:50:13,189 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 27 states. [2025-03-03 13:50:13,199 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 27 to 27. [2025-03-03 13:50:13,200 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 27 states, 13 states have (on average 1.2307692307692308) internal successors, (16), 14 states have internal predecessors, (16), 11 states have call successors, (11), 2 states have call predecessors, (11), 2 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2025-03-03 13:50:13,203 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 27 states to 27 states and 37 transitions. [2025-03-03 13:50:13,205 INFO L78 Accepts]: Start accepts. Automaton has 27 states and 37 transitions. Word has length 28 [2025-03-03 13:50:13,206 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 13:50:13,206 INFO L471 AbstractCegarLoop]: Abstraction has 27 states and 37 transitions. [2025-03-03 13:50:13,206 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:50:13,206 INFO L276 IsEmpty]: Start isEmpty. Operand 27 states and 37 transitions. [2025-03-03 13:50:13,207 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 29 [2025-03-03 13:50:13,207 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 13:50:13,207 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:50:13,213 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:50:13,412 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:50:13,412 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 13:50:13,413 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 13:50:13,413 INFO L85 PathProgramCache]: Analyzing trace with hash 682285849, now seen corresponding path program 1 times [2025-03-03 13:50:13,413 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 13:50:13,413 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [35664747] [2025-03-03 13:50:13,413 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 13:50:13,414 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 13:50:13,422 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 28 statements into 1 equivalence classes. [2025-03-03 13:50:13,438 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 28 of 28 statements. [2025-03-03 13:50:13,439 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 13:50:13,439 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-03 13:50:13,442 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [974773301] [2025-03-03 13:50:13,442 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 13:50:13,442 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 13:50:13,442 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 13:50:13,446 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:50:13,447 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:50:13,469 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 28 statements into 1 equivalence classes. [2025-03-03 13:50:13,488 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 28 of 28 statements. [2025-03-03 13:50:13,488 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 13:50:13,488 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 13:50:13,490 INFO L256 TraceCheckSpWp]: Trace formula consists of 82 conjuncts, 9 conjuncts are in the unsatisfiable core [2025-03-03 13:50:13,492 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-03 13:50:13,557 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:50:13,557 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2025-03-03 13:50:13,557 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-03 13:50:13,557 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [35664747] [2025-03-03 13:50:13,558 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-03 13:50:13,558 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [974773301] [2025-03-03 13:50:13,558 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [974773301] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-03 13:50:13,558 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-03 13:50:13,558 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2025-03-03 13:50:13,558 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1049667527] [2025-03-03 13:50:13,558 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-03 13:50:13,559 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2025-03-03 13:50:13,559 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-03 13:50:13,559 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2025-03-03 13:50:13,559 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2025-03-03 13:50:13,560 INFO L87 Difference]: Start difference. First operand 27 states and 37 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:50:13,612 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 13:50:13,612 INFO L93 Difference]: Finished difference Result 42 states and 59 transitions. [2025-03-03 13:50:13,612 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2025-03-03 13:50:13,612 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:50:13,613 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 13:50:13,613 INFO L225 Difference]: With dead ends: 42 [2025-03-03 13:50:13,613 INFO L226 Difference]: Without dead ends: 40 [2025-03-03 13:50:13,614 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:50:13,614 INFO L435 NwaCegarLoop]: 31 mSDtfsCounter, 5 mSDsluCounter, 86 mSDsCounter, 0 mSdLazyCounter, 30 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 11 SdHoareTripleChecker+Valid, 117 SdHoareTripleChecker+Invalid, 32 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 30 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-03-03 13:50:13,615 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [11 Valid, 117 Invalid, 32 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 30 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-03-03 13:50:13,616 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 40 states. [2025-03-03 13:50:13,623 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 40 to 39. [2025-03-03 13:50:13,623 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 39 states, 18 states have (on average 1.2777777777777777) internal successors, (23), 20 states have internal predecessors, (23), 17 states have call successors, (17), 3 states have call predecessors, (17), 3 states have return successors, (16), 15 states have call predecessors, (16), 16 states have call successors, (16) [2025-03-03 13:50:13,624 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 39 states to 39 states and 56 transitions. [2025-03-03 13:50:13,624 INFO L78 Accepts]: Start accepts. Automaton has 39 states and 56 transitions. Word has length 28 [2025-03-03 13:50:13,624 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 13:50:13,624 INFO L471 AbstractCegarLoop]: Abstraction has 39 states and 56 transitions. [2025-03-03 13:50:13,624 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:50:13,624 INFO L276 IsEmpty]: Start isEmpty. Operand 39 states and 56 transitions. [2025-03-03 13:50:13,625 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 34 [2025-03-03 13:50:13,625 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 13:50:13,625 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:50:13,631 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Ended with exit code 0 [2025-03-03 13:50:13,829 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:50:13,829 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 13:50:13,830 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 13:50:13,830 INFO L85 PathProgramCache]: Analyzing trace with hash -806119642, now seen corresponding path program 1 times [2025-03-03 13:50:13,830 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 13:50:13,830 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1201394006] [2025-03-03 13:50:13,830 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 13:50:13,830 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 13:50:13,838 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 33 statements into 1 equivalence classes. [2025-03-03 13:50:13,850 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 33 of 33 statements. [2025-03-03 13:50:13,852 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 13:50:13,852 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-03 13:50:13,853 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1752596125] [2025-03-03 13:50:13,855 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 13:50:13,855 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 13:50:13,855 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 13:50:13,857 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:50:13,858 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:50:13,880 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 33 statements into 1 equivalence classes. [2025-03-03 13:50:13,904 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 33 of 33 statements. [2025-03-03 13:50:13,904 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 13:50:13,904 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 13:50:13,905 INFO L256 TraceCheckSpWp]: Trace formula consists of 91 conjuncts, 12 conjuncts are in the unsatisfiable core [2025-03-03 13:50:13,906 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-03 13:50:13,958 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:50:13,958 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2025-03-03 13:50:13,958 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-03 13:50:13,958 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1201394006] [2025-03-03 13:50:13,958 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-03 13:50:13,958 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1752596125] [2025-03-03 13:50:13,958 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1752596125] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-03 13:50:13,958 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-03 13:50:13,958 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2025-03-03 13:50:13,958 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [677870581] [2025-03-03 13:50:13,958 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-03 13:50:13,958 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2025-03-03 13:50:13,959 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-03 13:50:13,959 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2025-03-03 13:50:13,959 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2025-03-03 13:50:13,959 INFO L87 Difference]: Start difference. First operand 39 states and 56 transitions. Second operand has 5 states, 4 states have (on average 3.25) 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:50:14,010 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 13:50:14,010 INFO L93 Difference]: Finished difference Result 62 states and 94 transitions. [2025-03-03 13:50:14,010 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2025-03-03 13:50:14,011 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 4 states have (on average 3.25) 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:50:14,011 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 13:50:14,012 INFO L225 Difference]: With dead ends: 62 [2025-03-03 13:50:14,013 INFO L226 Difference]: Without dead ends: 60 [2025-03-03 13:50:14,013 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 33 GetRequests, 29 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:50:14,013 INFO L435 NwaCegarLoop]: 33 mSDtfsCounter, 6 mSDsluCounter, 86 mSDsCounter, 0 mSdLazyCounter, 36 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 11 SdHoareTripleChecker+Valid, 119 SdHoareTripleChecker+Invalid, 36 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 36 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-03-03 13:50:14,014 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [11 Valid, 119 Invalid, 36 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 36 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-03-03 13:50:14,014 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 60 states. [2025-03-03 13:50:14,024 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 60 to 53. [2025-03-03 13:50:14,026 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 53 states, 25 states have (on average 1.36) internal successors, (34), 27 states have internal predecessors, (34), 23 states have call successors, (23), 4 states have call predecessors, (23), 4 states have return successors, (22), 21 states have call predecessors, (22), 22 states have call successors, (22) [2025-03-03 13:50:14,027 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 53 states to 53 states and 79 transitions. [2025-03-03 13:50:14,029 INFO L78 Accepts]: Start accepts. Automaton has 53 states and 79 transitions. Word has length 33 [2025-03-03 13:50:14,029 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 13:50:14,029 INFO L471 AbstractCegarLoop]: Abstraction has 53 states and 79 transitions. [2025-03-03 13:50:14,029 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 4 states have (on average 3.25) 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:50:14,029 INFO L276 IsEmpty]: Start isEmpty. Operand 53 states and 79 transitions. [2025-03-03 13:50:14,030 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 39 [2025-03-03 13:50:14,030 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 13:50:14,030 INFO L218 NwaCegarLoop]: trace histogram [4, 4, 4, 3, 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:50:14,035 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:50:14,231 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:50:14,232 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 13:50:14,232 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 13:50:14,232 INFO L85 PathProgramCache]: Analyzing trace with hash 1523729273, now seen corresponding path program 1 times [2025-03-03 13:50:14,232 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 13:50:14,232 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [155112114] [2025-03-03 13:50:14,232 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 13:50:14,233 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 13:50:14,237 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 38 statements into 1 equivalence classes. [2025-03-03 13:50:14,248 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 38 of 38 statements. [2025-03-03 13:50:14,249 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 13:50:14,249 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-03 13:50:14,251 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [745085476] [2025-03-03 13:50:14,251 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 13:50:14,253 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 13:50:14,253 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 13:50:14,254 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:50:14,256 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:50:14,282 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 38 statements into 1 equivalence classes. [2025-03-03 13:50:14,294 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 38 of 38 statements. [2025-03-03 13:50:14,294 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 13:50:14,294 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 13:50:14,294 INFO L256 TraceCheckSpWp]: Trace formula consists of 100 conjuncts, 9 conjuncts are in the unsatisfiable core [2025-03-03 13:50:14,296 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-03 13:50:14,358 INFO L134 CoverageAnalysis]: Checked inductivity of 32 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2025-03-03 13:50:14,358 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2025-03-03 13:50:14,358 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-03 13:50:14,358 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [155112114] [2025-03-03 13:50:14,358 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-03 13:50:14,358 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [745085476] [2025-03-03 13:50:14,358 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [745085476] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-03 13:50:14,358 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-03 13:50:14,358 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2025-03-03 13:50:14,358 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [805141669] [2025-03-03 13:50:14,359 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-03 13:50:14,359 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2025-03-03 13:50:14,359 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-03 13:50:14,359 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2025-03-03 13:50:14,359 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2025-03-03 13:50:14,359 INFO L87 Difference]: Start difference. First operand 53 states and 79 transitions. Second operand has 5 states, 4 states have (on average 3.25) internal successors, (13), 4 states have internal predecessors, (13), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) [2025-03-03 13:50:14,399 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 13:50:14,399 INFO L93 Difference]: Finished difference Result 60 states and 85 transitions. [2025-03-03 13:50:14,400 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2025-03-03 13:50:14,400 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 4 states have (on average 3.25) internal successors, (13), 4 states have internal predecessors, (13), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) Word has length 38 [2025-03-03 13:50:14,400 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 13:50:14,401 INFO L225 Difference]: With dead ends: 60 [2025-03-03 13:50:14,401 INFO L226 Difference]: Without dead ends: 56 [2025-03-03 13:50:14,401 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 38 GetRequests, 34 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:50:14,401 INFO L435 NwaCegarLoop]: 33 mSDtfsCounter, 6 mSDsluCounter, 85 mSDsCounter, 0 mSdLazyCounter, 37 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 10 SdHoareTripleChecker+Valid, 118 SdHoareTripleChecker+Invalid, 38 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 37 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-03-03 13:50:14,402 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [10 Valid, 118 Invalid, 38 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 37 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-03-03 13:50:14,402 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 56 states. [2025-03-03 13:50:14,408 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 56 to 56. [2025-03-03 13:50:14,409 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 56 states, 28 states have (on average 1.3214285714285714) internal successors, (37), 30 states have internal predecessors, (37), 22 states have call successors, (22), 5 states have call predecessors, (22), 5 states have return successors, (20), 20 states have call predecessors, (20), 20 states have call successors, (20) [2025-03-03 13:50:14,409 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 56 states to 56 states and 79 transitions. [2025-03-03 13:50:14,410 INFO L78 Accepts]: Start accepts. Automaton has 56 states and 79 transitions. Word has length 38 [2025-03-03 13:50:14,410 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 13:50:14,410 INFO L471 AbstractCegarLoop]: Abstraction has 56 states and 79 transitions. [2025-03-03 13:50:14,410 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 4 states have (on average 3.25) internal successors, (13), 4 states have internal predecessors, (13), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) [2025-03-03 13:50:14,410 INFO L276 IsEmpty]: Start isEmpty. Operand 56 states and 79 transitions. [2025-03-03 13:50:14,411 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 45 [2025-03-03 13:50:14,411 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 13:50:14,411 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, 1] [2025-03-03 13:50:14,417 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:50:14,611 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:50:14,611 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 13:50:14,612 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 13:50:14,612 INFO L85 PathProgramCache]: Analyzing trace with hash 1024589713, now seen corresponding path program 1 times [2025-03-03 13:50:14,612 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 13:50:14,612 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1821885810] [2025-03-03 13:50:14,612 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 13:50:14,612 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 13:50:14,617 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 44 statements into 1 equivalence classes. [2025-03-03 13:50:14,624 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 44 of 44 statements. [2025-03-03 13:50:14,624 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 13:50:14,624 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 13:50:14,752 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:50:14,752 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-03 13:50:14,752 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1821885810] [2025-03-03 13:50:14,752 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1821885810] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-03 13:50:14,752 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-03 13:50:14,752 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2025-03-03 13:50:14,752 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [363718211] [2025-03-03 13:50:14,752 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-03 13:50:14,753 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2025-03-03 13:50:14,753 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-03 13:50:14,753 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2025-03-03 13:50:14,754 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2025-03-03 13:50:14,755 INFO L87 Difference]: Start difference. First operand 56 states and 79 transitions. Second operand has 5 states, 4 states have (on average 3.5) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (7), 1 states have call predecessors, (7), 1 states have call successors, (7) [2025-03-03 13:50:14,797 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 13:50:14,797 INFO L93 Difference]: Finished difference Result 62 states and 84 transitions. [2025-03-03 13:50:14,797 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2025-03-03 13:50:14,798 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 4 states have (on average 3.5) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (7), 1 states have call predecessors, (7), 1 states have call successors, (7) Word has length 44 [2025-03-03 13:50:14,798 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 13:50:14,798 INFO L225 Difference]: With dead ends: 62 [2025-03-03 13:50:14,798 INFO L226 Difference]: Without dead ends: 60 [2025-03-03 13:50:14,798 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 7 GetRequests, 3 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:50:14,799 INFO L435 NwaCegarLoop]: 37 mSDtfsCounter, 3 mSDsluCounter, 91 mSDsCounter, 0 mSdLazyCounter, 23 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 6 SdHoareTripleChecker+Valid, 128 SdHoareTripleChecker+Invalid, 23 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 23 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-03-03 13:50:14,799 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [6 Valid, 128 Invalid, 23 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 23 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-03-03 13:50:14,799 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 60 states. [2025-03-03 13:50:14,804 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 60 to 60. [2025-03-03 13:50:14,805 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 60 states, 31 states have (on average 1.2903225806451613) internal successors, (40), 33 states have internal predecessors, (40), 22 states have call successors, (22), 6 states have call predecessors, (22), 6 states have return successors, (20), 20 states have call predecessors, (20), 20 states have call successors, (20) [2025-03-03 13:50:14,805 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 60 states to 60 states and 82 transitions. [2025-03-03 13:50:14,806 INFO L78 Accepts]: Start accepts. Automaton has 60 states and 82 transitions. Word has length 44 [2025-03-03 13:50:14,806 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 13:50:14,806 INFO L471 AbstractCegarLoop]: Abstraction has 60 states and 82 transitions. [2025-03-03 13:50:14,806 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 4 states have (on average 3.5) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (7), 1 states have call predecessors, (7), 1 states have call successors, (7) [2025-03-03 13:50:14,806 INFO L276 IsEmpty]: Start isEmpty. Operand 60 states and 82 transitions. [2025-03-03 13:50:14,807 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 46 [2025-03-03 13:50:14,807 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 13:50:14,807 INFO L218 NwaCegarLoop]: trace histogram [4, 4, 4, 4, 3, 3, 2, 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:50:14,807 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4 [2025-03-03 13:50:14,807 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 13:50:14,807 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 13:50:14,807 INFO L85 PathProgramCache]: Analyzing trace with hash 1697005566, now seen corresponding path program 1 times [2025-03-03 13:50:14,807 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 13:50:14,808 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [252198293] [2025-03-03 13:50:14,808 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 13:50:14,808 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 13:50:14,813 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 45 statements into 1 equivalence classes. [2025-03-03 13:50:14,825 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 45 of 45 statements. [2025-03-03 13:50:14,825 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 13:50:14,826 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-03 13:50:14,826 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [967911110] [2025-03-03 13:50:14,826 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 13:50:14,826 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 13:50:14,827 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 13:50:14,828 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:50:14,830 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:50:14,857 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 45 statements into 1 equivalence classes. [2025-03-03 13:50:14,870 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 45 of 45 statements. [2025-03-03 13:50:14,871 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 13:50:14,871 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 13:50:14,872 INFO L256 TraceCheckSpWp]: Trace formula consists of 117 conjuncts, 11 conjuncts are in the unsatisfiable core [2025-03-03 13:50:14,875 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-03 13:50:14,928 INFO L134 CoverageAnalysis]: Checked inductivity of 43 backedges. 6 proven. 0 refuted. 0 times theorem prover too weak. 37 trivial. 0 not checked. [2025-03-03 13:50:14,928 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2025-03-03 13:50:14,928 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-03 13:50:14,928 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [252198293] [2025-03-03 13:50:14,928 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-03 13:50:14,929 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [967911110] [2025-03-03 13:50:14,929 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [967911110] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-03 13:50:14,929 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-03 13:50:14,929 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2025-03-03 13:50:14,929 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [675826153] [2025-03-03 13:50:14,929 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-03 13:50:14,929 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2025-03-03 13:50:14,929 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-03 13:50:14,930 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2025-03-03 13:50:14,930 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2025-03-03 13:50:14,930 INFO L87 Difference]: Start difference. First operand 60 states and 82 transitions. Second operand has 5 states, 5 states have (on average 3.0) internal successors, (15), 4 states have internal predecessors, (15), 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:50:14,966 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 13:50:14,966 INFO L93 Difference]: Finished difference Result 76 states and 100 transitions. [2025-03-03 13:50:14,967 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2025-03-03 13:50:14,967 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.0) internal successors, (15), 4 states have internal predecessors, (15), 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 45 [2025-03-03 13:50:14,967 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 13:50:14,968 INFO L225 Difference]: With dead ends: 76 [2025-03-03 13:50:14,968 INFO L226 Difference]: Without dead ends: 74 [2025-03-03 13:50:14,968 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 45 GetRequests, 41 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:50:14,970 INFO L435 NwaCegarLoop]: 31 mSDtfsCounter, 4 mSDsluCounter, 86 mSDsCounter, 0 mSdLazyCounter, 30 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 7 SdHoareTripleChecker+Valid, 117 SdHoareTripleChecker+Invalid, 31 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 30 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-03-03 13:50:14,970 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [7 Valid, 117 Invalid, 31 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 30 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-03-03 13:50:14,971 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 74 states. [2025-03-03 13:50:14,980 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 74 to 71. [2025-03-03 13:50:14,980 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 71 states, 37 states have (on average 1.2432432432432432) internal successors, (46), 40 states have internal predecessors, (46), 25 states have call successors, (25), 8 states have call predecessors, (25), 8 states have return successors, (23), 22 states have call predecessors, (23), 23 states have call successors, (23) [2025-03-03 13:50:14,982 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 71 states to 71 states and 94 transitions. [2025-03-03 13:50:14,983 INFO L78 Accepts]: Start accepts. Automaton has 71 states and 94 transitions. Word has length 45 [2025-03-03 13:50:14,983 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 13:50:14,984 INFO L471 AbstractCegarLoop]: Abstraction has 71 states and 94 transitions. [2025-03-03 13:50:14,984 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.0) internal successors, (15), 4 states have internal predecessors, (15), 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:50:14,984 INFO L276 IsEmpty]: Start isEmpty. Operand 71 states and 94 transitions. [2025-03-03 13:50:14,985 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 50 [2025-03-03 13:50:14,986 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 13:50:14,986 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] [2025-03-03 13:50:14,992 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:50:15,187 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 13:50:15,188 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 13:50:15,188 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 13:50:15,188 INFO L85 PathProgramCache]: Analyzing trace with hash -1630456210, now seen corresponding path program 1 times [2025-03-03 13:50:15,188 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 13:50:15,188 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1220998549] [2025-03-03 13:50:15,188 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 13:50:15,188 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 13:50:15,193 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 49 statements into 1 equivalence classes. [2025-03-03 13:50:15,200 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 49 of 49 statements. [2025-03-03 13:50:15,200 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 13:50:15,200 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 13:50:15,412 INFO L134 CoverageAnalysis]: Checked inductivity of 56 backedges. 10 proven. 7 refuted. 0 times theorem prover too weak. 39 trivial. 0 not checked. [2025-03-03 13:50:15,412 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-03 13:50:15,413 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1220998549] [2025-03-03 13:50:15,413 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1220998549] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-03 13:50:15,413 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1428189077] [2025-03-03 13:50:15,413 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 13:50:15,413 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 13:50:15,413 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 13:50:15,417 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:50:15,419 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:50:15,440 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 49 statements into 1 equivalence classes. [2025-03-03 13:50:15,451 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 49 of 49 statements. [2025-03-03 13:50:15,451 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 13:50:15,451 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 13:50:15,452 INFO L256 TraceCheckSpWp]: Trace formula consists of 120 conjuncts, 11 conjuncts are in the unsatisfiable core [2025-03-03 13:50:15,454 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-03 13:50:15,537 INFO L134 CoverageAnalysis]: Checked inductivity of 56 backedges. 8 proven. 0 refuted. 0 times theorem prover too weak. 48 trivial. 0 not checked. [2025-03-03 13:50:15,538 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2025-03-03 13:50:15,538 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1428189077] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-03 13:50:15,538 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2025-03-03 13:50:15,538 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [7] total 11 [2025-03-03 13:50:15,538 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1478220358] [2025-03-03 13:50:15,538 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-03 13:50:15,539 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2025-03-03 13:50:15,539 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-03 13:50:15,540 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2025-03-03 13:50:15,540 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=25, Invalid=85, Unknown=0, NotChecked=0, Total=110 [2025-03-03 13:50:15,540 INFO L87 Difference]: Start difference. First operand 71 states and 94 transitions. Second operand has 6 states, 5 states have (on average 2.8) internal successors, (14), 5 states have internal predecessors, (14), 3 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (8), 3 states have call predecessors, (8), 3 states have call successors, (8) [2025-03-03 13:50:15,614 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 13:50:15,615 INFO L93 Difference]: Finished difference Result 84 states and 106 transitions. [2025-03-03 13:50:15,615 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2025-03-03 13:50:15,615 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 5 states have (on average 2.8) internal successors, (14), 5 states have internal predecessors, (14), 3 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (8), 3 states have call predecessors, (8), 3 states have call successors, (8) Word has length 49 [2025-03-03 13:50:15,615 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 13:50:15,616 INFO L225 Difference]: With dead ends: 84 [2025-03-03 13:50:15,617 INFO L226 Difference]: Without dead ends: 80 [2025-03-03 13:50:15,617 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 59 GetRequests, 48 SyntacticMatches, 0 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 14 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=37, Invalid=119, Unknown=0, NotChecked=0, Total=156 [2025-03-03 13:50:15,618 INFO L435 NwaCegarLoop]: 31 mSDtfsCounter, 6 mSDsluCounter, 111 mSDsCounter, 0 mSdLazyCounter, 53 mSolverCounterSat, 7 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 6 SdHoareTripleChecker+Valid, 142 SdHoareTripleChecker+Invalid, 60 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 7 IncrementalHoareTripleChecker+Valid, 53 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-03 13:50:15,618 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [6 Valid, 142 Invalid, 60 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [7 Valid, 53 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-03 13:50:15,619 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 80 states. [2025-03-03 13:50:15,629 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 80 to 79. [2025-03-03 13:50:15,630 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 79 states, 43 states have (on average 1.186046511627907) internal successors, (51), 46 states have internal predecessors, (51), 25 states have call successors, (25), 10 states have call predecessors, (25), 10 states have return successors, (23), 22 states have call predecessors, (23), 23 states have call successors, (23) [2025-03-03 13:50:15,631 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 79 states to 79 states and 99 transitions. [2025-03-03 13:50:15,631 INFO L78 Accepts]: Start accepts. Automaton has 79 states and 99 transitions. Word has length 49 [2025-03-03 13:50:15,631 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 13:50:15,631 INFO L471 AbstractCegarLoop]: Abstraction has 79 states and 99 transitions. [2025-03-03 13:50:15,632 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 5 states have (on average 2.8) internal successors, (14), 5 states have internal predecessors, (14), 3 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (8), 3 states have call predecessors, (8), 3 states have call successors, (8) [2025-03-03 13:50:15,632 INFO L276 IsEmpty]: Start isEmpty. Operand 79 states and 99 transitions. [2025-03-03 13:50:15,633 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 51 [2025-03-03 13:50:15,633 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 13:50:15,633 INFO L218 NwaCegarLoop]: trace histogram [5, 4, 4, 4, 4, 4, 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:50:15,639 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:50:15,833 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 13:50:15,834 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 13:50:15,834 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 13:50:15,834 INFO L85 PathProgramCache]: Analyzing trace with hash 1601374274, now seen corresponding path program 1 times [2025-03-03 13:50:15,834 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 13:50:15,834 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [549875064] [2025-03-03 13:50:15,834 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 13:50:15,834 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 13:50:15,840 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 50 statements into 1 equivalence classes. [2025-03-03 13:50:15,850 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 50 of 50 statements. [2025-03-03 13:50:15,852 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 13:50:15,853 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-03 13:50:15,853 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1534984542] [2025-03-03 13:50:15,853 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 13:50:15,854 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 13:50:15,854 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 13:50:15,855 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:50:15,857 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:50:15,878 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 50 statements into 1 equivalence classes. [2025-03-03 13:50:15,891 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 50 of 50 statements. [2025-03-03 13:50:15,891 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 13:50:15,892 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 13:50:15,892 INFO L256 TraceCheckSpWp]: Trace formula consists of 126 conjuncts, 32 conjuncts are in the unsatisfiable core [2025-03-03 13:50:15,894 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-03 13:50:16,131 INFO L134 CoverageAnalysis]: Checked inductivity of 58 backedges. 17 proven. 5 refuted. 0 times theorem prover too weak. 36 trivial. 0 not checked. [2025-03-03 13:50:16,133 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-03 13:50:16,252 INFO L134 CoverageAnalysis]: Checked inductivity of 58 backedges. 8 proven. 2 refuted. 0 times theorem prover too weak. 48 trivial. 0 not checked. [2025-03-03 13:50:16,252 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-03 13:50:16,252 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [549875064] [2025-03-03 13:50:16,252 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-03 13:50:16,252 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1534984542] [2025-03-03 13:50:16,252 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1534984542] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-03 13:50:16,252 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-03-03 13:50:16,253 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 6] total 12 [2025-03-03 13:50:16,253 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1184764841] [2025-03-03 13:50:16,253 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-03-03 13:50:16,253 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2025-03-03 13:50:16,253 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-03 13:50:16,254 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2025-03-03 13:50:16,254 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=29, Invalid=103, Unknown=0, NotChecked=0, Total=132 [2025-03-03 13:50:16,254 INFO L87 Difference]: Start difference. First operand 79 states and 99 transitions. Second operand has 12 states, 9 states have (on average 2.3333333333333335) internal successors, (21), 9 states have internal predecessors, (21), 6 states have call successors, (16), 2 states have call predecessors, (16), 2 states have return successors, (15), 7 states have call predecessors, (15), 6 states have call successors, (15) [2025-03-03 13:50:16,567 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 13:50:16,567 INFO L93 Difference]: Finished difference Result 124 states and 174 transitions. [2025-03-03 13:50:16,568 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2025-03-03 13:50:16,568 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 9 states have (on average 2.3333333333333335) internal successors, (21), 9 states have internal predecessors, (21), 6 states have call successors, (16), 2 states have call predecessors, (16), 2 states have return successors, (15), 7 states have call predecessors, (15), 6 states have call successors, (15) Word has length 50 [2025-03-03 13:50:16,568 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 13:50:16,569 INFO L225 Difference]: With dead ends: 124 [2025-03-03 13:50:16,569 INFO L226 Difference]: Without dead ends: 122 [2025-03-03 13:50:16,569 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 103 GetRequests, 86 SyntacticMatches, 2 SemanticMatches, 15 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 33 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=65, Invalid=207, Unknown=0, NotChecked=0, Total=272 [2025-03-03 13:50:16,570 INFO L435 NwaCegarLoop]: 31 mSDtfsCounter, 41 mSDsluCounter, 189 mSDsCounter, 0 mSdLazyCounter, 186 mSolverCounterSat, 46 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 46 SdHoareTripleChecker+Valid, 220 SdHoareTripleChecker+Invalid, 232 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 46 IncrementalHoareTripleChecker+Valid, 186 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2025-03-03 13:50:16,570 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [46 Valid, 220 Invalid, 232 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [46 Valid, 186 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2025-03-03 13:50:16,570 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 122 states. [2025-03-03 13:50:16,586 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 122 to 102. [2025-03-03 13:50:16,587 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 102 states, 55 states have (on average 1.2545454545454546) internal successors, (69), 58 states have internal predecessors, (69), 34 states have call successors, (34), 12 states have call predecessors, (34), 12 states have return successors, (32), 31 states have call predecessors, (32), 32 states have call successors, (32) [2025-03-03 13:50:16,587 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 102 states to 102 states and 135 transitions. [2025-03-03 13:50:16,588 INFO L78 Accepts]: Start accepts. Automaton has 102 states and 135 transitions. Word has length 50 [2025-03-03 13:50:16,588 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 13:50:16,588 INFO L471 AbstractCegarLoop]: Abstraction has 102 states and 135 transitions. [2025-03-03 13:50:16,588 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 9 states have (on average 2.3333333333333335) internal successors, (21), 9 states have internal predecessors, (21), 6 states have call successors, (16), 2 states have call predecessors, (16), 2 states have return successors, (15), 7 states have call predecessors, (15), 6 states have call successors, (15) [2025-03-03 13:50:16,588 INFO L276 IsEmpty]: Start isEmpty. Operand 102 states and 135 transitions. [2025-03-03 13:50:16,589 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 56 [2025-03-03 13:50:16,589 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 13:50:16,589 INFO L218 NwaCegarLoop]: trace histogram [6, 5, 5, 4, 4, 4, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-03 13:50:16,595 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Forceful destruction successful, exit code 0 [2025-03-03 13:50:16,793 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 13:50:16,793 INFO L396 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 13:50:16,793 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 13:50:16,793 INFO L85 PathProgramCache]: Analyzing trace with hash -750050, now seen corresponding path program 2 times [2025-03-03 13:50:16,793 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 13:50:16,793 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [17446675] [2025-03-03 13:50:16,794 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-03 13:50:16,794 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 13:50:16,798 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 55 statements into 2 equivalence classes. [2025-03-03 13:50:16,805 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 55 of 55 statements. [2025-03-03 13:50:16,805 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-03 13:50:16,805 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-03 13:50:16,806 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [294053471] [2025-03-03 13:50:16,806 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-03 13:50:16,806 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 13:50:16,806 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 13:50:16,808 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:50:16,809 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:50:16,830 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 55 statements into 2 equivalence classes. [2025-03-03 13:50:16,844 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 55 of 55 statements. [2025-03-03 13:50:16,844 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-03 13:50:16,844 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 13:50:16,845 INFO L256 TraceCheckSpWp]: Trace formula consists of 135 conjuncts, 21 conjuncts are in the unsatisfiable core [2025-03-03 13:50:16,846 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-03 13:50:16,964 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:50:16,964 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-03 13:50:17,033 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:50:17,034 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-03 13:50:17,034 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [17446675] [2025-03-03 13:50:17,034 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-03 13:50:17,034 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [294053471] [2025-03-03 13:50:17,034 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [294053471] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-03 13:50:17,034 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-03-03 13:50:17,034 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 8 [2025-03-03 13:50:17,035 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1447105996] [2025-03-03 13:50:17,035 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-03-03 13:50:17,035 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2025-03-03 13:50:17,035 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-03 13:50:17,036 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2025-03-03 13:50:17,036 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=16, Invalid=40, Unknown=0, NotChecked=0, Total=56 [2025-03-03 13:50:17,036 INFO L87 Difference]: Start difference. First operand 102 states and 135 transitions. Second operand has 8 states, 6 states have (on average 3.0) internal successors, (18), 7 states have internal predecessors, (18), 5 states have call successors, (16), 2 states have call predecessors, (16), 1 states have return successors, (14), 5 states have call predecessors, (14), 5 states have call successors, (14) [2025-03-03 13:50:17,255 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 13:50:17,256 INFO L93 Difference]: Finished difference Result 115 states and 153 transitions. [2025-03-03 13:50:17,256 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2025-03-03 13:50:17,256 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 6 states have (on average 3.0) internal successors, (18), 7 states have internal predecessors, (18), 5 states have call successors, (16), 2 states have call predecessors, (16), 1 states have return successors, (14), 5 states have call predecessors, (14), 5 states have call successors, (14) Word has length 55 [2025-03-03 13:50:17,256 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 13:50:17,257 INFO L225 Difference]: With dead ends: 115 [2025-03-03 13:50:17,257 INFO L226 Difference]: Without dead ends: 97 [2025-03-03 13:50:17,258 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 111 GetRequests, 100 SyntacticMatches, 2 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=31, Invalid=79, Unknown=0, NotChecked=0, Total=110 [2025-03-03 13:50:17,258 INFO L435 NwaCegarLoop]: 35 mSDtfsCounter, 11 mSDsluCounter, 166 mSDsCounter, 0 mSdLazyCounter, 98 mSolverCounterSat, 22 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 11 SdHoareTripleChecker+Valid, 201 SdHoareTripleChecker+Invalid, 120 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 22 IncrementalHoareTripleChecker+Valid, 98 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2025-03-03 13:50:17,258 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [11 Valid, 201 Invalid, 120 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [22 Valid, 98 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2025-03-03 13:50:17,259 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 97 states. [2025-03-03 13:50:17,276 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 97 to 94. [2025-03-03 13:50:17,276 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 94 states, 52 states have (on average 1.2307692307692308) internal successors, (64), 54 states have internal predecessors, (64), 30 states have call successors, (30), 11 states have call predecessors, (30), 11 states have return successors, (28), 28 states have call predecessors, (28), 28 states have call successors, (28) [2025-03-03 13:50:17,277 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 94 states to 94 states and 122 transitions. [2025-03-03 13:50:17,277 INFO L78 Accepts]: Start accepts. Automaton has 94 states and 122 transitions. Word has length 55 [2025-03-03 13:50:17,277 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 13:50:17,277 INFO L471 AbstractCegarLoop]: Abstraction has 94 states and 122 transitions. [2025-03-03 13:50:17,277 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 6 states have (on average 3.0) internal successors, (18), 7 states have internal predecessors, (18), 5 states have call successors, (16), 2 states have call predecessors, (16), 1 states have return successors, (14), 5 states have call predecessors, (14), 5 states have call successors, (14) [2025-03-03 13:50:17,277 INFO L276 IsEmpty]: Start isEmpty. Operand 94 states and 122 transitions. [2025-03-03 13:50:17,278 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 63 [2025-03-03 13:50:17,278 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 13:50:17,278 INFO L218 NwaCegarLoop]: trace histogram [7, 6, 6, 4, 4, 4, 3, 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:50:17,284 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:50:17,482 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 9 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable8 [2025-03-03 13:50:17,482 INFO L396 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 13:50:17,482 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 13:50:17,482 INFO L85 PathProgramCache]: Analyzing trace with hash -1705449702, now seen corresponding path program 1 times [2025-03-03 13:50:17,482 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 13:50:17,483 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [366591260] [2025-03-03 13:50:17,483 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 13:50:17,483 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 13:50:17,486 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 62 statements into 1 equivalence classes. [2025-03-03 13:50:17,498 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 62 of 62 statements. [2025-03-03 13:50:17,499 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 13:50:17,499 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-03 13:50:17,499 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [970926717] [2025-03-03 13:50:17,499 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 13:50:17,500 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 13:50:17,500 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 13:50:17,501 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:50:17,503 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:50:17,526 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 62 statements into 1 equivalence classes. [2025-03-03 13:50:17,541 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 62 of 62 statements. [2025-03-03 13:50:17,541 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 13:50:17,541 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 13:50:17,542 INFO L256 TraceCheckSpWp]: Trace formula consists of 152 conjuncts, 19 conjuncts are in the unsatisfiable core [2025-03-03 13:50:17,544 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-03 13:50:17,647 INFO L134 CoverageAnalysis]: Checked inductivity of 103 backedges. 12 proven. 7 refuted. 0 times theorem prover too weak. 84 trivial. 0 not checked. [2025-03-03 13:50:17,647 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-03 13:50:17,714 INFO L134 CoverageAnalysis]: Checked inductivity of 103 backedges. 12 proven. 0 refuted. 0 times theorem prover too weak. 91 trivial. 0 not checked. [2025-03-03 13:50:17,714 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-03 13:50:17,714 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [366591260] [2025-03-03 13:50:17,714 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-03 13:50:17,714 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [970926717] [2025-03-03 13:50:17,714 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [970926717] provided 1 perfect and 1 imperfect interpolant sequences [2025-03-03 13:50:17,714 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2025-03-03 13:50:17,714 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [7] total 8 [2025-03-03 13:50:17,715 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [136628322] [2025-03-03 13:50:17,715 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-03 13:50:17,715 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2025-03-03 13:50:17,715 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-03 13:50:17,715 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2025-03-03 13:50:17,715 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=16, Invalid=40, Unknown=0, NotChecked=0, Total=56 [2025-03-03 13:50:17,716 INFO L87 Difference]: Start difference. First operand 94 states and 122 transitions. Second operand has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 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:50:17,781 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 13:50:17,782 INFO L93 Difference]: Finished difference Result 100 states and 127 transitions. [2025-03-03 13:50:17,782 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2025-03-03 13:50:17,782 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 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 62 [2025-03-03 13:50:17,782 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 13:50:17,783 INFO L225 Difference]: With dead ends: 100 [2025-03-03 13:50:17,783 INFO L226 Difference]: Without dead ends: 95 [2025-03-03 13:50:17,783 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 123 GetRequests, 114 SyntacticMatches, 2 SemanticMatches, 7 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=20, Invalid=52, Unknown=0, NotChecked=0, Total=72 [2025-03-03 13:50:17,784 INFO L435 NwaCegarLoop]: 30 mSDtfsCounter, 4 mSDsluCounter, 76 mSDsCounter, 0 mSdLazyCounter, 22 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 6 SdHoareTripleChecker+Valid, 106 SdHoareTripleChecker+Invalid, 23 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 22 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-03-03 13:50:17,784 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [6 Valid, 106 Invalid, 23 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 22 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-03-03 13:50:17,784 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 95 states. [2025-03-03 13:50:17,797 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 95 to 93. [2025-03-03 13:50:17,797 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 93 states, 54 states have (on average 1.2037037037037037) internal successors, (65), 54 states have internal predecessors, (65), 27 states have call successors, (27), 12 states have call predecessors, (27), 11 states have return successors, (26), 26 states have call predecessors, (26), 26 states have call successors, (26) [2025-03-03 13:50:17,798 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 93 states to 93 states and 118 transitions. [2025-03-03 13:50:17,798 INFO L78 Accepts]: Start accepts. Automaton has 93 states and 118 transitions. Word has length 62 [2025-03-03 13:50:17,798 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 13:50:17,799 INFO L471 AbstractCegarLoop]: Abstraction has 93 states and 118 transitions. [2025-03-03 13:50:17,799 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 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:50:17,799 INFO L276 IsEmpty]: Start isEmpty. Operand 93 states and 118 transitions. [2025-03-03 13:50:17,799 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 67 [2025-03-03 13:50:17,799 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 13:50:17,800 INFO L218 NwaCegarLoop]: trace histogram [8, 7, 7, 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, 1, 1] [2025-03-03 13:50:17,806 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:50:18,000 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 10 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable9 [2025-03-03 13:50:18,000 INFO L396 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 13:50:18,000 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 13:50:18,000 INFO L85 PathProgramCache]: Analyzing trace with hash 501411722, now seen corresponding path program 1 times [2025-03-03 13:50:18,001 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 13:50:18,001 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [805373665] [2025-03-03 13:50:18,001 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 13:50:18,001 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 13:50:18,004 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 66 statements into 1 equivalence classes. [2025-03-03 13:50:18,010 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 66 of 66 statements. [2025-03-03 13:50:18,011 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 13:50:18,011 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 13:50:18,144 INFO L134 CoverageAnalysis]: Checked inductivity of 126 backedges. 27 proven. 7 refuted. 0 times theorem prover too weak. 92 trivial. 0 not checked. [2025-03-03 13:50:18,144 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-03 13:50:18,144 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [805373665] [2025-03-03 13:50:18,144 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [805373665] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-03 13:50:18,145 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [779123111] [2025-03-03 13:50:18,145 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 13:50:18,145 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 13:50:18,145 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 13:50:18,146 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:50:18,148 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:50:18,170 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 66 statements into 1 equivalence classes. [2025-03-03 13:50:18,183 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 66 of 66 statements. [2025-03-03 13:50:18,183 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 13:50:18,183 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 13:50:18,184 INFO L256 TraceCheckSpWp]: Trace formula consists of 155 conjuncts, 10 conjuncts are in the unsatisfiable core [2025-03-03 13:50:18,185 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-03 13:50:18,210 INFO L134 CoverageAnalysis]: Checked inductivity of 126 backedges. 27 proven. 7 refuted. 0 times theorem prover too weak. 92 trivial. 0 not checked. [2025-03-03 13:50:18,210 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-03 13:50:18,274 INFO L134 CoverageAnalysis]: Checked inductivity of 126 backedges. 27 proven. 7 refuted. 0 times theorem prover too weak. 92 trivial. 0 not checked. [2025-03-03 13:50:18,274 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [779123111] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-03 13:50:18,275 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-03 13:50:18,275 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8, 8] total 11 [2025-03-03 13:50:18,275 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [628112312] [2025-03-03 13:50:18,275 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-03 13:50:18,275 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 11 states [2025-03-03 13:50:18,275 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-03 13:50:18,275 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2025-03-03 13:50:18,276 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=26, Invalid=84, Unknown=0, NotChecked=0, Total=110 [2025-03-03 13:50:18,276 INFO L87 Difference]: Start difference. First operand 93 states and 118 transitions. Second operand has 11 states, 9 states have (on average 2.6666666666666665) internal successors, (24), 9 states have internal predecessors, (24), 4 states have call successors, (12), 3 states have call predecessors, (12), 2 states have return successors, (11), 3 states have call predecessors, (11), 4 states have call successors, (11) [2025-03-03 13:50:18,349 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 13:50:18,350 INFO L93 Difference]: Finished difference Result 103 states and 128 transitions. [2025-03-03 13:50:18,350 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2025-03-03 13:50:18,350 INFO L78 Accepts]: Start accepts. Automaton has has 11 states, 9 states have (on average 2.6666666666666665) internal successors, (24), 9 states have internal predecessors, (24), 4 states have call successors, (12), 3 states have call predecessors, (12), 2 states have return successors, (11), 3 states have call predecessors, (11), 4 states have call successors, (11) Word has length 66 [2025-03-03 13:50:18,350 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 13:50:18,351 INFO L225 Difference]: With dead ends: 103 [2025-03-03 13:50:18,351 INFO L226 Difference]: Without dead ends: 0 [2025-03-03 13:50:18,352 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 141 GetRequests, 129 SyntacticMatches, 2 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 20 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=34, Invalid=98, Unknown=0, NotChecked=0, Total=132 [2025-03-03 13:50:18,353 INFO L435 NwaCegarLoop]: 23 mSDtfsCounter, 5 mSDsluCounter, 80 mSDsCounter, 0 mSdLazyCounter, 66 mSolverCounterSat, 6 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 7 SdHoareTripleChecker+Valid, 103 SdHoareTripleChecker+Invalid, 72 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 6 IncrementalHoareTripleChecker+Valid, 66 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-03-03 13:50:18,353 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [7 Valid, 103 Invalid, 72 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [6 Valid, 66 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-03-03 13:50:18,353 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 0 states. [2025-03-03 13:50:18,353 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 0 to 0. [2025-03-03 13:50:18,354 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 0 states, 0 states have (on average 0.0) internal successors, (0), 0 states have internal predecessors, (0), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2025-03-03 13:50:18,354 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 0 states to 0 states and 0 transitions. [2025-03-03 13:50:18,354 INFO L78 Accepts]: Start accepts. Automaton has 0 states and 0 transitions. Word has length 66 [2025-03-03 13:50:18,354 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 13:50:18,354 INFO L471 AbstractCegarLoop]: Abstraction has 0 states and 0 transitions. [2025-03-03 13:50:18,354 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 11 states, 9 states have (on average 2.6666666666666665) internal successors, (24), 9 states have internal predecessors, (24), 4 states have call successors, (12), 3 states have call predecessors, (12), 2 states have return successors, (11), 3 states have call predecessors, (11), 4 states have call successors, (11) [2025-03-03 13:50:18,354 INFO L276 IsEmpty]: Start isEmpty. Operand 0 states and 0 transitions. [2025-03-03 13:50:18,354 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2025-03-03 13:50:18,356 INFO L782 garLoopResultBuilder]: Registering result SAFE for location __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION (0 of 1 remaining) [2025-03-03 13:50:18,362 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:50:18,561 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,SelfDestructingSolverStorable10 [2025-03-03 13:50:18,563 INFO L422 BasicCegarLoop]: Path program histogram: [2, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-03 13:50:18,564 INFO L343 DoubleDeckerVisitor]: Before removal of dead ends 0 states and 0 transitions. [2025-03-03 13:50:26,715 INFO L170 ceAbstractionStarter]: Computing trace abstraction results [2025-03-03 13:50:26,725 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 03.03 01:50:26 BoogieIcfgContainer [2025-03-03 13:50:26,725 INFO L131 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2025-03-03 13:50:26,726 INFO L112 PluginConnector]: ------------------------Witness Printer---------------------------- [2025-03-03 13:50:26,726 INFO L270 PluginConnector]: Initializing Witness Printer... [2025-03-03 13:50:26,726 INFO L274 PluginConnector]: Witness Printer initialized [2025-03-03 13:50:26,726 INFO L184 PluginConnector]: Executing the observer RCFGCatcher from plugin Witness Printer for "de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 03.03 01:50:12" (3/4) ... [2025-03-03 13:50:26,728 INFO L146 WitnessPrinter]: Generating witness for correct program [2025-03-03 13:50:26,731 INFO L385 IcfgBacktranslator]: Ignoring RootEdge to procedure assume_abort_if_not [2025-03-03 13:50:26,731 INFO L385 IcfgBacktranslator]: Ignoring RootEdge to procedure __VERIFIER_assert [2025-03-03 13:50:26,733 INFO L919 BoogieBacktranslator]: Reduced CFG by removing 13 nodes and edges [2025-03-03 13:50:26,733 INFO L919 BoogieBacktranslator]: Reduced CFG by removing 4 nodes and edges [2025-03-03 13:50:26,734 INFO L919 BoogieBacktranslator]: Reduced CFG by removing 3 nodes and edges [2025-03-03 13:50:26,734 INFO L919 BoogieBacktranslator]: Reduced CFG by removing 1 nodes and edges [2025-03-03 13:50:26,789 INFO L149 WitnessManager]: Wrote witness to /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/witness.graphml [2025-03-03 13:50:26,790 INFO L149 WitnessManager]: Wrote witness to /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/witness.yml [2025-03-03 13:50:26,790 INFO L131 PluginConnector]: ------------------------ END Witness Printer---------------------------- [2025-03-03 13:50:26,791 INFO L158 Benchmark]: Toolchain (without parser) took 14346.06ms. Allocated memory is still 167.8MB. Free memory was 123.5MB in the beginning and 133.5MB in the end (delta: -9.9MB). Peak memory consumption was 83.9MB. Max. memory is 16.1GB. [2025-03-03 13:50:26,791 INFO L158 Benchmark]: CDTParser took 0.13ms. Allocated memory is still 201.3MB. Free memory is still 116.5MB. There was no memory consumed. Max. memory is 16.1GB. [2025-03-03 13:50:26,792 INFO L158 Benchmark]: CACSL2BoogieTranslator took 143.04ms. Allocated memory is still 167.8MB. Free memory was 123.5MB in the beginning and 112.5MB in the end (delta: 11.0MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. [2025-03-03 13:50:26,792 INFO L158 Benchmark]: Boogie Procedure Inliner took 17.88ms. Allocated memory is still 167.8MB. Free memory was 112.5MB in the beginning and 111.5MB in the end (delta: 983.9kB). There was no memory consumed. Max. memory is 16.1GB. [2025-03-03 13:50:26,792 INFO L158 Benchmark]: Boogie Preprocessor took 18.18ms. Allocated memory is still 167.8MB. Free memory was 111.5MB in the beginning and 110.5MB in the end (delta: 1.0MB). There was no memory consumed. Max. memory is 16.1GB. [2025-03-03 13:50:26,792 INFO L158 Benchmark]: IcfgBuilder took 191.90ms. Allocated memory is still 167.8MB. Free memory was 110.5MB in the beginning and 97.8MB in the end (delta: 12.8MB). Peak memory consumption was 16.8MB. Max. memory is 16.1GB. [2025-03-03 13:50:26,792 INFO L158 Benchmark]: TraceAbstraction took 13905.83ms. Allocated memory is still 167.8MB. Free memory was 96.8MB in the beginning and 47.9MB in the end (delta: 48.8MB). Peak memory consumption was 58.7MB. Max. memory is 16.1GB. [2025-03-03 13:50:26,793 INFO L158 Benchmark]: Witness Printer took 64.10ms. Allocated memory is still 167.8MB. Free memory was 47.9MB in the beginning and 133.5MB in the end (delta: -85.5MB). Peak memory consumption was 8.6MB. Max. memory is 16.1GB. [2025-03-03 13:50:26,794 INFO L338 ainManager$Toolchain]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * CDTParser took 0.13ms. Allocated memory is still 201.3MB. Free memory is still 116.5MB. There was no memory consumed. Max. memory is 16.1GB. * CACSL2BoogieTranslator took 143.04ms. Allocated memory is still 167.8MB. Free memory was 123.5MB in the beginning and 112.5MB in the end (delta: 11.0MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. * Boogie Procedure Inliner took 17.88ms. Allocated memory is still 167.8MB. Free memory was 112.5MB in the beginning and 111.5MB in the end (delta: 983.9kB). There was no memory consumed. Max. memory is 16.1GB. * Boogie Preprocessor took 18.18ms. Allocated memory is still 167.8MB. Free memory was 111.5MB in the beginning and 110.5MB in the end (delta: 1.0MB). There was no memory consumed. Max. memory is 16.1GB. * IcfgBuilder took 191.90ms. Allocated memory is still 167.8MB. Free memory was 110.5MB in the beginning and 97.8MB in the end (delta: 12.8MB). Peak memory consumption was 16.8MB. Max. memory is 16.1GB. * TraceAbstraction took 13905.83ms. Allocated memory is still 167.8MB. Free memory was 96.8MB in the beginning and 47.9MB in the end (delta: 48.8MB). Peak memory consumption was 58.7MB. Max. memory is 16.1GB. * Witness Printer took 64.10ms. Allocated memory is still 167.8MB. Free memory was 47.9MB in the beginning and 133.5MB in the end (delta: -85.5MB). Peak memory consumption was 8.6MB. Max. memory is 16.1GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - StatisticsResult: ErrorAutomatonStatistics NumberErrorTraces: 0, NumberStatementsAllTraces: 0, NumberRelevantStatements: 0, 0.0s ErrorAutomatonConstructionTimeTotal, 0.0s FaulLocalizationTime, NumberStatementsFirstTrace: -1, TraceLengthAvg: 0, 0.0s ErrorAutomatonConstructionTimeAvg, 0.0s ErrorAutomatonDifferenceTimeAvg, 0.0s ErrorAutomatonDifferenceTimeTotal, NumberOfNoEnhancement: 0, NumberOfFiniteEnhancement: 0, NumberOfInfiniteEnhancement: 0 - PositiveResult [Line: 13]: a call to reach_error is unreachable For all program executions holds that a call to reach_error is unreachable at this location - StatisticsResult: Ultimate Automizer benchmark data CFG has 3 procedures, 31 locations, 1 error locations. Started 1 CEGAR loops. OverallTime: 5.7s, OverallIterations: 11, TraceHistogramMax: 8, PathProgramHistogramMax: 2, EmptinessCheckTime: 0.0s, AutomataDifference: 1.1s, DeadEndRemovalTime: 0.0s, HoareAnnotationTime: 0.0s, InitialAbstractionConstructionTime: 0.0s, HoareTripleCheckerStatistics: 0 mSolverCounterUnknown, 121 SdHoareTripleChecker+Valid, 0.7s IncrementalHoareTripleChecker+Time, 0 mSdLazyCounter, 91 mSDsluCounter, 1412 SdHoareTripleChecker+Invalid, 0.6s Time, 0 mProtectedAction, 0 SdHoareTripleChecker+Unchecked, 0 IncrementalHoareTripleChecker+Unchecked, 1056 mSDsCounter, 86 IncrementalHoareTripleChecker+Valid, 0 mProtectedPredicate, 581 IncrementalHoareTripleChecker+Invalid, 667 SdHoareTripleChecker+Unknown, 0 mSolverCounterNotChecked, 86 mSolverCounterUnsat, 356 mSDtfsCounter, 581 mSolverCounterSat, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Unknown, PredicateUnifierStatistics: 0 DeclaredPredicates, 717 GetRequests, 637 SyntacticMatches, 8 SemanticMatches, 72 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 70 ImplicationChecksByTransitivity, 0.5s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=102occurred in iteration=8, InterpolantAutomatonStates: 67, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 0.0s DumpTime, AutomataMinimizationStatistics: 0.1s AutomataMinimizationTime, 11 MinimizatonAttempts, 37 StatesRemovedByMinimization, 7 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TRACE_CHECK: 0.1s SsaConstructionTime, 0.3s SatisfiabilityAnalysisTime, 1.7s InterpolantComputationTime, 952 NumberOfCodeBlocks, 952 NumberOfCodeBlocksAsserted, 23 NumberOfCheckSat, 856 ConstructedInterpolants, 0 QuantifiedInterpolants, 2128 SizeOfPredicates, 18 NumberOfNonLiveVariables, 1160 ConjunctsInSsa, 135 ConjunctsInUnsatCore, 18 InterpolantComputations, 8 PerfectInterpolantSequences, 1127/1181 InterpolantCoveringCapability, INVARIANT_SYNTHESIS: No data available, INTERPOLANT_CONSOLIDATION: No data available, ABSTRACT_INTERPRETATION: No data available, PDR: No data available, ACCELERATED_INTERPOLATION: No data available, SIFA: No data available, ReuseStatistics: No data available, ConComCheckerStatistics: No data available - AllSpecificationsHoldResult: All specifications hold 1 specifications checked. All of them hold - InvariantResult [Line: 35]: Location Invariant Derived location invariant: (((((((__int128) p * s) == (((__int128) q * r) + 1)) && (1 <= y)) && (y <= 10)) && (((((__int128) r * y) + b) + ((__int128) p * x)) == ((a + ((__int128) s * y)) + ((__int128) q * x)))) && ((((__int128) r * y) + ((__int128) p * x)) == a)) RESULT: Ultimate proved your program to be correct! [2025-03-03 13:50:26,812 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (1)] Ended with exit code 0 Received shutdown request... --- End real Ultimate output --- Execution finished normally Writing output log to file Ultimate.log Result: TRUE