./Ultimate.py --spec ../sv-benchmarks/c/properties/unreach-call.prp --file ../sv-benchmarks/c/nla-digbench/egcd2-ll.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version c7c6ca5d Calling Ultimate with: /root/.sdkman/candidates/java/11.0.12-open/bin/java -Dosgi.configuration.area=/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/config -Xmx15G -Xms4m -jar /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data -tc /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/AutomizerReach.xml -i ../sv-benchmarks/c/nla-digbench/egcd2-ll.c -s /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf --cacsl2boogietranslator.entry.function main --witnessprinter.witness.directory /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux --witnessprinter.witness.filename witness --witnessprinter.write.witness.besides.input.file false --witnessprinter.graph.data.specification CHECK( init(main()), LTL(G ! call(reach_error())) ) --witnessprinter.graph.data.producer Automizer --witnessprinter.graph.data.architecture 32bit --witnessprinter.graph.data.programhash ed6536c9cb0e4b2be9a327fc4a25c6bfba6e98b1dfb78e314dd25bca8cbdb087 --- Real Ultimate output --- This is Ultimate 0.2.5-?-c7c6ca5-m [2024-11-08 14:16:06,207 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-11-08 14:16:06,282 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf [2024-11-08 14:16:06,289 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-11-08 14:16:06,291 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-11-08 14:16:06,319 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-11-08 14:16:06,321 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-11-08 14:16:06,322 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-11-08 14:16:06,323 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2024-11-08 14:16:06,324 INFO L153 SettingsManager]: * Use memory slicer=true [2024-11-08 14:16:06,324 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2024-11-08 14:16:06,325 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2024-11-08 14:16:06,325 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2024-11-08 14:16:06,326 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2024-11-08 14:16:06,328 INFO L153 SettingsManager]: * Use SBE=true [2024-11-08 14:16:06,328 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-11-08 14:16:06,328 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2024-11-08 14:16:06,329 INFO L153 SettingsManager]: * sizeof long=4 [2024-11-08 14:16:06,329 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2024-11-08 14:16:06,329 INFO L153 SettingsManager]: * sizeof POINTER=4 [2024-11-08 14:16:06,329 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-11-08 14:16:06,333 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2024-11-08 14:16:06,333 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2024-11-08 14:16:06,334 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2024-11-08 14:16:06,334 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-11-08 14:16:06,334 INFO L153 SettingsManager]: * sizeof long double=12 [2024-11-08 14:16:06,334 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-11-08 14:16:06,334 INFO L153 SettingsManager]: * Use constant arrays=true [2024-11-08 14:16:06,335 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2024-11-08 14:16:06,335 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2024-11-08 14:16:06,335 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2024-11-08 14:16:06,335 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2024-11-08 14:16:06,335 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-08 14:16:06,336 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-11-08 14:16:06,336 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2024-11-08 14:16:06,336 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2024-11-08 14:16:06,336 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2024-11-08 14:16:06,336 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2024-11-08 14:16:06,337 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2024-11-08 14:16:06,337 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2024-11-08 14:16:06,337 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2024-11-08 14:16:06,338 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2024-11-08 14:16:06,338 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/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/releaseScripts/default/UAutomizer-linux Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Witness filename -> witness Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Write witness besides input file -> false Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data specification -> CHECK( init(main()), LTL(G ! call(reach_error())) ) Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data producer -> Automizer Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data architecture -> 32bit Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data programhash -> ed6536c9cb0e4b2be9a327fc4a25c6bfba6e98b1dfb78e314dd25bca8cbdb087 [2024-11-08 14:16:06,622 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-11-08 14:16:06,647 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-11-08 14:16:06,650 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-11-08 14:16:06,651 INFO L270 PluginConnector]: Initializing CDTParser... [2024-11-08 14:16:06,652 INFO L274 PluginConnector]: CDTParser initialized [2024-11-08 14:16:06,653 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/nla-digbench/egcd2-ll.c [2024-11-08 14:16:08,080 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-11-08 14:16:08,272 INFO L384 CDTParser]: Found 1 translation units. [2024-11-08 14:16:08,273 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench/egcd2-ll.c [2024-11-08 14:16:08,280 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/8635caff9/f4115a0768fc4fb18ca5f42fdd4f7362/FLAGcf7143cd9 [2024-11-08 14:16:08,298 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/8635caff9/f4115a0768fc4fb18ca5f42fdd4f7362 [2024-11-08 14:16:08,300 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-11-08 14:16:08,302 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2024-11-08 14:16:08,303 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-11-08 14:16:08,303 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-11-08 14:16:08,309 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-11-08 14:16:08,310 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 08.11 02:16:08" (1/1) ... [2024-11-08 14:16:08,311 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@97026e1 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 02:16:08, skipping insertion in model container [2024-11-08 14:16:08,311 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 08.11 02:16:08" (1/1) ... [2024-11-08 14:16:08,331 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-11-08 14:16:08,503 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench/egcd2-ll.c[490,503] [2024-11-08 14:16:08,529 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-08 14:16:08,539 INFO L200 MainTranslator]: Completed pre-run [2024-11-08 14:16:08,552 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench/egcd2-ll.c[490,503] [2024-11-08 14:16:08,564 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-08 14:16:08,580 INFO L204 MainTranslator]: Completed translation [2024-11-08 14:16:08,581 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 02:16:08 WrapperNode [2024-11-08 14:16:08,581 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-11-08 14:16:08,582 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-11-08 14:16:08,582 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-11-08 14:16:08,582 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-11-08 14:16:08,589 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 02:16:08" (1/1) ... [2024-11-08 14:16:08,596 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 02:16:08" (1/1) ... [2024-11-08 14:16:08,610 INFO L138 Inliner]: procedures = 14, calls = 17, calls flagged for inlining = 2, calls inlined = 2, statements flattened = 77 [2024-11-08 14:16:08,611 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-11-08 14:16:08,611 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-11-08 14:16:08,612 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-11-08 14:16:08,612 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-11-08 14:16:08,620 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 02:16:08" (1/1) ... [2024-11-08 14:16:08,620 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 02:16:08" (1/1) ... [2024-11-08 14:16:08,621 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 02:16:08" (1/1) ... [2024-11-08 14:16:08,632 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-11-08 14:16:08,632 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 02:16:08" (1/1) ... [2024-11-08 14:16:08,632 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 02:16:08" (1/1) ... [2024-11-08 14:16:08,635 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 02:16:08" (1/1) ... [2024-11-08 14:16:08,638 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 02:16:08" (1/1) ... [2024-11-08 14:16:08,639 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 02:16:08" (1/1) ... [2024-11-08 14:16:08,640 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 02:16:08" (1/1) ... [2024-11-08 14:16:08,642 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-11-08 14:16:08,643 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2024-11-08 14:16:08,643 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2024-11-08 14:16:08,643 INFO L274 PluginConnector]: RCFGBuilder initialized [2024-11-08 14:16:08,644 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 02:16:08" (1/1) ... [2024-11-08 14:16:08,650 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-08 14:16:08,662 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-08 14:16:08,678 INFO L229 MonitoredProcess]: Starting monitored process 1 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (exit command is (exit), workingDir is null) [2024-11-08 14:16:08,681 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (1)] Waiting until timeout for monitored process [2024-11-08 14:16:08,729 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2024-11-08 14:16:08,730 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2024-11-08 14:16:08,730 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2024-11-08 14:16:08,730 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2024-11-08 14:16:08,730 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-11-08 14:16:08,730 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-11-08 14:16:08,730 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2024-11-08 14:16:08,732 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2024-11-08 14:16:08,802 INFO L238 CfgBuilder]: Building ICFG [2024-11-08 14:16:08,804 INFO L264 CfgBuilder]: Building CFG for each procedure with an implementation [2024-11-08 14:16:09,028 INFO L? ?]: Removed 11 outVars from TransFormulas that were not future-live. [2024-11-08 14:16:09,028 INFO L287 CfgBuilder]: Performing block encoding [2024-11-08 14:16:09,047 INFO L311 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-11-08 14:16:09,047 INFO L316 CfgBuilder]: Removed 2 assume(true) statements. [2024-11-08 14:16:09,047 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 08.11 02:16:09 BoogieIcfgContainer [2024-11-08 14:16:09,047 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2024-11-08 14:16:09,050 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2024-11-08 14:16:09,050 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2024-11-08 14:16:09,053 INFO L274 PluginConnector]: TraceAbstraction initialized [2024-11-08 14:16:09,053 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 08.11 02:16:08" (1/3) ... [2024-11-08 14:16:09,054 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@27510127 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 08.11 02:16:09, skipping insertion in model container [2024-11-08 14:16:09,054 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 02:16:08" (2/3) ... [2024-11-08 14:16:09,054 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@27510127 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 08.11 02:16:09, skipping insertion in model container [2024-11-08 14:16:09,055 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 08.11 02:16:09" (3/3) ... [2024-11-08 14:16:09,056 INFO L112 eAbstractionObserver]: Analyzing ICFG egcd2-ll.c [2024-11-08 14:16:09,072 INFO L214 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2024-11-08 14:16:09,072 INFO L154 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2024-11-08 14:16:09,126 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2024-11-08 14:16:09,132 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;@5d534598, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2024-11-08 14:16:09,132 INFO L334 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2024-11-08 14:16:09,136 INFO L276 IsEmpty]: Start isEmpty. Operand has 32 states, 18 states have (on average 1.5) internal successors, (27), 20 states have internal predecessors, (27), 10 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2024-11-08 14:16:09,142 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 29 [2024-11-08 14:16:09,142 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 14:16:09,142 INFO L215 NwaCegarLoop]: trace histogram [4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-08 14:16:09,143 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 14:16:09,146 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 14:16:09,147 INFO L85 PathProgramCache]: Analyzing trace with hash 223354930, now seen corresponding path program 1 times [2024-11-08 14:16:09,154 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 14:16:09,155 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1985033135] [2024-11-08 14:16:09,155 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:16:09,155 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 14:16:09,254 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:16:09,322 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-08 14:16:09,324 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:16:09,333 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2024-11-08 14:16:09,335 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:16:09,339 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 13 [2024-11-08 14:16:09,341 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:16:09,349 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 18 [2024-11-08 14:16:09,351 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:16:09,356 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2024-11-08 14:16:09,356 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 14:16:09,357 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1985033135] [2024-11-08 14:16:09,357 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1985033135] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-08 14:16:09,358 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-08 14:16:09,358 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2024-11-08 14:16:09,359 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [845866306] [2024-11-08 14:16:09,360 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-08 14:16:09,364 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2024-11-08 14:16:09,364 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 14:16:09,382 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2024-11-08 14:16:09,383 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2024-11-08 14:16:09,384 INFO L87 Difference]: Start difference. First operand has 32 states, 18 states have (on average 1.5) internal successors, (27), 20 states have internal predecessors, (27), 10 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) Second operand has 2 states, 2 states have (on average 5.0) internal successors, (10), 2 states have internal predecessors, (10), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 2 states have call successors, (4) [2024-11-08 14:16:09,401 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 14:16:09,401 INFO L93 Difference]: Finished difference Result 61 states and 100 transitions. [2024-11-08 14:16:09,402 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2024-11-08 14:16:09,404 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 5.0) internal successors, (10), 2 states have internal predecessors, (10), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 2 states have call successors, (4) Word has length 28 [2024-11-08 14:16:09,404 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 14:16:09,411 INFO L225 Difference]: With dead ends: 61 [2024-11-08 14:16:09,411 INFO L226 Difference]: Without dead ends: 28 [2024-11-08 14:16:09,416 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 14 GetRequests, 14 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-11-08 14:16:09,421 INFO L432 NwaCegarLoop]: 41 mSDtfsCounter, 0 mSDsluCounter, 0 mSDsCounter, 0 mSdLazyCounter, 0 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 41 SdHoareTripleChecker+Invalid, 0 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 0 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-08 14:16:09,422 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 41 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 0 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-08 14:16:09,439 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 28 states. [2024-11-08 14:16:09,458 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 28 to 28. [2024-11-08 14:16:09,459 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 28 states, 15 states have (on average 1.2) internal successors, (18), 17 states have internal predecessors, (18), 10 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2024-11-08 14:16:09,461 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 28 states to 28 states and 37 transitions. [2024-11-08 14:16:09,462 INFO L78 Accepts]: Start accepts. Automaton has 28 states and 37 transitions. Word has length 28 [2024-11-08 14:16:09,462 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 14:16:09,463 INFO L471 AbstractCegarLoop]: Abstraction has 28 states and 37 transitions. [2024-11-08 14:16:09,463 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 2 states have (on average 5.0) internal successors, (10), 2 states have internal predecessors, (10), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 2 states have call successors, (4) [2024-11-08 14:16:09,463 INFO L276 IsEmpty]: Start isEmpty. Operand 28 states and 37 transitions. [2024-11-08 14:16:09,464 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 30 [2024-11-08 14:16:09,465 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 14:16:09,465 INFO L215 NwaCegarLoop]: trace histogram [4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-08 14:16:09,465 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2024-11-08 14:16:09,465 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 14:16:09,466 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 14:16:09,466 INFO L85 PathProgramCache]: Analyzing trace with hash 727709964, now seen corresponding path program 1 times [2024-11-08 14:16:09,466 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 14:16:09,467 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1117393743] [2024-11-08 14:16:09,467 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:16:09,467 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 14:16:09,516 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:16:09,728 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-08 14:16:09,730 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:16:09,736 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2024-11-08 14:16:09,741 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:16:09,786 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 13 [2024-11-08 14:16:09,789 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:16:09,802 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 18 [2024-11-08 14:16:09,806 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:16:09,813 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 3 proven. 6 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2024-11-08 14:16:09,813 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 14:16:09,814 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1117393743] [2024-11-08 14:16:09,814 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1117393743] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-08 14:16:09,814 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [558800922] [2024-11-08 14:16:09,814 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:16:09,814 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 14:16:09,815 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-08 14:16:09,817 INFO L229 MonitoredProcess]: Starting monitored process 2 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-08 14:16:09,819 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2024-11-08 14:16:09,898 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:16:09,902 INFO L255 TraceCheckSpWp]: Trace formula consists of 93 conjuncts, 11 conjuncts are in the unsatisfiable core [2024-11-08 14:16:09,911 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-08 14:16:10,062 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2024-11-08 14:16:10,062 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-08 14:16:10,063 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [558800922] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-08 14:16:10,063 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-08 14:16:10,063 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [6] total 10 [2024-11-08 14:16:10,064 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [821370723] [2024-11-08 14:16:10,064 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-08 14:16:10,065 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2024-11-08 14:16:10,065 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 14:16:10,066 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2024-11-08 14:16:10,067 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=18, Invalid=72, Unknown=0, NotChecked=0, Total=90 [2024-11-08 14:16:10,067 INFO L87 Difference]: Start difference. First operand 28 states and 37 transitions. Second operand has 6 states, 5 states have (on average 2.2) internal successors, (11), 5 states have internal predecessors, (11), 3 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2024-11-08 14:16:10,189 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 14:16:10,189 INFO L93 Difference]: Finished difference Result 45 states and 60 transitions. [2024-11-08 14:16:10,190 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2024-11-08 14:16:10,190 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 5 states have (on average 2.2) internal successors, (11), 5 states have internal predecessors, (11), 3 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) Word has length 29 [2024-11-08 14:16:10,191 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 14:16:10,192 INFO L225 Difference]: With dead ends: 45 [2024-11-08 14:16:10,193 INFO L226 Difference]: Without dead ends: 43 [2024-11-08 14:16:10,193 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 42 GetRequests, 33 SyntacticMatches, 0 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 7 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=22, Invalid=88, Unknown=0, NotChecked=0, Total=110 [2024-11-08 14:16:10,195 INFO L432 NwaCegarLoop]: 28 mSDtfsCounter, 7 mSDsluCounter, 98 mSDsCounter, 0 mSdLazyCounter, 56 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 12 SdHoareTripleChecker+Valid, 126 SdHoareTripleChecker+Invalid, 57 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 56 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-08 14:16:10,196 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [12 Valid, 126 Invalid, 57 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 56 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-08 14:16:10,198 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 43 states. [2024-11-08 14:16:10,211 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 43 to 41. [2024-11-08 14:16:10,212 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 41 states, 22 states have (on average 1.2272727272727273) internal successors, (27), 24 states have internal predecessors, (27), 15 states have call successors, (15), 3 states have call predecessors, (15), 3 states have return successors, (14), 13 states have call predecessors, (14), 14 states have call successors, (14) [2024-11-08 14:16:10,213 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 41 states to 41 states and 56 transitions. [2024-11-08 14:16:10,214 INFO L78 Accepts]: Start accepts. Automaton has 41 states and 56 transitions. Word has length 29 [2024-11-08 14:16:10,214 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 14:16:10,214 INFO L471 AbstractCegarLoop]: Abstraction has 41 states and 56 transitions. [2024-11-08 14:16:10,215 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 5 states have (on average 2.2) internal successors, (11), 5 states have internal predecessors, (11), 3 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2024-11-08 14:16:10,215 INFO L276 IsEmpty]: Start isEmpty. Operand 41 states and 56 transitions. [2024-11-08 14:16:10,216 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 31 [2024-11-08 14:16:10,216 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 14:16:10,216 INFO L215 NwaCegarLoop]: trace histogram [4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-08 14:16:10,236 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Ended with exit code 0 [2024-11-08 14:16:10,417 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1,2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 14:16:10,417 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 14:16:10,418 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 14:16:10,418 INFO L85 PathProgramCache]: Analyzing trace with hash 1088429638, now seen corresponding path program 1 times [2024-11-08 14:16:10,418 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 14:16:10,418 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1242580524] [2024-11-08 14:16:10,418 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:16:10,419 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 14:16:10,446 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-08 14:16:10,452 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1786475263] [2024-11-08 14:16:10,452 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:16:10,453 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 14:16:10,453 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-08 14:16:10,458 INFO L229 MonitoredProcess]: Starting monitored process 3 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-08 14:16:10,461 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2024-11-08 14:16:10,518 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:16:10,521 INFO L255 TraceCheckSpWp]: Trace formula consists of 97 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-08 14:16:10,523 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-08 14:16:10,581 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2024-11-08 14:16:10,582 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-08 14:16:10,582 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 14:16:10,582 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1242580524] [2024-11-08 14:16:10,584 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-08 14:16:10,584 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1786475263] [2024-11-08 14:16:10,584 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1786475263] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-08 14:16:10,584 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-08 14:16:10,584 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-08 14:16:10,585 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1218830338] [2024-11-08 14:16:10,585 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-08 14:16:10,585 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-08 14:16:10,586 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 14:16:10,587 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-08 14:16:10,587 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-08 14:16:10,587 INFO L87 Difference]: Start difference. First operand 41 states and 56 transitions. Second operand has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2024-11-08 14:16:10,666 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 14:16:10,666 INFO L93 Difference]: Finished difference Result 60 states and 84 transitions. [2024-11-08 14:16:10,667 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-08 14:16:10,667 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) Word has length 30 [2024-11-08 14:16:10,668 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 14:16:10,671 INFO L225 Difference]: With dead ends: 60 [2024-11-08 14:16:10,671 INFO L226 Difference]: Without dead ends: 58 [2024-11-08 14:16:10,671 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 30 GetRequests, 26 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2024-11-08 14:16:10,672 INFO L432 NwaCegarLoop]: 34 mSDtfsCounter, 4 mSDsluCounter, 89 mSDsCounter, 0 mSdLazyCounter, 32 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 8 SdHoareTripleChecker+Valid, 123 SdHoareTripleChecker+Invalid, 32 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 32 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-08 14:16:10,673 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [8 Valid, 123 Invalid, 32 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 32 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-08 14:16:10,674 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 58 states. [2024-11-08 14:16:10,693 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 58 to 49. [2024-11-08 14:16:10,694 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 49 states, 27 states have (on average 1.1851851851851851) internal successors, (32), 31 states have internal predecessors, (32), 17 states have call successors, (17), 4 states have call predecessors, (17), 4 states have return successors, (16), 13 states have call predecessors, (16), 16 states have call successors, (16) [2024-11-08 14:16:10,698 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 49 states to 49 states and 65 transitions. [2024-11-08 14:16:10,699 INFO L78 Accepts]: Start accepts. Automaton has 49 states and 65 transitions. Word has length 30 [2024-11-08 14:16:10,699 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 14:16:10,699 INFO L471 AbstractCegarLoop]: Abstraction has 49 states and 65 transitions. [2024-11-08 14:16:10,699 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2024-11-08 14:16:10,700 INFO L276 IsEmpty]: Start isEmpty. Operand 49 states and 65 transitions. [2024-11-08 14:16:10,703 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 35 [2024-11-08 14:16:10,703 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 14:16:10,703 INFO L215 NwaCegarLoop]: trace histogram [4, 4, 4, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-08 14:16:10,723 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2024-11-08 14:16:10,904 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 3 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable2 [2024-11-08 14:16:10,904 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 14:16:10,905 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 14:16:10,905 INFO L85 PathProgramCache]: Analyzing trace with hash 692401170, now seen corresponding path program 1 times [2024-11-08 14:16:10,905 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 14:16:10,905 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1245056406] [2024-11-08 14:16:10,905 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:16:10,906 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 14:16:10,926 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:16:11,017 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-08 14:16:11,019 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:16:11,021 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2024-11-08 14:16:11,022 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:16:11,043 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 13 [2024-11-08 14:16:11,045 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:16:11,053 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 18 [2024-11-08 14:16:11,059 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:16:11,067 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 25 [2024-11-08 14:16:11,068 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:16:11,074 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 5 proven. 6 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2024-11-08 14:16:11,074 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 14:16:11,074 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1245056406] [2024-11-08 14:16:11,075 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1245056406] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-08 14:16:11,075 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [172336068] [2024-11-08 14:16:11,075 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:16:11,075 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 14:16:11,075 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-08 14:16:11,078 INFO L229 MonitoredProcess]: Starting monitored process 4 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-08 14:16:11,080 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2024-11-08 14:16:11,138 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:16:11,139 INFO L255 TraceCheckSpWp]: Trace formula consists of 102 conjuncts, 9 conjuncts are in the unsatisfiable core [2024-11-08 14:16:11,142 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-08 14:16:11,250 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2024-11-08 14:16:11,250 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-08 14:16:11,250 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [172336068] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-08 14:16:11,251 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-08 14:16:11,251 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [6] total 9 [2024-11-08 14:16:11,251 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1293365937] [2024-11-08 14:16:11,251 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-08 14:16:11,252 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-08 14:16:11,252 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 14:16:11,252 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-08 14:16:11,252 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=16, Invalid=56, Unknown=0, NotChecked=0, Total=72 [2024-11-08 14:16:11,253 INFO L87 Difference]: Start difference. First operand 49 states and 65 transitions. Second operand has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2024-11-08 14:16:11,309 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 14:16:11,310 INFO L93 Difference]: Finished difference Result 57 states and 72 transitions. [2024-11-08 14:16:11,310 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-08 14:16:11,311 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) Word has length 34 [2024-11-08 14:16:11,311 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 14:16:11,313 INFO L225 Difference]: With dead ends: 57 [2024-11-08 14:16:11,314 INFO L226 Difference]: Without dead ends: 53 [2024-11-08 14:16:11,315 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 49 GetRequests, 41 SyntacticMatches, 0 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 6 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=20, Invalid=70, Unknown=0, NotChecked=0, Total=90 [2024-11-08 14:16:11,316 INFO L432 NwaCegarLoop]: 35 mSDtfsCounter, 7 mSDsluCounter, 91 mSDsCounter, 0 mSdLazyCounter, 27 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 11 SdHoareTripleChecker+Valid, 126 SdHoareTripleChecker+Invalid, 28 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 27 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-08 14:16:11,316 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [11 Valid, 126 Invalid, 28 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 27 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-08 14:16:11,319 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 53 states. [2024-11-08 14:16:11,331 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 53 to 52. [2024-11-08 14:16:11,332 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 52 states, 30 states have (on average 1.1333333333333333) internal successors, (34), 33 states have internal predecessors, (34), 16 states have call successors, (16), 5 states have call predecessors, (16), 5 states have return successors, (15), 13 states have call predecessors, (15), 15 states have call successors, (15) [2024-11-08 14:16:11,333 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 52 states to 52 states and 65 transitions. [2024-11-08 14:16:11,335 INFO L78 Accepts]: Start accepts. Automaton has 52 states and 65 transitions. Word has length 34 [2024-11-08 14:16:11,336 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 14:16:11,336 INFO L471 AbstractCegarLoop]: Abstraction has 52 states and 65 transitions. [2024-11-08 14:16:11,336 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2024-11-08 14:16:11,336 INFO L276 IsEmpty]: Start isEmpty. Operand 52 states and 65 transitions. [2024-11-08 14:16:11,337 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 46 [2024-11-08 14:16:11,337 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 14:16:11,338 INFO L215 NwaCegarLoop]: trace histogram [4, 4, 4, 4, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-08 14:16:11,354 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Ended with exit code 0 [2024-11-08 14:16:11,539 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 14:16:11,539 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 14:16:11,540 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 14:16:11,540 INFO L85 PathProgramCache]: Analyzing trace with hash -98301800, now seen corresponding path program 1 times [2024-11-08 14:16:11,540 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 14:16:11,540 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2073695477] [2024-11-08 14:16:11,540 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:16:11,540 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 14:16:11,555 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-08 14:16:11,556 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [660124623] [2024-11-08 14:16:11,556 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:16:11,556 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 14:16:11,556 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-08 14:16:11,558 INFO L229 MonitoredProcess]: Starting monitored process 5 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-08 14:16:11,559 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2024-11-08 14:16:11,618 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:16:11,619 INFO L255 TraceCheckSpWp]: Trace formula consists of 124 conjuncts, 11 conjuncts are in the unsatisfiable core [2024-11-08 14:16:11,621 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-08 14:16:11,781 INFO L134 CoverageAnalysis]: Checked inductivity of 42 backedges. 6 proven. 0 refuted. 0 times theorem prover too weak. 36 trivial. 0 not checked. [2024-11-08 14:16:11,781 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-08 14:16:11,782 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 14:16:11,782 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2073695477] [2024-11-08 14:16:11,782 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-08 14:16:11,782 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [660124623] [2024-11-08 14:16:11,782 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [660124623] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-08 14:16:11,782 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-08 14:16:11,782 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-08 14:16:11,782 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [467887936] [2024-11-08 14:16:11,782 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-08 14:16:11,783 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-08 14:16:11,783 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 14:16:11,783 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-08 14:16:11,783 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-08 14:16:11,784 INFO L87 Difference]: Start difference. First operand 52 states and 65 transitions. Second operand has 5 states, 5 states have (on average 3.0) internal successors, (15), 4 states have internal predecessors, (15), 2 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2024-11-08 14:16:11,850 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 14:16:11,850 INFO L93 Difference]: Finished difference Result 59 states and 71 transitions. [2024-11-08 14:16:11,850 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-08 14:16:11,851 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.0) internal successors, (15), 4 states have internal predecessors, (15), 2 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) Word has length 45 [2024-11-08 14:16:11,851 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 14:16:11,852 INFO L225 Difference]: With dead ends: 59 [2024-11-08 14:16:11,852 INFO L226 Difference]: Without dead ends: 57 [2024-11-08 14:16:11,852 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 45 GetRequests, 41 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2024-11-08 14:16:11,853 INFO L432 NwaCegarLoop]: 32 mSDtfsCounter, 5 mSDsluCounter, 82 mSDsCounter, 0 mSdLazyCounter, 39 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 6 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.0s IncrementalHoareTripleChecker+Time [2024-11-08 14:16:11,853 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [6 Valid, 114 Invalid, 40 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 39 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-08 14:16:11,854 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 57 states. [2024-11-08 14:16:11,863 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 57 to 56. [2024-11-08 14:16:11,863 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 56 states, 33 states have (on average 1.121212121212121) internal successors, (37), 36 states have internal predecessors, (37), 16 states have call successors, (16), 6 states have call predecessors, (16), 6 states have return successors, (15), 13 states have call predecessors, (15), 15 states have call successors, (15) [2024-11-08 14:16:11,864 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 56 states to 56 states and 68 transitions. [2024-11-08 14:16:11,864 INFO L78 Accepts]: Start accepts. Automaton has 56 states and 68 transitions. Word has length 45 [2024-11-08 14:16:11,864 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 14:16:11,864 INFO L471 AbstractCegarLoop]: Abstraction has 56 states and 68 transitions. [2024-11-08 14:16:11,865 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.0) internal successors, (15), 4 states have internal predecessors, (15), 2 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2024-11-08 14:16:11,865 INFO L276 IsEmpty]: Start isEmpty. Operand 56 states and 68 transitions. [2024-11-08 14:16:11,866 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 53 [2024-11-08 14:16:11,866 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 14:16:11,866 INFO L215 NwaCegarLoop]: trace histogram [5, 4, 4, 4, 4, 4, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-08 14:16:11,882 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Ended with exit code 0 [2024-11-08 14:16:12,070 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 14:16:12,071 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 14:16:12,071 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 14:16:12,071 INFO L85 PathProgramCache]: Analyzing trace with hash -137832731, now seen corresponding path program 1 times [2024-11-08 14:16:12,071 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 14:16:12,071 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1306194438] [2024-11-08 14:16:12,072 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:16:12,072 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 14:16:12,088 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-08 14:16:12,089 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [478901354] [2024-11-08 14:16:12,090 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:16:12,090 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 14:16:12,090 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-08 14:16:12,092 INFO L229 MonitoredProcess]: Starting monitored process 6 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-08 14:16:12,093 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2024-11-08 14:16:12,157 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:16:12,159 INFO L255 TraceCheckSpWp]: Trace formula consists of 139 conjuncts, 13 conjuncts are in the unsatisfiable core [2024-11-08 14:16:12,161 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-08 14:16:12,330 INFO L134 CoverageAnalysis]: Checked inductivity of 58 backedges. 8 proven. 2 refuted. 0 times theorem prover too weak. 48 trivial. 0 not checked. [2024-11-08 14:16:12,330 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-08 14:16:12,451 INFO L134 CoverageAnalysis]: Checked inductivity of 58 backedges. 8 proven. 2 refuted. 0 times theorem prover too weak. 48 trivial. 0 not checked. [2024-11-08 14:16:12,451 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 14:16:12,452 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1306194438] [2024-11-08 14:16:12,452 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-08 14:16:12,452 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [478901354] [2024-11-08 14:16:12,453 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [478901354] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-08 14:16:12,453 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-08 14:16:12,453 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 7 [2024-11-08 14:16:12,453 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [414592561] [2024-11-08 14:16:12,453 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-08 14:16:12,454 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2024-11-08 14:16:12,454 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 14:16:12,454 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2024-11-08 14:16:12,455 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=29, Unknown=0, NotChecked=0, Total=42 [2024-11-08 14:16:12,456 INFO L87 Difference]: Start difference. First operand 56 states and 68 transitions. Second operand has 7 states, 7 states have (on average 2.7142857142857144) internal successors, (19), 6 states have internal predecessors, (19), 4 states have call successors, (10), 2 states have call predecessors, (10), 1 states have return successors, (8), 2 states have call predecessors, (8), 2 states have call successors, (8) [2024-11-08 14:16:12,572 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 14:16:12,573 INFO L93 Difference]: Finished difference Result 84 states and 113 transitions. [2024-11-08 14:16:12,574 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2024-11-08 14:16:12,574 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 7 states have (on average 2.7142857142857144) internal successors, (19), 6 states have internal predecessors, (19), 4 states have call successors, (10), 2 states have call predecessors, (10), 1 states have return successors, (8), 2 states have call predecessors, (8), 2 states have call successors, (8) Word has length 52 [2024-11-08 14:16:12,574 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 14:16:12,575 INFO L225 Difference]: With dead ends: 84 [2024-11-08 14:16:12,575 INFO L226 Difference]: Without dead ends: 82 [2024-11-08 14:16:12,576 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 103 GetRequests, 94 SyntacticMatches, 3 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=17, Invalid=39, Unknown=0, NotChecked=0, Total=56 [2024-11-08 14:16:12,576 INFO L432 NwaCegarLoop]: 39 mSDtfsCounter, 6 mSDsluCounter, 152 mSDsCounter, 0 mSdLazyCounter, 72 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 14 SdHoareTripleChecker+Valid, 191 SdHoareTripleChecker+Invalid, 74 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 72 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-08 14:16:12,577 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [14 Valid, 191 Invalid, 74 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 72 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-08 14:16:12,579 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 82 states. [2024-11-08 14:16:12,596 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 82 to 52. [2024-11-08 14:16:12,597 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 52 states, 31 states have (on average 1.1290322580645162) internal successors, (35), 32 states have internal predecessors, (35), 14 states have call successors, (14), 6 states have call predecessors, (14), 6 states have return successors, (13), 13 states have call predecessors, (13), 13 states have call successors, (13) [2024-11-08 14:16:12,598 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 52 states to 52 states and 62 transitions. [2024-11-08 14:16:12,600 INFO L78 Accepts]: Start accepts. Automaton has 52 states and 62 transitions. Word has length 52 [2024-11-08 14:16:12,600 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 14:16:12,600 INFO L471 AbstractCegarLoop]: Abstraction has 52 states and 62 transitions. [2024-11-08 14:16:12,601 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 7 states have (on average 2.7142857142857144) internal successors, (19), 6 states have internal predecessors, (19), 4 states have call successors, (10), 2 states have call predecessors, (10), 1 states have return successors, (8), 2 states have call predecessors, (8), 2 states have call successors, (8) [2024-11-08 14:16:12,601 INFO L276 IsEmpty]: Start isEmpty. Operand 52 states and 62 transitions. [2024-11-08 14:16:12,602 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 55 [2024-11-08 14:16:12,603 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 14:16:12,603 INFO L215 NwaCegarLoop]: trace histogram [5, 4, 4, 4, 4, 4, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-08 14:16:12,621 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Forceful destruction successful, exit code 0 [2024-11-08 14:16:12,804 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 14:16:12,804 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 14:16:12,805 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 14:16:12,805 INFO L85 PathProgramCache]: Analyzing trace with hash -1721617041, now seen corresponding path program 1 times [2024-11-08 14:16:12,805 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 14:16:12,805 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1704255434] [2024-11-08 14:16:12,805 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:16:12,805 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 14:16:12,817 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:16:12,896 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-08 14:16:12,898 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:16:12,918 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2024-11-08 14:16:12,920 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:16:12,921 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 13 [2024-11-08 14:16:12,922 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:16:12,924 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 18 [2024-11-08 14:16:12,926 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:16:12,927 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 26 [2024-11-08 14:16:12,928 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:16:12,930 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 31 [2024-11-08 14:16:12,931 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:16:12,934 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 36 [2024-11-08 14:16:12,935 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:16:12,937 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 41 [2024-11-08 14:16:12,938 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:16:12,941 INFO L134 CoverageAnalysis]: Checked inductivity of 58 backedges. 8 proven. 11 refuted. 0 times theorem prover too weak. 39 trivial. 0 not checked. [2024-11-08 14:16:12,941 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 14:16:12,941 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1704255434] [2024-11-08 14:16:12,941 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1704255434] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-08 14:16:12,941 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1308251375] [2024-11-08 14:16:12,941 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:16:12,941 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 14:16:12,941 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-08 14:16:12,943 INFO L229 MonitoredProcess]: Starting monitored process 7 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-08 14:16:12,944 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2024-11-08 14:16:12,998 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:16:12,999 INFO L255 TraceCheckSpWp]: Trace formula consists of 149 conjuncts, 9 conjuncts are in the unsatisfiable core [2024-11-08 14:16:13,001 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-08 14:16:13,032 INFO L134 CoverageAnalysis]: Checked inductivity of 58 backedges. 8 proven. 11 refuted. 0 times theorem prover too weak. 39 trivial. 0 not checked. [2024-11-08 14:16:13,032 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-08 14:16:13,126 INFO L134 CoverageAnalysis]: Checked inductivity of 58 backedges. 8 proven. 11 refuted. 0 times theorem prover too weak. 39 trivial. 0 not checked. [2024-11-08 14:16:13,126 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1308251375] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-08 14:16:13,126 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-08 14:16:13,126 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8, 8] total 9 [2024-11-08 14:16:13,127 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [130706225] [2024-11-08 14:16:13,127 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-08 14:16:13,127 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2024-11-08 14:16:13,127 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 14:16:13,128 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2024-11-08 14:16:13,128 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=17, Invalid=55, Unknown=0, NotChecked=0, Total=72 [2024-11-08 14:16:13,128 INFO L87 Difference]: Start difference. First operand 52 states and 62 transitions. Second operand has 9 states, 9 states have (on average 2.6666666666666665) internal successors, (24), 8 states have internal predecessors, (24), 5 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (8), 3 states have call predecessors, (8), 4 states have call successors, (8) [2024-11-08 14:16:13,310 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 14:16:13,310 INFO L93 Difference]: Finished difference Result 99 states and 137 transitions. [2024-11-08 14:16:13,311 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2024-11-08 14:16:13,311 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 9 states have (on average 2.6666666666666665) internal successors, (24), 8 states have internal predecessors, (24), 5 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (8), 3 states have call predecessors, (8), 4 states have call successors, (8) Word has length 54 [2024-11-08 14:16:13,311 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 14:16:13,312 INFO L225 Difference]: With dead ends: 99 [2024-11-08 14:16:13,312 INFO L226 Difference]: Without dead ends: 91 [2024-11-08 14:16:13,312 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 133 GetRequests, 118 SyntacticMatches, 4 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=42, Invalid=114, Unknown=0, NotChecked=0, Total=156 [2024-11-08 14:16:13,313 INFO L432 NwaCegarLoop]: 41 mSDtfsCounter, 32 mSDsluCounter, 236 mSDsCounter, 0 mSdLazyCounter, 98 mSolverCounterSat, 30 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 37 SdHoareTripleChecker+Valid, 277 SdHoareTripleChecker+Invalid, 128 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 30 IncrementalHoareTripleChecker+Valid, 98 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-08 14:16:13,313 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [37 Valid, 277 Invalid, 128 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [30 Valid, 98 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-08 14:16:13,314 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 91 states. [2024-11-08 14:16:13,339 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 91 to 82. [2024-11-08 14:16:13,339 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 82 states, 45 states have (on average 1.2) internal successors, (54), 46 states have internal predecessors, (54), 30 states have call successors, (30), 6 states have call predecessors, (30), 6 states have return successors, (29), 29 states have call predecessors, (29), 29 states have call successors, (29) [2024-11-08 14:16:13,340 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 82 states to 82 states and 113 transitions. [2024-11-08 14:16:13,341 INFO L78 Accepts]: Start accepts. Automaton has 82 states and 113 transitions. Word has length 54 [2024-11-08 14:16:13,341 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 14:16:13,341 INFO L471 AbstractCegarLoop]: Abstraction has 82 states and 113 transitions. [2024-11-08 14:16:13,341 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 9 states have (on average 2.6666666666666665) internal successors, (24), 8 states have internal predecessors, (24), 5 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (8), 3 states have call predecessors, (8), 4 states have call successors, (8) [2024-11-08 14:16:13,342 INFO L276 IsEmpty]: Start isEmpty. Operand 82 states and 113 transitions. [2024-11-08 14:16:13,342 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 61 [2024-11-08 14:16:13,342 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 14:16:13,343 INFO L215 NwaCegarLoop]: trace histogram [6, 5, 5, 4, 4, 4, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-08 14:16:13,357 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Ended with exit code 0 [2024-11-08 14:16:13,543 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 14:16:13,544 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 14:16:13,544 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 14:16:13,544 INFO L85 PathProgramCache]: Analyzing trace with hash -653850053, now seen corresponding path program 1 times [2024-11-08 14:16:13,544 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 14:16:13,544 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1783225559] [2024-11-08 14:16:13,544 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:16:13,544 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 14:16:13,559 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-08 14:16:13,564 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [318887213] [2024-11-08 14:16:13,564 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:16:13,564 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 14:16:13,564 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-08 14:16:13,568 INFO L229 MonitoredProcess]: Starting monitored process 8 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-08 14:16:13,571 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2024-11-08 14:16:13,627 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:16:13,628 INFO L255 TraceCheckSpWp]: Trace formula consists of 162 conjuncts, 31 conjuncts are in the unsatisfiable core [2024-11-08 14:16:13,630 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-08 14:16:13,853 INFO L134 CoverageAnalysis]: Checked inductivity of 79 backedges. 12 proven. 15 refuted. 0 times theorem prover too weak. 52 trivial. 0 not checked. [2024-11-08 14:16:13,853 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-08 14:16:14,035 INFO L134 CoverageAnalysis]: Checked inductivity of 79 backedges. 12 proven. 15 refuted. 0 times theorem prover too weak. 52 trivial. 0 not checked. [2024-11-08 14:16:14,035 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 14:16:14,035 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1783225559] [2024-11-08 14:16:14,035 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-08 14:16:14,035 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [318887213] [2024-11-08 14:16:14,036 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [318887213] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-08 14:16:14,036 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-08 14:16:14,036 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 8] total 14 [2024-11-08 14:16:14,036 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1271583546] [2024-11-08 14:16:14,036 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-08 14:16:14,036 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2024-11-08 14:16:14,037 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 14:16:14,037 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2024-11-08 14:16:14,037 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=38, Invalid=144, Unknown=0, NotChecked=0, Total=182 [2024-11-08 14:16:14,038 INFO L87 Difference]: Start difference. First operand 82 states and 113 transitions. Second operand has 14 states, 14 states have (on average 2.5714285714285716) internal successors, (36), 13 states have internal predecessors, (36), 7 states have call successors, (18), 3 states have call predecessors, (18), 2 states have return successors, (16), 7 states have call predecessors, (16), 7 states have call successors, (16) [2024-11-08 14:16:14,306 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 14:16:14,306 INFO L93 Difference]: Finished difference Result 125 states and 178 transitions. [2024-11-08 14:16:14,306 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2024-11-08 14:16:14,307 INFO L78 Accepts]: Start accepts. Automaton has has 14 states, 14 states have (on average 2.5714285714285716) internal successors, (36), 13 states have internal predecessors, (36), 7 states have call successors, (18), 3 states have call predecessors, (18), 2 states have return successors, (16), 7 states have call predecessors, (16), 7 states have call successors, (16) Word has length 60 [2024-11-08 14:16:14,307 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 14:16:14,308 INFO L225 Difference]: With dead ends: 125 [2024-11-08 14:16:14,308 INFO L226 Difference]: Without dead ends: 121 [2024-11-08 14:16:14,309 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 121 GetRequests, 106 SyntacticMatches, 0 SemanticMatches, 15 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 26 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=59, Invalid=213, Unknown=0, NotChecked=0, Total=272 [2024-11-08 14:16:14,309 INFO L432 NwaCegarLoop]: 37 mSDtfsCounter, 19 mSDsluCounter, 189 mSDsCounter, 0 mSdLazyCounter, 184 mSolverCounterSat, 15 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 28 SdHoareTripleChecker+Valid, 226 SdHoareTripleChecker+Invalid, 199 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 15 IncrementalHoareTripleChecker+Valid, 184 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-11-08 14:16:14,309 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [28 Valid, 226 Invalid, 199 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [15 Valid, 184 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-11-08 14:16:14,310 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 121 states. [2024-11-08 14:16:14,335 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 121 to 89. [2024-11-08 14:16:14,336 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 89 states, 49 states have (on average 1.183673469387755) internal successors, (58), 51 states have internal predecessors, (58), 32 states have call successors, (32), 7 states have call predecessors, (32), 7 states have return successors, (31), 30 states have call predecessors, (31), 31 states have call successors, (31) [2024-11-08 14:16:14,337 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 89 states to 89 states and 121 transitions. [2024-11-08 14:16:14,338 INFO L78 Accepts]: Start accepts. Automaton has 89 states and 121 transitions. Word has length 60 [2024-11-08 14:16:14,338 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 14:16:14,338 INFO L471 AbstractCegarLoop]: Abstraction has 89 states and 121 transitions. [2024-11-08 14:16:14,338 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 14 states, 14 states have (on average 2.5714285714285716) internal successors, (36), 13 states have internal predecessors, (36), 7 states have call successors, (18), 3 states have call predecessors, (18), 2 states have return successors, (16), 7 states have call predecessors, (16), 7 states have call successors, (16) [2024-11-08 14:16:14,339 INFO L276 IsEmpty]: Start isEmpty. Operand 89 states and 121 transitions. [2024-11-08 14:16:14,340 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 66 [2024-11-08 14:16:14,340 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 14:16:14,340 INFO L215 NwaCegarLoop]: trace histogram [7, 6, 6, 4, 4, 4, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-08 14:16:14,359 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Ended with exit code 0 [2024-11-08 14:16:14,544 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 14:16:14,545 INFO L396 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 14:16:14,545 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 14:16:14,545 INFO L85 PathProgramCache]: Analyzing trace with hash 1044201731, now seen corresponding path program 2 times [2024-11-08 14:16:14,545 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 14:16:14,546 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1643642130] [2024-11-08 14:16:14,546 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:16:14,546 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 14:16:14,560 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-08 14:16:14,561 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [301177233] [2024-11-08 14:16:14,561 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-08 14:16:14,561 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 14:16:14,562 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-08 14:16:14,563 INFO L229 MonitoredProcess]: Starting monitored process 9 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-08 14:16:14,564 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2024-11-08 14:16:14,626 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-08 14:16:14,626 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-08 14:16:14,627 INFO L255 TraceCheckSpWp]: Trace formula consists of 171 conjuncts, 21 conjuncts are in the unsatisfiable core [2024-11-08 14:16:14,629 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-08 14:16:14,807 INFO L134 CoverageAnalysis]: Checked inductivity of 102 backedges. 12 proven. 6 refuted. 0 times theorem prover too weak. 84 trivial. 0 not checked. [2024-11-08 14:16:14,807 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-08 14:16:14,847 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 14:16:14,848 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1643642130] [2024-11-08 14:16:14,848 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-08 14:16:14,848 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [301177233] [2024-11-08 14:16:14,848 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [301177233] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-08 14:16:14,848 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-11-08 14:16:14,848 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7] total 7 [2024-11-08 14:16:14,849 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [558321624] [2024-11-08 14:16:14,849 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-11-08 14:16:14,849 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2024-11-08 14:16:14,849 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 14:16:14,850 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2024-11-08 14:16:14,850 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=14, Invalid=42, Unknown=0, NotChecked=0, Total=56 [2024-11-08 14:16:14,850 INFO L87 Difference]: Start difference. First operand 89 states and 121 transitions. Second operand has 7 states, 7 states have (on average 2.857142857142857) internal successors, (20), 6 states have internal predecessors, (20), 4 states have call successors, (11), 2 states have call predecessors, (11), 1 states have return successors, (10), 4 states have call predecessors, (10), 4 states have call successors, (10) [2024-11-08 14:16:15,010 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 14:16:15,010 INFO L93 Difference]: Finished difference Result 121 states and 160 transitions. [2024-11-08 14:16:15,010 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2024-11-08 14:16:15,011 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 7 states have (on average 2.857142857142857) internal successors, (20), 6 states have internal predecessors, (20), 4 states have call successors, (11), 2 states have call predecessors, (11), 1 states have return successors, (10), 4 states have call predecessors, (10), 4 states have call successors, (10) Word has length 65 [2024-11-08 14:16:15,011 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 14:16:15,012 INFO L225 Difference]: With dead ends: 121 [2024-11-08 14:16:15,012 INFO L226 Difference]: Without dead ends: 119 [2024-11-08 14:16:15,012 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 71 GetRequests, 61 SyntacticMatches, 2 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=22, Invalid=68, Unknown=0, NotChecked=0, Total=90 [2024-11-08 14:16:15,013 INFO L432 NwaCegarLoop]: 36 mSDtfsCounter, 12 mSDsluCounter, 139 mSDsCounter, 0 mSdLazyCounter, 95 mSolverCounterSat, 7 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 18 SdHoareTripleChecker+Valid, 175 SdHoareTripleChecker+Invalid, 102 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 7 IncrementalHoareTripleChecker+Valid, 95 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-08 14:16:15,013 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [18 Valid, 175 Invalid, 102 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [7 Valid, 95 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-08 14:16:15,015 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 119 states. [2024-11-08 14:16:15,071 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 119 to 116. [2024-11-08 14:16:15,072 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 116 states, 65 states have (on average 1.1692307692307693) internal successors, (76), 67 states have internal predecessors, (76), 40 states have call successors, (40), 10 states have call predecessors, (40), 10 states have return successors, (39), 38 states have call predecessors, (39), 39 states have call successors, (39) [2024-11-08 14:16:15,072 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 116 states to 116 states and 155 transitions. [2024-11-08 14:16:15,073 INFO L78 Accepts]: Start accepts. Automaton has 116 states and 155 transitions. Word has length 65 [2024-11-08 14:16:15,073 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 14:16:15,073 INFO L471 AbstractCegarLoop]: Abstraction has 116 states and 155 transitions. [2024-11-08 14:16:15,073 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 7 states have (on average 2.857142857142857) internal successors, (20), 6 states have internal predecessors, (20), 4 states have call successors, (11), 2 states have call predecessors, (11), 1 states have return successors, (10), 4 states have call predecessors, (10), 4 states have call successors, (10) [2024-11-08 14:16:15,073 INFO L276 IsEmpty]: Start isEmpty. Operand 116 states and 155 transitions. [2024-11-08 14:16:15,075 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 71 [2024-11-08 14:16:15,075 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 14:16:15,075 INFO L215 NwaCegarLoop]: trace histogram [8, 7, 7, 4, 4, 4, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-08 14:16:15,091 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Ended with exit code 0 [2024-11-08 14:16:15,275 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 9 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable8 [2024-11-08 14:16:15,276 INFO L396 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 14:16:15,276 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 14:16:15,276 INFO L85 PathProgramCache]: Analyzing trace with hash 635379451, now seen corresponding path program 3 times [2024-11-08 14:16:15,276 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 14:16:15,276 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [522741589] [2024-11-08 14:16:15,276 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:16:15,276 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 14:16:15,296 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-08 14:16:15,297 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1977870909] [2024-11-08 14:16:15,298 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-08 14:16:15,298 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 14:16:15,298 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-08 14:16:15,300 INFO L229 MonitoredProcess]: Starting monitored process 10 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-08 14:16:15,301 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Waiting until timeout for monitored process [2024-11-08 14:16:15,357 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2024-11-08 14:16:15,358 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-08 14:16:15,359 INFO L255 TraceCheckSpWp]: Trace formula consists of 144 conjuncts, 42 conjuncts are in the unsatisfiable core [2024-11-08 14:16:15,361 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-08 14:16:15,769 INFO L134 CoverageAnalysis]: Checked inductivity of 129 backedges. 40 proven. 8 refuted. 0 times theorem prover too weak. 81 trivial. 0 not checked. [2024-11-08 14:16:15,769 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-08 14:16:16,786 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 14:16:16,786 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [522741589] [2024-11-08 14:16:16,786 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-08 14:16:16,786 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1977870909] [2024-11-08 14:16:16,786 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1977870909] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-08 14:16:16,786 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-11-08 14:16:16,786 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12] total 12 [2024-11-08 14:16:16,787 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [579410812] [2024-11-08 14:16:16,787 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-11-08 14:16:16,787 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2024-11-08 14:16:16,787 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 14:16:16,788 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2024-11-08 14:16:16,788 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=41, Invalid=231, Unknown=0, NotChecked=0, Total=272 [2024-11-08 14:16:16,788 INFO L87 Difference]: Start difference. First operand 116 states and 155 transitions. Second operand has 12 states, 11 states have (on average 2.3636363636363638) internal successors, (26), 11 states have internal predecessors, (26), 4 states have call successors, (12), 2 states have call predecessors, (12), 3 states have return successors, (11), 5 states have call predecessors, (11), 4 states have call successors, (11) [2024-11-08 14:16:17,294 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 14:16:17,294 INFO L93 Difference]: Finished difference Result 125 states and 163 transitions. [2024-11-08 14:16:17,295 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2024-11-08 14:16:17,295 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 11 states have (on average 2.3636363636363638) internal successors, (26), 11 states have internal predecessors, (26), 4 states have call successors, (12), 2 states have call predecessors, (12), 3 states have return successors, (11), 5 states have call predecessors, (11), 4 states have call successors, (11) Word has length 70 [2024-11-08 14:16:17,295 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 14:16:17,296 INFO L225 Difference]: With dead ends: 125 [2024-11-08 14:16:17,296 INFO L226 Difference]: Without dead ends: 123 [2024-11-08 14:16:17,297 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 96 GetRequests, 79 SyntacticMatches, 0 SemanticMatches, 17 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 30 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=55, Invalid=287, Unknown=0, NotChecked=0, Total=342 [2024-11-08 14:16:17,297 INFO L432 NwaCegarLoop]: 25 mSDtfsCounter, 12 mSDsluCounter, 196 mSDsCounter, 0 mSdLazyCounter, 274 mSolverCounterSat, 8 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 17 SdHoareTripleChecker+Valid, 221 SdHoareTripleChecker+Invalid, 282 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 8 IncrementalHoareTripleChecker+Valid, 274 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2024-11-08 14:16:17,298 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [17 Valid, 221 Invalid, 282 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [8 Valid, 274 Invalid, 0 Unknown, 0 Unchecked, 0.4s Time] [2024-11-08 14:16:17,298 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 123 states. [2024-11-08 14:16:17,321 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 123 to 120. [2024-11-08 14:16:17,322 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 120 states, 68 states have (on average 1.161764705882353) internal successors, (79), 70 states have internal predecessors, (79), 40 states have call successors, (40), 11 states have call predecessors, (40), 11 states have return successors, (39), 38 states have call predecessors, (39), 39 states have call successors, (39) [2024-11-08 14:16:17,323 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 120 states to 120 states and 158 transitions. [2024-11-08 14:16:17,323 INFO L78 Accepts]: Start accepts. Automaton has 120 states and 158 transitions. Word has length 70 [2024-11-08 14:16:17,324 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 14:16:17,324 INFO L471 AbstractCegarLoop]: Abstraction has 120 states and 158 transitions. [2024-11-08 14:16:17,324 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 11 states have (on average 2.3636363636363638) internal successors, (26), 11 states have internal predecessors, (26), 4 states have call successors, (12), 2 states have call predecessors, (12), 3 states have return successors, (11), 5 states have call predecessors, (11), 4 states have call successors, (11) [2024-11-08 14:16:17,324 INFO L276 IsEmpty]: Start isEmpty. Operand 120 states and 158 transitions. [2024-11-08 14:16:17,325 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 77 [2024-11-08 14:16:17,325 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 14:16:17,325 INFO L215 NwaCegarLoop]: trace histogram [9, 8, 8, 4, 4, 4, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-08 14:16:17,341 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Forceful destruction successful, exit code 0 [2024-11-08 14:16:17,525 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 10 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable9 [2024-11-08 14:16:17,526 INFO L396 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 14:16:17,526 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 14:16:17,526 INFO L85 PathProgramCache]: Analyzing trace with hash -375209714, now seen corresponding path program 1 times [2024-11-08 14:16:17,526 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 14:16:17,527 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [395298346] [2024-11-08 14:16:17,527 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:16:17,527 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 14:16:17,549 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-08 14:16:17,550 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1176481209] [2024-11-08 14:16:17,554 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:16:17,554 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 14:16:17,554 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-08 14:16:17,556 INFO L229 MonitoredProcess]: Starting monitored process 11 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-08 14:16:17,558 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Waiting until timeout for monitored process [2024-11-08 14:16:17,617 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:16:17,619 INFO L255 TraceCheckSpWp]: Trace formula consists of 191 conjuncts, 41 conjuncts are in the unsatisfiable core [2024-11-08 14:16:17,621 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-08 14:16:18,156 INFO L134 CoverageAnalysis]: Checked inductivity of 160 backedges. 16 proven. 17 refuted. 0 times theorem prover too weak. 127 trivial. 0 not checked. [2024-11-08 14:16:18,156 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-08 14:16:18,947 INFO L134 CoverageAnalysis]: Checked inductivity of 160 backedges. 16 proven. 8 refuted. 0 times theorem prover too weak. 136 trivial. 0 not checked. [2024-11-08 14:16:18,947 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 14:16:18,947 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [395298346] [2024-11-08 14:16:18,947 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-08 14:16:18,948 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1176481209] [2024-11-08 14:16:18,948 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1176481209] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-08 14:16:18,948 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-08 14:16:18,948 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 10] total 21 [2024-11-08 14:16:18,948 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [325299806] [2024-11-08 14:16:18,948 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-08 14:16:18,949 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 21 states [2024-11-08 14:16:18,949 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 14:16:18,949 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2024-11-08 14:16:18,950 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=64, Invalid=356, Unknown=0, NotChecked=0, Total=420 [2024-11-08 14:16:18,950 INFO L87 Difference]: Start difference. First operand 120 states and 158 transitions. Second operand has 21 states, 19 states have (on average 1.894736842105263) internal successors, (36), 18 states have internal predecessors, (36), 10 states have call successors, (25), 3 states have call predecessors, (25), 2 states have return successors, (24), 8 states have call predecessors, (24), 8 states have call successors, (24) [2024-11-08 14:16:22,898 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 3.24s for a HTC check with result VALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-08 14:16:24,640 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 14:16:24,640 INFO L93 Difference]: Finished difference Result 205 states and 290 transitions. [2024-11-08 14:16:24,640 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 25 states. [2024-11-08 14:16:24,641 INFO L78 Accepts]: Start accepts. Automaton has has 21 states, 19 states have (on average 1.894736842105263) internal successors, (36), 18 states have internal predecessors, (36), 10 states have call successors, (25), 3 states have call predecessors, (25), 2 states have return successors, (24), 8 states have call predecessors, (24), 8 states have call successors, (24) Word has length 76 [2024-11-08 14:16:24,641 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 14:16:24,642 INFO L225 Difference]: With dead ends: 205 [2024-11-08 14:16:24,642 INFO L226 Difference]: Without dead ends: 201 [2024-11-08 14:16:24,643 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 167 GetRequests, 131 SyntacticMatches, 0 SemanticMatches, 36 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 206 ImplicationChecksByTransitivity, 1.6s TimeCoverageRelationStatistics Valid=255, Invalid=1151, Unknown=0, NotChecked=0, Total=1406 [2024-11-08 14:16:24,644 INFO L432 NwaCegarLoop]: 42 mSDtfsCounter, 76 mSDsluCounter, 384 mSDsCounter, 0 mSdLazyCounter, 516 mSolverCounterSat, 96 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 4.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 80 SdHoareTripleChecker+Valid, 426 SdHoareTripleChecker+Invalid, 612 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 96 IncrementalHoareTripleChecker+Valid, 516 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 4.5s IncrementalHoareTripleChecker+Time [2024-11-08 14:16:24,644 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [80 Valid, 426 Invalid, 612 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [96 Valid, 516 Invalid, 0 Unknown, 0 Unchecked, 4.5s Time] [2024-11-08 14:16:24,647 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 201 states. [2024-11-08 14:16:24,716 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 201 to 197. [2024-11-08 14:16:24,717 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 197 states, 105 states have (on average 1.2) internal successors, (126), 106 states have internal predecessors, (126), 77 states have call successors, (77), 14 states have call predecessors, (77), 14 states have return successors, (76), 76 states have call predecessors, (76), 76 states have call successors, (76) [2024-11-08 14:16:24,718 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 197 states to 197 states and 279 transitions. [2024-11-08 14:16:24,720 INFO L78 Accepts]: Start accepts. Automaton has 197 states and 279 transitions. Word has length 76 [2024-11-08 14:16:24,720 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 14:16:24,720 INFO L471 AbstractCegarLoop]: Abstraction has 197 states and 279 transitions. [2024-11-08 14:16:24,721 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 21 states, 19 states have (on average 1.894736842105263) internal successors, (36), 18 states have internal predecessors, (36), 10 states have call successors, (25), 3 states have call predecessors, (25), 2 states have return successors, (24), 8 states have call predecessors, (24), 8 states have call successors, (24) [2024-11-08 14:16:24,721 INFO L276 IsEmpty]: Start isEmpty. Operand 197 states and 279 transitions. [2024-11-08 14:16:24,722 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 91 [2024-11-08 14:16:24,722 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 14:16:24,722 INFO L215 NwaCegarLoop]: trace histogram [11, 10, 10, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-08 14:16:24,739 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Ended with exit code 0 [2024-11-08 14:16:24,922 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 11 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable10 [2024-11-08 14:16:24,923 INFO L396 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 14:16:24,923 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 14:16:24,923 INFO L85 PathProgramCache]: Analyzing trace with hash 1119373286, now seen corresponding path program 4 times [2024-11-08 14:16:24,923 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 14:16:24,923 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1436280901] [2024-11-08 14:16:24,923 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:16:24,924 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 14:16:24,939 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:16:25,006 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-08 14:16:25,007 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:16:25,008 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2024-11-08 14:16:25,008 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:16:25,009 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 13 [2024-11-08 14:16:25,010 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:16:25,012 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 18 [2024-11-08 14:16:25,012 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:16:25,013 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 26 [2024-11-08 14:16:25,014 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:16:25,016 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 31 [2024-11-08 14:16:25,016 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:16:25,018 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 36 [2024-11-08 14:16:25,018 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:16:25,020 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 41 [2024-11-08 14:16:25,021 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:16:25,023 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 51 [2024-11-08 14:16:25,024 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:16:25,026 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 56 [2024-11-08 14:16:25,027 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:16:25,029 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 61 [2024-11-08 14:16:25,030 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:16:25,034 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 66 [2024-11-08 14:16:25,035 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:16:25,038 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 76 [2024-11-08 14:16:25,039 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:16:25,039 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 81 [2024-11-08 14:16:25,040 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:16:25,041 INFO L134 CoverageAnalysis]: Checked inductivity of 245 backedges. 41 proven. 0 refuted. 0 times theorem prover too weak. 204 trivial. 0 not checked. [2024-11-08 14:16:25,042 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 14:16:25,042 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1436280901] [2024-11-08 14:16:25,042 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1436280901] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-08 14:16:25,042 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-08 14:16:25,042 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-08 14:16:25,042 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1860954753] [2024-11-08 14:16:25,043 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-08 14:16:25,043 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-08 14:16:25,043 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 14:16:25,044 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-08 14:16:25,044 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-08 14:16:25,044 INFO L87 Difference]: Start difference. First operand 197 states and 279 transitions. Second operand has 5 states, 5 states have (on average 5.0) internal successors, (25), 5 states have internal predecessors, (25), 3 states have call successors, (15), 2 states have call predecessors, (15), 1 states have return successors, (14), 3 states have call predecessors, (14), 3 states have call successors, (14) [2024-11-08 14:16:25,149 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 14:16:25,149 INFO L93 Difference]: Finished difference Result 250 states and 351 transitions. [2024-11-08 14:16:25,150 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2024-11-08 14:16:25,150 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 5.0) internal successors, (25), 5 states have internal predecessors, (25), 3 states have call successors, (15), 2 states have call predecessors, (15), 1 states have return successors, (14), 3 states have call predecessors, (14), 3 states have call successors, (14) Word has length 90 [2024-11-08 14:16:25,150 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 14:16:25,151 INFO L225 Difference]: With dead ends: 250 [2024-11-08 14:16:25,151 INFO L226 Difference]: Without dead ends: 178 [2024-11-08 14:16:25,152 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 35 GetRequests, 30 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=15, Invalid=27, Unknown=0, NotChecked=0, Total=42 [2024-11-08 14:16:25,152 INFO L432 NwaCegarLoop]: 43 mSDtfsCounter, 6 mSDsluCounter, 100 mSDsCounter, 0 mSdLazyCounter, 39 mSolverCounterSat, 4 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 10 SdHoareTripleChecker+Valid, 143 SdHoareTripleChecker+Invalid, 43 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 4 IncrementalHoareTripleChecker+Valid, 39 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-08 14:16:25,152 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [10 Valid, 143 Invalid, 43 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [4 Valid, 39 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-08 14:16:25,153 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 178 states. [2024-11-08 14:16:25,198 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 178 to 164. [2024-11-08 14:16:25,198 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 164 states, 88 states have (on average 1.1477272727272727) internal successors, (101), 89 states have internal predecessors, (101), 61 states have call successors, (61), 14 states have call predecessors, (61), 14 states have return successors, (60), 60 states have call predecessors, (60), 60 states have call successors, (60) [2024-11-08 14:16:25,199 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 164 states to 164 states and 222 transitions. [2024-11-08 14:16:25,200 INFO L78 Accepts]: Start accepts. Automaton has 164 states and 222 transitions. Word has length 90 [2024-11-08 14:16:25,200 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 14:16:25,200 INFO L471 AbstractCegarLoop]: Abstraction has 164 states and 222 transitions. [2024-11-08 14:16:25,200 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 5.0) internal successors, (25), 5 states have internal predecessors, (25), 3 states have call successors, (15), 2 states have call predecessors, (15), 1 states have return successors, (14), 3 states have call predecessors, (14), 3 states have call successors, (14) [2024-11-08 14:16:25,200 INFO L276 IsEmpty]: Start isEmpty. Operand 164 states and 222 transitions. [2024-11-08 14:16:25,201 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 93 [2024-11-08 14:16:25,201 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 14:16:25,201 INFO L215 NwaCegarLoop]: trace histogram [12, 11, 11, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-08 14:16:25,201 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable11 [2024-11-08 14:16:25,201 INFO L396 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 14:16:25,202 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 14:16:25,202 INFO L85 PathProgramCache]: Analyzing trace with hash 1261079706, now seen corresponding path program 1 times [2024-11-08 14:16:25,202 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 14:16:25,202 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1695482661] [2024-11-08 14:16:25,202 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:16:25,202 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 14:16:25,220 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-08 14:16:25,221 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [463182482] [2024-11-08 14:16:25,221 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:16:25,222 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 14:16:25,222 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-08 14:16:25,223 INFO L229 MonitoredProcess]: Starting monitored process 12 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-08 14:16:25,225 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Waiting until timeout for monitored process [2024-11-08 14:16:25,294 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:16:25,296 INFO L255 TraceCheckSpWp]: Trace formula consists of 222 conjuncts, 47 conjuncts are in the unsatisfiable core [2024-11-08 14:16:25,298 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-08 14:16:26,122 INFO L134 CoverageAnalysis]: Checked inductivity of 284 backedges. 68 proven. 35 refuted. 0 times theorem prover too weak. 181 trivial. 0 not checked. [2024-11-08 14:16:26,123 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-08 14:16:26,333 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 14:16:26,333 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1695482661] [2024-11-08 14:16:26,333 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-08 14:16:26,333 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [463182482] [2024-11-08 14:16:26,333 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [463182482] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-08 14:16:26,333 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-11-08 14:16:26,333 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [17] total 17 [2024-11-08 14:16:26,334 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [711977990] [2024-11-08 14:16:26,334 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-11-08 14:16:26,334 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 17 states [2024-11-08 14:16:26,334 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 14:16:26,335 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2024-11-08 14:16:26,335 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=56, Invalid=324, Unknown=0, NotChecked=0, Total=380 [2024-11-08 14:16:26,335 INFO L87 Difference]: Start difference. First operand 164 states and 222 transitions. Second operand has 17 states, 16 states have (on average 1.75) internal successors, (28), 13 states have internal predecessors, (28), 7 states have call successors, (16), 2 states have call predecessors, (16), 3 states have return successors, (15), 7 states have call predecessors, (15), 6 states have call successors, (15) [2024-11-08 14:16:27,011 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 14:16:27,012 INFO L93 Difference]: Finished difference Result 174 states and 231 transitions. [2024-11-08 14:16:27,012 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 17 states. [2024-11-08 14:16:27,013 INFO L78 Accepts]: Start accepts. Automaton has has 17 states, 16 states have (on average 1.75) internal successors, (28), 13 states have internal predecessors, (28), 7 states have call successors, (16), 2 states have call predecessors, (16), 3 states have return successors, (15), 7 states have call predecessors, (15), 6 states have call successors, (15) Word has length 92 [2024-11-08 14:16:27,013 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 14:16:27,016 INFO L225 Difference]: With dead ends: 174 [2024-11-08 14:16:27,016 INFO L226 Difference]: Without dead ends: 172 [2024-11-08 14:16:27,017 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 101 GetRequests, 78 SyntacticMatches, 0 SemanticMatches, 23 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 81 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=93, Invalid=507, Unknown=0, NotChecked=0, Total=600 [2024-11-08 14:16:27,018 INFO L432 NwaCegarLoop]: 35 mSDtfsCounter, 29 mSDsluCounter, 315 mSDsCounter, 0 mSdLazyCounter, 514 mSolverCounterSat, 14 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 40 SdHoareTripleChecker+Valid, 350 SdHoareTripleChecker+Invalid, 528 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 14 IncrementalHoareTripleChecker+Valid, 514 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.5s IncrementalHoareTripleChecker+Time [2024-11-08 14:16:27,018 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [40 Valid, 350 Invalid, 528 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [14 Valid, 514 Invalid, 0 Unknown, 0 Unchecked, 0.5s Time] [2024-11-08 14:16:27,019 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 172 states. [2024-11-08 14:16:27,069 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 172 to 135. [2024-11-08 14:16:27,070 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 135 states, 73 states have (on average 1.1506849315068493) internal successors, (84), 74 states have internal predecessors, (84), 49 states have call successors, (49), 12 states have call predecessors, (49), 12 states have return successors, (48), 48 states have call predecessors, (48), 48 states have call successors, (48) [2024-11-08 14:16:27,070 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 135 states to 135 states and 181 transitions. [2024-11-08 14:16:27,071 INFO L78 Accepts]: Start accepts. Automaton has 135 states and 181 transitions. Word has length 92 [2024-11-08 14:16:27,071 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 14:16:27,071 INFO L471 AbstractCegarLoop]: Abstraction has 135 states and 181 transitions. [2024-11-08 14:16:27,071 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 17 states, 16 states have (on average 1.75) internal successors, (28), 13 states have internal predecessors, (28), 7 states have call successors, (16), 2 states have call predecessors, (16), 3 states have return successors, (15), 7 states have call predecessors, (15), 6 states have call successors, (15) [2024-11-08 14:16:27,071 INFO L276 IsEmpty]: Start isEmpty. Operand 135 states and 181 transitions. [2024-11-08 14:16:27,072 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 110 [2024-11-08 14:16:27,072 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 14:16:27,072 INFO L215 NwaCegarLoop]: trace histogram [15, 14, 14, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-08 14:16:27,091 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Ended with exit code 0 [2024-11-08 14:16:27,273 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 12 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable12 [2024-11-08 14:16:27,273 INFO L396 AbstractCegarLoop]: === Iteration 14 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 14:16:27,273 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 14:16:27,273 INFO L85 PathProgramCache]: Analyzing trace with hash 1880436805, now seen corresponding path program 2 times [2024-11-08 14:16:27,273 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 14:16:27,273 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1012874876] [2024-11-08 14:16:27,274 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:16:27,274 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 14:16:27,293 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-08 14:16:27,295 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [686097309] [2024-11-08 14:16:27,295 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-08 14:16:27,295 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 14:16:27,295 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-08 14:16:27,297 INFO L229 MonitoredProcess]: Starting monitored process 13 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-08 14:16:27,299 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Waiting until timeout for monitored process [2024-11-08 14:16:27,364 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-08 14:16:27,364 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-08 14:16:27,366 INFO L255 TraceCheckSpWp]: Trace formula consists of 255 conjuncts, 43 conjuncts are in the unsatisfiable core [2024-11-08 14:16:27,368 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-08 14:16:27,902 INFO L134 CoverageAnalysis]: Checked inductivity of 448 backedges. 31 proven. 38 refuted. 0 times theorem prover too weak. 379 trivial. 0 not checked. [2024-11-08 14:16:27,903 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-08 14:16:29,018 INFO L134 CoverageAnalysis]: Checked inductivity of 448 backedges. 28 proven. 32 refuted. 0 times theorem prover too weak. 388 trivial. 0 not checked. [2024-11-08 14:16:29,018 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 14:16:29,018 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1012874876] [2024-11-08 14:16:29,018 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-08 14:16:29,018 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [686097309] [2024-11-08 14:16:29,019 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [686097309] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-08 14:16:29,019 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-08 14:16:29,019 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 10] total 21 [2024-11-08 14:16:29,019 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [631263627] [2024-11-08 14:16:29,019 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-08 14:16:29,019 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 21 states [2024-11-08 14:16:29,019 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 14:16:29,020 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2024-11-08 14:16:29,020 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=68, Invalid=352, Unknown=0, NotChecked=0, Total=420 [2024-11-08 14:16:29,020 INFO L87 Difference]: Start difference. First operand 135 states and 181 transitions. Second operand has 21 states, 21 states have (on average 2.0) internal successors, (42), 18 states have internal predecessors, (42), 11 states have call successors, (36), 3 states have call predecessors, (36), 2 states have return successors, (35), 12 states have call predecessors, (35), 11 states have call successors, (35) [2024-11-08 14:16:33,317 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 14:16:33,317 INFO L93 Difference]: Finished difference Result 219 states and 306 transitions. [2024-11-08 14:16:33,317 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 26 states. [2024-11-08 14:16:33,318 INFO L78 Accepts]: Start accepts. Automaton has has 21 states, 21 states have (on average 2.0) internal successors, (42), 18 states have internal predecessors, (42), 11 states have call successors, (36), 3 states have call predecessors, (36), 2 states have return successors, (35), 12 states have call predecessors, (35), 11 states have call successors, (35) Word has length 109 [2024-11-08 14:16:33,318 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 14:16:33,319 INFO L225 Difference]: With dead ends: 219 [2024-11-08 14:16:33,319 INFO L226 Difference]: Without dead ends: 217 [2024-11-08 14:16:33,320 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 235 GetRequests, 197 SyntacticMatches, 0 SemanticMatches, 38 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 222 ImplicationChecksByTransitivity, 2.2s TimeCoverageRelationStatistics Valid=305, Invalid=1255, Unknown=0, NotChecked=0, Total=1560 [2024-11-08 14:16:33,320 INFO L432 NwaCegarLoop]: 56 mSDtfsCounter, 73 mSDsluCounter, 564 mSDsCounter, 0 mSdLazyCounter, 620 mSolverCounterSat, 95 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 2.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 77 SdHoareTripleChecker+Valid, 620 SdHoareTripleChecker+Invalid, 715 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 95 IncrementalHoareTripleChecker+Valid, 620 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 2.6s IncrementalHoareTripleChecker+Time [2024-11-08 14:16:33,320 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [77 Valid, 620 Invalid, 715 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [95 Valid, 620 Invalid, 0 Unknown, 0 Unchecked, 2.6s Time] [2024-11-08 14:16:33,321 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 217 states. [2024-11-08 14:16:33,388 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 217 to 183. [2024-11-08 14:16:33,388 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 183 states, 98 states have (on average 1.163265306122449) internal successors, (114), 99 states have internal predecessors, (114), 69 states have call successors, (69), 15 states have call predecessors, (69), 15 states have return successors, (68), 68 states have call predecessors, (68), 68 states have call successors, (68) [2024-11-08 14:16:33,390 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 183 states to 183 states and 251 transitions. [2024-11-08 14:16:33,390 INFO L78 Accepts]: Start accepts. Automaton has 183 states and 251 transitions. Word has length 109 [2024-11-08 14:16:33,390 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 14:16:33,390 INFO L471 AbstractCegarLoop]: Abstraction has 183 states and 251 transitions. [2024-11-08 14:16:33,391 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 21 states, 21 states have (on average 2.0) internal successors, (42), 18 states have internal predecessors, (42), 11 states have call successors, (36), 3 states have call predecessors, (36), 2 states have return successors, (35), 12 states have call predecessors, (35), 11 states have call successors, (35) [2024-11-08 14:16:33,391 INFO L276 IsEmpty]: Start isEmpty. Operand 183 states and 251 transitions. [2024-11-08 14:16:33,392 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 113 [2024-11-08 14:16:33,392 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 14:16:33,392 INFO L215 NwaCegarLoop]: trace histogram [15, 14, 14, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-08 14:16:33,406 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Forceful destruction successful, exit code 0 [2024-11-08 14:16:33,593 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 13 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable13 [2024-11-08 14:16:33,593 INFO L396 AbstractCegarLoop]: === Iteration 15 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 14:16:33,593 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 14:16:33,593 INFO L85 PathProgramCache]: Analyzing trace with hash 468383399, now seen corresponding path program 3 times [2024-11-08 14:16:33,593 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 14:16:33,593 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1558541710] [2024-11-08 14:16:33,594 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:16:33,594 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 14:16:33,613 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-08 14:16:33,614 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1496380468] [2024-11-08 14:16:33,614 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-08 14:16:33,614 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 14:16:33,615 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-08 14:16:33,616 INFO L229 MonitoredProcess]: Starting monitored process 14 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-08 14:16:33,620 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Waiting until timeout for monitored process [2024-11-08 14:16:33,692 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2024-11-08 14:16:33,692 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-08 14:16:33,693 INFO L255 TraceCheckSpWp]: Trace formula consists of 188 conjuncts, 66 conjuncts are in the unsatisfiable core [2024-11-08 14:16:33,696 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-08 14:16:35,413 INFO L134 CoverageAnalysis]: Checked inductivity of 453 backedges. 69 proven. 44 refuted. 0 times theorem prover too weak. 340 trivial. 0 not checked. [2024-11-08 14:16:35,413 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-08 14:16:43,695 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 14:16:43,695 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1558541710] [2024-11-08 14:16:43,695 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-08 14:16:43,695 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1496380468] [2024-11-08 14:16:43,695 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1496380468] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-08 14:16:43,695 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-11-08 14:16:43,696 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [19] total 19 [2024-11-08 14:16:43,696 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2060628004] [2024-11-08 14:16:43,696 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-11-08 14:16:43,696 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 19 states [2024-11-08 14:16:43,696 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 14:16:43,697 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 19 interpolants. [2024-11-08 14:16:43,697 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=100, Invalid=712, Unknown=0, NotChecked=0, Total=812 [2024-11-08 14:16:43,697 INFO L87 Difference]: Start difference. First operand 183 states and 251 transitions. Second operand has 19 states, 18 states have (on average 1.8333333333333333) internal successors, (33), 17 states have internal predecessors, (33), 6 states have call successors, (19), 2 states have call predecessors, (19), 3 states have return successors, (18), 8 states have call predecessors, (18), 6 states have call successors, (18) [2024-11-08 14:16:44,989 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 14:16:44,990 INFO L93 Difference]: Finished difference Result 254 states and 351 transitions. [2024-11-08 14:16:44,990 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 19 states. [2024-11-08 14:16:44,990 INFO L78 Accepts]: Start accepts. Automaton has has 19 states, 18 states have (on average 1.8333333333333333) internal successors, (33), 17 states have internal predecessors, (33), 6 states have call successors, (19), 2 states have call predecessors, (19), 3 states have return successors, (18), 8 states have call predecessors, (18), 6 states have call successors, (18) Word has length 112 [2024-11-08 14:16:44,990 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 14:16:44,992 INFO L225 Difference]: With dead ends: 254 [2024-11-08 14:16:44,992 INFO L226 Difference]: Without dead ends: 252 [2024-11-08 14:16:44,992 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 185 GetRequests, 151 SyntacticMatches, 0 SemanticMatches, 34 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 249 ImplicationChecksByTransitivity, 8.3s TimeCoverageRelationStatistics Valid=175, Invalid=1085, Unknown=0, NotChecked=0, Total=1260 [2024-11-08 14:16:44,993 INFO L432 NwaCegarLoop]: 37 mSDtfsCounter, 40 mSDsluCounter, 398 mSDsCounter, 0 mSdLazyCounter, 601 mSolverCounterSat, 32 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.8s Time, 0 mProtectedPredicate, 0 mProtectedAction, 54 SdHoareTripleChecker+Valid, 435 SdHoareTripleChecker+Invalid, 633 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 32 IncrementalHoareTripleChecker+Valid, 601 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.9s IncrementalHoareTripleChecker+Time [2024-11-08 14:16:44,993 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [54 Valid, 435 Invalid, 633 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [32 Valid, 601 Invalid, 0 Unknown, 0 Unchecked, 0.9s Time] [2024-11-08 14:16:44,994 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 252 states. [2024-11-08 14:16:45,091 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 252 to 247. [2024-11-08 14:16:45,092 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 247 states, 130 states have (on average 1.1615384615384616) internal successors, (151), 131 states have internal predecessors, (151), 97 states have call successors, (97), 19 states have call predecessors, (97), 19 states have return successors, (96), 96 states have call predecessors, (96), 96 states have call successors, (96) [2024-11-08 14:16:45,093 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 247 states to 247 states and 344 transitions. [2024-11-08 14:16:45,093 INFO L78 Accepts]: Start accepts. Automaton has 247 states and 344 transitions. Word has length 112 [2024-11-08 14:16:45,093 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 14:16:45,094 INFO L471 AbstractCegarLoop]: Abstraction has 247 states and 344 transitions. [2024-11-08 14:16:45,094 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 19 states, 18 states have (on average 1.8333333333333333) internal successors, (33), 17 states have internal predecessors, (33), 6 states have call successors, (19), 2 states have call predecessors, (19), 3 states have return successors, (18), 8 states have call predecessors, (18), 6 states have call successors, (18) [2024-11-08 14:16:45,094 INFO L276 IsEmpty]: Start isEmpty. Operand 247 states and 344 transitions. [2024-11-08 14:16:45,095 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 115 [2024-11-08 14:16:45,095 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 14:16:45,095 INFO L215 NwaCegarLoop]: trace histogram [16, 15, 15, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-08 14:16:45,107 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Ended with exit code 0 [2024-11-08 14:16:45,295 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 14 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable14 [2024-11-08 14:16:45,296 INFO L396 AbstractCegarLoop]: === Iteration 16 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 14:16:45,296 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 14:16:45,296 INFO L85 PathProgramCache]: Analyzing trace with hash -918263559, now seen corresponding path program 4 times [2024-11-08 14:16:45,296 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 14:16:45,296 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [454014002] [2024-11-08 14:16:45,296 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:16:45,296 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 14:16:45,315 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-08 14:16:45,318 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2059893475] [2024-11-08 14:16:45,318 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2024-11-08 14:16:45,318 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 14:16:45,318 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-08 14:16:45,320 INFO L229 MonitoredProcess]: Starting monitored process 15 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-08 14:16:45,321 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Waiting until timeout for monitored process [2024-11-08 14:16:45,387 INFO L227 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2024-11-08 14:16:45,387 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-08 14:16:45,388 INFO L255 TraceCheckSpWp]: Trace formula consists of 233 conjuncts, 40 conjuncts are in the unsatisfiable core [2024-11-08 14:16:45,389 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-08 14:16:46,576 INFO L134 CoverageAnalysis]: Checked inductivity of 509 backedges. 100 proven. 43 refuted. 0 times theorem prover too weak. 366 trivial. 0 not checked. [2024-11-08 14:16:46,576 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-08 14:16:46,819 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 14:16:46,819 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [454014002] [2024-11-08 14:16:46,819 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-08 14:16:46,819 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2059893475] [2024-11-08 14:16:46,819 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2059893475] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-08 14:16:46,819 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-11-08 14:16:46,819 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [15] total 15 [2024-11-08 14:16:46,819 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1911591582] [2024-11-08 14:16:46,819 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-11-08 14:16:46,819 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 15 states [2024-11-08 14:16:46,820 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 14:16:46,820 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2024-11-08 14:16:46,820 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=50, Invalid=222, Unknown=0, NotChecked=0, Total=272 [2024-11-08 14:16:46,820 INFO L87 Difference]: Start difference. First operand 247 states and 344 transitions. Second operand has 15 states, 14 states have (on average 1.9285714285714286) internal successors, (27), 12 states have internal predecessors, (27), 7 states have call successors, (20), 2 states have call predecessors, (20), 2 states have return successors, (19), 8 states have call predecessors, (19), 6 states have call successors, (19) [2024-11-08 14:16:47,893 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 14:16:47,893 INFO L93 Difference]: Finished difference Result 288 states and 402 transitions. [2024-11-08 14:16:47,894 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2024-11-08 14:16:47,894 INFO L78 Accepts]: Start accepts. Automaton has has 15 states, 14 states have (on average 1.9285714285714286) internal successors, (27), 12 states have internal predecessors, (27), 7 states have call successors, (20), 2 states have call predecessors, (20), 2 states have return successors, (19), 8 states have call predecessors, (19), 6 states have call successors, (19) Word has length 114 [2024-11-08 14:16:47,894 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 14:16:47,898 INFO L225 Difference]: With dead ends: 288 [2024-11-08 14:16:47,898 INFO L226 Difference]: Without dead ends: 286 [2024-11-08 14:16:47,899 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 123 GetRequests, 101 SyntacticMatches, 2 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 47 ImplicationChecksByTransitivity, 0.8s TimeCoverageRelationStatistics Valid=88, Invalid=374, Unknown=0, NotChecked=0, Total=462 [2024-11-08 14:16:47,899 INFO L432 NwaCegarLoop]: 46 mSDtfsCounter, 27 mSDsluCounter, 358 mSDsCounter, 0 mSdLazyCounter, 443 mSolverCounterSat, 26 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.8s Time, 0 mProtectedPredicate, 0 mProtectedAction, 34 SdHoareTripleChecker+Valid, 404 SdHoareTripleChecker+Invalid, 469 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 26 IncrementalHoareTripleChecker+Valid, 443 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.8s IncrementalHoareTripleChecker+Time [2024-11-08 14:16:47,899 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [34 Valid, 404 Invalid, 469 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [26 Valid, 443 Invalid, 0 Unknown, 0 Unchecked, 0.8s Time] [2024-11-08 14:16:47,900 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 286 states. [2024-11-08 14:16:48,017 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 286 to 282. [2024-11-08 14:16:48,017 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 282 states, 147 states have (on average 1.163265306122449) internal successors, (171), 148 states have internal predecessors, (171), 113 states have call successors, (113), 21 states have call predecessors, (113), 21 states have return successors, (112), 112 states have call predecessors, (112), 112 states have call successors, (112) [2024-11-08 14:16:48,018 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 282 states to 282 states and 396 transitions. [2024-11-08 14:16:48,019 INFO L78 Accepts]: Start accepts. Automaton has 282 states and 396 transitions. Word has length 114 [2024-11-08 14:16:48,019 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 14:16:48,019 INFO L471 AbstractCegarLoop]: Abstraction has 282 states and 396 transitions. [2024-11-08 14:16:48,019 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 15 states, 14 states have (on average 1.9285714285714286) internal successors, (27), 12 states have internal predecessors, (27), 7 states have call successors, (20), 2 states have call predecessors, (20), 2 states have return successors, (19), 8 states have call predecessors, (19), 6 states have call successors, (19) [2024-11-08 14:16:48,020 INFO L276 IsEmpty]: Start isEmpty. Operand 282 states and 396 transitions. [2024-11-08 14:16:48,021 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 118 [2024-11-08 14:16:48,021 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 14:16:48,021 INFO L215 NwaCegarLoop]: trace histogram [16, 15, 15, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-08 14:16:48,034 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Ended with exit code 0 [2024-11-08 14:16:48,221 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable15,15 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 14:16:48,222 INFO L396 AbstractCegarLoop]: === Iteration 17 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 14:16:48,222 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 14:16:48,222 INFO L85 PathProgramCache]: Analyzing trace with hash -1051373609, now seen corresponding path program 5 times [2024-11-08 14:16:48,222 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 14:16:48,222 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [496283745] [2024-11-08 14:16:48,222 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:16:48,223 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 14:16:48,258 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-08 14:16:48,262 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1686842226] [2024-11-08 14:16:48,263 INFO L93 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2024-11-08 14:16:48,263 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 14:16:48,263 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-08 14:16:48,264 INFO L229 MonitoredProcess]: Starting monitored process 16 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-08 14:16:48,265 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Waiting until timeout for monitored process [2024-11-08 14:16:48,568 INFO L227 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 6 check-sat command(s) [2024-11-08 14:16:48,568 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-08 14:16:48,569 INFO L255 TraceCheckSpWp]: Trace formula consists of 278 conjuncts, 30 conjuncts are in the unsatisfiable core [2024-11-08 14:16:48,571 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-08 14:16:49,767 INFO L134 CoverageAnalysis]: Checked inductivity of 514 backedges. 71 proven. 41 refuted. 0 times theorem prover too weak. 402 trivial. 0 not checked. [2024-11-08 14:16:49,767 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-08 14:16:50,262 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 14:16:50,262 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [496283745] [2024-11-08 14:16:50,262 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-08 14:16:50,262 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1686842226] [2024-11-08 14:16:50,262 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1686842226] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-08 14:16:50,262 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-11-08 14:16:50,262 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [15] total 15 [2024-11-08 14:16:50,262 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1822486665] [2024-11-08 14:16:50,262 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-11-08 14:16:50,263 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 15 states [2024-11-08 14:16:50,263 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 14:16:50,263 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2024-11-08 14:16:50,263 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=47, Invalid=259, Unknown=0, NotChecked=0, Total=306 [2024-11-08 14:16:50,263 INFO L87 Difference]: Start difference. First operand 282 states and 396 transitions. Second operand has 15 states, 14 states have (on average 2.142857142857143) internal successors, (30), 13 states have internal predecessors, (30), 7 states have call successors, (20), 2 states have call predecessors, (20), 2 states have return successors, (19), 7 states have call predecessors, (19), 6 states have call successors, (19) [2024-11-08 14:16:51,427 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 14:16:51,427 INFO L93 Difference]: Finished difference Result 297 states and 409 transitions. [2024-11-08 14:16:51,428 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2024-11-08 14:16:51,428 INFO L78 Accepts]: Start accepts. Automaton has has 15 states, 14 states have (on average 2.142857142857143) internal successors, (30), 13 states have internal predecessors, (30), 7 states have call successors, (20), 2 states have call predecessors, (20), 2 states have return successors, (19), 7 states have call predecessors, (19), 6 states have call successors, (19) Word has length 117 [2024-11-08 14:16:51,429 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 14:16:51,431 INFO L225 Difference]: With dead ends: 297 [2024-11-08 14:16:51,431 INFO L226 Difference]: Without dead ends: 295 [2024-11-08 14:16:51,431 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 127 GetRequests, 105 SyntacticMatches, 0 SemanticMatches, 22 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 54 ImplicationChecksByTransitivity, 1.1s TimeCoverageRelationStatistics Valid=83, Invalid=469, Unknown=0, NotChecked=0, Total=552 [2024-11-08 14:16:51,432 INFO L432 NwaCegarLoop]: 47 mSDtfsCounter, 23 mSDsluCounter, 448 mSDsCounter, 0 mSdLazyCounter, 514 mSolverCounterSat, 13 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.8s Time, 0 mProtectedPredicate, 0 mProtectedAction, 34 SdHoareTripleChecker+Valid, 495 SdHoareTripleChecker+Invalid, 527 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 13 IncrementalHoareTripleChecker+Valid, 514 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.9s IncrementalHoareTripleChecker+Time [2024-11-08 14:16:51,432 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [34 Valid, 495 Invalid, 527 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [13 Valid, 514 Invalid, 0 Unknown, 0 Unchecked, 0.9s Time] [2024-11-08 14:16:51,433 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 295 states. [2024-11-08 14:16:51,603 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 295 to 290. [2024-11-08 14:16:51,604 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 290 states, 153 states have (on average 1.1568627450980393) internal successors, (177), 154 states have internal predecessors, (177), 113 states have call successors, (113), 23 states have call predecessors, (113), 23 states have return successors, (112), 112 states have call predecessors, (112), 112 states have call successors, (112) [2024-11-08 14:16:51,605 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 290 states to 290 states and 402 transitions. [2024-11-08 14:16:51,606 INFO L78 Accepts]: Start accepts. Automaton has 290 states and 402 transitions. Word has length 117 [2024-11-08 14:16:51,606 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 14:16:51,606 INFO L471 AbstractCegarLoop]: Abstraction has 290 states and 402 transitions. [2024-11-08 14:16:51,607 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 15 states, 14 states have (on average 2.142857142857143) internal successors, (30), 13 states have internal predecessors, (30), 7 states have call successors, (20), 2 states have call predecessors, (20), 2 states have return successors, (19), 7 states have call predecessors, (19), 6 states have call successors, (19) [2024-11-08 14:16:51,607 INFO L276 IsEmpty]: Start isEmpty. Operand 290 states and 402 transitions. [2024-11-08 14:16:51,609 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 124 [2024-11-08 14:16:51,609 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 14:16:51,609 INFO L215 NwaCegarLoop]: trace histogram [17, 16, 16, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-08 14:16:51,619 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Ended with exit code 0 [2024-11-08 14:16:51,809 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 16 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable16 [2024-11-08 14:16:51,810 INFO L396 AbstractCegarLoop]: === Iteration 18 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 14:16:51,810 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 14:16:51,810 INFO L85 PathProgramCache]: Analyzing trace with hash 898620650, now seen corresponding path program 2 times [2024-11-08 14:16:51,810 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 14:16:51,810 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [680353694] [2024-11-08 14:16:51,810 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:16:51,811 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 14:16:51,833 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-08 14:16:51,834 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1633953584] [2024-11-08 14:16:51,834 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-08 14:16:51,834 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 14:16:51,834 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-08 14:16:51,836 INFO L229 MonitoredProcess]: Starting monitored process 17 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-08 14:16:51,841 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Waiting until timeout for monitored process [2024-11-08 14:16:51,925 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-08 14:16:51,925 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-08 14:16:51,927 INFO L255 TraceCheckSpWp]: Trace formula consists of 289 conjuncts, 65 conjuncts are in the unsatisfiable core [2024-11-08 14:16:51,930 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-08 14:16:52,589 INFO L134 CoverageAnalysis]: Checked inductivity of 579 backedges. 76 proven. 53 refuted. 0 times theorem prover too weak. 450 trivial. 0 not checked. [2024-11-08 14:16:52,589 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-08 14:16:54,846 INFO L134 CoverageAnalysis]: Checked inductivity of 579 backedges. 73 proven. 47 refuted. 0 times theorem prover too weak. 459 trivial. 0 not checked. [2024-11-08 14:16:54,847 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 14:16:54,847 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [680353694] [2024-11-08 14:16:54,847 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-08 14:16:54,847 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1633953584] [2024-11-08 14:16:54,847 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1633953584] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-08 14:16:54,847 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-08 14:16:54,847 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [18, 15] total 30 [2024-11-08 14:16:54,847 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [572772187] [2024-11-08 14:16:54,847 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-08 14:16:54,847 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 30 states [2024-11-08 14:16:54,848 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 14:16:54,848 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 30 interpolants. [2024-11-08 14:16:54,849 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=133, Invalid=737, Unknown=0, NotChecked=0, Total=870 [2024-11-08 14:16:54,849 INFO L87 Difference]: Start difference. First operand 290 states and 402 transitions. Second operand has 30 states, 28 states have (on average 1.9642857142857142) internal successors, (55), 27 states have internal predecessors, (55), 14 states have call successors, (40), 3 states have call predecessors, (40), 3 states have return successors, (39), 13 states have call predecessors, (39), 12 states have call successors, (39) [2024-11-08 14:17:00,908 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-08 14:17:04,337 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.75s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-08 14:17:06,109 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 14:17:06,109 INFO L93 Difference]: Finished difference Result 367 states and 505 transitions. [2024-11-08 14:17:06,109 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 38 states. [2024-11-08 14:17:06,110 INFO L78 Accepts]: Start accepts. Automaton has has 30 states, 28 states have (on average 1.9642857142857142) internal successors, (55), 27 states have internal predecessors, (55), 14 states have call successors, (40), 3 states have call predecessors, (40), 3 states have return successors, (39), 13 states have call predecessors, (39), 12 states have call successors, (39) Word has length 123 [2024-11-08 14:17:06,110 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 14:17:06,112 INFO L225 Difference]: With dead ends: 367 [2024-11-08 14:17:06,112 INFO L226 Difference]: Without dead ends: 359 [2024-11-08 14:17:06,113 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 271 GetRequests, 216 SyntacticMatches, 0 SemanticMatches, 55 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 557 ImplicationChecksByTransitivity, 3.8s TimeCoverageRelationStatistics Valid=589, Invalid=2603, Unknown=0, NotChecked=0, Total=3192 [2024-11-08 14:17:06,113 INFO L432 NwaCegarLoop]: 49 mSDtfsCounter, 129 mSDsluCounter, 741 mSDsCounter, 0 mSdLazyCounter, 1022 mSolverCounterSat, 212 mSolverCounterUnsat, 1 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 8.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 129 SdHoareTripleChecker+Valid, 790 SdHoareTripleChecker+Invalid, 1235 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 212 IncrementalHoareTripleChecker+Valid, 1022 IncrementalHoareTripleChecker+Invalid, 1 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 8.5s IncrementalHoareTripleChecker+Time [2024-11-08 14:17:06,114 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [129 Valid, 790 Invalid, 1235 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [212 Valid, 1022 Invalid, 1 Unknown, 0 Unchecked, 8.5s Time] [2024-11-08 14:17:06,114 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 359 states. [2024-11-08 14:17:06,295 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 359 to 316. [2024-11-08 14:17:06,296 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 316 states, 168 states have (on average 1.1428571428571428) internal successors, (192), 170 states have internal predecessors, (192), 120 states have call successors, (120), 27 states have call predecessors, (120), 27 states have return successors, (119), 118 states have call predecessors, (119), 119 states have call successors, (119) [2024-11-08 14:17:06,297 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 316 states to 316 states and 431 transitions. [2024-11-08 14:17:06,298 INFO L78 Accepts]: Start accepts. Automaton has 316 states and 431 transitions. Word has length 123 [2024-11-08 14:17:06,298 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 14:17:06,298 INFO L471 AbstractCegarLoop]: Abstraction has 316 states and 431 transitions. [2024-11-08 14:17:06,299 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 30 states, 28 states have (on average 1.9642857142857142) internal successors, (55), 27 states have internal predecessors, (55), 14 states have call successors, (40), 3 states have call predecessors, (40), 3 states have return successors, (39), 13 states have call predecessors, (39), 12 states have call successors, (39) [2024-11-08 14:17:06,299 INFO L276 IsEmpty]: Start isEmpty. Operand 316 states and 431 transitions. [2024-11-08 14:17:06,300 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 135 [2024-11-08 14:17:06,300 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 14:17:06,300 INFO L215 NwaCegarLoop]: trace histogram [19, 18, 18, 5, 5, 5, 5, 5, 5, 4, 4, 4, 4, 4, 4, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-08 14:17:06,315 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Forceful destruction successful, exit code 0 [2024-11-08 14:17:06,504 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 17 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable17 [2024-11-08 14:17:06,505 INFO L396 AbstractCegarLoop]: === Iteration 19 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 14:17:06,505 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 14:17:06,505 INFO L85 PathProgramCache]: Analyzing trace with hash -1287524986, now seen corresponding path program 6 times [2024-11-08 14:17:06,505 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 14:17:06,505 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1776124954] [2024-11-08 14:17:06,505 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:17:06,505 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 14:17:06,525 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-08 14:17:06,527 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [243177681] [2024-11-08 14:17:06,527 INFO L93 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2024-11-08 14:17:06,527 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 14:17:06,527 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-08 14:17:06,529 INFO L229 MonitoredProcess]: Starting monitored process 18 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-08 14:17:06,534 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (18)] Waiting until timeout for monitored process [2024-11-08 14:17:06,672 INFO L227 tOrderPrioritization]: Assert order MIX_INSIDE_OUTSIDE issued 5 check-sat command(s) [2024-11-08 14:17:06,672 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-08 14:17:06,673 INFO L255 TraceCheckSpWp]: Trace formula consists of 224 conjuncts, 80 conjuncts are in the unsatisfiable core [2024-11-08 14:17:06,676 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-08 14:17:09,905 INFO L134 CoverageAnalysis]: Checked inductivity of 731 backedges. 147 proven. 86 refuted. 0 times theorem prover too weak. 498 trivial. 0 not checked. [2024-11-08 14:17:09,906 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-08 14:17:11,724 INFO L134 CoverageAnalysis]: Checked inductivity of 731 backedges. 184 proven. 38 refuted. 0 times theorem prover too weak. 509 trivial. 0 not checked. [2024-11-08 14:17:11,724 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 14:17:11,724 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1776124954] [2024-11-08 14:17:11,724 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-08 14:17:11,724 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [243177681] [2024-11-08 14:17:11,724 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [243177681] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-08 14:17:11,724 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-08 14:17:11,724 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [19, 12] total 28 [2024-11-08 14:17:11,724 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2092006967] [2024-11-08 14:17:11,724 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-08 14:17:11,725 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 28 states [2024-11-08 14:17:11,725 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 14:17:11,726 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 28 interpolants. [2024-11-08 14:17:11,726 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=115, Invalid=641, Unknown=0, NotChecked=0, Total=756 [2024-11-08 14:17:11,726 INFO L87 Difference]: Start difference. First operand 316 states and 431 transitions. Second operand has 28 states, 26 states have (on average 2.076923076923077) internal successors, (54), 20 states have internal predecessors, (54), 13 states have call successors, (37), 3 states have call predecessors, (37), 3 states have return successors, (36), 15 states have call predecessors, (36), 11 states have call successors, (36) [2024-11-08 14:17:19,834 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 14:17:19,834 INFO L93 Difference]: Finished difference Result 389 states and 539 transitions. [2024-11-08 14:17:19,835 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 34 states. [2024-11-08 14:17:19,835 INFO L78 Accepts]: Start accepts. Automaton has has 28 states, 26 states have (on average 2.076923076923077) internal successors, (54), 20 states have internal predecessors, (54), 13 states have call successors, (37), 3 states have call predecessors, (37), 3 states have return successors, (36), 15 states have call predecessors, (36), 11 states have call successors, (36) Word has length 134 [2024-11-08 14:17:19,835 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 14:17:19,838 INFO L225 Difference]: With dead ends: 389 [2024-11-08 14:17:19,838 INFO L226 Difference]: Without dead ends: 387 [2024-11-08 14:17:19,840 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 288 GetRequests, 240 SyntacticMatches, 0 SemanticMatches, 48 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 503 ImplicationChecksByTransitivity, 6.9s TimeCoverageRelationStatistics Valid=443, Invalid=2007, Unknown=0, NotChecked=0, Total=2450 [2024-11-08 14:17:19,840 INFO L432 NwaCegarLoop]: 46 mSDtfsCounter, 46 mSDsluCounter, 507 mSDsCounter, 0 mSdLazyCounter, 666 mSolverCounterSat, 83 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 3.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 48 SdHoareTripleChecker+Valid, 553 SdHoareTripleChecker+Invalid, 749 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 83 IncrementalHoareTripleChecker+Valid, 666 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 3.5s IncrementalHoareTripleChecker+Time [2024-11-08 14:17:19,841 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [48 Valid, 553 Invalid, 749 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [83 Valid, 666 Invalid, 0 Unknown, 0 Unchecked, 3.5s Time] [2024-11-08 14:17:19,841 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 387 states. [2024-11-08 14:17:20,092 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 387 to 382. [2024-11-08 14:17:20,092 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 382 states, 199 states have (on average 1.150753768844221) internal successors, (229), 201 states have internal predecessors, (229), 152 states have call successors, (152), 30 states have call predecessors, (152), 30 states have return successors, (151), 150 states have call predecessors, (151), 151 states have call successors, (151) [2024-11-08 14:17:20,094 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 382 states to 382 states and 532 transitions. [2024-11-08 14:17:20,095 INFO L78 Accepts]: Start accepts. Automaton has 382 states and 532 transitions. Word has length 134 [2024-11-08 14:17:20,095 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 14:17:20,095 INFO L471 AbstractCegarLoop]: Abstraction has 382 states and 532 transitions. [2024-11-08 14:17:20,096 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 28 states, 26 states have (on average 2.076923076923077) internal successors, (54), 20 states have internal predecessors, (54), 13 states have call successors, (37), 3 states have call predecessors, (37), 3 states have return successors, (36), 15 states have call predecessors, (36), 11 states have call successors, (36) [2024-11-08 14:17:20,096 INFO L276 IsEmpty]: Start isEmpty. Operand 382 states and 532 transitions. [2024-11-08 14:17:20,097 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 140 [2024-11-08 14:17:20,097 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 14:17:20,097 INFO L215 NwaCegarLoop]: trace histogram [20, 19, 19, 5, 5, 5, 5, 5, 5, 5, 5, 4, 4, 4, 4, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-08 14:17:20,105 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (18)] Forceful destruction successful, exit code 0 [2024-11-08 14:17:20,298 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable18,18 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 14:17:20,298 INFO L396 AbstractCegarLoop]: === Iteration 20 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 14:17:20,298 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 14:17:20,298 INFO L85 PathProgramCache]: Analyzing trace with hash 1501327478, now seen corresponding path program 7 times [2024-11-08 14:17:20,298 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 14:17:20,299 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1334933919] [2024-11-08 14:17:20,299 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:17:20,299 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 14:17:20,327 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-08 14:17:20,329 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1632591160] [2024-11-08 14:17:20,329 INFO L93 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2024-11-08 14:17:20,329 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 14:17:20,329 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-08 14:17:20,331 INFO L229 MonitoredProcess]: Starting monitored process 19 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-08 14:17:20,336 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (19)] Waiting until timeout for monitored process [2024-11-08 14:17:20,425 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:17:20,426 INFO L255 TraceCheckSpWp]: Trace formula consists of 320 conjuncts, 80 conjuncts are in the unsatisfiable core [2024-11-08 14:17:20,429 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-08 14:17:22,315 INFO L134 CoverageAnalysis]: Checked inductivity of 809 backedges. 166 proven. 124 refuted. 0 times theorem prover too weak. 519 trivial. 0 not checked. [2024-11-08 14:17:22,315 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-08 14:17:31,594 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 14:17:31,594 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1334933919] [2024-11-08 14:17:31,594 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-08 14:17:31,594 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1632591160] [2024-11-08 14:17:31,594 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1632591160] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-08 14:17:31,594 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-11-08 14:17:31,594 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [24] total 24 [2024-11-08 14:17:31,595 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [11862780] [2024-11-08 14:17:31,595 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-11-08 14:17:31,595 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 24 states [2024-11-08 14:17:31,595 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 14:17:31,596 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 24 interpolants. [2024-11-08 14:17:31,596 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=150, Invalid=842, Unknown=0, NotChecked=0, Total=992 [2024-11-08 14:17:31,596 INFO L87 Difference]: Start difference. First operand 382 states and 532 transitions. Second operand has 24 states, 21 states have (on average 1.6666666666666667) internal successors, (35), 18 states have internal predecessors, (35), 10 states have call successors, (24), 2 states have call predecessors, (24), 3 states have return successors, (23), 11 states have call predecessors, (23), 9 states have call successors, (23) [2024-11-08 14:17:33,192 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 14:17:33,193 INFO L93 Difference]: Finished difference Result 416 states and 580 transitions. [2024-11-08 14:17:33,193 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 24 states. [2024-11-08 14:17:33,193 INFO L78 Accepts]: Start accepts. Automaton has has 24 states, 21 states have (on average 1.6666666666666667) internal successors, (35), 18 states have internal predecessors, (35), 10 states have call successors, (24), 2 states have call predecessors, (24), 3 states have return successors, (23), 11 states have call predecessors, (23), 9 states have call successors, (23) Word has length 139 [2024-11-08 14:17:33,193 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 14:17:33,196 INFO L225 Difference]: With dead ends: 416 [2024-11-08 14:17:33,196 INFO L226 Difference]: Without dead ends: 414 [2024-11-08 14:17:33,197 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 173 GetRequests, 133 SyntacticMatches, 0 SemanticMatches, 40 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 334 ImplicationChecksByTransitivity, 10.0s TimeCoverageRelationStatistics Valid=254, Invalid=1468, Unknown=0, NotChecked=0, Total=1722 [2024-11-08 14:17:33,197 INFO L432 NwaCegarLoop]: 44 mSDtfsCounter, 50 mSDsluCounter, 507 mSDsCounter, 0 mSdLazyCounter, 777 mSolverCounterSat, 36 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.7s Time, 0 mProtectedPredicate, 0 mProtectedAction, 65 SdHoareTripleChecker+Valid, 551 SdHoareTripleChecker+Invalid, 813 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 36 IncrementalHoareTripleChecker+Valid, 777 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.8s IncrementalHoareTripleChecker+Time [2024-11-08 14:17:33,197 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [65 Valid, 551 Invalid, 813 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [36 Valid, 777 Invalid, 0 Unknown, 0 Unchecked, 0.8s Time] [2024-11-08 14:17:33,198 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 414 states. [2024-11-08 14:17:33,484 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 414 to 410. [2024-11-08 14:17:33,485 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 410 states, 212 states have (on average 1.1556603773584906) internal successors, (245), 213 states have internal predecessors, (245), 165 states have call successors, (165), 32 states have call predecessors, (165), 32 states have return successors, (164), 164 states have call predecessors, (164), 164 states have call successors, (164) [2024-11-08 14:17:33,486 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 410 states to 410 states and 574 transitions. [2024-11-08 14:17:33,487 INFO L78 Accepts]: Start accepts. Automaton has 410 states and 574 transitions. Word has length 139 [2024-11-08 14:17:33,487 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 14:17:33,487 INFO L471 AbstractCegarLoop]: Abstraction has 410 states and 574 transitions. [2024-11-08 14:17:33,487 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 24 states, 21 states have (on average 1.6666666666666667) internal successors, (35), 18 states have internal predecessors, (35), 10 states have call successors, (24), 2 states have call predecessors, (24), 3 states have return successors, (23), 11 states have call predecessors, (23), 9 states have call successors, (23) [2024-11-08 14:17:33,487 INFO L276 IsEmpty]: Start isEmpty. Operand 410 states and 574 transitions. [2024-11-08 14:17:33,488 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 140 [2024-11-08 14:17:33,488 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 14:17:33,489 INFO L215 NwaCegarLoop]: trace histogram [20, 19, 19, 5, 5, 5, 5, 5, 5, 5, 5, 4, 4, 4, 4, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-08 14:17:33,508 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (19)] Forceful destruction successful, exit code 0 [2024-11-08 14:17:33,689 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable19,19 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 14:17:33,689 INFO L396 AbstractCegarLoop]: === Iteration 21 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 14:17:33,689 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 14:17:33,690 INFO L85 PathProgramCache]: Analyzing trace with hash -1804546984, now seen corresponding path program 8 times [2024-11-08 14:17:33,690 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 14:17:33,690 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [548154492] [2024-11-08 14:17:33,690 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:17:33,690 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 14:17:33,712 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-08 14:17:33,713 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [475299707] [2024-11-08 14:17:33,713 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-08 14:17:33,713 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 14:17:33,714 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-08 14:17:33,715 INFO L229 MonitoredProcess]: Starting monitored process 20 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-08 14:17:33,718 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (20)] Waiting until timeout for monitored process [2024-11-08 14:17:33,802 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-08 14:17:33,802 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-08 14:17:33,804 INFO L255 TraceCheckSpWp]: Trace formula consists of 320 conjuncts, 52 conjuncts are in the unsatisfiable core [2024-11-08 14:17:33,807 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-08 14:17:44,169 INFO L134 CoverageAnalysis]: Checked inductivity of 809 backedges. 166 proven. 115 refuted. 0 times theorem prover too weak. 528 trivial. 0 not checked. [2024-11-08 14:17:44,170 INFO L311 TraceCheckSpWp]: Computing backward predicates...