./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/prodbin-ll_unwindbound100.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/prodbin-ll_unwindbound100.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 d87fab1dc6e9b3b1ef38291e10411689fc961abba4e105f2586cc8da9615d8a6 --- Real Ultimate output --- This is Ultimate 0.2.5-dev-84cfde4 [2024-10-11 02:26:03,943 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-10-11 02:26:04,005 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:26:04,009 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-10-11 02:26:04,009 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-10-11 02:26:04,037 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-10-11 02:26:04,038 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-10-11 02:26:04,038 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-10-11 02:26:04,038 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2024-10-11 02:26:04,039 INFO L153 SettingsManager]: * Use memory slicer=true [2024-10-11 02:26:04,039 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2024-10-11 02:26:04,039 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2024-10-11 02:26:04,040 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2024-10-11 02:26:04,042 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2024-10-11 02:26:04,042 INFO L153 SettingsManager]: * Use SBE=true [2024-10-11 02:26:04,042 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-10-11 02:26:04,043 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2024-10-11 02:26:04,043 INFO L153 SettingsManager]: * sizeof long=4 [2024-10-11 02:26:04,043 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2024-10-11 02:26:04,044 INFO L153 SettingsManager]: * sizeof POINTER=4 [2024-10-11 02:26:04,044 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-10-11 02:26:04,044 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2024-10-11 02:26:04,045 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2024-10-11 02:26:04,045 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2024-10-11 02:26:04,045 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-10-11 02:26:04,045 INFO L153 SettingsManager]: * sizeof long double=12 [2024-10-11 02:26:04,046 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-10-11 02:26:04,046 INFO L153 SettingsManager]: * Use constant arrays=true [2024-10-11 02:26:04,046 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2024-10-11 02:26:04,047 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2024-10-11 02:26:04,047 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2024-10-11 02:26:04,047 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2024-10-11 02:26:04,047 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-10-11 02:26:04,048 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-10-11 02:26:04,048 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2024-10-11 02:26:04,048 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2024-10-11 02:26:04,048 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2024-10-11 02:26:04,049 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2024-10-11 02:26:04,049 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2024-10-11 02:26:04,049 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2024-10-11 02:26:04,050 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2024-10-11 02:26:04,050 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2024-10-11 02:26:04,050 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 -> d87fab1dc6e9b3b1ef38291e10411689fc961abba4e105f2586cc8da9615d8a6 [2024-10-11 02:26:04,284 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-10-11 02:26:04,307 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-10-11 02:26:04,310 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-10-11 02:26:04,311 INFO L270 PluginConnector]: Initializing CDTParser... [2024-10-11 02:26:04,311 INFO L274 PluginConnector]: CDTParser initialized [2024-10-11 02:26:04,312 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/prodbin-ll_unwindbound100.c [2024-10-11 02:26:05,756 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-10-11 02:26:05,938 INFO L384 CDTParser]: Found 1 translation units. [2024-10-11 02:26:05,939 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/prodbin-ll_unwindbound100.c [2024-10-11 02:26:05,949 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/data/2a360e3b1/b7b06c1e56fb4d3d9fef711eed6fd30e/FLAG1b5bfb2b1 [2024-10-11 02:26:05,967 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/data/2a360e3b1/b7b06c1e56fb4d3d9fef711eed6fd30e [2024-10-11 02:26:05,971 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-10-11 02:26:05,972 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2024-10-11 02:26:05,975 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-10-11 02:26:05,975 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-10-11 02:26:05,981 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-10-11 02:26:05,982 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 11.10 02:26:05" (1/1) ... [2024-10-11 02:26:05,984 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@3fa0a3d6 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.10 02:26:05, skipping insertion in model container [2024-10-11 02:26:05,985 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 11.10 02:26:05" (1/1) ... [2024-10-11 02:26:06,005 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-10-11 02:26:06,194 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/prodbin-ll_unwindbound100.c[1263,1276] [2024-10-11 02:26:06,212 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-10-11 02:26:06,220 INFO L200 MainTranslator]: Completed pre-run [2024-10-11 02:26:06,233 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/prodbin-ll_unwindbound100.c[1263,1276] [2024-10-11 02:26:06,242 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-10-11 02:26:06,261 INFO L204 MainTranslator]: Completed translation [2024-10-11 02:26:06,262 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.10 02:26:06 WrapperNode [2024-10-11 02:26:06,262 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-10-11 02:26:06,263 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-10-11 02:26:06,264 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-10-11 02:26:06,264 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-10-11 02:26:06,271 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:26:06" (1/1) ... [2024-10-11 02:26:06,279 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:26:06" (1/1) ... [2024-10-11 02:26:06,300 INFO L138 Inliner]: procedures = 14, calls = 10, calls flagged for inlining = 3, calls inlined = 3, statements flattened = 49 [2024-10-11 02:26:06,302 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-10-11 02:26:06,303 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-10-11 02:26:06,303 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-10-11 02:26:06,303 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-10-11 02:26:06,314 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.10 02:26:06" (1/1) ... [2024-10-11 02:26:06,315 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.10 02:26:06" (1/1) ... [2024-10-11 02:26:06,316 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.10 02:26:06" (1/1) ... [2024-10-11 02:26:06,332 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:26:06,333 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.10 02:26:06" (1/1) ... [2024-10-11 02:26:06,333 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.10 02:26:06" (1/1) ... [2024-10-11 02:26:06,337 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.10 02:26:06" (1/1) ... [2024-10-11 02:26:06,340 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.10 02:26:06" (1/1) ... [2024-10-11 02:26:06,341 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.10 02:26:06" (1/1) ... [2024-10-11 02:26:06,342 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.10 02:26:06" (1/1) ... [2024-10-11 02:26:06,343 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-10-11 02:26:06,344 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2024-10-11 02:26:06,344 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2024-10-11 02:26:06,344 INFO L274 PluginConnector]: RCFGBuilder initialized [2024-10-11 02:26:06,345 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.10 02:26:06" (1/1) ... [2024-10-11 02:26:06,354 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-10-11 02:26:06,363 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 [2024-10-11 02:26:06,376 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:26:06,379 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:26:06,421 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2024-10-11 02:26:06,421 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2024-10-11 02:26:06,421 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-10-11 02:26:06,421 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-10-11 02:26:06,421 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2024-10-11 02:26:06,422 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2024-10-11 02:26:06,482 INFO L238 CfgBuilder]: Building ICFG [2024-10-11 02:26:06,486 INFO L264 CfgBuilder]: Building CFG for each procedure with an implementation [2024-10-11 02:26:06,601 INFO L? ?]: Removed 7 outVars from TransFormulas that were not future-live. [2024-10-11 02:26:06,602 INFO L287 CfgBuilder]: Performing block encoding [2024-10-11 02:26:06,631 INFO L309 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-10-11 02:26:06,632 INFO L314 CfgBuilder]: Removed 1 assume(true) statements. [2024-10-11 02:26:06,632 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 11.10 02:26:06 BoogieIcfgContainer [2024-10-11 02:26:06,633 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2024-10-11 02:26:06,638 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2024-10-11 02:26:06,638 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2024-10-11 02:26:06,645 INFO L274 PluginConnector]: TraceAbstraction initialized [2024-10-11 02:26:06,645 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 11.10 02:26:05" (1/3) ... [2024-10-11 02:26:06,646 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@48157c7d and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 11.10 02:26:06, skipping insertion in model container [2024-10-11 02:26:06,646 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.10 02:26:06" (2/3) ... [2024-10-11 02:26:06,646 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@48157c7d and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 11.10 02:26:06, skipping insertion in model container [2024-10-11 02:26:06,646 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 11.10 02:26:06" (3/3) ... [2024-10-11 02:26:06,647 INFO L112 eAbstractionObserver]: Analyzing ICFG prodbin-ll_unwindbound100.c [2024-10-11 02:26:06,666 INFO L209 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2024-10-11 02:26:06,666 INFO L149 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2024-10-11 02:26:06,739 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2024-10-11 02:26:06,747 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;@13e89c75, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2024-10-11 02:26:06,748 INFO L334 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2024-10-11 02:26:06,752 INFO L276 IsEmpty]: Start isEmpty. Operand has 18 states, 13 states have (on average 1.5384615384615385) internal successors, (20), 14 states have internal predecessors, (20), 2 states have call successors, (2), 1 states have call predecessors, (2), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2024-10-11 02:26:06,759 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 9 [2024-10-11 02:26:06,760 INFO L207 NwaCegarLoop]: Found error trace [2024-10-11 02:26:06,761 INFO L215 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1] [2024-10-11 02:26:06,761 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-11 02:26:06,767 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-11 02:26:06,767 INFO L85 PathProgramCache]: Analyzing trace with hash -818250469, now seen corresponding path program 1 times [2024-10-11 02:26:06,775 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-11 02:26:06,778 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [709631782] [2024-10-11 02:26:06,778 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-11 02:26:06,778 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-11 02:26:06,864 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:26:06,918 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-10-11 02:26:06,918 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-11 02:26:06,919 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [709631782] [2024-10-11 02:26:06,920 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [709631782] provided 1 perfect and 0 imperfect interpolant sequences [2024-10-11 02:26:06,920 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-10-11 02:26:06,920 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2024-10-11 02:26:06,923 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [858354894] [2024-10-11 02:26:06,924 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-10-11 02:26:06,928 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2024-10-11 02:26:06,929 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-11 02:26:06,951 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2024-10-11 02:26:06,952 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2024-10-11 02:26:06,954 INFO L87 Difference]: Start difference. First operand has 18 states, 13 states have (on average 1.5384615384615385) internal successors, (20), 14 states have internal predecessors, (20), 2 states have call successors, (2), 1 states have call predecessors, (2), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) Second operand has 2 states, 2 states have (on average 3.5) internal successors, (7), 2 states have internal predecessors, (7), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-10-11 02:26:06,981 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-11 02:26:06,982 INFO L93 Difference]: Finished difference Result 34 states and 47 transitions. [2024-10-11 02:26:06,983 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2024-10-11 02:26:06,984 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 3.5) internal successors, (7), 2 states have internal predecessors, (7), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 8 [2024-10-11 02:26:06,985 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-11 02:26:06,991 INFO L225 Difference]: With dead ends: 34 [2024-10-11 02:26:06,991 INFO L226 Difference]: Without dead ends: 16 [2024-10-11 02:26:06,995 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 2 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 0 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2024-10-11 02:26:06,999 INFO L432 NwaCegarLoop]: 19 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, 19 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:26:07,000 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 19 Invalid, 2 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 2 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-10-11 02:26:07,014 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 16 states. [2024-10-11 02:26:07,025 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 16 to 16. [2024-10-11 02:26:07,026 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 16 states, 12 states have (on average 1.3333333333333333) internal successors, (16), 13 states have internal predecessors, (16), 2 states have call successors, (2), 1 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-10-11 02:26:07,027 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 16 states to 16 states and 19 transitions. [2024-10-11 02:26:07,028 INFO L78 Accepts]: Start accepts. Automaton has 16 states and 19 transitions. Word has length 8 [2024-10-11 02:26:07,028 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-11 02:26:07,028 INFO L471 AbstractCegarLoop]: Abstraction has 16 states and 19 transitions. [2024-10-11 02:26:07,028 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 2 states have (on average 3.5) internal successors, (7), 2 states have internal predecessors, (7), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-10-11 02:26:07,029 INFO L276 IsEmpty]: Start isEmpty. Operand 16 states and 19 transitions. [2024-10-11 02:26:07,029 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 10 [2024-10-11 02:26:07,029 INFO L207 NwaCegarLoop]: Found error trace [2024-10-11 02:26:07,029 INFO L215 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-11 02:26:07,030 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2024-10-11 02:26:07,030 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-11 02:26:07,030 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-11 02:26:07,031 INFO L85 PathProgramCache]: Analyzing trace with hash -1011676302, now seen corresponding path program 1 times [2024-10-11 02:26:07,031 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-11 02:26:07,031 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1942983755] [2024-10-11 02:26:07,031 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-11 02:26:07,031 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-11 02:26:07,050 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:26:07,140 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-10-11 02:26:07,140 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-11 02:26:07,140 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1942983755] [2024-10-11 02:26:07,140 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1942983755] provided 1 perfect and 0 imperfect interpolant sequences [2024-10-11 02:26:07,141 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-10-11 02:26:07,141 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2024-10-11 02:26:07,141 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [143644168] [2024-10-11 02:26:07,141 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-10-11 02:26:07,143 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2024-10-11 02:26:07,143 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-11 02:26:07,144 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2024-10-11 02:26:07,144 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2024-10-11 02:26:07,144 INFO L87 Difference]: Start difference. First operand 16 states and 19 transitions. Second operand has 4 states, 4 states have (on average 2.0) internal successors, (8), 3 states have internal predecessors, (8), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-10-11 02:26:07,173 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-11 02:26:07,173 INFO L93 Difference]: Finished difference Result 25 states and 28 transitions. [2024-10-11 02:26:07,174 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2024-10-11 02:26:07,174 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 2.0) internal successors, (8), 3 states have internal predecessors, (8), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 9 [2024-10-11 02:26:07,174 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-11 02:26:07,175 INFO L225 Difference]: With dead ends: 25 [2024-10-11 02:26:07,175 INFO L226 Difference]: Without dead ends: 18 [2024-10-11 02:26:07,175 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 3 GetRequests, 1 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:26:07,176 INFO L432 NwaCegarLoop]: 16 mSDtfsCounter, 0 mSDsluCounter, 29 mSDsCounter, 0 mSdLazyCounter, 9 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 45 SdHoareTripleChecker+Invalid, 9 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 9 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-10-11 02:26:07,177 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 45 Invalid, 9 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 9 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-10-11 02:26:07,180 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 18 states. [2024-10-11 02:26:07,184 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 18 to 18. [2024-10-11 02:26:07,184 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 18 states, 14 states have (on average 1.2857142857142858) internal successors, (18), 15 states have internal predecessors, (18), 2 states have call successors, (2), 1 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-10-11 02:26:07,184 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 18 states to 18 states and 21 transitions. [2024-10-11 02:26:07,185 INFO L78 Accepts]: Start accepts. Automaton has 18 states and 21 transitions. Word has length 9 [2024-10-11 02:26:07,185 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-11 02:26:07,185 INFO L471 AbstractCegarLoop]: Abstraction has 18 states and 21 transitions. [2024-10-11 02:26:07,185 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 2.0) internal successors, (8), 3 states have internal predecessors, (8), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-10-11 02:26:07,185 INFO L276 IsEmpty]: Start isEmpty. Operand 18 states and 21 transitions. [2024-10-11 02:26:07,186 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 10 [2024-10-11 02:26:07,186 INFO L207 NwaCegarLoop]: Found error trace [2024-10-11 02:26:07,186 INFO L215 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-11 02:26:07,186 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2024-10-11 02:26:07,186 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-11 02:26:07,187 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-11 02:26:07,187 INFO L85 PathProgramCache]: Analyzing trace with hash -1009888842, now seen corresponding path program 1 times [2024-10-11 02:26:07,187 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-11 02:26:07,187 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1829160410] [2024-10-11 02:26:07,187 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-11 02:26:07,188 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-11 02:26:07,215 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-10-11 02:26:07,219 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2128279524] [2024-10-11 02:26:07,220 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-11 02:26:07,220 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-11 02:26:07,220 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 [2024-10-11 02:26:07,222 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:26:07,223 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:26:07,288 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:26:07,290 INFO L255 TraceCheckSpWp]: Trace formula consists of 50 conjuncts, 12 conjuncts are in the unsatisfiable core [2024-10-11 02:26:07,297 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-11 02:26:07,543 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-10-11 02:26:07,544 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-10-11 02:26:07,544 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-11 02:26:07,544 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1829160410] [2024-10-11 02:26:07,545 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-10-11 02:26:07,545 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2128279524] [2024-10-11 02:26:07,545 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2128279524] provided 1 perfect and 0 imperfect interpolant sequences [2024-10-11 02:26:07,545 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-10-11 02:26:07,545 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2024-10-11 02:26:07,545 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [172563305] [2024-10-11 02:26:07,546 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-10-11 02:26:07,546 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2024-10-11 02:26:07,546 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-11 02:26:07,547 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2024-10-11 02:26:07,547 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=12, Invalid=30, Unknown=0, NotChecked=0, Total=42 [2024-10-11 02:26:07,548 INFO L87 Difference]: Start difference. First operand 18 states and 21 transitions. Second operand has 7 states, 7 states have (on average 1.1428571428571428) internal successors, (8), 5 states have internal predecessors, (8), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-10-11 02:26:07,662 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-11 02:26:07,662 INFO L93 Difference]: Finished difference Result 33 states and 38 transitions. [2024-10-11 02:26:07,662 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2024-10-11 02:26:07,663 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 7 states have (on average 1.1428571428571428) internal successors, (8), 5 states have internal predecessors, (8), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 9 [2024-10-11 02:26:07,663 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-11 02:26:07,664 INFO L225 Difference]: With dead ends: 33 [2024-10-11 02:26:07,664 INFO L226 Difference]: Without dead ends: 26 [2024-10-11 02:26:07,664 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 9 GetRequests, 3 SyntacticMatches, 0 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=16, Invalid=40, Unknown=0, NotChecked=0, Total=56 [2024-10-11 02:26:07,665 INFO L432 NwaCegarLoop]: 10 mSDtfsCounter, 16 mSDsluCounter, 36 mSDsCounter, 0 mSdLazyCounter, 52 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 18 SdHoareTripleChecker+Valid, 46 SdHoareTripleChecker+Invalid, 54 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 52 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-10-11 02:26:07,666 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [18 Valid, 46 Invalid, 54 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 52 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-10-11 02:26:07,667 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 26 states. [2024-10-11 02:26:07,670 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 26 to 24. [2024-10-11 02:26:07,671 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 24 states, 18 states have (on average 1.2222222222222223) internal successors, (22), 19 states have internal predecessors, (22), 3 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2024-10-11 02:26:07,671 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 24 states to 24 states and 27 transitions. [2024-10-11 02:26:07,671 INFO L78 Accepts]: Start accepts. Automaton has 24 states and 27 transitions. Word has length 9 [2024-10-11 02:26:07,672 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-11 02:26:07,672 INFO L471 AbstractCegarLoop]: Abstraction has 24 states and 27 transitions. [2024-10-11 02:26:07,672 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 7 states have (on average 1.1428571428571428) internal successors, (8), 5 states have internal predecessors, (8), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-10-11 02:26:07,672 INFO L276 IsEmpty]: Start isEmpty. Operand 24 states and 27 transitions. [2024-10-11 02:26:07,672 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 20 [2024-10-11 02:26:07,673 INFO L207 NwaCegarLoop]: Found error trace [2024-10-11 02:26:07,673 INFO L215 NwaCegarLoop]: trace histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-11 02:26:07,691 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Forceful destruction successful, exit code 0 [2024-10-11 02:26:07,877 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2,2 /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-11 02:26:07,878 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-11 02:26:07,879 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-11 02:26:07,879 INFO L85 PathProgramCache]: Analyzing trace with hash 1083966870, now seen corresponding path program 1 times [2024-10-11 02:26:07,879 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-11 02:26:07,879 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [321261666] [2024-10-11 02:26:07,880 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-11 02:26:07,880 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-11 02:26:07,908 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:26:08,061 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 5 [2024-10-11 02:26:08,064 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:26:08,079 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 2 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-10-11 02:26:08,083 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-11 02:26:08,083 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [321261666] [2024-10-11 02:26:08,083 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [321261666] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-11 02:26:08,084 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1683793476] [2024-10-11 02:26:08,084 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-11 02:26:08,084 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-11 02:26:08,084 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 [2024-10-11 02:26:08,086 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:26:08,088 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:26:08,137 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:26:08,138 INFO L255 TraceCheckSpWp]: Trace formula consists of 75 conjuncts, 5 conjuncts are in the unsatisfiable core [2024-10-11 02:26:08,139 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-11 02:26:08,185 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 2 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-10-11 02:26:08,185 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-11 02:26:08,246 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 2 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-10-11 02:26:08,246 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1683793476] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-11 02:26:08,246 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-10-11 02:26:08,246 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 4, 5] total 10 [2024-10-11 02:26:08,246 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [209041577] [2024-10-11 02:26:08,247 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-10-11 02:26:08,247 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2024-10-11 02:26:08,247 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-11 02:26:08,248 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2024-10-11 02:26:08,249 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=33, Invalid=57, Unknown=0, NotChecked=0, Total=90 [2024-10-11 02:26:08,249 INFO L87 Difference]: Start difference. First operand 24 states and 27 transitions. Second operand has 10 states, 10 states have (on average 3.4) internal successors, (34), 10 states have internal predecessors, (34), 3 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2024-10-11 02:26:08,331 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-11 02:26:08,331 INFO L93 Difference]: Finished difference Result 61 states and 71 transitions. [2024-10-11 02:26:08,332 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2024-10-11 02:26:08,332 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 10 states have (on average 3.4) internal successors, (34), 10 states have internal predecessors, (34), 3 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) Word has length 19 [2024-10-11 02:26:08,332 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-11 02:26:08,333 INFO L225 Difference]: With dead ends: 61 [2024-10-11 02:26:08,333 INFO L226 Difference]: Without dead ends: 54 [2024-10-11 02:26:08,334 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 45 GetRequests, 35 SyntacticMatches, 0 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 15 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=46, Invalid=86, Unknown=0, NotChecked=0, Total=132 [2024-10-11 02:26:08,335 INFO L432 NwaCegarLoop]: 16 mSDtfsCounter, 25 mSDsluCounter, 98 mSDsCounter, 0 mSdLazyCounter, 39 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 25 SdHoareTripleChecker+Valid, 114 SdHoareTripleChecker+Invalid, 40 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 39 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-10-11 02:26:08,335 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [25 Valid, 114 Invalid, 40 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 39 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-10-11 02:26:08,336 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 54 states. [2024-10-11 02:26:08,342 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 54 to 50. [2024-10-11 02:26:08,342 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 50 states, 38 states have (on average 1.2894736842105263) internal successors, (49), 41 states have internal predecessors, (49), 7 states have call successors, (7), 4 states have call predecessors, (7), 4 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) [2024-10-11 02:26:08,345 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 50 states to 50 states and 60 transitions. [2024-10-11 02:26:08,345 INFO L78 Accepts]: Start accepts. Automaton has 50 states and 60 transitions. Word has length 19 [2024-10-11 02:26:08,346 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-11 02:26:08,346 INFO L471 AbstractCegarLoop]: Abstraction has 50 states and 60 transitions. [2024-10-11 02:26:08,346 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 10 states have (on average 3.4) internal successors, (34), 10 states have internal predecessors, (34), 3 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2024-10-11 02:26:08,346 INFO L276 IsEmpty]: Start isEmpty. Operand 50 states and 60 transitions. [2024-10-11 02:26:08,347 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 20 [2024-10-11 02:26:08,347 INFO L207 NwaCegarLoop]: Found error trace [2024-10-11 02:26:08,347 INFO L215 NwaCegarLoop]: trace histogram [2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-11 02:26:08,359 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2024-10-11 02:26:08,548 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,3 /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-11 02:26:08,548 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-11 02:26:08,549 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-11 02:26:08,549 INFO L85 PathProgramCache]: Analyzing trace with hash 1085754330, now seen corresponding path program 1 times [2024-10-11 02:26:08,549 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-11 02:26:08,549 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [666114460] [2024-10-11 02:26:08,549 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-11 02:26:08,549 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-11 02:26:08,577 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-10-11 02:26:08,578 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [319658816] [2024-10-11 02:26:08,578 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-11 02:26:08,578 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-11 02:26:08,579 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 [2024-10-11 02:26:08,583 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:26:08,585 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:26:08,633 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:26:08,634 INFO L255 TraceCheckSpWp]: Trace formula consists of 75 conjuncts, 27 conjuncts are in the unsatisfiable core [2024-10-11 02:26:08,636 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-11 02:26:08,976 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 1 proven. 4 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-10-11 02:26:08,977 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-11 02:26:10,530 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 4 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-10-11 02:26:10,530 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-11 02:26:10,530 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [666114460] [2024-10-11 02:26:10,530 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-10-11 02:26:10,531 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [319658816] [2024-10-11 02:26:10,531 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [319658816] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-11 02:26:10,531 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-10-11 02:26:10,531 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 8] total 15 [2024-10-11 02:26:10,531 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1901738849] [2024-10-11 02:26:10,531 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-10-11 02:26:10,532 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 15 states [2024-10-11 02:26:10,532 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-11 02:26:10,533 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2024-10-11 02:26:10,533 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=43, Invalid=167, Unknown=0, NotChecked=0, Total=210 [2024-10-11 02:26:10,533 INFO L87 Difference]: Start difference. First operand 50 states and 60 transitions. Second operand has 15 states, 15 states have (on average 1.8666666666666667) internal successors, (28), 14 states have internal predecessors, (28), 4 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2024-10-11 02:26:11,613 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-11 02:26:11,613 INFO L93 Difference]: Finished difference Result 83 states and 98 transitions. [2024-10-11 02:26:11,613 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2024-10-11 02:26:11,614 INFO L78 Accepts]: Start accepts. Automaton has has 15 states, 15 states have (on average 1.8666666666666667) internal successors, (28), 14 states have internal predecessors, (28), 4 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) Word has length 19 [2024-10-11 02:26:11,614 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-11 02:26:11,617 INFO L225 Difference]: With dead ends: 83 [2024-10-11 02:26:11,618 INFO L226 Difference]: Without dead ends: 81 [2024-10-11 02:26:11,619 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 39 GetRequests, 23 SyntacticMatches, 0 SemanticMatches, 16 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 33 ImplicationChecksByTransitivity, 1.2s TimeCoverageRelationStatistics Valid=64, Invalid=242, Unknown=0, NotChecked=0, Total=306 [2024-10-11 02:26:11,620 INFO L432 NwaCegarLoop]: 13 mSDtfsCounter, 13 mSDsluCounter, 76 mSDsCounter, 0 mSdLazyCounter, 116 mSolverCounterSat, 7 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.9s Time, 0 mProtectedPredicate, 0 mProtectedAction, 14 SdHoareTripleChecker+Valid, 89 SdHoareTripleChecker+Invalid, 123 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 7 IncrementalHoareTripleChecker+Valid, 116 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.0s IncrementalHoareTripleChecker+Time [2024-10-11 02:26:11,621 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [14 Valid, 89 Invalid, 123 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [7 Valid, 116 Invalid, 0 Unknown, 0 Unchecked, 1.0s Time] [2024-10-11 02:26:11,621 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 81 states. [2024-10-11 02:26:11,631 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 81 to 79. [2024-10-11 02:26:11,632 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 79 states, 61 states have (on average 1.2295081967213115) internal successors, (75), 66 states have internal predecessors, (75), 10 states have call successors, (10), 7 states have call predecessors, (10), 7 states have return successors, (7), 5 states have call predecessors, (7), 7 states have call successors, (7) [2024-10-11 02:26:11,634 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 79 states to 79 states and 92 transitions. [2024-10-11 02:26:11,634 INFO L78 Accepts]: Start accepts. Automaton has 79 states and 92 transitions. Word has length 19 [2024-10-11 02:26:11,634 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-11 02:26:11,634 INFO L471 AbstractCegarLoop]: Abstraction has 79 states and 92 transitions. [2024-10-11 02:26:11,635 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 15 states, 15 states have (on average 1.8666666666666667) internal successors, (28), 14 states have internal predecessors, (28), 4 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2024-10-11 02:26:11,635 INFO L276 IsEmpty]: Start isEmpty. Operand 79 states and 92 transitions. [2024-10-11 02:26:11,635 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 20 [2024-10-11 02:26:11,635 INFO L207 NwaCegarLoop]: Found error trace [2024-10-11 02:26:11,636 INFO L215 NwaCegarLoop]: trace histogram [2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-11 02:26:11,653 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:26:11,836 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,4 /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-11 02:26:11,837 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-11 02:26:11,837 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-11 02:26:11,837 INFO L85 PathProgramCache]: Analyzing trace with hash 276407704, now seen corresponding path program 1 times [2024-10-11 02:26:11,837 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-11 02:26:11,837 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [924122927] [2024-10-11 02:26:11,838 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-11 02:26:11,838 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-11 02:26:11,856 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-10-11 02:26:11,857 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1699810696] [2024-10-11 02:26:11,857 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-11 02:26:11,857 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-11 02:26:11,858 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 [2024-10-11 02:26:11,859 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:26:11,865 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:26:11,907 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:26:11,908 INFO L255 TraceCheckSpWp]: Trace formula consists of 70 conjuncts, 17 conjuncts are in the unsatisfiable core [2024-10-11 02:26:11,910 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-11 02:26:12,445 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 1 proven. 4 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-10-11 02:26:12,445 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-11 02:26:13,097 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-11 02:26:13,097 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [924122927] [2024-10-11 02:26:13,097 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-10-11 02:26:13,097 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1699810696] [2024-10-11 02:26:13,098 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1699810696] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-11 02:26:13,098 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-10-11 02:26:13,098 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12] total 12 [2024-10-11 02:26:13,098 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1779831401] [2024-10-11 02:26:13,098 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-10-11 02:26:13,098 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2024-10-11 02:26:13,098 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-11 02:26:13,099 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2024-10-11 02:26:13,100 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=49, Invalid=191, Unknown=0, NotChecked=0, Total=240 [2024-10-11 02:26:13,101 INFO L87 Difference]: Start difference. First operand 79 states and 92 transitions. Second operand has 12 states, 12 states have (on average 1.3333333333333333) internal successors, (16), 10 states have internal predecessors, (16), 2 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-10-11 02:26:15,203 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.47s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [0] [2024-10-11 02:26:15,304 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-11 02:26:15,304 INFO L93 Difference]: Finished difference Result 90 states and 102 transitions. [2024-10-11 02:26:15,305 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2024-10-11 02:26:15,305 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 12 states have (on average 1.3333333333333333) internal successors, (16), 10 states have internal predecessors, (16), 2 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 19 [2024-10-11 02:26:15,305 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-11 02:26:15,306 INFO L225 Difference]: With dead ends: 90 [2024-10-11 02:26:15,306 INFO L226 Difference]: Without dead ends: 81 [2024-10-11 02:26:15,307 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 29 GetRequests, 12 SyntacticMatches, 2 SemanticMatches, 15 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 52 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=55, Invalid=217, Unknown=0, NotChecked=0, Total=272 [2024-10-11 02:26:15,307 INFO L432 NwaCegarLoop]: 12 mSDtfsCounter, 17 mSDsluCounter, 65 mSDsCounter, 0 mSdLazyCounter, 137 mSolverCounterSat, 4 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 2.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 19 SdHoareTripleChecker+Valid, 77 SdHoareTripleChecker+Invalid, 141 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 4 IncrementalHoareTripleChecker+Valid, 137 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 2.2s IncrementalHoareTripleChecker+Time [2024-10-11 02:26:15,308 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [19 Valid, 77 Invalid, 141 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [4 Valid, 137 Invalid, 0 Unknown, 0 Unchecked, 2.2s Time] [2024-10-11 02:26:15,309 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 81 states. [2024-10-11 02:26:15,325 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 81 to 81. [2024-10-11 02:26:15,327 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 81 states, 63 states have (on average 1.1904761904761905) internal successors, (75), 67 states have internal predecessors, (75), 10 states have call successors, (10), 8 states have call predecessors, (10), 7 states have return successors, (7), 5 states have call predecessors, (7), 7 states have call successors, (7) [2024-10-11 02:26:15,329 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 81 states to 81 states and 92 transitions. [2024-10-11 02:26:15,330 INFO L78 Accepts]: Start accepts. Automaton has 81 states and 92 transitions. Word has length 19 [2024-10-11 02:26:15,331 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-11 02:26:15,331 INFO L471 AbstractCegarLoop]: Abstraction has 81 states and 92 transitions. [2024-10-11 02:26:15,331 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 12 states have (on average 1.3333333333333333) internal successors, (16), 10 states have internal predecessors, (16), 2 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-10-11 02:26:15,331 INFO L276 IsEmpty]: Start isEmpty. Operand 81 states and 92 transitions. [2024-10-11 02:26:15,332 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 26 [2024-10-11 02:26:15,332 INFO L207 NwaCegarLoop]: Found error trace [2024-10-11 02:26:15,332 INFO L215 NwaCegarLoop]: trace histogram [3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-11 02:26:15,349 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Forceful destruction successful, exit code 0 [2024-10-11 02:26:15,536 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,SelfDestructingSolverStorable5 [2024-10-11 02:26:15,537 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-11 02:26:15,538 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-11 02:26:15,538 INFO L85 PathProgramCache]: Analyzing trace with hash -2037077519, now seen corresponding path program 1 times [2024-10-11 02:26:15,538 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-11 02:26:15,538 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1403356976] [2024-10-11 02:26:15,538 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-11 02:26:15,538 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-11 02:26:15,572 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-10-11 02:26:15,575 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1043093089] [2024-10-11 02:26:15,577 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-11 02:26:15,577 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-11 02:26:15,578 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 [2024-10-11 02:26:15,579 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:26:15,582 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:26:15,621 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:26:15,622 INFO L255 TraceCheckSpWp]: Trace formula consists of 86 conjuncts, 14 conjuncts are in the unsatisfiable core [2024-10-11 02:26:15,624 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-11 02:26:15,682 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 7 proven. 1 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-10-11 02:26:15,683 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-11 02:26:15,749 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 7 proven. 1 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-10-11 02:26:15,750 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-11 02:26:15,750 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1403356976] [2024-10-11 02:26:15,750 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-10-11 02:26:15,750 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1043093089] [2024-10-11 02:26:15,750 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1043093089] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-11 02:26:15,750 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-10-11 02:26:15,750 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 7] total 11 [2024-10-11 02:26:15,751 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [167550984] [2024-10-11 02:26:15,751 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-10-11 02:26:15,751 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 11 states [2024-10-11 02:26:15,751 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-11 02:26:15,752 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2024-10-11 02:26:15,752 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=27, Invalid=83, Unknown=0, NotChecked=0, Total=110 [2024-10-11 02:26:15,752 INFO L87 Difference]: Start difference. First operand 81 states and 92 transitions. Second operand has 11 states, 10 states have (on average 2.3) internal successors, (23), 8 states have internal predecessors, (23), 2 states have call successors, (3), 3 states have call predecessors, (3), 2 states have return successors, (3), 3 states have call predecessors, (3), 1 states have call successors, (3) [2024-10-11 02:26:15,855 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-11 02:26:15,856 INFO L93 Difference]: Finished difference Result 93 states and 103 transitions. [2024-10-11 02:26:15,856 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2024-10-11 02:26:15,856 INFO L78 Accepts]: Start accepts. Automaton has has 11 states, 10 states have (on average 2.3) internal successors, (23), 8 states have internal predecessors, (23), 2 states have call successors, (3), 3 states have call predecessors, (3), 2 states have return successors, (3), 3 states have call predecessors, (3), 1 states have call successors, (3) Word has length 25 [2024-10-11 02:26:15,857 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-11 02:26:15,857 INFO L225 Difference]: With dead ends: 93 [2024-10-11 02:26:15,859 INFO L226 Difference]: Without dead ends: 78 [2024-10-11 02:26:15,860 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 49 GetRequests, 39 SyntacticMatches, 0 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 15 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=35, Invalid=97, Unknown=0, NotChecked=0, Total=132 [2024-10-11 02:26:15,860 INFO L432 NwaCegarLoop]: 12 mSDtfsCounter, 7 mSDsluCounter, 61 mSDsCounter, 0 mSdLazyCounter, 78 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 7 SdHoareTripleChecker+Valid, 73 SdHoareTripleChecker+Invalid, 79 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 78 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-10-11 02:26:15,861 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [7 Valid, 73 Invalid, 79 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 78 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-10-11 02:26:15,861 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 78 states. [2024-10-11 02:26:15,875 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 78 to 77. [2024-10-11 02:26:15,876 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 77 states, 61 states have (on average 1.1475409836065573) internal successors, (70), 64 states have internal predecessors, (70), 8 states have call successors, (8), 7 states have call predecessors, (8), 7 states have return successors, (7), 5 states have call predecessors, (7), 7 states have call successors, (7) [2024-10-11 02:26:15,877 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 77 states to 77 states and 85 transitions. [2024-10-11 02:26:15,878 INFO L78 Accepts]: Start accepts. Automaton has 77 states and 85 transitions. Word has length 25 [2024-10-11 02:26:15,880 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-11 02:26:15,880 INFO L471 AbstractCegarLoop]: Abstraction has 77 states and 85 transitions. [2024-10-11 02:26:15,880 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 11 states, 10 states have (on average 2.3) internal successors, (23), 8 states have internal predecessors, (23), 2 states have call successors, (3), 3 states have call predecessors, (3), 2 states have return successors, (3), 3 states have call predecessors, (3), 1 states have call successors, (3) [2024-10-11 02:26:15,880 INFO L276 IsEmpty]: Start isEmpty. Operand 77 states and 85 transitions. [2024-10-11 02:26:15,881 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 30 [2024-10-11 02:26:15,881 INFO L207 NwaCegarLoop]: Found error trace [2024-10-11 02:26:15,881 INFO L215 NwaCegarLoop]: trace histogram [3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1] [2024-10-11 02:26:15,898 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:26:16,085 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,6 /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-11 02:26:16,086 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-11 02:26:16,087 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-11 02:26:16,087 INFO L85 PathProgramCache]: Analyzing trace with hash 1530857210, now seen corresponding path program 2 times [2024-10-11 02:26:16,087 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-11 02:26:16,087 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1108681129] [2024-10-11 02:26:16,087 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-11 02:26:16,087 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-11 02:26:16,118 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-10-11 02:26:16,123 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [567483712] [2024-10-11 02:26:16,123 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-10-11 02:26:16,123 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-11 02:26:16,123 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 [2024-10-11 02:26:16,128 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:26:16,129 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:26:16,171 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-10-11 02:26:16,171 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2024-10-11 02:26:16,172 INFO L255 TraceCheckSpWp]: Trace formula consists of 90 conjuncts, 27 conjuncts are in the unsatisfiable core [2024-10-11 02:26:16,174 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-11 02:26:17,919 INFO L134 CoverageAnalysis]: Checked inductivity of 20 backedges. 6 proven. 13 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2024-10-11 02:26:17,919 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-11 02:26:20,068 INFO L134 CoverageAnalysis]: Checked inductivity of 20 backedges. 6 proven. 13 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2024-10-11 02:26:20,068 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-11 02:26:20,069 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1108681129] [2024-10-11 02:26:20,069 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-10-11 02:26:20,069 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [567483712] [2024-10-11 02:26:20,069 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [567483712] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-11 02:26:20,069 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-10-11 02:26:20,069 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 13] total 21 [2024-10-11 02:26:20,069 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2020384813] [2024-10-11 02:26:20,069 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-10-11 02:26:20,069 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 21 states [2024-10-11 02:26:20,070 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-11 02:26:20,070 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2024-10-11 02:26:20,070 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=89, Invalid=331, Unknown=0, NotChecked=0, Total=420 [2024-10-11 02:26:20,070 INFO L87 Difference]: Start difference. First operand 77 states and 85 transitions. Second operand has 21 states, 21 states have (on average 1.9523809523809523) internal successors, (41), 20 states have internal predecessors, (41), 6 states have call successors, (6), 2 states have call predecessors, (6), 2 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) [2024-10-11 02:26:22,214 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-11 02:26:22,215 INFO L93 Difference]: Finished difference Result 112 states and 129 transitions. [2024-10-11 02:26:22,215 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 19 states. [2024-10-11 02:26:22,216 INFO L78 Accepts]: Start accepts. Automaton has has 21 states, 21 states have (on average 1.9523809523809523) internal successors, (41), 20 states have internal predecessors, (41), 6 states have call successors, (6), 2 states have call predecessors, (6), 2 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) Word has length 29 [2024-10-11 02:26:22,216 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-11 02:26:22,217 INFO L225 Difference]: With dead ends: 112 [2024-10-11 02:26:22,217 INFO L226 Difference]: Without dead ends: 110 [2024-10-11 02:26:22,218 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 63 GetRequests, 34 SyntacticMatches, 3 SemanticMatches, 26 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 171 ImplicationChecksByTransitivity, 2.7s TimeCoverageRelationStatistics Valid=182, Invalid=574, Unknown=0, NotChecked=0, Total=756 [2024-10-11 02:26:22,218 INFO L432 NwaCegarLoop]: 13 mSDtfsCounter, 34 mSDsluCounter, 99 mSDsCounter, 0 mSdLazyCounter, 185 mSolverCounterSat, 19 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.7s Time, 0 mProtectedPredicate, 0 mProtectedAction, 36 SdHoareTripleChecker+Valid, 112 SdHoareTripleChecker+Invalid, 204 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 19 IncrementalHoareTripleChecker+Valid, 185 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.7s IncrementalHoareTripleChecker+Time [2024-10-11 02:26:22,218 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [36 Valid, 112 Invalid, 204 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [19 Valid, 185 Invalid, 0 Unknown, 0 Unchecked, 0.7s Time] [2024-10-11 02:26:22,219 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 110 states. [2024-10-11 02:26:22,234 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 110 to 108. [2024-10-11 02:26:22,234 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 108 states, 87 states have (on average 1.160919540229885) internal successors, (101), 90 states have internal predecessors, (101), 12 states have call successors, (12), 8 states have call predecessors, (12), 8 states have return successors, (11), 9 states have call predecessors, (11), 11 states have call successors, (11) [2024-10-11 02:26:22,235 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 108 states to 108 states and 124 transitions. [2024-10-11 02:26:22,236 INFO L78 Accepts]: Start accepts. Automaton has 108 states and 124 transitions. Word has length 29 [2024-10-11 02:26:22,236 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-11 02:26:22,236 INFO L471 AbstractCegarLoop]: Abstraction has 108 states and 124 transitions. [2024-10-11 02:26:22,237 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 21 states, 21 states have (on average 1.9523809523809523) internal successors, (41), 20 states have internal predecessors, (41), 6 states have call successors, (6), 2 states have call predecessors, (6), 2 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) [2024-10-11 02:26:22,237 INFO L276 IsEmpty]: Start isEmpty. Operand 108 states and 124 transitions. [2024-10-11 02:26:22,238 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 40 [2024-10-11 02:26:22,239 INFO L207 NwaCegarLoop]: Found error trace [2024-10-11 02:26:22,239 INFO L215 NwaCegarLoop]: trace histogram [4, 4, 4, 4, 3, 3, 3, 3, 3, 2, 1, 1, 1, 1, 1, 1] [2024-10-11 02:26:22,256 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Forceful destruction successful, exit code 0 [2024-10-11 02:26:22,439 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,SelfDestructingSolverStorable7 [2024-10-11 02:26:22,440 INFO L396 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-11 02:26:22,440 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-11 02:26:22,440 INFO L85 PathProgramCache]: Analyzing trace with hash 2036959006, now seen corresponding path program 1 times [2024-10-11 02:26:22,440 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-11 02:26:22,440 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1371085774] [2024-10-11 02:26:22,440 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-11 02:26:22,440 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-11 02:26:22,467 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-10-11 02:26:22,468 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1890109859] [2024-10-11 02:26:22,468 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-11 02:26:22,468 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-11 02:26:22,469 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 [2024-10-11 02:26:22,475 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:26:22,476 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:26:22,522 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:26:22,523 INFO L255 TraceCheckSpWp]: Trace formula consists of 115 conjuncts, 31 conjuncts are in the unsatisfiable core [2024-10-11 02:26:22,525 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-11 02:26:23,100 INFO L134 CoverageAnalysis]: Checked inductivity of 45 backedges. 11 proven. 28 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2024-10-11 02:26:23,100 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-11 02:26:23,619 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-11 02:26:23,619 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1371085774] [2024-10-11 02:26:23,619 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-10-11 02:26:23,620 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1890109859] [2024-10-11 02:26:23,620 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1890109859] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-11 02:26:23,620 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-10-11 02:26:23,620 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [14] total 14 [2024-10-11 02:26:23,620 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [726951088] [2024-10-11 02:26:23,620 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-10-11 02:26:23,620 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2024-10-11 02:26:23,621 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-11 02:26:23,621 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2024-10-11 02:26:23,621 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=55, Invalid=287, Unknown=0, NotChecked=0, Total=342 [2024-10-11 02:26:23,621 INFO L87 Difference]: Start difference. First operand 108 states and 124 transitions. Second operand has 14 states, 14 states have (on average 2.0714285714285716) internal successors, (29), 13 states have internal predecessors, (29), 4 states have call successors, (4), 2 states have call predecessors, (4), 2 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2024-10-11 02:26:23,963 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-11 02:26:23,963 INFO L93 Difference]: Finished difference Result 118 states and 135 transitions. [2024-10-11 02:26:23,963 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2024-10-11 02:26:23,964 INFO L78 Accepts]: Start accepts. Automaton has has 14 states, 14 states have (on average 2.0714285714285716) internal successors, (29), 13 states have internal predecessors, (29), 4 states have call successors, (4), 2 states have call predecessors, (4), 2 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) Word has length 39 [2024-10-11 02:26:23,964 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-11 02:26:23,966 INFO L225 Difference]: With dead ends: 118 [2024-10-11 02:26:23,966 INFO L226 Difference]: Without dead ends: 116 [2024-10-11 02:26:23,966 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 49 GetRequests, 31 SyntacticMatches, 0 SemanticMatches, 18 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 50 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=62, Invalid=318, Unknown=0, NotChecked=0, Total=380 [2024-10-11 02:26:23,967 INFO L432 NwaCegarLoop]: 20 mSDtfsCounter, 6 mSDsluCounter, 183 mSDsCounter, 0 mSdLazyCounter, 308 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 7 SdHoareTripleChecker+Valid, 203 SdHoareTripleChecker+Invalid, 308 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 308 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2024-10-11 02:26:23,967 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [7 Valid, 203 Invalid, 308 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 308 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2024-10-11 02:26:23,968 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 116 states. [2024-10-11 02:26:23,985 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 116 to 113. [2024-10-11 02:26:23,985 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 113 states, 90 states have (on average 1.1555555555555554) internal successors, (104), 94 states have internal predecessors, (104), 13 states have call successors, (13), 9 states have call predecessors, (13), 9 states have return successors, (12), 9 states have call predecessors, (12), 12 states have call successors, (12) [2024-10-11 02:26:23,986 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 113 states to 113 states and 129 transitions. [2024-10-11 02:26:23,986 INFO L78 Accepts]: Start accepts. Automaton has 113 states and 129 transitions. Word has length 39 [2024-10-11 02:26:23,986 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-11 02:26:23,987 INFO L471 AbstractCegarLoop]: Abstraction has 113 states and 129 transitions. [2024-10-11 02:26:23,987 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 14 states, 14 states have (on average 2.0714285714285716) internal successors, (29), 13 states have internal predecessors, (29), 4 states have call successors, (4), 2 states have call predecessors, (4), 2 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2024-10-11 02:26:23,987 INFO L276 IsEmpty]: Start isEmpty. Operand 113 states and 129 transitions. [2024-10-11 02:26:23,988 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 50 [2024-10-11 02:26:23,988 INFO L207 NwaCegarLoop]: Found error trace [2024-10-11 02:26:23,988 INFO L215 NwaCegarLoop]: trace histogram [5, 5, 4, 4, 4, 4, 4, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1] [2024-10-11 02:26:24,004 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:26:24,192 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,8 /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-11 02:26:24,193 INFO L396 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-11 02:26:24,193 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-11 02:26:24,193 INFO L85 PathProgramCache]: Analyzing trace with hash 1536935426, now seen corresponding path program 2 times [2024-10-11 02:26:24,193 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-11 02:26:24,194 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [439624998] [2024-10-11 02:26:24,194 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-11 02:26:24,194 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-11 02:26:24,222 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:26:24,410 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 5 [2024-10-11 02:26:24,412 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:26:24,419 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 15 [2024-10-11 02:26:24,421 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:26:24,423 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 25 [2024-10-11 02:26:24,428 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:26:24,431 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 35 [2024-10-11 02:26:24,433 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:26:24,436 INFO L134 CoverageAnalysis]: Checked inductivity of 76 backedges. 8 proven. 44 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2024-10-11 02:26:24,437 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-11 02:26:24,437 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [439624998] [2024-10-11 02:26:24,437 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [439624998] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-11 02:26:24,437 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1190837524] [2024-10-11 02:26:24,437 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-10-11 02:26:24,438 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-11 02:26:24,438 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 [2024-10-11 02:26:24,439 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:26:24,441 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:26:24,497 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-10-11 02:26:24,497 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2024-10-11 02:26:24,498 INFO L255 TraceCheckSpWp]: Trace formula consists of 150 conjuncts, 11 conjuncts are in the unsatisfiable core [2024-10-11 02:26:24,500 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-11 02:26:24,560 INFO L134 CoverageAnalysis]: Checked inductivity of 76 backedges. 8 proven. 68 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-10-11 02:26:24,561 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-11 02:26:24,664 INFO L134 CoverageAnalysis]: Checked inductivity of 76 backedges. 8 proven. 44 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2024-10-11 02:26:24,664 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1190837524] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-11 02:26:24,664 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-10-11 02:26:24,664 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 7, 8] total 16 [2024-10-11 02:26:24,664 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [782596830] [2024-10-11 02:26:24,665 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-10-11 02:26:24,665 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2024-10-11 02:26:24,665 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-11 02:26:24,666 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2024-10-11 02:26:24,666 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=96, Invalid=144, Unknown=0, NotChecked=0, Total=240 [2024-10-11 02:26:24,666 INFO L87 Difference]: Start difference. First operand 113 states and 129 transitions. Second operand has 16 states, 16 states have (on average 4.5625) internal successors, (73), 16 states have internal predecessors, (73), 9 states have call successors, (13), 6 states have call predecessors, (13), 5 states have return successors, (12), 8 states have call predecessors, (12), 8 states have call successors, (12) [2024-10-11 02:26:24,792 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-11 02:26:24,792 INFO L93 Difference]: Finished difference Result 293 states and 338 transitions. [2024-10-11 02:26:24,792 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 22 states. [2024-10-11 02:26:24,792 INFO L78 Accepts]: Start accepts. Automaton has has 16 states, 16 states have (on average 4.5625) internal successors, (73), 16 states have internal predecessors, (73), 9 states have call successors, (13), 6 states have call predecessors, (13), 5 states have return successors, (12), 8 states have call predecessors, (12), 8 states have call successors, (12) Word has length 49 [2024-10-11 02:26:24,796 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-11 02:26:24,798 INFO L225 Difference]: With dead ends: 293 [2024-10-11 02:26:24,798 INFO L226 Difference]: Without dead ends: 286 [2024-10-11 02:26:24,799 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 120 GetRequests, 98 SyntacticMatches, 0 SemanticMatches, 22 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 75 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=196, Invalid=356, Unknown=0, NotChecked=0, Total=552 [2024-10-11 02:26:24,800 INFO L432 NwaCegarLoop]: 15 mSDtfsCounter, 68 mSDsluCounter, 136 mSDsCounter, 0 mSdLazyCounter, 57 mSolverCounterSat, 4 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 68 SdHoareTripleChecker+Valid, 151 SdHoareTripleChecker+Invalid, 61 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 4 IncrementalHoareTripleChecker+Valid, 57 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-10-11 02:26:24,800 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [68 Valid, 151 Invalid, 61 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [4 Valid, 57 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-10-11 02:26:24,801 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 286 states. [2024-10-11 02:26:24,832 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 286 to 276. [2024-10-11 02:26:24,833 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 276 states, 219 states have (on average 1.1369863013698631) internal successors, (249), 228 states have internal predecessors, (249), 30 states have call successors, (30), 26 states have call predecessors, (30), 26 states have return successors, (29), 21 states have call predecessors, (29), 29 states have call successors, (29) [2024-10-11 02:26:24,834 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 276 states to 276 states and 308 transitions. [2024-10-11 02:26:24,834 INFO L78 Accepts]: Start accepts. Automaton has 276 states and 308 transitions. Word has length 49 [2024-10-11 02:26:24,834 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-11 02:26:24,835 INFO L471 AbstractCegarLoop]: Abstraction has 276 states and 308 transitions. [2024-10-11 02:26:24,835 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 16 states, 16 states have (on average 4.5625) internal successors, (73), 16 states have internal predecessors, (73), 9 states have call successors, (13), 6 states have call predecessors, (13), 5 states have return successors, (12), 8 states have call predecessors, (12), 8 states have call successors, (12) [2024-10-11 02:26:24,835 INFO L276 IsEmpty]: Start isEmpty. Operand 276 states and 308 transitions. [2024-10-11 02:26:24,836 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 50 [2024-10-11 02:26:24,836 INFO L207 NwaCegarLoop]: Found error trace [2024-10-11 02:26:24,836 INFO L215 NwaCegarLoop]: trace histogram [5, 5, 5, 5, 4, 4, 4, 4, 4, 2, 2, 1, 1, 1, 1, 1] [2024-10-11 02:26:24,849 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:26:25,039 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,SelfDestructingSolverStorable9 [2024-10-11 02:26:25,039 INFO L396 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-11 02:26:25,039 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-11 02:26:25,040 INFO L85 PathProgramCache]: Analyzing trace with hash -1264768446, now seen corresponding path program 2 times [2024-10-11 02:26:25,040 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-11 02:26:25,040 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [132915089] [2024-10-11 02:26:25,040 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-11 02:26:25,040 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-11 02:26:25,075 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-10-11 02:26:25,077 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1936606407] [2024-10-11 02:26:25,077 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-10-11 02:26:25,077 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-11 02:26:25,077 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 [2024-10-11 02:26:25,079 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:26:25,081 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:26:25,136 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-10-11 02:26:25,136 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2024-10-11 02:26:25,137 INFO L255 TraceCheckSpWp]: Trace formula consists of 140 conjuncts, 32 conjuncts are in the unsatisfiable core [2024-10-11 02:26:25,141 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-11 02:26:26,090 INFO L134 CoverageAnalysis]: Checked inductivity of 80 backedges. 10 proven. 55 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2024-10-11 02:26:26,090 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-11 02:26:44,205 INFO L134 CoverageAnalysis]: Checked inductivity of 80 backedges. 37 proven. 25 refuted. 0 times theorem prover too weak. 18 trivial. 0 not checked. [2024-10-11 02:26:44,205 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-11 02:26:44,205 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [132915089] [2024-10-11 02:26:44,205 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-10-11 02:26:44,205 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1936606407] [2024-10-11 02:26:44,205 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1936606407] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-11 02:26:44,205 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-10-11 02:26:44,205 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 13] total 24 [2024-10-11 02:26:44,206 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1709745781] [2024-10-11 02:26:44,206 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-10-11 02:26:44,206 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 24 states [2024-10-11 02:26:44,206 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-11 02:26:44,207 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 24 interpolants. [2024-10-11 02:26:44,207 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=96, Invalid=456, Unknown=0, NotChecked=0, Total=552 [2024-10-11 02:26:44,207 INFO L87 Difference]: Start difference. First operand 276 states and 308 transitions. Second operand has 24 states, 24 states have (on average 2.375) internal successors, (57), 22 states have internal predecessors, (57), 9 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (8), 8 states have call predecessors, (8), 7 states have call successors, (8) [2024-10-11 02:26:52,646 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.13s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-10-11 02:27:08,011 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-11 02:27:08,011 INFO L93 Difference]: Finished difference Result 397 states and 451 transitions. [2024-10-11 02:27:08,012 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 27 states. [2024-10-11 02:27:08,012 INFO L78 Accepts]: Start accepts. Automaton has has 24 states, 24 states have (on average 2.375) internal successors, (57), 22 states have internal predecessors, (57), 9 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (8), 8 states have call predecessors, (8), 7 states have call successors, (8) Word has length 49 [2024-10-11 02:27:08,012 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-11 02:27:08,015 INFO L225 Difference]: With dead ends: 397 [2024-10-11 02:27:08,015 INFO L226 Difference]: Without dead ends: 395 [2024-10-11 02:27:08,016 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 112 GetRequests, 76 SyntacticMatches, 2 SemanticMatches, 34 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 243 ImplicationChecksByTransitivity, 27.4s TimeCoverageRelationStatistics Valid=243, Invalid=1017, Unknown=0, NotChecked=0, Total=1260 [2024-10-11 02:27:08,017 INFO L432 NwaCegarLoop]: 21 mSDtfsCounter, 27 mSDsluCounter, 208 mSDsCounter, 0 mSdLazyCounter, 336 mSolverCounterSat, 26 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 6.8s Time, 0 mProtectedPredicate, 0 mProtectedAction, 28 SdHoareTripleChecker+Valid, 229 SdHoareTripleChecker+Invalid, 362 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 26 IncrementalHoareTripleChecker+Valid, 336 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 6.8s IncrementalHoareTripleChecker+Time [2024-10-11 02:27:08,017 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [28 Valid, 229 Invalid, 362 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [26 Valid, 336 Invalid, 0 Unknown, 0 Unchecked, 6.8s Time] [2024-10-11 02:27:08,018 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 395 states. [2024-10-11 02:27:08,064 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 395 to 391. [2024-10-11 02:27:08,065 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 391 states, 312 states have (on average 1.1378205128205128) internal successors, (355), 322 states have internal predecessors, (355), 43 states have call successors, (43), 35 states have call predecessors, (43), 35 states have return successors, (42), 33 states have call predecessors, (42), 42 states have call successors, (42) [2024-10-11 02:27:08,067 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 391 states to 391 states and 440 transitions. [2024-10-11 02:27:08,067 INFO L78 Accepts]: Start accepts. Automaton has 391 states and 440 transitions. Word has length 49 [2024-10-11 02:27:08,067 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-11 02:27:08,067 INFO L471 AbstractCegarLoop]: Abstraction has 391 states and 440 transitions. [2024-10-11 02:27:08,068 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 24 states, 24 states have (on average 2.375) internal successors, (57), 22 states have internal predecessors, (57), 9 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (8), 8 states have call predecessors, (8), 7 states have call successors, (8) [2024-10-11 02:27:08,068 INFO L276 IsEmpty]: Start isEmpty. Operand 391 states and 440 transitions. [2024-10-11 02:27:08,069 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 50 [2024-10-11 02:27:08,069 INFO L207 NwaCegarLoop]: Found error trace [2024-10-11 02:27:08,069 INFO L215 NwaCegarLoop]: trace histogram [5, 5, 5, 5, 4, 4, 4, 4, 4, 3, 1, 1, 1, 1, 1, 1] [2024-10-11 02:27:08,083 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Forceful destruction successful, exit code 0 [2024-10-11 02:27:08,270 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable10,10 /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-11 02:27:08,270 INFO L396 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-11 02:27:08,271 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-11 02:27:08,271 INFO L85 PathProgramCache]: Analyzing trace with hash -1774241536, now seen corresponding path program 3 times [2024-10-11 02:27:08,271 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-11 02:27:08,271 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [280361288] [2024-10-11 02:27:08,271 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-11 02:27:08,271 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-11 02:27:08,301 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-10-11 02:27:08,302 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1691546260] [2024-10-11 02:27:08,302 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-10-11 02:27:08,302 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-11 02:27:08,302 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 [2024-10-11 02:27:08,304 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:27:08,305 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:27:08,362 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 5 check-sat command(s) [2024-10-11 02:27:08,362 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2024-10-11 02:27:08,363 INFO L255 TraceCheckSpWp]: Trace formula consists of 135 conjuncts, 24 conjuncts are in the unsatisfiable core [2024-10-11 02:27:08,365 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-11 02:27:09,397 INFO L134 CoverageAnalysis]: Checked inductivity of 80 backedges. 16 proven. 49 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2024-10-11 02:27:09,398 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-11 02:27:09,726 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-11 02:27:09,726 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [280361288] [2024-10-11 02:27:09,726 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-10-11 02:27:09,726 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1691546260] [2024-10-11 02:27:09,727 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1691546260] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-11 02:27:09,727 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-10-11 02:27:09,727 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [19] total 19 [2024-10-11 02:27:09,727 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [619969822] [2024-10-11 02:27:09,727 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-10-11 02:27:09,727 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 19 states [2024-10-11 02:27:09,728 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-11 02:27:09,729 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 19 interpolants. [2024-10-11 02:27:09,729 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=94, Invalid=412, Unknown=0, NotChecked=0, Total=506 [2024-10-11 02:27:09,730 INFO L87 Difference]: Start difference. First operand 391 states and 440 transitions. Second operand has 19 states, 19 states have (on average 1.7894736842105263) internal successors, (34), 18 states have internal predecessors, (34), 5 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) [2024-10-11 02:27:11,189 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-11 02:27:11,189 INFO L93 Difference]: Finished difference Result 393 states and 441 transitions. [2024-10-11 02:27:11,190 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 24 states. [2024-10-11 02:27:11,190 INFO L78 Accepts]: Start accepts. Automaton has has 19 states, 19 states have (on average 1.7894736842105263) internal successors, (34), 18 states have internal predecessors, (34), 5 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) Word has length 49 [2024-10-11 02:27:11,190 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-11 02:27:11,192 INFO L225 Difference]: With dead ends: 393 [2024-10-11 02:27:11,192 INFO L226 Difference]: Without dead ends: 391 [2024-10-11 02:27:11,193 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 69 GetRequests, 35 SyntacticMatches, 2 SemanticMatches, 32 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 311 ImplicationChecksByTransitivity, 1.4s TimeCoverageRelationStatistics Valid=245, Invalid=877, Unknown=0, NotChecked=0, Total=1122 [2024-10-11 02:27:11,193 INFO L432 NwaCegarLoop]: 10 mSDtfsCounter, 32 mSDsluCounter, 90 mSDsCounter, 0 mSdLazyCounter, 207 mSolverCounterSat, 10 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 34 SdHoareTripleChecker+Valid, 100 SdHoareTripleChecker+Invalid, 217 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 10 IncrementalHoareTripleChecker+Valid, 207 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.5s IncrementalHoareTripleChecker+Time [2024-10-11 02:27:11,194 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [34 Valid, 100 Invalid, 217 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [10 Valid, 207 Invalid, 0 Unknown, 0 Unchecked, 0.5s Time] [2024-10-11 02:27:11,195 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 391 states. [2024-10-11 02:27:11,231 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 391 to 391. [2024-10-11 02:27:11,233 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 391 states, 312 states have (on average 1.1346153846153846) internal successors, (354), 322 states have internal predecessors, (354), 43 states have call successors, (43), 35 states have call predecessors, (43), 35 states have return successors, (42), 33 states have call predecessors, (42), 42 states have call successors, (42) [2024-10-11 02:27:11,234 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 391 states to 391 states and 439 transitions. [2024-10-11 02:27:11,235 INFO L78 Accepts]: Start accepts. Automaton has 391 states and 439 transitions. Word has length 49 [2024-10-11 02:27:11,235 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-11 02:27:11,235 INFO L471 AbstractCegarLoop]: Abstraction has 391 states and 439 transitions. [2024-10-11 02:27:11,235 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 19 states, 19 states have (on average 1.7894736842105263) internal successors, (34), 18 states have internal predecessors, (34), 5 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) [2024-10-11 02:27:11,236 INFO L276 IsEmpty]: Start isEmpty. Operand 391 states and 439 transitions. [2024-10-11 02:27:11,237 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 60 [2024-10-11 02:27:11,237 INFO L207 NwaCegarLoop]: Found error trace [2024-10-11 02:27:11,237 INFO L215 NwaCegarLoop]: trace histogram [6, 6, 6, 6, 5, 5, 5, 5, 5, 4, 1, 1, 1, 1, 1, 1] [2024-10-11 02:27:11,251 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Forceful destruction successful, exit code 0 [2024-10-11 02:27:11,438 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,SelfDestructingSolverStorable11 [2024-10-11 02:27:11,438 INFO L396 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-11 02:27:11,438 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-11 02:27:11,439 INFO L85 PathProgramCache]: Analyzing trace with hash -28215198, now seen corresponding path program 4 times [2024-10-11 02:27:11,439 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-11 02:27:11,439 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1161901602] [2024-10-11 02:27:11,439 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-11 02:27:11,439 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-11 02:27:11,459 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-10-11 02:27:11,460 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [527623074] [2024-10-11 02:27:11,460 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2024-10-11 02:27:11,461 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-11 02:27:11,461 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 [2024-10-11 02:27:11,462 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:27:11,472 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:27:11,534 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2024-10-11 02:27:11,535 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2024-10-11 02:27:11,536 INFO L255 TraceCheckSpWp]: Trace formula consists of 122 conjuncts, 37 conjuncts are in the unsatisfiable core [2024-10-11 02:27:11,540 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-11 02:27:24,629 INFO L134 CoverageAnalysis]: Checked inductivity of 125 backedges. 89 proven. 8 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2024-10-11 02:27:24,629 INFO L311 TraceCheckSpWp]: Computing backward predicates...