./Ultimate.py --spec /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/properties/unreach-call.prp --file /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/egcd3-ll_unwindbound50.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version 84cfde4a Calling Ultimate with: /root/.sdkman/candidates/java/current/bin/java -Dosgi.configuration.area=/storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/data/config -Xmx15G -Xms4m -jar /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/data -tc /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/config/AutomizerReach.xml -i /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/egcd3-ll_unwindbound50.c -s /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf --cacsl2boogietranslator.entry.function main --witnessprinter.witness.directory /storage/repos/ultimate-clean/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 436f0a1b9da8affd8e76edc25dee0cffff5a08ff489ec96067821d6a4548518b --- Real Ultimate output --- This is Ultimate 0.2.5-dev-84cfde4 [2024-10-11 02:10:05,995 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-10-11 02:10:06,078 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf [2024-10-11 02:10:06,083 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-10-11 02:10:06,084 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-10-11 02:10:06,116 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-10-11 02:10:06,116 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-10-11 02:10:06,117 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-10-11 02:10:06,117 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2024-10-11 02:10:06,117 INFO L153 SettingsManager]: * Use memory slicer=true [2024-10-11 02:10:06,118 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2024-10-11 02:10:06,118 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2024-10-11 02:10:06,119 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2024-10-11 02:10:06,122 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2024-10-11 02:10:06,123 INFO L153 SettingsManager]: * Use SBE=true [2024-10-11 02:10:06,123 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-10-11 02:10:06,123 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2024-10-11 02:10:06,123 INFO L153 SettingsManager]: * sizeof long=4 [2024-10-11 02:10:06,124 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2024-10-11 02:10:06,124 INFO L153 SettingsManager]: * sizeof POINTER=4 [2024-10-11 02:10:06,124 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-10-11 02:10:06,125 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2024-10-11 02:10:06,125 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2024-10-11 02:10:06,125 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2024-10-11 02:10:06,125 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-10-11 02:10:06,126 INFO L153 SettingsManager]: * sizeof long double=12 [2024-10-11 02:10:06,126 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-10-11 02:10:06,126 INFO L153 SettingsManager]: * Use constant arrays=true [2024-10-11 02:10:06,126 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2024-10-11 02:10:06,127 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2024-10-11 02:10:06,127 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2024-10-11 02:10:06,127 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2024-10-11 02:10:06,127 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-10-11 02:10:06,128 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-10-11 02:10:06,128 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2024-10-11 02:10:06,128 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2024-10-11 02:10:06,128 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2024-10-11 02:10:06,129 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2024-10-11 02:10:06,129 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2024-10-11 02:10:06,129 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2024-10-11 02:10:06,129 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2024-10-11 02:10:06,130 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2024-10-11 02:10:06,130 INFO L153 SettingsManager]: * Looper check in Petri net analysis=SEMANTIC WARNING: An illegal reflective access operation has occurred WARNING: Illegal reflective access by com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 (file:/storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/plugins/com.sun.xml.bind_2.2.0.v201505121915.jar) to method java.lang.ClassLoader.defineClass(java.lang.String,byte[],int,int) WARNING: Please consider reporting this to the maintainers of com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 WARNING: Use --illegal-access=warn to enable warnings of further illegal reflective access operations WARNING: All illegal access operations will be denied in a future release 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-clean/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 -> 436f0a1b9da8affd8e76edc25dee0cffff5a08ff489ec96067821d6a4548518b [2024-10-11 02:10:06,382 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-10-11 02:10:06,404 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-10-11 02:10:06,408 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-10-11 02:10:06,409 INFO L270 PluginConnector]: Initializing CDTParser... [2024-10-11 02:10:06,412 INFO L274 PluginConnector]: CDTParser initialized [2024-10-11 02:10:06,414 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/egcd3-ll_unwindbound50.c [2024-10-11 02:10:07,861 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-10-11 02:10:08,036 INFO L384 CDTParser]: Found 1 translation units. [2024-10-11 02:10:08,037 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/egcd3-ll_unwindbound50.c [2024-10-11 02:10:08,045 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/data/b806f6a8e/be3145b705bc417cb43b9bd39d81b3a5/FLAGb1b1e4cc8 [2024-10-11 02:10:08,436 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/data/b806f6a8e/be3145b705bc417cb43b9bd39d81b3a5 [2024-10-11 02:10:08,438 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-10-11 02:10:08,440 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2024-10-11 02:10:08,441 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-10-11 02:10:08,441 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-10-11 02:10:08,447 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-10-11 02:10:08,448 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 11.10 02:10:08" (1/1) ... [2024-10-11 02:10:08,449 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@5e193b75 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.10 02:10:08, skipping insertion in model container [2024-10-11 02:10:08,449 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 11.10 02:10:08" (1/1) ... [2024-10-11 02:10:08,468 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-10-11 02:10:08,637 WARN L248 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/egcd3-ll_unwindbound50.c[490,503] [2024-10-11 02:10:08,673 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-10-11 02:10:08,683 INFO L200 MainTranslator]: Completed pre-run [2024-10-11 02:10:08,694 WARN L248 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/egcd3-ll_unwindbound50.c[490,503] [2024-10-11 02:10:08,711 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-10-11 02:10:08,753 INFO L204 MainTranslator]: Completed translation [2024-10-11 02:10:08,753 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.10 02:10:08 WrapperNode [2024-10-11 02:10:08,753 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-10-11 02:10:08,754 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-10-11 02:10:08,755 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-10-11 02:10:08,755 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-10-11 02:10:08,774 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.10 02:10:08" (1/1) ... [2024-10-11 02:10:08,788 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.10 02:10:08" (1/1) ... [2024-10-11 02:10:08,841 INFO L138 Inliner]: procedures = 14, calls = 14, calls flagged for inlining = 2, calls inlined = 2, statements flattened = 94 [2024-10-11 02:10:08,842 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-10-11 02:10:08,842 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-10-11 02:10:08,842 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-10-11 02:10:08,843 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-10-11 02:10:08,858 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.10 02:10:08" (1/1) ... [2024-10-11 02:10:08,859 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.10 02:10:08" (1/1) ... [2024-10-11 02:10:08,860 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.10 02:10:08" (1/1) ... [2024-10-11 02:10:08,872 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]. [2024-10-11 02:10:08,873 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.10 02:10:08" (1/1) ... [2024-10-11 02:10:08,876 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.10 02:10:08" (1/1) ... [2024-10-11 02:10:08,879 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.10 02:10:08" (1/1) ... [2024-10-11 02:10:08,882 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.10 02:10:08" (1/1) ... [2024-10-11 02:10:08,883 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.10 02:10:08" (1/1) ... [2024-10-11 02:10:08,883 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.10 02:10:08" (1/1) ... [2024-10-11 02:10:08,885 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-10-11 02:10:08,886 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2024-10-11 02:10:08,886 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2024-10-11 02:10:08,886 INFO L274 PluginConnector]: RCFGBuilder initialized [2024-10-11 02:10:08,887 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.10 02:10:08" (1/1) ... [2024-10-11 02:10:08,892 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-10-11 02:10:08,904 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 [2024-10-11 02:10:08,922 INFO L229 MonitoredProcess]: Starting monitored process 1 with /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (exit command is (exit), workingDir is null) [2024-10-11 02:10:08,924 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (1)] Waiting until timeout for monitored process [2024-10-11 02:10:08,963 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2024-10-11 02:10:08,964 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2024-10-11 02:10:08,964 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2024-10-11 02:10:08,964 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2024-10-11 02:10:08,964 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-10-11 02:10:08,964 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-10-11 02:10:08,964 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2024-10-11 02:10:08,964 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2024-10-11 02:10:09,017 INFO L238 CfgBuilder]: Building ICFG [2024-10-11 02:10:09,019 INFO L264 CfgBuilder]: Building CFG for each procedure with an implementation [2024-10-11 02:10:09,159 INFO L? ?]: Removed 6 outVars from TransFormulas that were not future-live. [2024-10-11 02:10:09,159 INFO L287 CfgBuilder]: Performing block encoding [2024-10-11 02:10:09,186 INFO L309 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-10-11 02:10:09,187 INFO L314 CfgBuilder]: Removed 3 assume(true) statements. [2024-10-11 02:10:09,187 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 11.10 02:10:09 BoogieIcfgContainer [2024-10-11 02:10:09,187 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2024-10-11 02:10:09,189 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2024-10-11 02:10:09,189 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2024-10-11 02:10:09,193 INFO L274 PluginConnector]: TraceAbstraction initialized [2024-10-11 02:10:09,193 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 11.10 02:10:08" (1/3) ... [2024-10-11 02:10:09,194 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@36bb12b2 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 11.10 02:10:09, skipping insertion in model container [2024-10-11 02:10:09,194 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.10 02:10:08" (2/3) ... [2024-10-11 02:10:09,195 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@36bb12b2 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 11.10 02:10:09, skipping insertion in model container [2024-10-11 02:10:09,195 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 11.10 02:10:09" (3/3) ... [2024-10-11 02:10:09,196 INFO L112 eAbstractionObserver]: Analyzing ICFG egcd3-ll_unwindbound50.c [2024-10-11 02:10:09,213 INFO L209 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2024-10-11 02:10:09,213 INFO L149 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2024-10-11 02:10:09,267 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2024-10-11 02:10:09,272 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;@52fab4, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2024-10-11 02:10:09,272 INFO L334 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2024-10-11 02:10:09,275 INFO L276 IsEmpty]: Start isEmpty. Operand has 32 states, 21 states have (on average 1.5714285714285714) internal successors, (33), 22 states have internal predecessors, (33), 7 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2024-10-11 02:10:09,280 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 18 [2024-10-11 02:10:09,281 INFO L207 NwaCegarLoop]: Found error trace [2024-10-11 02:10:09,281 INFO L215 NwaCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-11 02:10:09,281 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-11 02:10:09,285 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-11 02:10:09,285 INFO L85 PathProgramCache]: Analyzing trace with hash -832436526, now seen corresponding path program 1 times [2024-10-11 02:10:09,293 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-11 02:10:09,293 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1460107954] [2024-10-11 02:10:09,294 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-11 02:10:09,294 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-11 02:10:09,400 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:10:09,461 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 1 [2024-10-11 02:10:09,463 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:10:09,471 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2024-10-11 02:10:09,475 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:10:09,482 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-10-11 02:10:09,486 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-11 02:10:09,486 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1460107954] [2024-10-11 02:10:09,487 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1460107954] provided 1 perfect and 0 imperfect interpolant sequences [2024-10-11 02:10:09,487 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-10-11 02:10:09,488 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2024-10-11 02:10:09,489 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1912681968] [2024-10-11 02:10:09,490 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-10-11 02:10:09,493 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2024-10-11 02:10:09,494 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-11 02:10:09,517 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2024-10-11 02:10:09,517 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2024-10-11 02:10:09,520 INFO L87 Difference]: Start difference. First operand has 32 states, 21 states have (on average 1.5714285714285714) internal successors, (33), 22 states have internal predecessors, (33), 7 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) Second operand has 2 states, 2 states have (on average 4.5) internal successors, (9), 2 states have internal predecessors, (9), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) [2024-10-11 02:10:09,553 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-11 02:10:09,553 INFO L93 Difference]: Finished difference Result 62 states and 98 transitions. [2024-10-11 02:10:09,558 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2024-10-11 02:10:09,559 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 4.5) internal successors, (9), 2 states have internal predecessors, (9), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) Word has length 17 [2024-10-11 02:10:09,559 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-11 02:10:09,566 INFO L225 Difference]: With dead ends: 62 [2024-10-11 02:10:09,566 INFO L226 Difference]: Without dead ends: 30 [2024-10-11 02:10:09,570 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 8 GetRequests, 8 SyntacticMatches, 0 SemanticMatches, 0 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2024-10-11 02:10:09,574 INFO L432 NwaCegarLoop]: 40 mSDtfsCounter, 0 mSDsluCounter, 0 mSDsCounter, 0 mSdLazyCounter, 2 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 40 SdHoareTripleChecker+Invalid, 2 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 2 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-10-11 02:10:09,575 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 40 Invalid, 2 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 2 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-10-11 02:10:09,590 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 30 states. [2024-10-11 02:10:09,606 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 30 to 30. [2024-10-11 02:10:09,608 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 30 states, 20 states have (on average 1.35) internal successors, (27), 21 states have internal predecessors, (27), 7 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2024-10-11 02:10:09,610 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 30 states to 30 states and 40 transitions. [2024-10-11 02:10:09,611 INFO L78 Accepts]: Start accepts. Automaton has 30 states and 40 transitions. Word has length 17 [2024-10-11 02:10:09,612 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-11 02:10:09,613 INFO L471 AbstractCegarLoop]: Abstraction has 30 states and 40 transitions. [2024-10-11 02:10:09,613 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 2 states have (on average 4.5) internal successors, (9), 2 states have internal predecessors, (9), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) [2024-10-11 02:10:09,613 INFO L276 IsEmpty]: Start isEmpty. Operand 30 states and 40 transitions. [2024-10-11 02:10:09,614 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 19 [2024-10-11 02:10:09,614 INFO L207 NwaCegarLoop]: Found error trace [2024-10-11 02:10:09,614 INFO L215 NwaCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-11 02:10:09,615 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2024-10-11 02:10:09,615 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-11 02:10:09,617 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-11 02:10:09,618 INFO L85 PathProgramCache]: Analyzing trace with hash 958862887, now seen corresponding path program 1 times [2024-10-11 02:10:09,618 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-11 02:10:09,618 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [447206858] [2024-10-11 02:10:09,618 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-11 02:10:09,618 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-11 02:10:09,649 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:10:09,753 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 1 [2024-10-11 02:10:09,758 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:10:09,764 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2024-10-11 02:10:09,767 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:10:09,773 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-10-11 02:10:09,773 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-11 02:10:09,773 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [447206858] [2024-10-11 02:10:09,773 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [447206858] provided 1 perfect and 0 imperfect interpolant sequences [2024-10-11 02:10:09,774 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-10-11 02:10:09,774 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2024-10-11 02:10:09,774 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [86840863] [2024-10-11 02:10:09,774 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-10-11 02:10:09,775 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2024-10-11 02:10:09,775 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-11 02:10:09,776 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2024-10-11 02:10:09,776 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2024-10-11 02:10:09,776 INFO L87 Difference]: Start difference. First operand 30 states and 40 transitions. Second operand has 4 states, 4 states have (on average 2.5) internal successors, (10), 4 states have internal predecessors, (10), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2024-10-11 02:10:09,801 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-11 02:10:09,801 INFO L93 Difference]: Finished difference Result 39 states and 49 transitions. [2024-10-11 02:10:09,802 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2024-10-11 02:10:09,802 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 2.5) internal successors, (10), 4 states have internal predecessors, (10), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) Word has length 18 [2024-10-11 02:10:09,802 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-11 02:10:09,803 INFO L225 Difference]: With dead ends: 39 [2024-10-11 02:10:09,803 INFO L226 Difference]: Without dead ends: 32 [2024-10-11 02:10:09,804 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 7 GetRequests, 5 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2024-10-11 02:10:09,805 INFO L432 NwaCegarLoop]: 37 mSDtfsCounter, 5 mSDsluCounter, 63 mSDsCounter, 0 mSdLazyCounter, 11 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 5 SdHoareTripleChecker+Valid, 100 SdHoareTripleChecker+Invalid, 11 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 11 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-10-11 02:10:09,805 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [5 Valid, 100 Invalid, 11 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 11 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-10-11 02:10:09,806 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 32 states. [2024-10-11 02:10:09,811 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 32 to 32. [2024-10-11 02:10:09,811 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 32 states, 22 states have (on average 1.3181818181818181) internal successors, (29), 23 states have internal predecessors, (29), 7 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2024-10-11 02:10:09,812 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 32 states to 32 states and 42 transitions. [2024-10-11 02:10:09,813 INFO L78 Accepts]: Start accepts. Automaton has 32 states and 42 transitions. Word has length 18 [2024-10-11 02:10:09,814 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-11 02:10:09,814 INFO L471 AbstractCegarLoop]: Abstraction has 32 states and 42 transitions. [2024-10-11 02:10:09,814 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 2.5) internal successors, (10), 4 states have internal predecessors, (10), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2024-10-11 02:10:09,814 INFO L276 IsEmpty]: Start isEmpty. Operand 32 states and 42 transitions. [2024-10-11 02:10:09,815 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 20 [2024-10-11 02:10:09,815 INFO L207 NwaCegarLoop]: Found error trace [2024-10-11 02:10:09,815 INFO L215 NwaCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-11 02:10:09,815 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2024-10-11 02:10:09,815 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-11 02:10:09,816 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-11 02:10:09,816 INFO L85 PathProgramCache]: Analyzing trace with hash -359656705, now seen corresponding path program 1 times [2024-10-11 02:10:09,816 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-11 02:10:09,816 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [100432194] [2024-10-11 02:10:09,816 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-11 02:10:09,816 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-11 02:10:09,845 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:10:09,947 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 1 [2024-10-11 02:10:09,949 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:10:09,952 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2024-10-11 02:10:09,955 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:10:09,985 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 3 proven. 0 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2024-10-11 02:10:09,985 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-11 02:10:09,985 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [100432194] [2024-10-11 02:10:09,985 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [100432194] provided 1 perfect and 0 imperfect interpolant sequences [2024-10-11 02:10:09,986 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-10-11 02:10:09,986 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2024-10-11 02:10:09,986 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [533421950] [2024-10-11 02:10:09,986 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-10-11 02:10:09,987 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2024-10-11 02:10:09,987 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-11 02:10:09,988 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2024-10-11 02:10:09,988 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2024-10-11 02:10:09,988 INFO L87 Difference]: Start difference. First operand 32 states and 42 transitions. Second operand has 6 states, 6 states have (on average 2.3333333333333335) internal successors, (14), 5 states have internal predecessors, (14), 2 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) [2024-10-11 02:10:10,082 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-11 02:10:10,082 INFO L93 Difference]: Finished difference Result 52 states and 70 transitions. [2024-10-11 02:10:10,083 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2024-10-11 02:10:10,083 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 2.3333333333333335) internal successors, (14), 5 states have internal predecessors, (14), 2 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) Word has length 19 [2024-10-11 02:10:10,083 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-11 02:10:10,098 INFO L225 Difference]: With dead ends: 52 [2024-10-11 02:10:10,098 INFO L226 Difference]: Without dead ends: 45 [2024-10-11 02:10:10,099 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 10 GetRequests, 5 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=13, Invalid=29, Unknown=0, NotChecked=0, Total=42 [2024-10-11 02:10:10,100 INFO L432 NwaCegarLoop]: 31 mSDtfsCounter, 45 mSDsluCounter, 99 mSDsCounter, 0 mSdLazyCounter, 43 mSolverCounterSat, 8 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 49 SdHoareTripleChecker+Valid, 130 SdHoareTripleChecker+Invalid, 51 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 8 IncrementalHoareTripleChecker+Valid, 43 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-10-11 02:10:10,100 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [49 Valid, 130 Invalid, 51 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [8 Valid, 43 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-10-11 02:10:10,101 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 45 states. [2024-10-11 02:10:10,108 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 45 to 33. [2024-10-11 02:10:10,109 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 33 states, 23 states have (on average 1.3043478260869565) internal successors, (30), 24 states have internal predecessors, (30), 7 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2024-10-11 02:10:10,110 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 33 states to 33 states and 43 transitions. [2024-10-11 02:10:10,110 INFO L78 Accepts]: Start accepts. Automaton has 33 states and 43 transitions. Word has length 19 [2024-10-11 02:10:10,110 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-11 02:10:10,110 INFO L471 AbstractCegarLoop]: Abstraction has 33 states and 43 transitions. [2024-10-11 02:10:10,111 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 2.3333333333333335) internal successors, (14), 5 states have internal predecessors, (14), 2 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) [2024-10-11 02:10:10,111 INFO L276 IsEmpty]: Start isEmpty. Operand 33 states and 43 transitions. [2024-10-11 02:10:10,112 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 25 [2024-10-11 02:10:10,112 INFO L207 NwaCegarLoop]: Found error trace [2024-10-11 02:10:10,113 INFO L215 NwaCegarLoop]: trace histogram [2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-11 02:10:10,113 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2 [2024-10-11 02:10:10,113 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-11 02:10:10,113 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-11 02:10:10,113 INFO L85 PathProgramCache]: Analyzing trace with hash -1735129581, now seen corresponding path program 1 times [2024-10-11 02:10:10,114 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-11 02:10:10,114 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1131388533] [2024-10-11 02:10:10,114 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-11 02:10:10,114 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-11 02:10:10,135 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:10:10,229 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 1 [2024-10-11 02:10:10,232 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:10:10,235 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2024-10-11 02:10:10,237 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:10:10,240 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-10-11 02:10:10,241 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-11 02:10:10,241 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1131388533] [2024-10-11 02:10:10,241 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1131388533] provided 1 perfect and 0 imperfect interpolant sequences [2024-10-11 02:10:10,241 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-10-11 02:10:10,242 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2024-10-11 02:10:10,242 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1449099361] [2024-10-11 02:10:10,242 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-10-11 02:10:10,242 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2024-10-11 02:10:10,242 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-11 02:10:10,243 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2024-10-11 02:10:10,243 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2024-10-11 02:10:10,244 INFO L87 Difference]: Start difference. First operand 33 states and 43 transitions. Second operand has 6 states, 6 states have (on average 2.6666666666666665) internal successors, (16), 6 states have internal predecessors, (16), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2024-10-11 02:10:10,292 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-11 02:10:10,292 INFO L93 Difference]: Finished difference Result 57 states and 77 transitions. [2024-10-11 02:10:10,295 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2024-10-11 02:10:10,295 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 2.6666666666666665) internal successors, (16), 6 states have internal predecessors, (16), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) Word has length 24 [2024-10-11 02:10:10,296 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-11 02:10:10,296 INFO L225 Difference]: With dead ends: 57 [2024-10-11 02:10:10,296 INFO L226 Difference]: Without dead ends: 35 [2024-10-11 02:10:10,297 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 9 GetRequests, 5 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2024-10-11 02:10:10,300 INFO L432 NwaCegarLoop]: 35 mSDtfsCounter, 8 mSDsluCounter, 91 mSDsCounter, 0 mSdLazyCounter, 28 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 8 SdHoareTripleChecker+Valid, 126 SdHoareTripleChecker+Invalid, 30 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 28 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-10-11 02:10:10,301 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [8 Valid, 126 Invalid, 30 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 28 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-10-11 02:10:10,301 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 35 states. [2024-10-11 02:10:10,307 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 35 to 35. [2024-10-11 02:10:10,307 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 35 states, 25 states have (on average 1.28) internal successors, (32), 26 states have internal predecessors, (32), 7 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2024-10-11 02:10:10,308 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 35 states to 35 states and 45 transitions. [2024-10-11 02:10:10,308 INFO L78 Accepts]: Start accepts. Automaton has 35 states and 45 transitions. Word has length 24 [2024-10-11 02:10:10,308 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-11 02:10:10,309 INFO L471 AbstractCegarLoop]: Abstraction has 35 states and 45 transitions. [2024-10-11 02:10:10,309 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 2.6666666666666665) internal successors, (16), 6 states have internal predecessors, (16), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2024-10-11 02:10:10,310 INFO L276 IsEmpty]: Start isEmpty. Operand 35 states and 45 transitions. [2024-10-11 02:10:10,310 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 25 [2024-10-11 02:10:10,311 INFO L207 NwaCegarLoop]: Found error trace [2024-10-11 02:10:10,311 INFO L215 NwaCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-11 02:10:10,312 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3 [2024-10-11 02:10:10,312 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-11 02:10:10,312 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-11 02:10:10,312 INFO L85 PathProgramCache]: Analyzing trace with hash 150917056, now seen corresponding path program 1 times [2024-10-11 02:10:10,312 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-11 02:10:10,313 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [620177029] [2024-10-11 02:10:10,313 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-11 02:10:10,313 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-11 02:10:10,328 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-10-11 02:10:10,331 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [788446973] [2024-10-11 02:10:10,334 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-11 02:10:10,334 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-11 02:10:10,334 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 [2024-10-11 02:10:10,337 INFO L229 MonitoredProcess]: Starting monitored process 2 with /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-10-11 02:10:10,339 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2024-10-11 02:10:10,404 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:10:10,406 INFO L255 TraceCheckSpWp]: Trace formula consists of 91 conjuncts, 9 conjuncts are in the unsatisfiable core [2024-10-11 02:10:10,414 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-11 02:10:10,573 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-10-11 02:10:10,573 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-10-11 02:10:10,573 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-11 02:10:10,573 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [620177029] [2024-10-11 02:10:10,574 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-10-11 02:10:10,574 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [788446973] [2024-10-11 02:10:10,574 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [788446973] provided 1 perfect and 0 imperfect interpolant sequences [2024-10-11 02:10:10,574 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-10-11 02:10:10,575 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-10-11 02:10:10,575 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1526887868] [2024-10-11 02:10:10,575 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-10-11 02:10:10,579 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-10-11 02:10:10,580 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-11 02:10:10,580 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-10-11 02:10:10,580 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-10-11 02:10:10,580 INFO L87 Difference]: Start difference. First operand 35 states and 45 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, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2024-10-11 02:10:10,636 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-11 02:10:10,637 INFO L93 Difference]: Finished difference Result 53 states and 70 transitions. [2024-10-11 02:10:10,637 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-10-11 02:10:10,637 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, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) Word has length 24 [2024-10-11 02:10:10,637 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-11 02:10:10,638 INFO L225 Difference]: With dead ends: 53 [2024-10-11 02:10:10,638 INFO L226 Difference]: Without dead ends: 51 [2024-10-11 02:10:10,638 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 24 GetRequests, 20 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2024-10-11 02:10:10,639 INFO L432 NwaCegarLoop]: 34 mSDtfsCounter, 9 mSDsluCounter, 97 mSDsCounter, 0 mSdLazyCounter, 28 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 13 SdHoareTripleChecker+Valid, 131 SdHoareTripleChecker+Invalid, 28 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 28 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-10-11 02:10:10,640 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [13 Valid, 131 Invalid, 28 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 28 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-10-11 02:10:10,642 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 51 states. [2024-10-11 02:10:10,651 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 51 to 50. [2024-10-11 02:10:10,651 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 50 states, 35 states have (on average 1.3142857142857143) internal successors, (46), 36 states have internal predecessors, (46), 11 states have call successors, (11), 3 states have call predecessors, (11), 3 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2024-10-11 02:10:10,652 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 50 states to 50 states and 67 transitions. [2024-10-11 02:10:10,652 INFO L78 Accepts]: Start accepts. Automaton has 50 states and 67 transitions. Word has length 24 [2024-10-11 02:10:10,652 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-11 02:10:10,652 INFO L471 AbstractCegarLoop]: Abstraction has 50 states and 67 transitions. [2024-10-11 02:10:10,653 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, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2024-10-11 02:10:10,653 INFO L276 IsEmpty]: Start isEmpty. Operand 50 states and 67 transitions. [2024-10-11 02:10:10,653 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 26 [2024-10-11 02:10:10,653 INFO L207 NwaCegarLoop]: Found error trace [2024-10-11 02:10:10,653 INFO L215 NwaCegarLoop]: trace histogram [2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-11 02:10:10,668 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Ended with exit code 0 [2024-10-11 02:10:10,854 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,2 /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-11 02:10:10,854 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-11 02:10:10,855 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-11 02:10:10,855 INFO L85 PathProgramCache]: Analyzing trace with hash -1833090586, now seen corresponding path program 1 times [2024-10-11 02:10:10,855 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-11 02:10:10,855 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [812165009] [2024-10-11 02:10:10,856 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-11 02:10:10,856 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-11 02:10:10,868 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:10:10,989 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 1 [2024-10-11 02:10:10,990 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:10:11,000 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2024-10-11 02:10:11,001 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:10:11,006 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-10-11 02:10:11,010 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-11 02:10:11,011 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [812165009] [2024-10-11 02:10:11,011 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [812165009] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-11 02:10:11,011 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1173924088] [2024-10-11 02:10:11,011 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-11 02:10:11,011 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-11 02:10:11,011 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 [2024-10-11 02:10:11,015 INFO L229 MonitoredProcess]: Starting monitored process 3 with /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-10-11 02:10:11,019 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2024-10-11 02:10:11,073 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:10:11,074 INFO L255 TraceCheckSpWp]: Trace formula consists of 99 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-10-11 02:10:11,076 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-11 02:10:11,135 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-10-11 02:10:11,136 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-11 02:10:11,232 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-10-11 02:10:11,233 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1173924088] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-11 02:10:11,233 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-10-11 02:10:11,233 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 5, 6] total 12 [2024-10-11 02:10:11,233 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [751212594] [2024-10-11 02:10:11,233 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-10-11 02:10:11,234 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2024-10-11 02:10:11,234 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-11 02:10:11,234 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2024-10-11 02:10:11,235 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=50, Invalid=82, Unknown=0, NotChecked=0, Total=132 [2024-10-11 02:10:11,235 INFO L87 Difference]: Start difference. First operand 50 states and 67 transitions. Second operand has 12 states, 12 states have (on average 2.9166666666666665) internal successors, (35), 12 states have internal predecessors, (35), 4 states have call successors, (7), 3 states have call predecessors, (7), 2 states have return successors, (6), 3 states have call predecessors, (6), 3 states have call successors, (6) [2024-10-11 02:10:11,431 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-11 02:10:11,432 INFO L93 Difference]: Finished difference Result 146 states and 192 transitions. [2024-10-11 02:10:11,433 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2024-10-11 02:10:11,434 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 12 states have (on average 2.9166666666666665) internal successors, (35), 12 states have internal predecessors, (35), 4 states have call successors, (7), 3 states have call predecessors, (7), 2 states have return successors, (6), 3 states have call predecessors, (6), 3 states have call successors, (6) Word has length 25 [2024-10-11 02:10:11,434 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-11 02:10:11,438 INFO L225 Difference]: With dead ends: 146 [2024-10-11 02:10:11,438 INFO L226 Difference]: Without dead ends: 139 [2024-10-11 02:10:11,439 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 60 GetRequests, 48 SyntacticMatches, 0 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 23 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=64, Invalid=118, Unknown=0, NotChecked=0, Total=182 [2024-10-11 02:10:11,439 INFO L432 NwaCegarLoop]: 35 mSDtfsCounter, 88 mSDsluCounter, 185 mSDsCounter, 0 mSdLazyCounter, 93 mSolverCounterSat, 16 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 88 SdHoareTripleChecker+Valid, 220 SdHoareTripleChecker+Invalid, 109 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 16 IncrementalHoareTripleChecker+Valid, 93 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-10-11 02:10:11,440 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [88 Valid, 220 Invalid, 109 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [16 Valid, 93 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-10-11 02:10:11,441 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 139 states. [2024-10-11 02:10:11,474 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 139 to 96. [2024-10-11 02:10:11,474 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 96 states, 68 states have (on average 1.338235294117647) internal successors, (91), 70 states have internal predecessors, (91), 20 states have call successors, (20), 7 states have call predecessors, (20), 7 states have return successors, (18), 18 states have call predecessors, (18), 18 states have call successors, (18) [2024-10-11 02:10:11,475 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 96 states to 96 states and 129 transitions. [2024-10-11 02:10:11,476 INFO L78 Accepts]: Start accepts. Automaton has 96 states and 129 transitions. Word has length 25 [2024-10-11 02:10:11,476 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-11 02:10:11,476 INFO L471 AbstractCegarLoop]: Abstraction has 96 states and 129 transitions. [2024-10-11 02:10:11,476 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 12 states have (on average 2.9166666666666665) internal successors, (35), 12 states have internal predecessors, (35), 4 states have call successors, (7), 3 states have call predecessors, (7), 2 states have return successors, (6), 3 states have call predecessors, (6), 3 states have call successors, (6) [2024-10-11 02:10:11,477 INFO L276 IsEmpty]: Start isEmpty. Operand 96 states and 129 transitions. [2024-10-11 02:10:11,477 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 27 [2024-10-11 02:10:11,477 INFO L207 NwaCegarLoop]: Found error trace [2024-10-11 02:10:11,477 INFO L215 NwaCegarLoop]: trace histogram [2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-11 02:10:11,494 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Ended with exit code 0 [2024-10-11 02:10:11,679 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,3 /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-11 02:10:11,680 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-11 02:10:11,680 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-11 02:10:11,680 INFO L85 PathProgramCache]: Analyzing trace with hash -1010868448, now seen corresponding path program 1 times [2024-10-11 02:10:11,681 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-11 02:10:11,681 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [513159999] [2024-10-11 02:10:11,681 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-11 02:10:11,681 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-11 02:10:11,692 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:10:11,776 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 1 [2024-10-11 02:10:11,777 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:10:11,814 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2024-10-11 02:10:11,816 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:10:11,819 INFO L134 CoverageAnalysis]: Checked inductivity of 7 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2024-10-11 02:10:11,819 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-11 02:10:11,819 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [513159999] [2024-10-11 02:10:11,819 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [513159999] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-11 02:10:11,820 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [456290140] [2024-10-11 02:10:11,820 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-11 02:10:11,820 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-11 02:10:11,820 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 [2024-10-11 02:10:11,822 INFO L229 MonitoredProcess]: Starting monitored process 4 with /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-10-11 02:10:11,824 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2024-10-11 02:10:11,875 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:10:11,877 INFO L255 TraceCheckSpWp]: Trace formula consists of 101 conjuncts, 9 conjuncts are in the unsatisfiable core [2024-10-11 02:10:11,878 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-11 02:10:11,923 INFO L134 CoverageAnalysis]: Checked inductivity of 7 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2024-10-11 02:10:11,923 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-11 02:10:12,010 INFO L134 CoverageAnalysis]: Checked inductivity of 7 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2024-10-11 02:10:12,010 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [456290140] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-11 02:10:12,011 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-10-11 02:10:12,011 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8, 8] total 9 [2024-10-11 02:10:12,011 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [91535741] [2024-10-11 02:10:12,011 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-10-11 02:10:12,012 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2024-10-11 02:10:12,012 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-11 02:10:12,013 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2024-10-11 02:10:12,013 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=17, Invalid=55, Unknown=0, NotChecked=0, Total=72 [2024-10-11 02:10:12,013 INFO L87 Difference]: Start difference. First operand 96 states and 129 transitions. Second operand has 9 states, 9 states have (on average 2.5555555555555554) internal successors, (23), 8 states have internal predecessors, (23), 3 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) [2024-10-11 02:10:12,255 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-11 02:10:12,255 INFO L93 Difference]: Finished difference Result 182 states and 260 transitions. [2024-10-11 02:10:12,256 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2024-10-11 02:10:12,256 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 9 states have (on average 2.5555555555555554) internal successors, (23), 8 states have internal predecessors, (23), 3 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) Word has length 26 [2024-10-11 02:10:12,256 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-11 02:10:12,259 INFO L225 Difference]: With dead ends: 182 [2024-10-11 02:10:12,260 INFO L226 Difference]: Without dead ends: 170 [2024-10-11 02:10:12,260 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 67 GetRequests, 50 SyntacticMatches, 4 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 10 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=55, Invalid=155, Unknown=0, NotChecked=0, Total=210 [2024-10-11 02:10:12,264 INFO L432 NwaCegarLoop]: 47 mSDtfsCounter, 112 mSDsluCounter, 228 mSDsCounter, 0 mSdLazyCounter, 103 mSolverCounterSat, 41 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 116 SdHoareTripleChecker+Valid, 275 SdHoareTripleChecker+Invalid, 144 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 41 IncrementalHoareTripleChecker+Valid, 103 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-10-11 02:10:12,265 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [116 Valid, 275 Invalid, 144 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [41 Valid, 103 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-10-11 02:10:12,266 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 170 states. [2024-10-11 02:10:12,297 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 170 to 127. [2024-10-11 02:10:12,301 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 127 states, 96 states have (on average 1.3541666666666667) internal successors, (130), 97 states have internal predecessors, (130), 23 states have call successors, (23), 7 states have call predecessors, (23), 7 states have return successors, (22), 22 states have call predecessors, (22), 22 states have call successors, (22) [2024-10-11 02:10:12,302 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 127 states to 127 states and 175 transitions. [2024-10-11 02:10:12,303 INFO L78 Accepts]: Start accepts. Automaton has 127 states and 175 transitions. Word has length 26 [2024-10-11 02:10:12,303 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-11 02:10:12,306 INFO L471 AbstractCegarLoop]: Abstraction has 127 states and 175 transitions. [2024-10-11 02:10:12,306 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 9 states have (on average 2.5555555555555554) internal successors, (23), 8 states have internal predecessors, (23), 3 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) [2024-10-11 02:10:12,307 INFO L276 IsEmpty]: Start isEmpty. Operand 127 states and 175 transitions. [2024-10-11 02:10:12,308 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 30 [2024-10-11 02:10:12,308 INFO L207 NwaCegarLoop]: Found error trace [2024-10-11 02:10:12,308 INFO L215 NwaCegarLoop]: trace histogram [2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-11 02:10:12,326 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Ended with exit code 0 [2024-10-11 02:10:12,508 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,4 /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-11 02:10:12,509 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-11 02:10:12,509 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-11 02:10:12,509 INFO L85 PathProgramCache]: Analyzing trace with hash 2130442992, now seen corresponding path program 1 times [2024-10-11 02:10:12,510 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-11 02:10:12,510 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [136446376] [2024-10-11 02:10:12,510 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-11 02:10:12,510 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-11 02:10:12,524 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-10-11 02:10:12,525 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [800438933] [2024-10-11 02:10:12,525 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-11 02:10:12,525 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-11 02:10:12,526 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 [2024-10-11 02:10:12,527 INFO L229 MonitoredProcess]: Starting monitored process 5 with /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-10-11 02:10:12,529 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2024-10-11 02:10:12,574 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:10:12,575 INFO L255 TraceCheckSpWp]: Trace formula consists of 100 conjuncts, 9 conjuncts are in the unsatisfiable core [2024-10-11 02:10:12,577 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-11 02:10:12,666 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-10-11 02:10:12,666 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-10-11 02:10:12,667 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-11 02:10:12,667 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [136446376] [2024-10-11 02:10:12,667 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-10-11 02:10:12,667 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [800438933] [2024-10-11 02:10:12,667 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [800438933] provided 1 perfect and 0 imperfect interpolant sequences [2024-10-11 02:10:12,667 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-10-11 02:10:12,668 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-10-11 02:10:12,668 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2022471022] [2024-10-11 02:10:12,668 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-10-11 02:10:12,669 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-10-11 02:10:12,670 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-11 02:10:12,670 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-10-11 02:10:12,670 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-10-11 02:10:12,671 INFO L87 Difference]: Start difference. First operand 127 states and 175 transitions. Second operand has 5 states, 5 states have (on average 3.8) internal successors, (19), 4 states have internal predecessors, (19), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2024-10-11 02:10:12,745 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-11 02:10:12,746 INFO L93 Difference]: Finished difference Result 142 states and 189 transitions. [2024-10-11 02:10:12,746 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-10-11 02:10:12,746 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.8) internal successors, (19), 4 states have internal predecessors, (19), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) Word has length 29 [2024-10-11 02:10:12,747 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-11 02:10:12,748 INFO L225 Difference]: With dead ends: 142 [2024-10-11 02:10:12,748 INFO L226 Difference]: Without dead ends: 140 [2024-10-11 02:10:12,748 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 29 GetRequests, 25 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2024-10-11 02:10:12,750 INFO L432 NwaCegarLoop]: 35 mSDtfsCounter, 9 mSDsluCounter, 94 mSDsCounter, 0 mSdLazyCounter, 38 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 12 SdHoareTripleChecker+Valid, 129 SdHoareTripleChecker+Invalid, 38 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 38 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-10-11 02:10:12,750 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [12 Valid, 129 Invalid, 38 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 38 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-10-11 02:10:12,753 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 140 states. [2024-10-11 02:10:12,798 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 140 to 139. [2024-10-11 02:10:12,800 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 139 states, 105 states have (on average 1.3238095238095238) internal successors, (139), 106 states have internal predecessors, (139), 23 states have call successors, (23), 10 states have call predecessors, (23), 10 states have return successors, (22), 22 states have call predecessors, (22), 22 states have call successors, (22) [2024-10-11 02:10:12,802 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 139 states to 139 states and 184 transitions. [2024-10-11 02:10:12,806 INFO L78 Accepts]: Start accepts. Automaton has 139 states and 184 transitions. Word has length 29 [2024-10-11 02:10:12,806 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-11 02:10:12,806 INFO L471 AbstractCegarLoop]: Abstraction has 139 states and 184 transitions. [2024-10-11 02:10:12,807 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.8) internal successors, (19), 4 states have internal predecessors, (19), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2024-10-11 02:10:12,807 INFO L276 IsEmpty]: Start isEmpty. Operand 139 states and 184 transitions. [2024-10-11 02:10:12,808 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 32 [2024-10-11 02:10:12,808 INFO L207 NwaCegarLoop]: Found error trace [2024-10-11 02:10:12,808 INFO L215 NwaCegarLoop]: trace histogram [2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-11 02:10:12,832 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Ended with exit code 0 [2024-10-11 02:10:13,009 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 5 /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable7 [2024-10-11 02:10:13,009 INFO L396 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-11 02:10:13,009 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-11 02:10:13,010 INFO L85 PathProgramCache]: Analyzing trace with hash 2110713919, now seen corresponding path program 1 times [2024-10-11 02:10:13,010 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-11 02:10:13,010 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [164828343] [2024-10-11 02:10:13,010 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-11 02:10:13,010 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-11 02:10:13,028 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-10-11 02:10:13,029 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [179066211] [2024-10-11 02:10:13,030 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-11 02:10:13,030 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-11 02:10:13,030 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 [2024-10-11 02:10:13,032 INFO L229 MonitoredProcess]: Starting monitored process 6 with /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-10-11 02:10:13,034 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2024-10-11 02:10:13,091 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:10:13,093 INFO L255 TraceCheckSpWp]: Trace formula consists of 119 conjuncts, 15 conjuncts are in the unsatisfiable core [2024-10-11 02:10:13,095 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-11 02:10:13,256 INFO L134 CoverageAnalysis]: Checked inductivity of 10 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-10-11 02:10:13,257 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-11 02:10:13,428 INFO L134 CoverageAnalysis]: Checked inductivity of 10 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-10-11 02:10:13,429 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-11 02:10:13,429 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [164828343] [2024-10-11 02:10:13,429 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-10-11 02:10:13,429 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [179066211] [2024-10-11 02:10:13,429 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [179066211] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-11 02:10:13,429 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-10-11 02:10:13,429 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 8 [2024-10-11 02:10:13,429 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [186175644] [2024-10-11 02:10:13,430 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-10-11 02:10:13,430 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2024-10-11 02:10:13,430 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-11 02:10:13,431 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2024-10-11 02:10:13,431 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=15, Invalid=41, Unknown=0, NotChecked=0, Total=56 [2024-10-11 02:10:13,431 INFO L87 Difference]: Start difference. First operand 139 states and 184 transitions. Second operand has 8 states, 8 states have (on average 4.875) internal successors, (39), 7 states have internal predecessors, (39), 3 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2024-10-11 02:10:13,636 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-11 02:10:13,636 INFO L93 Difference]: Finished difference Result 174 states and 236 transitions. [2024-10-11 02:10:13,636 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2024-10-11 02:10:13,637 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 8 states have (on average 4.875) internal successors, (39), 7 states have internal predecessors, (39), 3 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) Word has length 31 [2024-10-11 02:10:13,637 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-11 02:10:13,638 INFO L225 Difference]: With dead ends: 174 [2024-10-11 02:10:13,638 INFO L226 Difference]: Without dead ends: 172 [2024-10-11 02:10:13,639 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 61 GetRequests, 52 SyntacticMatches, 2 SemanticMatches, 7 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=19, Invalid=53, Unknown=0, NotChecked=0, Total=72 [2024-10-11 02:10:13,639 INFO L432 NwaCegarLoop]: 56 mSDtfsCounter, 19 mSDsluCounter, 238 mSDsCounter, 0 mSdLazyCounter, 91 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 27 SdHoareTripleChecker+Valid, 294 SdHoareTripleChecker+Invalid, 92 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 91 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-10-11 02:10:13,639 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [27 Valid, 294 Invalid, 92 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 91 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-10-11 02:10:13,640 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 172 states. [2024-10-11 02:10:13,666 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 172 to 169. [2024-10-11 02:10:13,668 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 169 states, 126 states have (on average 1.3492063492063493) internal successors, (170), 127 states have internal predecessors, (170), 31 states have call successors, (31), 11 states have call predecessors, (31), 11 states have return successors, (30), 30 states have call predecessors, (30), 30 states have call successors, (30) [2024-10-11 02:10:13,671 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 169 states to 169 states and 231 transitions. [2024-10-11 02:10:13,671 INFO L78 Accepts]: Start accepts. Automaton has 169 states and 231 transitions. Word has length 31 [2024-10-11 02:10:13,673 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-11 02:10:13,673 INFO L471 AbstractCegarLoop]: Abstraction has 169 states and 231 transitions. [2024-10-11 02:10:13,674 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 8 states have (on average 4.875) internal successors, (39), 7 states have internal predecessors, (39), 3 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2024-10-11 02:10:13,674 INFO L276 IsEmpty]: Start isEmpty. Operand 169 states and 231 transitions. [2024-10-11 02:10:13,675 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 32 [2024-10-11 02:10:13,679 INFO L207 NwaCegarLoop]: Found error trace [2024-10-11 02:10:13,679 INFO L215 NwaCegarLoop]: trace histogram [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] [2024-10-11 02:10:13,698 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Ended with exit code 0 [2024-10-11 02:10:13,880 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,6 /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-11 02:10:13,880 INFO L396 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-11 02:10:13,881 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-11 02:10:13,881 INFO L85 PathProgramCache]: Analyzing trace with hash -363027956, now seen corresponding path program 1 times [2024-10-11 02:10:13,881 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-11 02:10:13,881 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1688861180] [2024-10-11 02:10:13,881 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-11 02:10:13,881 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-11 02:10:13,890 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:10:13,966 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 1 [2024-10-11 02:10:13,967 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:10:13,973 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2024-10-11 02:10:13,977 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:10:13,982 INFO L134 CoverageAnalysis]: Checked inductivity of 9 backedges. 5 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-10-11 02:10:13,982 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-11 02:10:13,982 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1688861180] [2024-10-11 02:10:13,982 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1688861180] provided 1 perfect and 0 imperfect interpolant sequences [2024-10-11 02:10:13,982 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-10-11 02:10:13,983 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [7] imperfect sequences [] total 7 [2024-10-11 02:10:13,983 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [183675381] [2024-10-11 02:10:13,983 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-10-11 02:10:13,983 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2024-10-11 02:10:13,983 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-11 02:10:13,984 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2024-10-11 02:10:13,984 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=16, Invalid=26, Unknown=0, NotChecked=0, Total=42 [2024-10-11 02:10:13,984 INFO L87 Difference]: Start difference. First operand 169 states and 231 transitions. Second operand has 7 states, 7 states have (on average 3.2857142857142856) internal successors, (23), 7 states have internal predecessors, (23), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2024-10-11 02:10:14,043 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-11 02:10:14,043 INFO L93 Difference]: Finished difference Result 236 states and 324 transitions. [2024-10-11 02:10:14,044 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2024-10-11 02:10:14,044 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 7 states have (on average 3.2857142857142856) internal successors, (23), 7 states have internal predecessors, (23), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) Word has length 31 [2024-10-11 02:10:14,044 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-11 02:10:14,046 INFO L225 Difference]: With dead ends: 236 [2024-10-11 02:10:14,047 INFO L226 Difference]: Without dead ends: 169 [2024-10-11 02:10:14,047 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 10 GetRequests, 5 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=16, Invalid=26, Unknown=0, NotChecked=0, Total=42 [2024-10-11 02:10:14,048 INFO L432 NwaCegarLoop]: 34 mSDtfsCounter, 10 mSDsluCounter, 117 mSDsCounter, 0 mSdLazyCounter, 34 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 10 SdHoareTripleChecker+Valid, 151 SdHoareTripleChecker+Invalid, 36 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 34 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-10-11 02:10:14,048 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [10 Valid, 151 Invalid, 36 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 34 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-10-11 02:10:14,049 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 169 states. [2024-10-11 02:10:14,066 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 169 to 169. [2024-10-11 02:10:14,067 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 169 states, 126 states have (on average 1.3412698412698412) internal successors, (169), 127 states have internal predecessors, (169), 31 states have call successors, (31), 11 states have call predecessors, (31), 11 states have return successors, (30), 30 states have call predecessors, (30), 30 states have call successors, (30) [2024-10-11 02:10:14,068 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 169 states to 169 states and 230 transitions. [2024-10-11 02:10:14,068 INFO L78 Accepts]: Start accepts. Automaton has 169 states and 230 transitions. Word has length 31 [2024-10-11 02:10:14,068 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-11 02:10:14,069 INFO L471 AbstractCegarLoop]: Abstraction has 169 states and 230 transitions. [2024-10-11 02:10:14,069 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 7 states have (on average 3.2857142857142856) internal successors, (23), 7 states have internal predecessors, (23), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2024-10-11 02:10:14,069 INFO L276 IsEmpty]: Start isEmpty. Operand 169 states and 230 transitions. [2024-10-11 02:10:14,070 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 35 [2024-10-11 02:10:14,070 INFO L207 NwaCegarLoop]: Found error trace [2024-10-11 02:10:14,070 INFO L215 NwaCegarLoop]: trace histogram [3, 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, 1] [2024-10-11 02:10:14,070 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable9 [2024-10-11 02:10:14,070 INFO L396 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-11 02:10:14,071 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-11 02:10:14,071 INFO L85 PathProgramCache]: Analyzing trace with hash -242784896, now seen corresponding path program 1 times [2024-10-11 02:10:14,071 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-11 02:10:14,071 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [112337230] [2024-10-11 02:10:14,071 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-11 02:10:14,071 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-11 02:10:14,081 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-10-11 02:10:14,082 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [398849622] [2024-10-11 02:10:14,082 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-11 02:10:14,082 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-11 02:10:14,082 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 [2024-10-11 02:10:14,084 INFO L229 MonitoredProcess]: Starting monitored process 7 with /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-10-11 02:10:14,085 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2024-10-11 02:10:14,130 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:10:14,131 INFO L255 TraceCheckSpWp]: Trace formula consists of 109 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-10-11 02:10:14,133 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-11 02:10:14,211 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 8 trivial. 0 not checked. [2024-10-11 02:10:14,211 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-10-11 02:10:14,211 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-11 02:10:14,212 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [112337230] [2024-10-11 02:10:14,212 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-10-11 02:10:14,212 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [398849622] [2024-10-11 02:10:14,212 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [398849622] provided 1 perfect and 0 imperfect interpolant sequences [2024-10-11 02:10:14,212 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-10-11 02:10:14,212 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-10-11 02:10:14,213 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1272114967] [2024-10-11 02:10:14,213 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-10-11 02:10:14,213 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-10-11 02:10:14,213 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-11 02:10:14,214 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-10-11 02:10:14,214 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-10-11 02:10:14,214 INFO L87 Difference]: Start difference. First operand 169 states and 230 transitions. Second operand has 5 states, 5 states have (on average 3.8) internal successors, (19), 4 states have internal predecessors, (19), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2024-10-11 02:10:14,296 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-11 02:10:14,296 INFO L93 Difference]: Finished difference Result 234 states and 330 transitions. [2024-10-11 02:10:14,297 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-10-11 02:10:14,297 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.8) internal successors, (19), 4 states have internal predecessors, (19), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) Word has length 34 [2024-10-11 02:10:14,297 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-11 02:10:14,299 INFO L225 Difference]: With dead ends: 234 [2024-10-11 02:10:14,299 INFO L226 Difference]: Without dead ends: 232 [2024-10-11 02:10:14,300 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 34 GetRequests, 30 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2024-10-11 02:10:14,300 INFO L432 NwaCegarLoop]: 33 mSDtfsCounter, 8 mSDsluCounter, 88 mSDsCounter, 0 mSdLazyCounter, 46 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 10 SdHoareTripleChecker+Valid, 121 SdHoareTripleChecker+Invalid, 46 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 46 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-10-11 02:10:14,301 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [10 Valid, 121 Invalid, 46 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 46 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-10-11 02:10:14,302 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 232 states. [2024-10-11 02:10:14,325 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 232 to 225. [2024-10-11 02:10:14,326 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 225 states, 159 states have (on average 1.371069182389937) internal successors, (218), 160 states have internal predecessors, (218), 51 states have call successors, (51), 14 states have call predecessors, (51), 14 states have return successors, (50), 50 states have call predecessors, (50), 50 states have call successors, (50) [2024-10-11 02:10:14,328 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 225 states to 225 states and 319 transitions. [2024-10-11 02:10:14,328 INFO L78 Accepts]: Start accepts. Automaton has 225 states and 319 transitions. Word has length 34 [2024-10-11 02:10:14,329 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-11 02:10:14,329 INFO L471 AbstractCegarLoop]: Abstraction has 225 states and 319 transitions. [2024-10-11 02:10:14,329 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.8) internal successors, (19), 4 states have internal predecessors, (19), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2024-10-11 02:10:14,329 INFO L276 IsEmpty]: Start isEmpty. Operand 225 states and 319 transitions. [2024-10-11 02:10:14,330 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 37 [2024-10-11 02:10:14,330 INFO L207 NwaCegarLoop]: Found error trace [2024-10-11 02:10:14,330 INFO L215 NwaCegarLoop]: trace histogram [2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-11 02:10:14,349 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Ended with exit code 0 [2024-10-11 02:10:14,531 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 7 /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable10 [2024-10-11 02:10:14,532 INFO L396 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-11 02:10:14,532 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-11 02:10:14,532 INFO L85 PathProgramCache]: Analyzing trace with hash -568879, now seen corresponding path program 1 times [2024-10-11 02:10:14,532 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-11 02:10:14,533 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [400373239] [2024-10-11 02:10:14,533 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-11 02:10:14,533 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-11 02:10:14,548 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-10-11 02:10:14,549 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [465048475] [2024-10-11 02:10:14,549 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-11 02:10:14,549 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-11 02:10:14,549 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 [2024-10-11 02:10:14,557 INFO L229 MonitoredProcess]: Starting monitored process 8 with /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-10-11 02:10:14,560 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2024-10-11 02:10:14,608 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:10:14,610 INFO L255 TraceCheckSpWp]: Trace formula consists of 128 conjuncts, 29 conjuncts are in the unsatisfiable core [2024-10-11 02:10:14,612 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-11 02:10:14,867 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 2 proven. 9 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2024-10-11 02:10:14,867 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-11 02:10:14,927 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-11 02:10:14,927 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [400373239] [2024-10-11 02:10:14,927 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-10-11 02:10:14,927 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [465048475] [2024-10-11 02:10:14,927 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [465048475] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-11 02:10:14,927 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-10-11 02:10:14,927 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10] total 10 [2024-10-11 02:10:14,927 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1734873253] [2024-10-11 02:10:14,928 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-10-11 02:10:14,928 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2024-10-11 02:10:14,928 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-11 02:10:14,929 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2024-10-11 02:10:14,929 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=29, Invalid=127, Unknown=0, NotChecked=0, Total=156 [2024-10-11 02:10:14,929 INFO L87 Difference]: Start difference. First operand 225 states and 319 transitions. Second operand has 10 states, 10 states have (on average 2.9) internal successors, (29), 8 states have internal predecessors, (29), 3 states have call successors, (4), 2 states have call predecessors, (4), 2 states have return successors, (3), 2 states have call predecessors, (3), 3 states have call successors, (3) [2024-10-11 02:10:15,164 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-11 02:10:15,164 INFO L93 Difference]: Finished difference Result 237 states and 329 transitions. [2024-10-11 02:10:15,164 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2024-10-11 02:10:15,165 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 10 states have (on average 2.9) internal successors, (29), 8 states have internal predecessors, (29), 3 states have call successors, (4), 2 states have call predecessors, (4), 2 states have return successors, (3), 2 states have call predecessors, (3), 3 states have call successors, (3) Word has length 36 [2024-10-11 02:10:15,165 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-11 02:10:15,166 INFO L225 Difference]: With dead ends: 237 [2024-10-11 02:10:15,167 INFO L226 Difference]: Without dead ends: 235 [2024-10-11 02:10:15,167 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 42 GetRequests, 29 SyntacticMatches, 0 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 22 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=40, Invalid=170, Unknown=0, NotChecked=0, Total=210 [2024-10-11 02:10:15,168 INFO L432 NwaCegarLoop]: 42 mSDtfsCounter, 68 mSDsluCounter, 211 mSDsCounter, 0 mSdLazyCounter, 171 mSolverCounterSat, 21 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 79 SdHoareTripleChecker+Valid, 253 SdHoareTripleChecker+Invalid, 192 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 21 IncrementalHoareTripleChecker+Valid, 171 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-10-11 02:10:15,168 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [79 Valid, 253 Invalid, 192 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [21 Valid, 171 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-10-11 02:10:15,168 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 235 states. [2024-10-11 02:10:15,204 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 235 to 233. [2024-10-11 02:10:15,205 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 233 states, 165 states have (on average 1.3575757575757577) internal successors, (224), 166 states have internal predecessors, (224), 51 states have call successors, (51), 16 states have call predecessors, (51), 16 states have return successors, (50), 50 states have call predecessors, (50), 50 states have call successors, (50) [2024-10-11 02:10:15,207 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 233 states to 233 states and 325 transitions. [2024-10-11 02:10:15,208 INFO L78 Accepts]: Start accepts. Automaton has 233 states and 325 transitions. Word has length 36 [2024-10-11 02:10:15,208 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-11 02:10:15,209 INFO L471 AbstractCegarLoop]: Abstraction has 233 states and 325 transitions. [2024-10-11 02:10:15,209 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 10 states have (on average 2.9) internal successors, (29), 8 states have internal predecessors, (29), 3 states have call successors, (4), 2 states have call predecessors, (4), 2 states have return successors, (3), 2 states have call predecessors, (3), 3 states have call successors, (3) [2024-10-11 02:10:15,209 INFO L276 IsEmpty]: Start isEmpty. Operand 233 states and 325 transitions. [2024-10-11 02:10:15,211 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 40 [2024-10-11 02:10:15,211 INFO L207 NwaCegarLoop]: Found error trace [2024-10-11 02:10:15,212 INFO L215 NwaCegarLoop]: trace histogram [4, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-11 02:10:15,230 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Ended with exit code 0 [2024-10-11 02:10:15,415 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable11,8 /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-11 02:10:15,416 INFO L396 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-11 02:10:15,416 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-11 02:10:15,416 INFO L85 PathProgramCache]: Analyzing trace with hash 895823024, now seen corresponding path program 1 times [2024-10-11 02:10:15,416 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-11 02:10:15,416 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [914495275] [2024-10-11 02:10:15,417 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-11 02:10:15,417 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-11 02:10:15,426 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-10-11 02:10:15,427 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [948642456] [2024-10-11 02:10:15,427 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-11 02:10:15,427 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-11 02:10:15,427 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 [2024-10-11 02:10:15,432 INFO L229 MonitoredProcess]: Starting monitored process 9 with /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-10-11 02:10:15,434 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2024-10-11 02:10:15,480 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:10:15,481 INFO L255 TraceCheckSpWp]: Trace formula consists of 118 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-10-11 02:10:15,482 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-11 02:10:15,526 INFO L134 CoverageAnalysis]: Checked inductivity of 22 backedges. 6 proven. 0 refuted. 0 times theorem prover too weak. 16 trivial. 0 not checked. [2024-10-11 02:10:15,527 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-10-11 02:10:15,527 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-11 02:10:15,527 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [914495275] [2024-10-11 02:10:15,527 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-10-11 02:10:15,527 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [948642456] [2024-10-11 02:10:15,527 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [948642456] provided 1 perfect and 0 imperfect interpolant sequences [2024-10-11 02:10:15,527 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-10-11 02:10:15,527 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-10-11 02:10:15,527 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [553667026] [2024-10-11 02:10:15,527 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-10-11 02:10:15,528 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-10-11 02:10:15,528 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-11 02:10:15,528 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-10-11 02:10:15,528 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-10-11 02:10:15,528 INFO L87 Difference]: Start difference. First operand 233 states and 325 transitions. Second operand has 5 states, 5 states have (on average 3.8) internal successors, (19), 4 states have internal predecessors, (19), 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) [2024-10-11 02:10:15,602 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-11 02:10:15,602 INFO L93 Difference]: Finished difference Result 308 states and 453 transitions. [2024-10-11 02:10:15,603 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-10-11 02:10:15,603 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.8) internal successors, (19), 4 states have internal predecessors, (19), 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 39 [2024-10-11 02:10:15,603 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-11 02:10:15,605 INFO L225 Difference]: With dead ends: 308 [2024-10-11 02:10:15,605 INFO L226 Difference]: Without dead ends: 306 [2024-10-11 02:10:15,606 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 39 GetRequests, 35 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2024-10-11 02:10:15,607 INFO L432 NwaCegarLoop]: 36 mSDtfsCounter, 5 mSDsluCounter, 93 mSDsCounter, 0 mSdLazyCounter, 38 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 6 SdHoareTripleChecker+Valid, 129 SdHoareTripleChecker+Invalid, 38 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 38 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-10-11 02:10:15,607 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [6 Valid, 129 Invalid, 38 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 38 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-10-11 02:10:15,607 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 306 states. [2024-10-11 02:10:15,638 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 306 to 291. [2024-10-11 02:10:15,639 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 291 states, 186 states have (on average 1.3602150537634408) internal successors, (253), 196 states have internal predecessors, (253), 87 states have call successors, (87), 17 states have call predecessors, (87), 17 states have return successors, (86), 77 states have call predecessors, (86), 86 states have call successors, (86) [2024-10-11 02:10:15,640 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 291 states to 291 states and 426 transitions. [2024-10-11 02:10:15,641 INFO L78 Accepts]: Start accepts. Automaton has 291 states and 426 transitions. Word has length 39 [2024-10-11 02:10:15,641 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-11 02:10:15,641 INFO L471 AbstractCegarLoop]: Abstraction has 291 states and 426 transitions. [2024-10-11 02:10:15,641 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.8) internal successors, (19), 4 states have internal predecessors, (19), 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) [2024-10-11 02:10:15,641 INFO L276 IsEmpty]: Start isEmpty. Operand 291 states and 426 transitions. [2024-10-11 02:10:15,642 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 38 [2024-10-11 02:10:15,642 INFO L207 NwaCegarLoop]: Found error trace [2024-10-11 02:10:15,642 INFO L215 NwaCegarLoop]: trace histogram [4, 3, 3, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-11 02:10:15,658 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Forceful destruction successful, exit code 0 [2024-10-11 02:10:15,846 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 9 /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable12 [2024-10-11 02:10:15,847 INFO L396 AbstractCegarLoop]: === Iteration 14 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-11 02:10:15,847 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-11 02:10:15,847 INFO L85 PathProgramCache]: Analyzing trace with hash 184539710, now seen corresponding path program 1 times [2024-10-11 02:10:15,847 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-11 02:10:15,848 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1202354529] [2024-10-11 02:10:15,848 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-11 02:10:15,848 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-11 02:10:15,861 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:10:15,968 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 1 [2024-10-11 02:10:15,969 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:10:15,972 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2024-10-11 02:10:15,973 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:10:15,975 INFO L134 CoverageAnalysis]: Checked inductivity of 28 backedges. 16 proven. 5 refuted. 0 times theorem prover too weak. 7 trivial. 0 not checked. [2024-10-11 02:10:15,975 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-11 02:10:15,975 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1202354529] [2024-10-11 02:10:15,975 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1202354529] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-11 02:10:15,975 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1364541296] [2024-10-11 02:10:15,975 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-11 02:10:15,975 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-11 02:10:15,975 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 [2024-10-11 02:10:15,977 INFO L229 MonitoredProcess]: Starting monitored process 10 with /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-10-11 02:10:15,978 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Waiting until timeout for monitored process [2024-10-11 02:10:16,028 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:10:16,029 INFO L255 TraceCheckSpWp]: Trace formula consists of 153 conjuncts, 9 conjuncts are in the unsatisfiable core [2024-10-11 02:10:16,030 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-11 02:10:16,069 INFO L134 CoverageAnalysis]: Checked inductivity of 28 backedges. 16 proven. 5 refuted. 0 times theorem prover too weak. 7 trivial. 0 not checked. [2024-10-11 02:10:16,071 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-11 02:10:16,160 INFO L134 CoverageAnalysis]: Checked inductivity of 28 backedges. 16 proven. 5 refuted. 0 times theorem prover too weak. 7 trivial. 0 not checked. [2024-10-11 02:10:16,160 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1364541296] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-11 02:10:16,161 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-10-11 02:10:16,161 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 6, 7] total 14 [2024-10-11 02:10:16,161 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [990241734] [2024-10-11 02:10:16,161 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-10-11 02:10:16,161 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2024-10-11 02:10:16,162 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-11 02:10:16,162 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2024-10-11 02:10:16,162 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=69, Invalid=113, Unknown=0, NotChecked=0, Total=182 [2024-10-11 02:10:16,163 INFO L87 Difference]: Start difference. First operand 291 states and 426 transitions. Second operand has 14 states, 14 states have (on average 3.4285714285714284) internal successors, (48), 14 states have internal predecessors, (48), 4 states have call successors, (7), 3 states have call predecessors, (7), 2 states have return successors, (6), 3 states have call predecessors, (6), 3 states have call successors, (6) [2024-10-11 02:10:16,467 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-11 02:10:16,467 INFO L93 Difference]: Finished difference Result 724 states and 1030 transitions. [2024-10-11 02:10:16,467 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 17 states. [2024-10-11 02:10:16,468 INFO L78 Accepts]: Start accepts. Automaton has has 14 states, 14 states have (on average 3.4285714285714284) internal successors, (48), 14 states have internal predecessors, (48), 4 states have call successors, (7), 3 states have call predecessors, (7), 2 states have return successors, (6), 3 states have call predecessors, (6), 3 states have call successors, (6) Word has length 37 [2024-10-11 02:10:16,468 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-11 02:10:16,474 INFO L225 Difference]: With dead ends: 724 [2024-10-11 02:10:16,474 INFO L226 Difference]: Without dead ends: 574 [2024-10-11 02:10:16,476 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 88 GetRequests, 71 SyntacticMatches, 0 SemanticMatches, 17 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 43 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=112, Invalid=230, Unknown=0, NotChecked=0, Total=342 [2024-10-11 02:10:16,478 INFO L432 NwaCegarLoop]: 42 mSDtfsCounter, 141 mSDsluCounter, 188 mSDsCounter, 0 mSdLazyCounter, 115 mSolverCounterSat, 37 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 141 SdHoareTripleChecker+Valid, 230 SdHoareTripleChecker+Invalid, 152 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 37 IncrementalHoareTripleChecker+Valid, 115 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-10-11 02:10:16,478 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [141 Valid, 230 Invalid, 152 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [37 Valid, 115 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-10-11 02:10:16,479 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 574 states. [2024-10-11 02:10:16,540 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 574 to 540. [2024-10-11 02:10:16,541 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 540 states, 356 states have (on average 1.300561797752809) internal successors, (463), 370 states have internal predecessors, (463), 142 states have call successors, (142), 41 states have call predecessors, (142), 41 states have return successors, (138), 128 states have call predecessors, (138), 138 states have call successors, (138) [2024-10-11 02:10:16,545 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 540 states to 540 states and 743 transitions. [2024-10-11 02:10:16,546 INFO L78 Accepts]: Start accepts. Automaton has 540 states and 743 transitions. Word has length 37 [2024-10-11 02:10:16,546 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-11 02:10:16,546 INFO L471 AbstractCegarLoop]: Abstraction has 540 states and 743 transitions. [2024-10-11 02:10:16,546 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 14 states, 14 states have (on average 3.4285714285714284) internal successors, (48), 14 states have internal predecessors, (48), 4 states have call successors, (7), 3 states have call predecessors, (7), 2 states have return successors, (6), 3 states have call predecessors, (6), 3 states have call successors, (6) [2024-10-11 02:10:16,546 INFO L276 IsEmpty]: Start isEmpty. Operand 540 states and 743 transitions. [2024-10-11 02:10:16,547 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 39 [2024-10-11 02:10:16,547 INFO L207 NwaCegarLoop]: Found error trace [2024-10-11 02:10:16,547 INFO L215 NwaCegarLoop]: trace histogram [3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-11 02:10:16,564 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Ended with exit code 0 [2024-10-11 02:10:16,747 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable13,10 /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-11 02:10:16,748 INFO L396 AbstractCegarLoop]: === Iteration 15 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-11 02:10:16,748 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-11 02:10:16,748 INFO L85 PathProgramCache]: Analyzing trace with hash -1387261216, now seen corresponding path program 2 times [2024-10-11 02:10:16,748 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-11 02:10:16,748 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [520935059] [2024-10-11 02:10:16,748 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-11 02:10:16,749 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-11 02:10:16,757 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:10:16,802 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 1 [2024-10-11 02:10:16,803 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:10:16,805 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2024-10-11 02:10:16,806 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:10:16,807 INFO L134 CoverageAnalysis]: Checked inductivity of 23 backedges. 19 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-10-11 02:10:16,808 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-11 02:10:16,808 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [520935059] [2024-10-11 02:10:16,808 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [520935059] provided 1 perfect and 0 imperfect interpolant sequences [2024-10-11 02:10:16,808 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-10-11 02:10:16,808 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-10-11 02:10:16,808 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1663688716] [2024-10-11 02:10:16,808 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-10-11 02:10:16,809 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-10-11 02:10:16,809 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-11 02:10:16,809 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-10-11 02:10:16,809 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-10-11 02:10:16,810 INFO L87 Difference]: Start difference. First operand 540 states and 743 transitions. Second operand has 5 states, 5 states have (on average 6.0) internal successors, (30), 5 states have internal predecessors, (30), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2024-10-11 02:10:16,970 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-11 02:10:16,970 INFO L93 Difference]: Finished difference Result 788 states and 1135 transitions. [2024-10-11 02:10:16,971 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2024-10-11 02:10:16,971 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 6.0) internal successors, (30), 5 states have internal predecessors, (30), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) Word has length 38 [2024-10-11 02:10:16,971 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-11 02:10:16,976 INFO L225 Difference]: With dead ends: 788 [2024-10-11 02:10:16,977 INFO L226 Difference]: Without dead ends: 643 [2024-10-11 02:10:16,977 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 12 GetRequests, 7 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=15, Invalid=27, Unknown=0, NotChecked=0, Total=42 [2024-10-11 02:10:16,978 INFO L432 NwaCegarLoop]: 51 mSDtfsCounter, 29 mSDsluCounter, 118 mSDsCounter, 0 mSdLazyCounter, 58 mSolverCounterSat, 8 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 33 SdHoareTripleChecker+Valid, 169 SdHoareTripleChecker+Invalid, 66 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 8 IncrementalHoareTripleChecker+Valid, 58 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-10-11 02:10:16,978 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [33 Valid, 169 Invalid, 66 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [8 Valid, 58 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-10-11 02:10:16,979 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 643 states. [2024-10-11 02:10:17,038 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 643 to 538. [2024-10-11 02:10:17,039 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 538 states, 358 states have (on average 1.3072625698324023) internal successors, (468), 372 states have internal predecessors, (468), 138 states have call successors, (138), 41 states have call predecessors, (138), 41 states have return successors, (134), 124 states have call predecessors, (134), 134 states have call successors, (134) [2024-10-11 02:10:17,041 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 538 states to 538 states and 740 transitions. [2024-10-11 02:10:17,042 INFO L78 Accepts]: Start accepts. Automaton has 538 states and 740 transitions. Word has length 38 [2024-10-11 02:10:17,044 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-11 02:10:17,044 INFO L471 AbstractCegarLoop]: Abstraction has 538 states and 740 transitions. [2024-10-11 02:10:17,044 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 6.0) internal successors, (30), 5 states have internal predecessors, (30), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2024-10-11 02:10:17,044 INFO L276 IsEmpty]: Start isEmpty. Operand 538 states and 740 transitions. [2024-10-11 02:10:17,044 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 39 [2024-10-11 02:10:17,044 INFO L207 NwaCegarLoop]: Found error trace [2024-10-11 02:10:17,045 INFO L215 NwaCegarLoop]: trace histogram [3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-11 02:10:17,045 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable14 [2024-10-11 02:10:17,045 INFO L396 AbstractCegarLoop]: === Iteration 16 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-11 02:10:17,045 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-11 02:10:17,045 INFO L85 PathProgramCache]: Analyzing trace with hash 869918208, now seen corresponding path program 1 times [2024-10-11 02:10:17,045 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-11 02:10:17,045 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1243952557] [2024-10-11 02:10:17,046 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-11 02:10:17,046 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-11 02:10:17,066 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:10:17,177 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 1 [2024-10-11 02:10:17,179 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:10:17,181 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2024-10-11 02:10:17,182 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:10:17,184 INFO L134 CoverageAnalysis]: Checked inductivity of 21 backedges. 11 proven. 6 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-10-11 02:10:17,184 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-11 02:10:17,184 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1243952557] [2024-10-11 02:10:17,184 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1243952557] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-11 02:10:17,185 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1814012537] [2024-10-11 02:10:17,185 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-11 02:10:17,185 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-11 02:10:17,185 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 [2024-10-11 02:10:17,187 INFO L229 MonitoredProcess]: Starting monitored process 11 with /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-10-11 02:10:17,188 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Waiting until timeout for monitored process [2024-10-11 02:10:17,235 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:10:17,237 INFO L255 TraceCheckSpWp]: Trace formula consists of 146 conjuncts, 11 conjuncts are in the unsatisfiable core [2024-10-11 02:10:17,238 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-11 02:10:17,283 INFO L134 CoverageAnalysis]: Checked inductivity of 21 backedges. 11 proven. 6 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-10-11 02:10:17,283 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-11 02:10:17,383 INFO L134 CoverageAnalysis]: Checked inductivity of 21 backedges. 11 proven. 6 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-10-11 02:10:17,384 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1814012537] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-11 02:10:17,384 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-10-11 02:10:17,384 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 7, 8] total 16 [2024-10-11 02:10:17,384 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [274414586] [2024-10-11 02:10:17,384 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-10-11 02:10:17,385 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2024-10-11 02:10:17,385 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-11 02:10:17,386 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2024-10-11 02:10:17,386 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=94, Invalid=146, Unknown=0, NotChecked=0, Total=240 [2024-10-11 02:10:17,386 INFO L87 Difference]: Start difference. First operand 538 states and 740 transitions. Second operand has 16 states, 16 states have (on average 3.375) internal successors, (54), 16 states have internal predecessors, (54), 4 states have call successors, (7), 3 states have call predecessors, (7), 2 states have return successors, (6), 3 states have call predecessors, (6), 3 states have call successors, (6) [2024-10-11 02:10:17,795 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-11 02:10:17,795 INFO L93 Difference]: Finished difference Result 1162 states and 1624 transitions. [2024-10-11 02:10:17,796 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 21 states. [2024-10-11 02:10:17,796 INFO L78 Accepts]: Start accepts. Automaton has has 16 states, 16 states have (on average 3.375) internal successors, (54), 16 states have internal predecessors, (54), 4 states have call successors, (7), 3 states have call predecessors, (7), 2 states have return successors, (6), 3 states have call predecessors, (6), 3 states have call successors, (6) Word has length 38 [2024-10-11 02:10:17,797 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-11 02:10:17,802 INFO L225 Difference]: With dead ends: 1162 [2024-10-11 02:10:17,802 INFO L226 Difference]: Without dead ends: 839 [2024-10-11 02:10:17,803 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 93 GetRequests, 72 SyntacticMatches, 0 SemanticMatches, 21 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 68 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=167, Invalid=339, Unknown=0, NotChecked=0, Total=506 [2024-10-11 02:10:17,803 INFO L432 NwaCegarLoop]: 36 mSDtfsCounter, 186 mSDsluCounter, 257 mSDsCounter, 0 mSdLazyCounter, 147 mSolverCounterSat, 41 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 186 SdHoareTripleChecker+Valid, 293 SdHoareTripleChecker+Invalid, 188 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 41 IncrementalHoareTripleChecker+Valid, 147 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-10-11 02:10:17,804 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [186 Valid, 293 Invalid, 188 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [41 Valid, 147 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-10-11 02:10:17,805 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 839 states. [2024-10-11 02:10:17,901 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 839 to 802. [2024-10-11 02:10:17,903 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 802 states, 532 states have (on average 1.25) internal successors, (665), 554 states have internal predecessors, (665), 212 states have call successors, (212), 57 states have call predecessors, (212), 57 states have return successors, (206), 190 states have call predecessors, (206), 206 states have call successors, (206) [2024-10-11 02:10:17,907 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 802 states to 802 states and 1083 transitions. [2024-10-11 02:10:17,908 INFO L78 Accepts]: Start accepts. Automaton has 802 states and 1083 transitions. Word has length 38 [2024-10-11 02:10:17,908 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-11 02:10:17,908 INFO L471 AbstractCegarLoop]: Abstraction has 802 states and 1083 transitions. [2024-10-11 02:10:17,908 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 16 states, 16 states have (on average 3.375) internal successors, (54), 16 states have internal predecessors, (54), 4 states have call successors, (7), 3 states have call predecessors, (7), 2 states have return successors, (6), 3 states have call predecessors, (6), 3 states have call successors, (6) [2024-10-11 02:10:17,909 INFO L276 IsEmpty]: Start isEmpty. Operand 802 states and 1083 transitions. [2024-10-11 02:10:17,909 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 54 [2024-10-11 02:10:17,909 INFO L207 NwaCegarLoop]: Found error trace [2024-10-11 02:10:17,909 INFO L215 NwaCegarLoop]: trace histogram [5, 4, 4, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-11 02:10:17,926 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Ended with exit code 0 [2024-10-11 02:10:18,113 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 11 /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable15 [2024-10-11 02:10:18,114 INFO L396 AbstractCegarLoop]: === Iteration 17 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-11 02:10:18,115 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-11 02:10:18,115 INFO L85 PathProgramCache]: Analyzing trace with hash -263121925, now seen corresponding path program 1 times [2024-10-11 02:10:18,115 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-11 02:10:18,115 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1594591255] [2024-10-11 02:10:18,115 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-11 02:10:18,115 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-11 02:10:18,137 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-10-11 02:10:18,138 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1897293660] [2024-10-11 02:10:18,138 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-11 02:10:18,138 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-11 02:10:18,138 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 [2024-10-11 02:10:18,141 INFO L229 MonitoredProcess]: Starting monitored process 12 with /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-10-11 02:10:18,142 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Waiting until timeout for monitored process [2024-10-11 02:10:18,204 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:10:18,206 INFO L255 TraceCheckSpWp]: Trace formula consists of 157 conjuncts, 47 conjuncts are in the unsatisfiable core [2024-10-11 02:10:18,209 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-11 02:10:19,024 INFO L134 CoverageAnalysis]: Checked inductivity of 42 backedges. 8 proven. 9 refuted. 0 times theorem prover too weak. 25 trivial. 0 not checked. [2024-10-11 02:10:19,025 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-11 02:10:20,710 INFO L134 CoverageAnalysis]: Checked inductivity of 42 backedges. 8 proven. 6 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2024-10-11 02:10:20,710 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-11 02:10:20,711 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1594591255] [2024-10-11 02:10:20,711 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-10-11 02:10:20,711 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1897293660] [2024-10-11 02:10:20,711 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1897293660] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-11 02:10:20,711 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-10-11 02:10:20,711 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 11] total 23 [2024-10-11 02:10:20,711 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1825806371] [2024-10-11 02:10:20,712 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-10-11 02:10:20,712 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 23 states [2024-10-11 02:10:20,712 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-11 02:10:20,713 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 23 interpolants. [2024-10-11 02:10:20,713 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=74, Invalid=432, Unknown=0, NotChecked=0, Total=506 [2024-10-11 02:10:20,713 INFO L87 Difference]: Start difference. First operand 802 states and 1083 transitions. Second operand has 23 states, 21 states have (on average 2.4285714285714284) internal successors, (51), 20 states have internal predecessors, (51), 6 states have call successors, (13), 3 states have call predecessors, (13), 2 states have return successors, (12), 4 states have call predecessors, (12), 4 states have call successors, (12) [2024-10-11 02:10:25,734 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-10-11 02:10:29,724 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-11 02:10:29,724 INFO L93 Difference]: Finished difference Result 1217 states and 1722 transitions. [2024-10-11 02:10:29,725 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 41 states. [2024-10-11 02:10:29,726 INFO L78 Accepts]: Start accepts. Automaton has has 23 states, 21 states have (on average 2.4285714285714284) internal successors, (51), 20 states have internal predecessors, (51), 6 states have call successors, (13), 3 states have call predecessors, (13), 2 states have return successors, (12), 4 states have call predecessors, (12), 4 states have call successors, (12) Word has length 53 [2024-10-11 02:10:29,726 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-11 02:10:29,732 INFO L225 Difference]: With dead ends: 1217 [2024-10-11 02:10:29,733 INFO L226 Difference]: Without dead ends: 1195 [2024-10-11 02:10:29,734 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 137 GetRequests, 83 SyntacticMatches, 0 SemanticMatches, 54 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 743 ImplicationChecksByTransitivity, 3.1s TimeCoverageRelationStatistics Valid=548, Invalid=2532, Unknown=0, NotChecked=0, Total=3080 [2024-10-11 02:10:29,735 INFO L432 NwaCegarLoop]: 83 mSDtfsCounter, 323 mSDsluCounter, 1099 mSDsCounter, 0 mSdLazyCounter, 841 mSolverCounterSat, 177 mSolverCounterUnsat, 1 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 6.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 331 SdHoareTripleChecker+Valid, 1182 SdHoareTripleChecker+Invalid, 1019 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 177 IncrementalHoareTripleChecker+Valid, 841 IncrementalHoareTripleChecker+Invalid, 1 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 6.4s IncrementalHoareTripleChecker+Time [2024-10-11 02:10:29,735 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [331 Valid, 1182 Invalid, 1019 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [177 Valid, 841 Invalid, 1 Unknown, 0 Unchecked, 6.4s Time] [2024-10-11 02:10:29,736 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1195 states. [2024-10-11 02:10:29,949 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1195 to 884. [2024-10-11 02:10:29,951 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 884 states, 591 states have (on average 1.2538071065989849) internal successors, (741), 611 states have internal predecessors, (741), 231 states have call successors, (231), 61 states have call predecessors, (231), 61 states have return successors, (226), 211 states have call predecessors, (226), 226 states have call successors, (226) [2024-10-11 02:10:29,956 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 884 states to 884 states and 1198 transitions. [2024-10-11 02:10:29,959 INFO L78 Accepts]: Start accepts. Automaton has 884 states and 1198 transitions. Word has length 53 [2024-10-11 02:10:29,959 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-11 02:10:29,959 INFO L471 AbstractCegarLoop]: Abstraction has 884 states and 1198 transitions. [2024-10-11 02:10:29,959 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 23 states, 21 states have (on average 2.4285714285714284) internal successors, (51), 20 states have internal predecessors, (51), 6 states have call successors, (13), 3 states have call predecessors, (13), 2 states have return successors, (12), 4 states have call predecessors, (12), 4 states have call successors, (12) [2024-10-11 02:10:29,960 INFO L276 IsEmpty]: Start isEmpty. Operand 884 states and 1198 transitions. [2024-10-11 02:10:29,960 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 60 [2024-10-11 02:10:29,960 INFO L207 NwaCegarLoop]: Found error trace [2024-10-11 02:10:29,961 INFO L215 NwaCegarLoop]: trace histogram [5, 4, 4, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-11 02:10:29,975 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Ended with exit code 0 [2024-10-11 02:10:30,161 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 12 /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable16 [2024-10-11 02:10:30,161 INFO L396 AbstractCegarLoop]: === Iteration 18 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-11 02:10:30,162 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-11 02:10:30,162 INFO L85 PathProgramCache]: Analyzing trace with hash -2029616726, now seen corresponding path program 1 times [2024-10-11 02:10:30,162 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-11 02:10:30,162 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1632054991] [2024-10-11 02:10:30,162 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-11 02:10:30,162 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-11 02:10:30,172 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:10:30,378 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 1 [2024-10-11 02:10:30,379 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:10:30,382 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2024-10-11 02:10:30,383 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:10:30,385 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 27 [2024-10-11 02:10:30,386 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:10:30,389 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 32 [2024-10-11 02:10:30,390 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:10:30,393 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 37 [2024-10-11 02:10:30,394 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:10:30,396 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 42 [2024-10-11 02:10:30,397 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:10:30,400 INFO L134 CoverageAnalysis]: Checked inductivity of 53 backedges. 8 proven. 17 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2024-10-11 02:10:30,400 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-11 02:10:30,400 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1632054991] [2024-10-11 02:10:30,400 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1632054991] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-11 02:10:30,401 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1277065878] [2024-10-11 02:10:30,401 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-11 02:10:30,401 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-11 02:10:30,401 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 [2024-10-11 02:10:30,403 INFO L229 MonitoredProcess]: Starting monitored process 13 with /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-10-11 02:10:30,405 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Waiting until timeout for monitored process [2024-10-11 02:10:30,464 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:10:30,465 INFO L255 TraceCheckSpWp]: Trace formula consists of 183 conjuncts, 15 conjuncts are in the unsatisfiable core [2024-10-11 02:10:30,468 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-11 02:10:30,540 INFO L134 CoverageAnalysis]: Checked inductivity of 53 backedges. 8 proven. 17 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2024-10-11 02:10:30,540 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-11 02:10:30,675 INFO L134 CoverageAnalysis]: Checked inductivity of 53 backedges. 8 proven. 17 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2024-10-11 02:10:30,675 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1277065878] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-11 02:10:30,675 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-10-11 02:10:30,675 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 9, 10] total 20 [2024-10-11 02:10:30,675 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1987889673] [2024-10-11 02:10:30,675 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-10-11 02:10:30,676 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 20 states [2024-10-11 02:10:30,676 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-11 02:10:30,676 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 20 interpolants. [2024-10-11 02:10:30,677 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=158, Invalid=222, Unknown=0, NotChecked=0, Total=380 [2024-10-11 02:10:30,677 INFO L87 Difference]: Start difference. First operand 884 states and 1198 transitions. Second operand has 20 states, 20 states have (on average 3.45) internal successors, (69), 20 states have internal predecessors, (69), 6 states have call successors, (19), 4 states have call predecessors, (19), 3 states have return successors, (18), 5 states have call predecessors, (18), 5 states have call successors, (18) [2024-10-11 02:10:31,409 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-11 02:10:31,409 INFO L93 Difference]: Finished difference Result 1905 states and 2712 transitions. [2024-10-11 02:10:31,409 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 28 states. [2024-10-11 02:10:31,410 INFO L78 Accepts]: Start accepts. Automaton has has 20 states, 20 states have (on average 3.45) internal successors, (69), 20 states have internal predecessors, (69), 6 states have call successors, (19), 4 states have call predecessors, (19), 3 states have return successors, (18), 5 states have call predecessors, (18), 5 states have call successors, (18) Word has length 59 [2024-10-11 02:10:31,410 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-11 02:10:31,420 INFO L225 Difference]: With dead ends: 1905 [2024-10-11 02:10:31,420 INFO L226 Difference]: Without dead ends: 1883 [2024-10-11 02:10:31,421 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 148 GetRequests, 120 SyntacticMatches, 0 SemanticMatches, 28 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 122 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=303, Invalid=567, Unknown=0, NotChecked=0, Total=870 [2024-10-11 02:10:31,422 INFO L432 NwaCegarLoop]: 37 mSDtfsCounter, 355 mSDsluCounter, 293 mSDsCounter, 0 mSdLazyCounter, 178 mSolverCounterSat, 117 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 355 SdHoareTripleChecker+Valid, 330 SdHoareTripleChecker+Invalid, 295 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 117 IncrementalHoareTripleChecker+Valid, 178 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-10-11 02:10:31,422 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [355 Valid, 330 Invalid, 295 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [117 Valid, 178 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-10-11 02:10:31,424 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1883 states. [2024-10-11 02:10:31,843 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1883 to 1789. [2024-10-11 02:10:31,847 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 1789 states, 1180 states have (on average 1.2923728813559323) internal successors, (1525), 1240 states have internal predecessors, (1525), 511 states have call successors, (511), 97 states have call predecessors, (511), 97 states have return successors, (502), 451 states have call predecessors, (502), 502 states have call successors, (502) [2024-10-11 02:10:31,855 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1789 states to 1789 states and 2538 transitions. [2024-10-11 02:10:31,858 INFO L78 Accepts]: Start accepts. Automaton has 1789 states and 2538 transitions. Word has length 59 [2024-10-11 02:10:31,859 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-11 02:10:31,859 INFO L471 AbstractCegarLoop]: Abstraction has 1789 states and 2538 transitions. [2024-10-11 02:10:31,860 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 20 states, 20 states have (on average 3.45) internal successors, (69), 20 states have internal predecessors, (69), 6 states have call successors, (19), 4 states have call predecessors, (19), 3 states have return successors, (18), 5 states have call predecessors, (18), 5 states have call successors, (18) [2024-10-11 02:10:31,860 INFO L276 IsEmpty]: Start isEmpty. Operand 1789 states and 2538 transitions. [2024-10-11 02:10:31,860 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 62 [2024-10-11 02:10:31,860 INFO L207 NwaCegarLoop]: Found error trace [2024-10-11 02:10:31,861 INFO L215 NwaCegarLoop]: trace histogram [7, 6, 6, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-11 02:10:31,876 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Forceful destruction successful, exit code 0 [2024-10-11 02:10:32,064 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 13 /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable17 [2024-10-11 02:10:32,065 INFO L396 AbstractCegarLoop]: === Iteration 19 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-11 02:10:32,065 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-11 02:10:32,065 INFO L85 PathProgramCache]: Analyzing trace with hash -240119973, now seen corresponding path program 1 times [2024-10-11 02:10:32,065 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-11 02:10:32,065 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1962986004] [2024-10-11 02:10:32,065 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-11 02:10:32,065 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-11 02:10:32,073 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:10:32,115 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 1 [2024-10-11 02:10:32,116 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:10:32,117 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2024-10-11 02:10:32,118 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:10:32,119 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 20 [2024-10-11 02:10:32,120 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:10:32,121 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 25 [2024-10-11 02:10:32,123 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:10:32,128 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 30 [2024-10-11 02:10:32,129 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:10:32,131 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 35 [2024-10-11 02:10:32,135 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:10:32,136 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 47 [2024-10-11 02:10:32,137 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:10:32,140 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 52 [2024-10-11 02:10:32,140 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:10:32,143 INFO L134 CoverageAnalysis]: Checked inductivity of 84 backedges. 20 proven. 0 refuted. 0 times theorem prover too weak. 64 trivial. 0 not checked. [2024-10-11 02:10:32,143 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-11 02:10:32,144 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1962986004] [2024-10-11 02:10:32,145 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1962986004] provided 1 perfect and 0 imperfect interpolant sequences [2024-10-11 02:10:32,145 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-10-11 02:10:32,145 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-10-11 02:10:32,145 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [186085585] [2024-10-11 02:10:32,145 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-10-11 02:10:32,145 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-10-11 02:10:32,146 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-11 02:10:32,146 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-10-11 02:10:32,146 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-10-11 02:10:32,147 INFO L87 Difference]: Start difference. First operand 1789 states and 2538 transitions. Second operand has 5 states, 5 states have (on average 5.2) internal successors, (26), 5 states have internal predecessors, (26), 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) [2024-10-11 02:10:32,526 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-11 02:10:32,526 INFO L93 Difference]: Finished difference Result 3148 states and 4463 transitions. [2024-10-11 02:10:32,527 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-10-11 02:10:32,527 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 5.2) internal successors, (26), 5 states have internal predecessors, (26), 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 61 [2024-10-11 02:10:32,527 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-11 02:10:32,536 INFO L225 Difference]: With dead ends: 3148 [2024-10-11 02:10:32,536 INFO L226 Difference]: Without dead ends: 1883 [2024-10-11 02:10:32,540 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 22 GetRequests, 18 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2024-10-11 02:10:32,540 INFO L432 NwaCegarLoop]: 38 mSDtfsCounter, 3 mSDsluCounter, 88 mSDsCounter, 0 mSdLazyCounter, 45 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 3 SdHoareTripleChecker+Valid, 126 SdHoareTripleChecker+Invalid, 46 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 45 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-10-11 02:10:32,541 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [3 Valid, 126 Invalid, 46 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 45 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-10-11 02:10:32,542 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1883 states. [2024-10-11 02:10:32,939 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1883 to 1810. [2024-10-11 02:10:32,941 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 1810 states, 1241 states have (on average 1.2957292506043514) internal successors, (1608), 1270 states have internal predecessors, (1608), 471 states have call successors, (471), 97 states have call predecessors, (471), 97 states have return successors, (462), 442 states have call predecessors, (462), 462 states have call successors, (462) [2024-10-11 02:10:32,948 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1810 states to 1810 states and 2541 transitions. [2024-10-11 02:10:32,951 INFO L78 Accepts]: Start accepts. Automaton has 1810 states and 2541 transitions. Word has length 61 [2024-10-11 02:10:32,951 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-11 02:10:32,951 INFO L471 AbstractCegarLoop]: Abstraction has 1810 states and 2541 transitions. [2024-10-11 02:10:32,952 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 5.2) internal successors, (26), 5 states have internal predecessors, (26), 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) [2024-10-11 02:10:32,952 INFO L276 IsEmpty]: Start isEmpty. Operand 1810 states and 2541 transitions. [2024-10-11 02:10:32,952 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 63 [2024-10-11 02:10:32,953 INFO L207 NwaCegarLoop]: Found error trace [2024-10-11 02:10:32,953 INFO L215 NwaCegarLoop]: trace histogram [8, 7, 7, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-11 02:10:32,953 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable18 [2024-10-11 02:10:32,953 INFO L396 AbstractCegarLoop]: === Iteration 20 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-11 02:10:32,953 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-11 02:10:32,954 INFO L85 PathProgramCache]: Analyzing trace with hash -421215721, now seen corresponding path program 1 times [2024-10-11 02:10:32,954 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-11 02:10:32,954 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1582651062] [2024-10-11 02:10:32,954 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-11 02:10:32,954 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-11 02:10:32,979 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-10-11 02:10:32,980 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [658294961] [2024-10-11 02:10:32,980 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-11 02:10:32,981 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-11 02:10:32,981 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 [2024-10-11 02:10:32,982 INFO L229 MonitoredProcess]: Starting monitored process 14 with /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-10-11 02:10:32,984 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Waiting until timeout for monitored process [2024-10-11 02:10:33,036 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:10:33,037 INFO L255 TraceCheckSpWp]: Trace formula consists of 164 conjuncts, 13 conjuncts are in the unsatisfiable core [2024-10-11 02:10:33,038 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-11 02:10:33,100 INFO L134 CoverageAnalysis]: Checked inductivity of 108 backedges. 14 proven. 6 refuted. 0 times theorem prover too weak. 88 trivial. 0 not checked. [2024-10-11 02:10:33,100 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-11 02:10:33,170 INFO L134 CoverageAnalysis]: Checked inductivity of 108 backedges. 14 proven. 0 refuted. 0 times theorem prover too weak. 94 trivial. 0 not checked. [2024-10-11 02:10:33,170 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-11 02:10:33,170 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1582651062] [2024-10-11 02:10:33,170 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-10-11 02:10:33,170 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [658294961] [2024-10-11 02:10:33,170 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [658294961] provided 1 perfect and 1 imperfect interpolant sequences [2024-10-11 02:10:33,170 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-10-11 02:10:33,170 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [6] total 7 [2024-10-11 02:10:33,170 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [768897303] [2024-10-11 02:10:33,171 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-10-11 02:10:33,171 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-10-11 02:10:33,171 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-11 02:10:33,171 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-10-11 02:10:33,171 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=29, Unknown=0, NotChecked=0, Total=42 [2024-10-11 02:10:33,172 INFO L87 Difference]: Start difference. First operand 1810 states and 2541 transitions. Second operand has 5 states, 5 states have (on average 4.0) internal successors, (20), 4 states have internal predecessors, (20), 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) [2024-10-11 02:10:33,488 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-11 02:10:33,488 INFO L93 Difference]: Finished difference Result 1848 states and 2578 transitions. [2024-10-11 02:10:33,489 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-10-11 02:10:33,489 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 4.0) internal successors, (20), 4 states have internal predecessors, (20), 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 62 [2024-10-11 02:10:33,489 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-11 02:10:33,501 INFO L225 Difference]: With dead ends: 1848 [2024-10-11 02:10:33,501 INFO L226 Difference]: Without dead ends: 1846 [2024-10-11 02:10:33,502 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 123 GetRequests, 115 SyntacticMatches, 2 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=17, Invalid=39, Unknown=0, NotChecked=0, Total=56 [2024-10-11 02:10:33,503 INFO L432 NwaCegarLoop]: 36 mSDtfsCounter, 5 mSDsluCounter, 86 mSDsCounter, 0 mSdLazyCounter, 35 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 5 SdHoareTripleChecker+Valid, 122 SdHoareTripleChecker+Invalid, 35 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 35 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-10-11 02:10:33,503 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [5 Valid, 122 Invalid, 35 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 35 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-10-11 02:10:33,504 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1846 states. [2024-10-11 02:10:33,930 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1846 to 1846. [2024-10-11 02:10:33,933 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 1846 states, 1268 states have (on average 1.2878548895899053) internal successors, (1633), 1297 states have internal predecessors, (1633), 471 states have call successors, (471), 106 states have call predecessors, (471), 106 states have return successors, (462), 442 states have call predecessors, (462), 462 states have call successors, (462) [2024-10-11 02:10:33,941 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1846 states to 1846 states and 2566 transitions. [2024-10-11 02:10:33,944 INFO L78 Accepts]: Start accepts. Automaton has 1846 states and 2566 transitions. Word has length 62 [2024-10-11 02:10:33,945 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-11 02:10:33,945 INFO L471 AbstractCegarLoop]: Abstraction has 1846 states and 2566 transitions. [2024-10-11 02:10:33,945 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 4.0) internal successors, (20), 4 states have internal predecessors, (20), 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) [2024-10-11 02:10:33,945 INFO L276 IsEmpty]: Start isEmpty. Operand 1846 states and 2566 transitions. [2024-10-11 02:10:33,946 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 64 [2024-10-11 02:10:33,946 INFO L207 NwaCegarLoop]: Found error trace [2024-10-11 02:10:33,946 INFO L215 NwaCegarLoop]: trace histogram [6, 5, 5, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-11 02:10:33,962 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Forceful destruction successful, exit code 0 [2024-10-11 02:10:34,147 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable19,14 /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-11 02:10:34,147 INFO L396 AbstractCegarLoop]: === Iteration 21 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-11 02:10:34,148 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-11 02:10:34,148 INFO L85 PathProgramCache]: Analyzing trace with hash -1734545172, now seen corresponding path program 1 times [2024-10-11 02:10:34,148 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-11 02:10:34,148 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [802407899] [2024-10-11 02:10:34,148 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-11 02:10:34,148 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-11 02:10:34,165 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-10-11 02:10:34,166 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [261150724] [2024-10-11 02:10:34,167 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-11 02:10:34,167 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-11 02:10:34,167 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 [2024-10-11 02:10:34,169 INFO L229 MonitoredProcess]: Starting monitored process 15 with /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-10-11 02:10:34,171 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Waiting until timeout for monitored process [2024-10-11 02:10:34,231 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:10:34,233 INFO L255 TraceCheckSpWp]: Trace formula consists of 184 conjuncts, 44 conjuncts are in the unsatisfiable core [2024-10-11 02:10:34,237 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-11 02:10:34,850 INFO L134 CoverageAnalysis]: Checked inductivity of 70 backedges. 10 proven. 19 refuted. 0 times theorem prover too weak. 41 trivial. 0 not checked. [2024-10-11 02:10:34,850 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-11 02:10:36,078 INFO L134 CoverageAnalysis]: Checked inductivity of 70 backedges. 10 proven. 16 refuted. 0 times theorem prover too weak. 44 trivial. 0 not checked. [2024-10-11 02:10:36,078 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-11 02:10:36,078 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [802407899] [2024-10-11 02:10:36,078 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-10-11 02:10:36,079 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [261150724] [2024-10-11 02:10:36,079 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [261150724] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-11 02:10:36,079 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-10-11 02:10:36,079 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 11] total 23 [2024-10-11 02:10:36,079 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1786734765] [2024-10-11 02:10:36,079 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-10-11 02:10:36,079 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 23 states [2024-10-11 02:10:36,079 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-11 02:10:36,080 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 23 interpolants. [2024-10-11 02:10:36,080 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=74, Invalid=432, Unknown=0, NotChecked=0, Total=506 [2024-10-11 02:10:36,080 INFO L87 Difference]: Start difference. First operand 1846 states and 2566 transitions. Second operand has 23 states, 23 states have (on average 2.652173913043478) internal successors, (61), 20 states have internal predecessors, (61), 6 states have call successors, (15), 3 states have call predecessors, (15), 2 states have return successors, (14), 6 states have call predecessors, (14), 6 states have call successors, (14) [2024-10-11 02:10:41,522 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-10-11 02:10:43,201 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.00s for a HTC check with result VALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-10-11 02:10:46,243 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-11 02:10:46,243 INFO L93 Difference]: Finished difference Result 2448 states and 3457 transitions. [2024-10-11 02:10:46,244 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 30 states. [2024-10-11 02:10:46,244 INFO L78 Accepts]: Start accepts. Automaton has has 23 states, 23 states have (on average 2.652173913043478) internal successors, (61), 20 states have internal predecessors, (61), 6 states have call successors, (15), 3 states have call predecessors, (15), 2 states have return successors, (14), 6 states have call predecessors, (14), 6 states have call successors, (14) Word has length 63 [2024-10-11 02:10:46,244 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-11 02:10:46,257 INFO L225 Difference]: With dead ends: 2448 [2024-10-11 02:10:46,257 INFO L226 Difference]: Without dead ends: 2446 [2024-10-11 02:10:46,259 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 148 GetRequests, 103 SyntacticMatches, 1 SemanticMatches, 44 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 416 ImplicationChecksByTransitivity, 3.4s TimeCoverageRelationStatistics Valid=417, Invalid=1653, Unknown=0, NotChecked=0, Total=2070 [2024-10-11 02:10:46,259 INFO L432 NwaCegarLoop]: 50 mSDtfsCounter, 262 mSDsluCounter, 559 mSDsCounter, 0 mSdLazyCounter, 469 mSolverCounterSat, 153 mSolverCounterUnsat, 1 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 6.8s Time, 0 mProtectedPredicate, 0 mProtectedAction, 270 SdHoareTripleChecker+Valid, 609 SdHoareTripleChecker+Invalid, 623 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 153 IncrementalHoareTripleChecker+Valid, 469 IncrementalHoareTripleChecker+Invalid, 1 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 6.9s IncrementalHoareTripleChecker+Time [2024-10-11 02:10:46,259 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [270 Valid, 609 Invalid, 623 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [153 Valid, 469 Invalid, 1 Unknown, 0 Unchecked, 6.9s Time] [2024-10-11 02:10:46,262 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 2446 states. [2024-10-11 02:10:46,992 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 2446 to 2316. [2024-10-11 02:10:46,996 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 2316 states, 1610 states have (on average 1.3093167701863353) internal successors, (2108), 1647 states have internal predecessors, (2108), 591 states have call successors, (591), 114 states have call predecessors, (591), 114 states have return successors, (582), 554 states have call predecessors, (582), 582 states have call successors, (582) [2024-10-11 02:10:47,006 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 2316 states to 2316 states and 3281 transitions. [2024-10-11 02:10:47,010 INFO L78 Accepts]: Start accepts. Automaton has 2316 states and 3281 transitions. Word has length 63 [2024-10-11 02:10:47,010 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-11 02:10:47,011 INFO L471 AbstractCegarLoop]: Abstraction has 2316 states and 3281 transitions. [2024-10-11 02:10:47,011 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 23 states, 23 states have (on average 2.652173913043478) internal successors, (61), 20 states have internal predecessors, (61), 6 states have call successors, (15), 3 states have call predecessors, (15), 2 states have return successors, (14), 6 states have call predecessors, (14), 6 states have call successors, (14) [2024-10-11 02:10:47,011 INFO L276 IsEmpty]: Start isEmpty. Operand 2316 states and 3281 transitions. [2024-10-11 02:10:47,013 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 66 [2024-10-11 02:10:47,014 INFO L207 NwaCegarLoop]: Found error trace [2024-10-11 02:10:47,014 INFO L215 NwaCegarLoop]: trace histogram [5, 4, 4, 4, 4, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-11 02:10:47,033 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Ended with exit code 0 [2024-10-11 02:10:47,214 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 15 /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable20 [2024-10-11 02:10:47,215 INFO L396 AbstractCegarLoop]: === Iteration 22 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-11 02:10:47,216 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-11 02:10:47,216 INFO L85 PathProgramCache]: Analyzing trace with hash -2144187133, now seen corresponding path program 2 times [2024-10-11 02:10:47,216 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-11 02:10:47,216 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [142077842] [2024-10-11 02:10:47,216 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-11 02:10:47,217 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-11 02:10:47,236 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-10-11 02:10:47,238 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1662248331] [2024-10-11 02:10:47,239 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-10-11 02:10:47,239 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-11 02:10:47,239 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 [2024-10-11 02:10:47,241 INFO L229 MonitoredProcess]: Starting monitored process 16 with /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-10-11 02:10:47,243 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Waiting until timeout for monitored process [2024-10-11 02:10:47,303 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-10-11 02:10:47,303 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2024-10-11 02:10:47,304 INFO L255 TraceCheckSpWp]: Trace formula consists of 203 conjuncts, 38 conjuncts are in the unsatisfiable core [2024-10-11 02:10:47,307 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-11 02:10:47,529 INFO L134 CoverageAnalysis]: Checked inductivity of 67 backedges. 10 proven. 35 refuted. 0 times theorem prover too weak. 22 trivial. 0 not checked. [2024-10-11 02:10:47,529 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-11 02:10:47,625 INFO L134 CoverageAnalysis]: Checked inductivity of 67 backedges. 32 proven. 10 refuted. 0 times theorem prover too weak. 25 trivial. 0 not checked. [2024-10-11 02:10:47,625 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-11 02:10:47,625 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [142077842] [2024-10-11 02:10:47,625 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-10-11 02:10:47,625 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1662248331] [2024-10-11 02:10:47,625 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1662248331] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-11 02:10:47,625 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-10-11 02:10:47,626 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 8] total 13 [2024-10-11 02:10:47,626 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1013093205] [2024-10-11 02:10:47,626 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-10-11 02:10:47,626 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 13 states [2024-10-11 02:10:47,626 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-11 02:10:47,627 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2024-10-11 02:10:47,627 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=31, Invalid=125, Unknown=0, NotChecked=0, Total=156 [2024-10-11 02:10:47,627 INFO L87 Difference]: Start difference. First operand 2316 states and 3281 transitions. Second operand has 13 states, 13 states have (on average 5.230769230769231) internal successors, (68), 12 states have internal predecessors, (68), 5 states have call successors, (12), 2 states have call predecessors, (12), 2 states have return successors, (10), 3 states have call predecessors, (10), 3 states have call successors, (10) [2024-10-11 02:10:48,517 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-11 02:10:48,518 INFO L93 Difference]: Finished difference Result 2758 states and 3906 transitions. [2024-10-11 02:10:48,518 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2024-10-11 02:10:48,518 INFO L78 Accepts]: Start accepts. Automaton has has 13 states, 13 states have (on average 5.230769230769231) internal successors, (68), 12 states have internal predecessors, (68), 5 states have call successors, (12), 2 states have call predecessors, (12), 2 states have return successors, (10), 3 states have call predecessors, (10), 3 states have call successors, (10) Word has length 65 [2024-10-11 02:10:48,519 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-11 02:10:48,531 INFO L225 Difference]: With dead ends: 2758 [2024-10-11 02:10:48,531 INFO L226 Difference]: Without dead ends: 2756 [2024-10-11 02:10:48,532 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 139 GetRequests, 120 SyntacticMatches, 2 SemanticMatches, 17 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 35 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=72, Invalid=270, Unknown=0, NotChecked=0, Total=342 [2024-10-11 02:10:48,533 INFO L432 NwaCegarLoop]: 49 mSDtfsCounter, 88 mSDsluCounter, 291 mSDsCounter, 0 mSdLazyCounter, 198 mSolverCounterSat, 43 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 92 SdHoareTripleChecker+Valid, 340 SdHoareTripleChecker+Invalid, 241 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 43 IncrementalHoareTripleChecker+Valid, 198 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-10-11 02:10:48,533 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [92 Valid, 340 Invalid, 241 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [43 Valid, 198 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-10-11 02:10:48,536 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 2756 states. [2024-10-11 02:10:49,206 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 2756 to 2563. [2024-10-11 02:10:49,209 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 2563 states, 1824 states have (on average 1.3135964912280702) internal successors, (2396), 1873 states have internal predecessors, (2396), 611 states have call successors, (611), 127 states have call predecessors, (611), 127 states have return successors, (602), 562 states have call predecessors, (602), 602 states have call successors, (602) [2024-10-11 02:10:49,215 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 2563 states to 2563 states and 3609 transitions. [2024-10-11 02:10:49,218 INFO L78 Accepts]: Start accepts. Automaton has 2563 states and 3609 transitions. Word has length 65 [2024-10-11 02:10:49,218 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-11 02:10:49,219 INFO L471 AbstractCegarLoop]: Abstraction has 2563 states and 3609 transitions. [2024-10-11 02:10:49,219 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 13 states, 13 states have (on average 5.230769230769231) internal successors, (68), 12 states have internal predecessors, (68), 5 states have call successors, (12), 2 states have call predecessors, (12), 2 states have return successors, (10), 3 states have call predecessors, (10), 3 states have call successors, (10) [2024-10-11 02:10:49,219 INFO L276 IsEmpty]: Start isEmpty. Operand 2563 states and 3609 transitions. [2024-10-11 02:10:49,220 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 77 [2024-10-11 02:10:49,220 INFO L207 NwaCegarLoop]: Found error trace [2024-10-11 02:10:49,220 INFO L215 NwaCegarLoop]: trace histogram [9, 8, 8, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-11 02:10:49,237 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Forceful destruction successful, exit code 0 [2024-10-11 02:10:49,421 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable21,16 /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-11 02:10:49,421 INFO L396 AbstractCegarLoop]: === Iteration 23 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-11 02:10:49,421 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-11 02:10:49,421 INFO L85 PathProgramCache]: Analyzing trace with hash 1940891938, now seen corresponding path program 1 times [2024-10-11 02:10:49,421 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-11 02:10:49,421 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1650013100] [2024-10-11 02:10:49,421 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-11 02:10:49,422 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-11 02:10:49,440 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-10-11 02:10:49,444 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1459558728] [2024-10-11 02:10:49,444 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-11 02:10:49,445 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-11 02:10:49,445 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 [2024-10-11 02:10:49,446 INFO L229 MonitoredProcess]: Starting monitored process 17 with /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-10-11 02:10:49,448 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Waiting until timeout for monitored process [2024-10-11 02:10:49,511 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:10:49,512 INFO L255 TraceCheckSpWp]: Trace formula consists of 203 conjuncts, 55 conjuncts are in the unsatisfiable core [2024-10-11 02:10:49,514 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-11 02:10:50,278 INFO L134 CoverageAnalysis]: Checked inductivity of 145 backedges. 16 proven. 16 refuted. 0 times theorem prover too weak. 113 trivial. 0 not checked. [2024-10-11 02:10:50,278 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-11 02:10:52,406 INFO L134 CoverageAnalysis]: Checked inductivity of 145 backedges. 16 proven. 13 refuted. 0 times theorem prover too weak. 116 trivial. 0 not checked. [2024-10-11 02:10:52,407 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-11 02:10:52,407 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1650013100] [2024-10-11 02:10:52,407 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-10-11 02:10:52,407 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1459558728] [2024-10-11 02:10:52,407 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1459558728] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-11 02:10:52,407 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-10-11 02:10:52,407 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [15, 12] total 25 [2024-10-11 02:10:52,407 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [662038457] [2024-10-11 02:10:52,407 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-10-11 02:10:52,408 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 25 states [2024-10-11 02:10:52,408 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-11 02:10:52,408 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 25 interpolants. [2024-10-11 02:10:52,409 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=88, Invalid=512, Unknown=0, NotChecked=0, Total=600 [2024-10-11 02:10:52,409 INFO L87 Difference]: Start difference. First operand 2563 states and 3609 transitions. Second operand has 25 states, 23 states have (on average 2.4782608695652173) internal successors, (57), 22 states have internal predecessors, (57), 8 states have call successors, (21), 3 states have call predecessors, (21), 2 states have return successors, (20), 6 states have call predecessors, (20), 6 states have call successors, (20) [2024-10-11 02:10:57,901 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-11 02:10:57,901 INFO L93 Difference]: Finished difference Result 2868 states and 4008 transitions. [2024-10-11 02:10:57,902 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 46 states. [2024-10-11 02:10:57,902 INFO L78 Accepts]: Start accepts. Automaton has has 25 states, 23 states have (on average 2.4782608695652173) internal successors, (57), 22 states have internal predecessors, (57), 8 states have call successors, (21), 3 states have call predecessors, (21), 2 states have return successors, (20), 6 states have call predecessors, (20), 6 states have call successors, (20) Word has length 76 [2024-10-11 02:10:57,902 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-11 02:10:57,917 INFO L225 Difference]: With dead ends: 2868 [2024-10-11 02:10:57,917 INFO L226 Difference]: Without dead ends: 2861 [2024-10-11 02:10:57,919 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 187 GetRequests, 127 SyntacticMatches, 0 SemanticMatches, 60 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 867 ImplicationChecksByTransitivity, 3.7s TimeCoverageRelationStatistics Valid=737, Invalid=3045, Unknown=0, NotChecked=0, Total=3782 [2024-10-11 02:10:57,920 INFO L432 NwaCegarLoop]: 65 mSDtfsCounter, 263 mSDsluCounter, 827 mSDsCounter, 0 mSdLazyCounter, 809 mSolverCounterSat, 206 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 2.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 263 SdHoareTripleChecker+Valid, 892 SdHoareTripleChecker+Invalid, 1015 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 206 IncrementalHoareTripleChecker+Valid, 809 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 2.1s IncrementalHoareTripleChecker+Time [2024-10-11 02:10:57,920 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [263 Valid, 892 Invalid, 1015 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [206 Valid, 809 Invalid, 0 Unknown, 0 Unchecked, 2.1s Time] [2024-10-11 02:10:57,923 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 2861 states. [2024-10-11 02:10:58,861 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 2861 to 2779. [2024-10-11 02:10:58,865 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 2779 states, 1954 states have (on average 1.3070624360286591) internal successors, (2554), 2004 states have internal predecessors, (2554), 676 states have call successors, (676), 148 states have call predecessors, (676), 148 states have return successors, (670), 626 states have call predecessors, (670), 670 states have call successors, (670) [2024-10-11 02:10:58,871 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 2779 states to 2779 states and 3900 transitions. [2024-10-11 02:10:58,874 INFO L78 Accepts]: Start accepts. Automaton has 2779 states and 3900 transitions. Word has length 76 [2024-10-11 02:10:58,874 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-11 02:10:58,874 INFO L471 AbstractCegarLoop]: Abstraction has 2779 states and 3900 transitions. [2024-10-11 02:10:58,874 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 25 states, 23 states have (on average 2.4782608695652173) internal successors, (57), 22 states have internal predecessors, (57), 8 states have call successors, (21), 3 states have call predecessors, (21), 2 states have return successors, (20), 6 states have call predecessors, (20), 6 states have call successors, (20) [2024-10-11 02:10:58,874 INFO L276 IsEmpty]: Start isEmpty. Operand 2779 states and 3900 transitions. [2024-10-11 02:10:58,876 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 92 [2024-10-11 02:10:58,876 INFO L207 NwaCegarLoop]: Found error trace [2024-10-11 02:10:58,876 INFO L215 NwaCegarLoop]: trace histogram [11, 10, 10, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-11 02:10:58,893 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Ended with exit code 0 [2024-10-11 02:10:59,080 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 17 /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable22 [2024-10-11 02:10:59,081 INFO L396 AbstractCegarLoop]: === Iteration 24 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-11 02:10:59,081 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-11 02:10:59,081 INFO L85 PathProgramCache]: Analyzing trace with hash -1286517375, now seen corresponding path program 1 times [2024-10-11 02:10:59,081 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-11 02:10:59,081 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [454136824] [2024-10-11 02:10:59,081 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-11 02:10:59,081 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-11 02:10:59,095 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-10-11 02:10:59,096 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [820221111] [2024-10-11 02:10:59,096 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-11 02:10:59,097 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-11 02:10:59,097 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 [2024-10-11 02:10:59,098 INFO L229 MonitoredProcess]: Starting monitored process 18 with /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-10-11 02:10:59,101 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (18)] Waiting until timeout for monitored process [2024-10-11 02:10:59,163 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:10:59,164 INFO L255 TraceCheckSpWp]: Trace formula consists of 239 conjuncts, 32 conjuncts are in the unsatisfiable core [2024-10-11 02:10:59,166 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-11 02:10:59,380 INFO L134 CoverageAnalysis]: Checked inductivity of 233 backedges. 26 proven. 23 refuted. 0 times theorem prover too weak. 184 trivial. 0 not checked. [2024-10-11 02:10:59,380 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-11 02:10:59,709 INFO L134 CoverageAnalysis]: Checked inductivity of 233 backedges. 29 proven. 17 refuted. 0 times theorem prover too weak. 187 trivial. 0 not checked. [2024-10-11 02:10:59,709 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-11 02:10:59,710 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [454136824] [2024-10-11 02:10:59,710 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-10-11 02:10:59,710 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [820221111] [2024-10-11 02:10:59,710 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [820221111] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-11 02:10:59,710 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-10-11 02:10:59,710 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 10] total 21 [2024-10-11 02:10:59,710 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [183944380] [2024-10-11 02:10:59,710 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-10-11 02:10:59,710 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 21 states [2024-10-11 02:10:59,711 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-11 02:10:59,711 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2024-10-11 02:10:59,711 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=81, Invalid=339, Unknown=0, NotChecked=0, Total=420 [2024-10-11 02:10:59,711 INFO L87 Difference]: Start difference. First operand 2779 states and 3900 transitions. Second operand has 21 states, 21 states have (on average 2.6666666666666665) internal successors, (56), 18 states have internal predecessors, (56), 8 states have call successors, (25), 3 states have call predecessors, (25), 2 states have return successors, (24), 8 states have call predecessors, (24), 8 states have call successors, (24) [2024-10-11 02:11:01,990 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-11 02:11:01,990 INFO L93 Difference]: Finished difference Result 4052 states and 5924 transitions. [2024-10-11 02:11:01,990 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 25 states. [2024-10-11 02:11:01,991 INFO L78 Accepts]: Start accepts. Automaton has has 21 states, 21 states have (on average 2.6666666666666665) internal successors, (56), 18 states have internal predecessors, (56), 8 states have call successors, (25), 3 states have call predecessors, (25), 2 states have return successors, (24), 8 states have call predecessors, (24), 8 states have call successors, (24) Word has length 91 [2024-10-11 02:11:01,991 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-11 02:11:02,009 INFO L225 Difference]: With dead ends: 4052 [2024-10-11 02:11:02,010 INFO L226 Difference]: Without dead ends: 4048 [2024-10-11 02:11:02,011 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 203 GetRequests, 165 SyntacticMatches, 0 SemanticMatches, 38 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 306 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=345, Invalid=1215, Unknown=0, NotChecked=0, Total=1560 [2024-10-11 02:11:02,012 INFO L432 NwaCegarLoop]: 50 mSDtfsCounter, 183 mSDsluCounter, 409 mSDsCounter, 0 mSdLazyCounter, 333 mSolverCounterSat, 102 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 187 SdHoareTripleChecker+Valid, 459 SdHoareTripleChecker+Invalid, 435 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 102 IncrementalHoareTripleChecker+Valid, 333 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.5s IncrementalHoareTripleChecker+Time [2024-10-11 02:11:02,012 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [187 Valid, 459 Invalid, 435 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [102 Valid, 333 Invalid, 0 Unknown, 0 Unchecked, 0.5s Time] [2024-10-11 02:11:02,015 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 4048 states. [2024-10-11 02:11:03,514 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 4048 to 3761. [2024-10-11 02:11:03,519 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 3761 states, 2465 states have (on average 1.3509127789046653) internal successors, (3330), 2538 states have internal predecessors, (3330), 1128 states have call successors, (1128), 168 states have call predecessors, (1128), 167 states have return successors, (1122), 1054 states have call predecessors, (1122), 1122 states have call successors, (1122) [2024-10-11 02:11:03,532 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 3761 states to 3761 states and 5580 transitions. [2024-10-11 02:11:03,536 INFO L78 Accepts]: Start accepts. Automaton has 3761 states and 5580 transitions. Word has length 91 [2024-10-11 02:11:03,536 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-11 02:11:03,536 INFO L471 AbstractCegarLoop]: Abstraction has 3761 states and 5580 transitions. [2024-10-11 02:11:03,537 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 21 states, 21 states have (on average 2.6666666666666665) internal successors, (56), 18 states have internal predecessors, (56), 8 states have call successors, (25), 3 states have call predecessors, (25), 2 states have return successors, (24), 8 states have call predecessors, (24), 8 states have call successors, (24) [2024-10-11 02:11:03,537 INFO L276 IsEmpty]: Start isEmpty. Operand 3761 states and 5580 transitions. [2024-10-11 02:11:03,538 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 94 [2024-10-11 02:11:03,539 INFO L207 NwaCegarLoop]: Found error trace [2024-10-11 02:11:03,539 INFO L215 NwaCegarLoop]: trace histogram [10, 9, 9, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-11 02:11:03,556 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (18)] Ended with exit code 0 [2024-10-11 02:11:03,739 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable23,18 /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-11 02:11:03,740 INFO L396 AbstractCegarLoop]: === Iteration 25 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-11 02:11:03,740 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-11 02:11:03,740 INFO L85 PathProgramCache]: Analyzing trace with hash 1994866066, now seen corresponding path program 2 times [2024-10-11 02:11:03,740 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-11 02:11:03,740 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1154646780] [2024-10-11 02:11:03,740 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-11 02:11:03,740 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-11 02:11:03,761 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-10-11 02:11:03,763 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [731950714] [2024-10-11 02:11:03,763 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-10-11 02:11:03,763 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-11 02:11:03,763 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 [2024-10-11 02:11:03,765 INFO L229 MonitoredProcess]: Starting monitored process 19 with /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-10-11 02:11:03,767 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (19)] Waiting until timeout for monitored process [2024-10-11 02:11:03,845 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-10-11 02:11:03,845 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2024-10-11 02:11:03,848 INFO L255 TraceCheckSpWp]: Trace formula consists of 258 conjuncts, 70 conjuncts are in the unsatisfiable core [2024-10-11 02:11:03,850 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-11 02:11:04,847 INFO L134 CoverageAnalysis]: Checked inductivity of 209 backedges. 32 proven. 56 refuted. 0 times theorem prover too weak. 121 trivial. 0 not checked. [2024-10-11 02:11:04,847 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-11 02:11:09,044 INFO L134 CoverageAnalysis]: Checked inductivity of 209 backedges. 38 proven. 47 refuted. 0 times theorem prover too weak. 124 trivial. 0 not checked. [2024-10-11 02:11:09,044 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-11 02:11:09,044 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1154646780] [2024-10-11 02:11:09,044 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-10-11 02:11:09,044 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [731950714] [2024-10-11 02:11:09,044 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [731950714] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-11 02:11:09,044 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-10-11 02:11:09,044 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [20, 16] total 33 [2024-10-11 02:11:09,045 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [236462370] [2024-10-11 02:11:09,045 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-10-11 02:11:09,045 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 33 states [2024-10-11 02:11:09,045 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-11 02:11:09,046 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 33 interpolants. [2024-10-11 02:11:09,046 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=160, Invalid=896, Unknown=0, NotChecked=0, Total=1056 [2024-10-11 02:11:09,046 INFO L87 Difference]: Start difference. First operand 3761 states and 5580 transitions. Second operand has 33 states, 33 states have (on average 2.606060606060606) internal successors, (86), 31 states have internal predecessors, (86), 9 states have call successors, (23), 3 states have call predecessors, (23), 3 states have return successors, (22), 9 states have call predecessors, (22), 9 states have call successors, (22) [2024-10-11 02:11:13,363 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.21s for a HTC check with result VALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-10-11 02:11:18,554 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.01s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-10-11 02:11:31,048 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-11 02:11:31,048 INFO L93 Difference]: Finished difference Result 4856 states and 7066 transitions. [2024-10-11 02:11:31,049 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 72 states. [2024-10-11 02:11:31,049 INFO L78 Accepts]: Start accepts. Automaton has has 33 states, 33 states have (on average 2.606060606060606) internal successors, (86), 31 states have internal predecessors, (86), 9 states have call successors, (23), 3 states have call predecessors, (23), 3 states have return successors, (22), 9 states have call predecessors, (22), 9 states have call successors, (22) Word has length 93 [2024-10-11 02:11:31,049 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-11 02:11:31,074 INFO L225 Difference]: With dead ends: 4856 [2024-10-11 02:11:31,074 INFO L226 Difference]: Without dead ends: 4854 [2024-10-11 02:11:31,078 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 246 GetRequests, 153 SyntacticMatches, 0 SemanticMatches, 93 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2663 ImplicationChecksByTransitivity, 11.8s TimeCoverageRelationStatistics Valid=1897, Invalid=7033, Unknown=0, NotChecked=0, Total=8930 [2024-10-11 02:11:31,079 INFO L432 NwaCegarLoop]: 79 mSDtfsCounter, 533 mSDsluCounter, 1229 mSDsCounter, 0 mSdLazyCounter, 1380 mSolverCounterSat, 312 mSolverCounterUnsat, 1 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 9.9s Time, 0 mProtectedPredicate, 0 mProtectedAction, 533 SdHoareTripleChecker+Valid, 1308 SdHoareTripleChecker+Invalid, 1693 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 312 IncrementalHoareTripleChecker+Valid, 1380 IncrementalHoareTripleChecker+Invalid, 1 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 10.0s IncrementalHoareTripleChecker+Time [2024-10-11 02:11:31,079 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [533 Valid, 1308 Invalid, 1693 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [312 Valid, 1380 Invalid, 1 Unknown, 0 Unchecked, 10.0s Time] [2024-10-11 02:11:31,084 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 4854 states. [2024-10-11 02:11:33,070 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 4854 to 4401. [2024-10-11 02:11:33,076 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 4401 states, 3029 states have (on average 1.3456586332122813) internal successors, (4076), 3115 states have internal predecessors, (4076), 1170 states have call successors, (1170), 202 states have call predecessors, (1170), 201 states have return successors, (1164), 1083 states have call predecessors, (1164), 1164 states have call successors, (1164) [2024-10-11 02:11:33,086 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 4401 states to 4401 states and 6410 transitions. [2024-10-11 02:11:33,089 INFO L78 Accepts]: Start accepts. Automaton has 4401 states and 6410 transitions. Word has length 93 [2024-10-11 02:11:33,089 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-11 02:11:33,089 INFO L471 AbstractCegarLoop]: Abstraction has 4401 states and 6410 transitions. [2024-10-11 02:11:33,089 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 33 states, 33 states have (on average 2.606060606060606) internal successors, (86), 31 states have internal predecessors, (86), 9 states have call successors, (23), 3 states have call predecessors, (23), 3 states have return successors, (22), 9 states have call predecessors, (22), 9 states have call successors, (22) [2024-10-11 02:11:33,089 INFO L276 IsEmpty]: Start isEmpty. Operand 4401 states and 6410 transitions. [2024-10-11 02:11:33,091 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 94 [2024-10-11 02:11:33,091 INFO L207 NwaCegarLoop]: Found error trace [2024-10-11 02:11:33,091 INFO L215 NwaCegarLoop]: trace histogram [9, 8, 8, 5, 4, 4, 4, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-11 02:11:33,108 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (19)] Ended with exit code 0 [2024-10-11 02:11:33,292 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 19 /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable24 [2024-10-11 02:11:33,292 INFO L396 AbstractCegarLoop]: === Iteration 26 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-11 02:11:33,292 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-11 02:11:33,293 INFO L85 PathProgramCache]: Analyzing trace with hash 607563547, now seen corresponding path program 1 times [2024-10-11 02:11:33,293 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-11 02:11:33,293 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1416764039] [2024-10-11 02:11:33,293 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-11 02:11:33,293 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-11 02:11:33,312 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:11:33,577 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 1 [2024-10-11 02:11:33,578 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:11:33,580 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2024-10-11 02:11:33,581 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:11:33,583 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 27 [2024-10-11 02:11:33,584 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:11:33,589 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 32 [2024-10-11 02:11:33,590 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:11:33,595 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 37 [2024-10-11 02:11:33,597 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:11:33,598 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 42 [2024-10-11 02:11:33,599 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:11:33,602 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 61 [2024-10-11 02:11:33,603 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:11:33,604 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 66 [2024-10-11 02:11:33,605 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:11:33,608 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 71 [2024-10-11 02:11:33,610 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:11:33,612 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 76 [2024-10-11 02:11:33,616 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:11:33,618 INFO L134 CoverageAnalysis]: Checked inductivity of 187 backedges. 27 proven. 44 refuted. 0 times theorem prover too weak. 116 trivial. 0 not checked. [2024-10-11 02:11:33,619 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-11 02:11:33,619 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1416764039] [2024-10-11 02:11:33,619 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1416764039] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-11 02:11:33,619 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2098178770] [2024-10-11 02:11:33,619 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-11 02:11:33,620 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-11 02:11:33,620 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 [2024-10-11 02:11:33,621 INFO L229 MonitoredProcess]: Starting monitored process 20 with /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-10-11 02:11:33,623 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (20)] Waiting until timeout for monitored process [2024-10-11 02:11:33,691 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:11:33,693 INFO L255 TraceCheckSpWp]: Trace formula consists of 268 conjuncts, 21 conjuncts are in the unsatisfiable core [2024-10-11 02:11:33,696 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-11 02:11:33,799 INFO L134 CoverageAnalysis]: Checked inductivity of 187 backedges. 27 proven. 108 refuted. 0 times theorem prover too weak. 52 trivial. 0 not checked. [2024-10-11 02:11:33,799 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-11 02:11:34,042 INFO L134 CoverageAnalysis]: Checked inductivity of 187 backedges. 27 proven. 44 refuted. 0 times theorem prover too weak. 116 trivial. 0 not checked. [2024-10-11 02:11:34,042 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2098178770] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-11 02:11:34,042 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-10-11 02:11:34,042 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 12, 13] total 26 [2024-10-11 02:11:34,042 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [307331479] [2024-10-11 02:11:34,042 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-10-11 02:11:34,043 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 26 states [2024-10-11 02:11:34,043 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-11 02:11:34,044 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 26 interpolants. [2024-10-11 02:11:34,044 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=279, Invalid=371, Unknown=0, NotChecked=0, Total=650 [2024-10-11 02:11:34,044 INFO L87 Difference]: Start difference. First operand 4401 states and 6410 transitions. Second operand has 26 states, 26 states have (on average 3.6923076923076925) internal successors, (96), 26 states have internal predecessors, (96), 8 states have call successors, (31), 5 states have call predecessors, (31), 4 states have return successors, (30), 7 states have call predecessors, (30), 7 states have call successors, (30)