./Ultimate.py --spec ../sv-benchmarks/c/properties/unreach-call.prp --file ../sv-benchmarks/c/nla-digbench-scaling/egcd-ll_unwindbound2.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-scaling/egcd-ll_unwindbound2.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 dad54faad409a509f8fe160c736fa981b1b72909c611eb2d7f09e49e6ca0dfcb --- Real Ultimate output --- This is Ultimate 0.2.5-?-c7c6ca5-m [2024-11-08 14:23:51,960 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-11-08 14:23:52,025 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf [2024-11-08 14:23:52,031 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-11-08 14:23:52,033 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-11-08 14:23:52,061 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-11-08 14:23:52,061 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-11-08 14:23:52,062 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-11-08 14:23:52,062 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2024-11-08 14:23:52,066 INFO L153 SettingsManager]: * Use memory slicer=true [2024-11-08 14:23:52,066 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2024-11-08 14:23:52,067 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2024-11-08 14:23:52,067 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2024-11-08 14:23:52,067 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2024-11-08 14:23:52,067 INFO L153 SettingsManager]: * Use SBE=true [2024-11-08 14:23:52,068 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-11-08 14:23:52,068 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2024-11-08 14:23:52,068 INFO L153 SettingsManager]: * sizeof long=4 [2024-11-08 14:23:52,068 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2024-11-08 14:23:52,069 INFO L153 SettingsManager]: * sizeof POINTER=4 [2024-11-08 14:23:52,069 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-11-08 14:23:52,070 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2024-11-08 14:23:52,070 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2024-11-08 14:23:52,071 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2024-11-08 14:23:52,072 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-11-08 14:23:52,072 INFO L153 SettingsManager]: * sizeof long double=12 [2024-11-08 14:23:52,072 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-11-08 14:23:52,072 INFO L153 SettingsManager]: * Use constant arrays=true [2024-11-08 14:23:52,073 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2024-11-08 14:23:52,073 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2024-11-08 14:23:52,073 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2024-11-08 14:23:52,073 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2024-11-08 14:23:52,073 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-08 14:23:52,073 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-11-08 14:23:52,074 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2024-11-08 14:23:52,074 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2024-11-08 14:23:52,074 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2024-11-08 14:23:52,074 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2024-11-08 14:23:52,074 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2024-11-08 14:23:52,075 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2024-11-08 14:23:52,075 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2024-11-08 14:23:52,077 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2024-11-08 14:23:52,077 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 -> dad54faad409a509f8fe160c736fa981b1b72909c611eb2d7f09e49e6ca0dfcb [2024-11-08 14:23:52,349 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-11-08 14:23:52,371 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-11-08 14:23:52,375 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-11-08 14:23:52,376 INFO L270 PluginConnector]: Initializing CDTParser... [2024-11-08 14:23:52,376 INFO L274 PluginConnector]: CDTParser initialized [2024-11-08 14:23:52,377 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/nla-digbench-scaling/egcd-ll_unwindbound2.c [2024-11-08 14:23:53,765 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-11-08 14:23:53,946 INFO L384 CDTParser]: Found 1 translation units. [2024-11-08 14:23:53,947 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/egcd-ll_unwindbound2.c [2024-11-08 14:23:53,956 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/6e24c0908/0acbd336f9af4a4f8f4299df55290a5c/FLAG385571482 [2024-11-08 14:23:53,975 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/6e24c0908/0acbd336f9af4a4f8f4299df55290a5c [2024-11-08 14:23:53,979 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-11-08 14:23:53,980 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2024-11-08 14:23:53,983 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-11-08 14:23:53,984 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-11-08 14:23:53,990 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-11-08 14:23:53,990 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 08.11 02:23:53" (1/1) ... [2024-11-08 14:23:54,013 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@2da3a1f9 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 02:23:54, skipping insertion in model container [2024-11-08 14:23:54,014 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 08.11 02:23:53" (1/1) ... [2024-11-08 14:23:54,041 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-11-08 14:23:54,223 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/egcd-ll_unwindbound2.c[489,502] [2024-11-08 14:23:54,245 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-08 14:23:54,255 INFO L200 MainTranslator]: Completed pre-run [2024-11-08 14:23:54,266 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/egcd-ll_unwindbound2.c[489,502] [2024-11-08 14:23:54,277 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-08 14:23:54,294 INFO L204 MainTranslator]: Completed translation [2024-11-08 14:23:54,295 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 02:23:54 WrapperNode [2024-11-08 14:23:54,295 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-11-08 14:23:54,296 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-11-08 14:23:54,296 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-11-08 14:23:54,296 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-11-08 14:23:54,303 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:23:54" (1/1) ... [2024-11-08 14:23:54,309 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:23:54" (1/1) ... [2024-11-08 14:23:54,326 INFO L138 Inliner]: procedures = 14, calls = 16, calls flagged for inlining = 2, calls inlined = 2, statements flattened = 60 [2024-11-08 14:23:54,326 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-11-08 14:23:54,327 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-11-08 14:23:54,327 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-11-08 14:23:54,327 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-11-08 14:23:54,335 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 02:23:54" (1/1) ... [2024-11-08 14:23:54,335 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 02:23:54" (1/1) ... [2024-11-08 14:23:54,337 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 02:23:54" (1/1) ... [2024-11-08 14:23:54,346 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:23:54,346 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 02:23:54" (1/1) ... [2024-11-08 14:23:54,346 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 02:23:54" (1/1) ... [2024-11-08 14:23:54,349 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 02:23:54" (1/1) ... [2024-11-08 14:23:54,352 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 02:23:54" (1/1) ... [2024-11-08 14:23:54,353 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 02:23:54" (1/1) ... [2024-11-08 14:23:54,353 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 02:23:54" (1/1) ... [2024-11-08 14:23:54,355 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-11-08 14:23:54,356 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2024-11-08 14:23:54,356 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2024-11-08 14:23:54,356 INFO L274 PluginConnector]: RCFGBuilder initialized [2024-11-08 14:23:54,357 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 02:23:54" (1/1) ... [2024-11-08 14:23:54,364 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-08 14:23:54,376 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-08 14:23:54,391 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:23:54,393 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:23:54,428 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2024-11-08 14:23:54,428 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2024-11-08 14:23:54,428 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2024-11-08 14:23:54,428 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2024-11-08 14:23:54,428 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-11-08 14:23:54,428 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-11-08 14:23:54,428 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2024-11-08 14:23:54,428 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2024-11-08 14:23:54,481 INFO L238 CfgBuilder]: Building ICFG [2024-11-08 14:23:54,483 INFO L264 CfgBuilder]: Building CFG for each procedure with an implementation [2024-11-08 14:23:54,618 INFO L? ?]: Removed 5 outVars from TransFormulas that were not future-live. [2024-11-08 14:23:54,618 INFO L287 CfgBuilder]: Performing block encoding [2024-11-08 14:23:54,631 INFO L311 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-11-08 14:23:54,631 INFO L316 CfgBuilder]: Removed 1 assume(true) statements. [2024-11-08 14:23:54,632 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 08.11 02:23:54 BoogieIcfgContainer [2024-11-08 14:23:54,632 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2024-11-08 14:23:54,633 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2024-11-08 14:23:54,634 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2024-11-08 14:23:54,636 INFO L274 PluginConnector]: TraceAbstraction initialized [2024-11-08 14:23:54,637 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 08.11 02:23:53" (1/3) ... [2024-11-08 14:23:54,637 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@19767044 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 08.11 02:23:54, skipping insertion in model container [2024-11-08 14:23:54,637 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 02:23:54" (2/3) ... [2024-11-08 14:23:54,638 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@19767044 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 08.11 02:23:54, skipping insertion in model container [2024-11-08 14:23:54,638 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 08.11 02:23:54" (3/3) ... [2024-11-08 14:23:54,639 INFO L112 eAbstractionObserver]: Analyzing ICFG egcd-ll_unwindbound2.c [2024-11-08 14:23:54,657 INFO L214 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2024-11-08 14:23:54,657 INFO L154 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2024-11-08 14:23:54,712 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2024-11-08 14:23:54,718 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;@6a9d216c, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2024-11-08 14:23:54,718 INFO L334 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2024-11-08 14:23:54,722 INFO L276 IsEmpty]: Start isEmpty. Operand has 30 states, 17 states have (on average 1.411764705882353) internal successors, (24), 18 states have internal predecessors, (24), 9 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2024-11-08 14:23:54,729 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 19 [2024-11-08 14:23:54,729 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 14:23:54,730 INFO L215 NwaCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-08 14:23:54,730 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 14:23:54,736 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 14:23:54,736 INFO L85 PathProgramCache]: Analyzing trace with hash 1165920622, now seen corresponding path program 1 times [2024-11-08 14:23:54,746 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 14:23:54,746 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [727389865] [2024-11-08 14:23:54,747 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:23:54,747 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 14:23:54,864 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:23:54,922 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-08 14:23:54,926 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:23:54,935 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2024-11-08 14:23:54,940 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:23:54,945 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-11-08 14:23:54,945 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 14:23:54,946 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [727389865] [2024-11-08 14:23:54,946 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [727389865] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-08 14:23:54,946 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-08 14:23:54,947 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2024-11-08 14:23:54,949 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2022288651] [2024-11-08 14:23:54,949 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-08 14:23:54,953 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2024-11-08 14:23:54,953 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 14:23:54,977 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2024-11-08 14:23:54,978 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2024-11-08 14:23:54,980 INFO L87 Difference]: Start difference. First operand has 30 states, 17 states have (on average 1.411764705882353) internal successors, (24), 18 states have internal predecessors, (24), 9 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) 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, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) [2024-11-08 14:23:55,004 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 14:23:55,004 INFO L93 Difference]: Finished difference Result 57 states and 89 transitions. [2024-11-08 14:23:55,005 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2024-11-08 14:23:55,006 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, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) Word has length 18 [2024-11-08 14:23:55,007 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 14:23:55,013 INFO L225 Difference]: With dead ends: 57 [2024-11-08 14:23:55,013 INFO L226 Difference]: Without dead ends: 26 [2024-11-08 14:23:55,016 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 8 GetRequests, 8 SyntacticMatches, 0 SemanticMatches, 0 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2024-11-08 14:23:55,020 INFO L432 NwaCegarLoop]: 39 mSDtfsCounter, 0 mSDsluCounter, 0 mSDsCounter, 0 mSdLazyCounter, 0 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 39 SdHoareTripleChecker+Invalid, 0 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 0 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-08 14:23:55,022 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 39 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 0 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-08 14:23:55,037 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 26 states. [2024-11-08 14:23:55,055 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 26 to 26. [2024-11-08 14:23:55,057 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 26 states, 14 states have (on average 1.2857142857142858) internal successors, (18), 15 states have internal predecessors, (18), 9 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2024-11-08 14:23:55,059 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 26 states to 26 states and 35 transitions. [2024-11-08 14:23:55,060 INFO L78 Accepts]: Start accepts. Automaton has 26 states and 35 transitions. Word has length 18 [2024-11-08 14:23:55,062 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 14:23:55,062 INFO L471 AbstractCegarLoop]: Abstraction has 26 states and 35 transitions. [2024-11-08 14:23:55,062 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, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) [2024-11-08 14:23:55,062 INFO L276 IsEmpty]: Start isEmpty. Operand 26 states and 35 transitions. [2024-11-08 14:23:55,064 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 20 [2024-11-08 14:23:55,064 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 14:23:55,065 INFO L215 NwaCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-08 14:23:55,065 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2024-11-08 14:23:55,065 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 14:23:55,066 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 14:23:55,066 INFO L85 PathProgramCache]: Analyzing trace with hash -542319922, now seen corresponding path program 1 times [2024-11-08 14:23:55,067 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 14:23:55,067 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1013281592] [2024-11-08 14:23:55,067 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:23:55,068 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 14:23:55,102 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:23:55,214 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-08 14:23:55,218 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:23:55,228 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2024-11-08 14:23:55,232 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:23:55,246 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-11-08 14:23:55,246 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 14:23:55,247 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1013281592] [2024-11-08 14:23:55,247 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1013281592] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-08 14:23:55,247 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-08 14:23:55,250 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2024-11-08 14:23:55,250 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [651039298] [2024-11-08 14:23:55,250 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-08 14:23:55,251 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2024-11-08 14:23:55,251 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 14:23:55,252 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2024-11-08 14:23:55,252 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2024-11-08 14:23:55,252 INFO L87 Difference]: Start difference. First operand 26 states and 35 transitions. Second operand has 4 states, 4 states have (on average 2.75) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2024-11-08 14:23:55,276 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 14:23:55,276 INFO L93 Difference]: Finished difference Result 38 states and 50 transitions. [2024-11-08 14:23:55,277 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2024-11-08 14:23:55,277 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 2.75) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) Word has length 19 [2024-11-08 14:23:55,277 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 14:23:55,278 INFO L225 Difference]: With dead ends: 38 [2024-11-08 14:23:55,278 INFO L226 Difference]: Without dead ends: 28 [2024-11-08 14:23:55,279 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 7 GetRequests, 5 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2024-11-08 14:23:55,280 INFO L432 NwaCegarLoop]: 33 mSDtfsCounter, 5 mSDsluCounter, 54 mSDsCounter, 0 mSdLazyCounter, 8 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 5 SdHoareTripleChecker+Valid, 87 SdHoareTripleChecker+Invalid, 8 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 8 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-08 14:23:55,281 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [5 Valid, 87 Invalid, 8 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 8 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-08 14:23:55,281 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 28 states. [2024-11-08 14:23:55,286 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 28 to 28. [2024-11-08 14:23:55,287 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 28 states, 16 states have (on average 1.25) internal successors, (20), 17 states have internal predecessors, (20), 9 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2024-11-08 14:23:55,288 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 28 states to 28 states and 37 transitions. [2024-11-08 14:23:55,288 INFO L78 Accepts]: Start accepts. Automaton has 28 states and 37 transitions. Word has length 19 [2024-11-08 14:23:55,289 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 14:23:55,289 INFO L471 AbstractCegarLoop]: Abstraction has 28 states and 37 transitions. [2024-11-08 14:23:55,290 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 2.75) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2024-11-08 14:23:55,290 INFO L276 IsEmpty]: Start isEmpty. Operand 28 states and 37 transitions. [2024-11-08 14:23:55,290 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 20 [2024-11-08 14:23:55,291 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 14:23:55,291 INFO L215 NwaCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-08 14:23:55,291 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2024-11-08 14:23:55,291 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 14:23:55,291 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 14:23:55,292 INFO L85 PathProgramCache]: Analyzing trace with hash -540651626, now seen corresponding path program 1 times [2024-11-08 14:23:55,292 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 14:23:55,292 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [55507761] [2024-11-08 14:23:55,292 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:23:55,292 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 14:23:55,328 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-08 14:23:55,331 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [206497963] [2024-11-08 14:23:55,333 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:23:55,333 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 14:23:55,333 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-08 14:23:55,335 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:23:55,336 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:23:55,402 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:23:55,407 INFO L255 TraceCheckSpWp]: Trace formula consists of 71 conjuncts, 9 conjuncts are in the unsatisfiable core [2024-11-08 14:23:55,414 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-08 14:23:55,535 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-11-08 14:23:55,536 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-08 14:23:55,537 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 14:23:55,538 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [55507761] [2024-11-08 14:23:55,538 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-08 14:23:55,539 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [206497963] [2024-11-08 14:23:55,540 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [206497963] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-08 14:23:55,540 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-08 14:23:55,540 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-08 14:23:55,541 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1225610488] [2024-11-08 14:23:55,541 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-08 14:23:55,541 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-08 14:23:55,542 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 14:23:55,543 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-08 14:23:55,545 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-08 14:23:55,545 INFO L87 Difference]: Start difference. First operand 28 states and 37 transitions. Second operand has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2024-11-08 14:23:55,613 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 14:23:55,614 INFO L93 Difference]: Finished difference Result 45 states and 62 transitions. [2024-11-08 14:23:55,615 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-08 14:23:55,616 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) Word has length 19 [2024-11-08 14:23:55,616 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 14:23:55,617 INFO L225 Difference]: With dead ends: 45 [2024-11-08 14:23:55,617 INFO L226 Difference]: Without dead ends: 43 [2024-11-08 14:23:55,617 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 19 GetRequests, 15 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:23:55,618 INFO L432 NwaCegarLoop]: 32 mSDtfsCounter, 6 mSDsluCounter, 86 mSDsCounter, 0 mSdLazyCounter, 31 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 12 SdHoareTripleChecker+Valid, 118 SdHoareTripleChecker+Invalid, 33 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 31 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-08 14:23:55,619 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [12 Valid, 118 Invalid, 33 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 31 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-08 14:23:55,620 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 43 states. [2024-11-08 14:23:55,629 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 43 to 42. [2024-11-08 14:23:55,630 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 42 states, 23 states have (on average 1.3043478260869565) internal successors, (30), 25 states have internal predecessors, (30), 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:23:55,631 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 42 states to 42 states and 59 transitions. [2024-11-08 14:23:55,632 INFO L78 Accepts]: Start accepts. Automaton has 42 states and 59 transitions. Word has length 19 [2024-11-08 14:23:55,632 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 14:23:55,636 INFO L471 AbstractCegarLoop]: Abstraction has 42 states and 59 transitions. [2024-11-08 14:23:55,636 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2024-11-08 14:23:55,637 INFO L276 IsEmpty]: Start isEmpty. Operand 42 states and 59 transitions. [2024-11-08 14:23:55,637 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 25 [2024-11-08 14:23:55,638 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 14:23:55,638 INFO L215 NwaCegarLoop]: trace histogram [2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-08 14:23:55,651 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:23:55,841 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2,2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 14:23:55,842 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 14:23:55,842 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 14:23:55,842 INFO L85 PathProgramCache]: Analyzing trace with hash -276555716, now seen corresponding path program 1 times [2024-11-08 14:23:55,843 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 14:23:55,843 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [648573276] [2024-11-08 14:23:55,843 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:23:55,843 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 14:23:55,867 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-08 14:23:55,872 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1849531848] [2024-11-08 14:23:55,874 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:23:55,874 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 14:23:55,874 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-08 14:23:55,876 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:23:55,878 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:23:55,930 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:23:55,933 INFO L255 TraceCheckSpWp]: Trace formula consists of 80 conjuncts, 9 conjuncts are in the unsatisfiable core [2024-11-08 14:23:55,935 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-08 14:23:56,017 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-11-08 14:23:56,017 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-08 14:23:56,017 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 14:23:56,018 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [648573276] [2024-11-08 14:23:56,018 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-08 14:23:56,018 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1849531848] [2024-11-08 14:23:56,018 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1849531848] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-08 14:23:56,019 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-08 14:23:56,019 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-08 14:23:56,019 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1152980808] [2024-11-08 14:23:56,019 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-08 14:23:56,020 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-08 14:23:56,020 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 14:23:56,020 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-08 14:23:56,021 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-08 14:23:56,021 INFO L87 Difference]: Start difference. First operand 42 states and 59 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, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2024-11-08 14:23:56,097 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 14:23:56,097 INFO L93 Difference]: Finished difference Result 49 states and 65 transitions. [2024-11-08 14:23:56,097 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-08 14:23:56,098 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, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) Word has length 24 [2024-11-08 14:23:56,098 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 14:23:56,100 INFO L225 Difference]: With dead ends: 49 [2024-11-08 14:23:56,100 INFO L226 Difference]: Without dead ends: 47 [2024-11-08 14:23:56,101 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 24 GetRequests, 20 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2024-11-08 14:23:56,102 INFO L432 NwaCegarLoop]: 38 mSDtfsCounter, 7 mSDsluCounter, 94 mSDsCounter, 0 mSdLazyCounter, 39 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 12 SdHoareTripleChecker+Valid, 132 SdHoareTripleChecker+Invalid, 39 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 39 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-08 14:23:56,102 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [12 Valid, 132 Invalid, 39 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 39 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-08 14:23:56,103 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 47 states. [2024-11-08 14:23:56,113 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 47 to 46. [2024-11-08 14:23:56,117 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 46 states, 26 states have (on average 1.2692307692307692) internal successors, (33), 28 states have internal predecessors, (33), 15 states have call successors, (15), 4 states have call predecessors, (15), 4 states have return successors, (14), 13 states have call predecessors, (14), 14 states have call successors, (14) [2024-11-08 14:23:56,118 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 46 states to 46 states and 62 transitions. [2024-11-08 14:23:56,119 INFO L78 Accepts]: Start accepts. Automaton has 46 states and 62 transitions. Word has length 24 [2024-11-08 14:23:56,119 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 14:23:56,119 INFO L471 AbstractCegarLoop]: Abstraction has 46 states and 62 transitions. [2024-11-08 14:23:56,119 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, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2024-11-08 14:23:56,119 INFO L276 IsEmpty]: Start isEmpty. Operand 46 states and 62 transitions. [2024-11-08 14:23:56,120 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 30 [2024-11-08 14:23:56,120 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 14:23:56,120 INFO L215 NwaCegarLoop]: trace histogram [3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-08 14:23:56,140 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Ended with exit code 0 [2024-11-08 14:23:56,328 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,SelfDestructingSolverStorable3 [2024-11-08 14:23:56,328 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 14:23:56,329 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 14:23:56,329 INFO L85 PathProgramCache]: Analyzing trace with hash -1836785898, now seen corresponding path program 1 times [2024-11-08 14:23:56,329 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 14:23:56,329 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [70406304] [2024-11-08 14:23:56,329 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:23:56,329 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 14:23:56,347 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-08 14:23:56,349 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [999026606] [2024-11-08 14:23:56,349 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:23:56,349 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 14:23:56,349 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-08 14:23:56,351 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:23:56,352 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:23:56,397 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:23:56,398 INFO L255 TraceCheckSpWp]: Trace formula consists of 89 conjuncts, 12 conjuncts are in the unsatisfiable core [2024-11-08 14:23:56,400 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-08 14:23:56,503 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 8 trivial. 0 not checked. [2024-11-08 14:23:56,504 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-08 14:23:56,504 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 14:23:56,505 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [70406304] [2024-11-08 14:23:56,505 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-08 14:23:56,505 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [999026606] [2024-11-08 14:23:56,505 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [999026606] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-08 14:23:56,505 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-08 14:23:56,506 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-08 14:23:56,506 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [124493800] [2024-11-08 14:23:56,506 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-08 14:23:56,507 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-08 14:23:56,507 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 14:23:56,508 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-08 14:23:56,508 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-08 14:23:56,511 INFO L87 Difference]: Start difference. First operand 46 states and 62 transitions. Second operand has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (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:23:56,573 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 14:23:56,574 INFO L93 Difference]: Finished difference Result 71 states and 103 transitions. [2024-11-08 14:23:56,574 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-08 14:23:56,574 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, (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:23:56,575 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 14:23:56,577 INFO L225 Difference]: With dead ends: 71 [2024-11-08 14:23:56,578 INFO L226 Difference]: Without dead ends: 67 [2024-11-08 14:23:56,578 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 29 GetRequests, 25 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2024-11-08 14:23:56,579 INFO L432 NwaCegarLoop]: 31 mSDtfsCounter, 7 mSDsluCounter, 80 mSDsCounter, 0 mSdLazyCounter, 36 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 11 SdHoareTripleChecker+Valid, 111 SdHoareTripleChecker+Invalid, 37 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 36 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-08 14:23:56,579 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [11 Valid, 111 Invalid, 37 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 36 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-08 14:23:56,585 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 67 states. [2024-11-08 14:23:56,601 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 67 to 67. [2024-11-08 14:23:56,602 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 67 states, 35 states have (on average 1.3428571428571427) internal successors, (47), 39 states have internal predecessors, (47), 26 states have call successors, (26), 5 states have call predecessors, (26), 5 states have return successors, (23), 22 states have call predecessors, (23), 23 states have call successors, (23) [2024-11-08 14:23:56,603 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 67 states to 67 states and 96 transitions. [2024-11-08 14:23:56,604 INFO L78 Accepts]: Start accepts. Automaton has 67 states and 96 transitions. Word has length 29 [2024-11-08 14:23:56,604 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 14:23:56,604 INFO L471 AbstractCegarLoop]: Abstraction has 67 states and 96 transitions. [2024-11-08 14:23:56,605 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, (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:23:56,605 INFO L276 IsEmpty]: Start isEmpty. Operand 67 states and 96 transitions. [2024-11-08 14:23:56,606 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 36 [2024-11-08 14:23:56,606 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 14:23:56,606 INFO L215 NwaCegarLoop]: trace histogram [4, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-08 14:23:56,623 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Forceful destruction successful, exit code 0 [2024-11-08 14:23:56,810 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 14:23:56,811 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 14:23:56,811 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 14:23:56,812 INFO L85 PathProgramCache]: Analyzing trace with hash 1071030291, now seen corresponding path program 1 times [2024-11-08 14:23:56,812 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 14:23:56,812 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1621952828] [2024-11-08 14:23:56,812 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:23:56,812 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 14:23:56,825 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:23:56,933 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-08 14:23:56,934 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:23:56,942 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2024-11-08 14:23:56,943 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:23:56,949 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 15 [2024-11-08 14:23:56,950 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:23:56,953 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 20 [2024-11-08 14:23:56,958 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:23:56,964 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 25 [2024-11-08 14:23:56,966 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:23:56,975 INFO L134 CoverageAnalysis]: Checked inductivity of 22 backedges. 6 proven. 0 refuted. 0 times theorem prover too weak. 16 trivial. 0 not checked. [2024-11-08 14:23:56,975 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 14:23:56,976 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1621952828] [2024-11-08 14:23:56,976 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1621952828] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-08 14:23:56,976 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-08 14:23:56,976 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-08 14:23:56,976 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [866953881] [2024-11-08 14:23:56,977 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-08 14:23:56,977 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-08 14:23:56,977 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 14:23:56,978 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-08 14:23:56,978 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-08 14:23:56,979 INFO L87 Difference]: Start difference. First operand 67 states and 96 transitions. Second operand has 5 states, 4 states have (on average 3.75) internal successors, (15), 4 states have internal predecessors, (15), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (5), 1 states have call predecessors, (5), 1 states have call successors, (5) [2024-11-08 14:23:57,036 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 14:23:57,036 INFO L93 Difference]: Finished difference Result 83 states and 119 transitions. [2024-11-08 14:23:57,036 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-08 14:23:57,037 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 4 states have (on average 3.75) internal successors, (15), 4 states have internal predecessors, (15), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (5), 1 states have call predecessors, (5), 1 states have call successors, (5) Word has length 35 [2024-11-08 14:23:57,037 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 14:23:57,039 INFO L225 Difference]: With dead ends: 83 [2024-11-08 14:23:57,039 INFO L226 Difference]: Without dead ends: 81 [2024-11-08 14:23:57,039 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 17 GetRequests, 13 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:23:57,040 INFO L432 NwaCegarLoop]: 39 mSDtfsCounter, 3 mSDsluCounter, 96 mSDsCounter, 0 mSdLazyCounter, 26 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 6 SdHoareTripleChecker+Valid, 135 SdHoareTripleChecker+Invalid, 26 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 26 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-08 14:23:57,040 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [6 Valid, 135 Invalid, 26 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 26 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-08 14:23:57,041 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 81 states. [2024-11-08 14:23:57,067 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 81 to 74. [2024-11-08 14:23:57,069 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 74 states, 38 states have (on average 1.3157894736842106) internal successors, (50), 45 states have internal predecessors, (50), 29 states have call successors, (29), 6 states have call predecessors, (29), 6 states have return successors, (26), 22 states have call predecessors, (26), 26 states have call successors, (26) [2024-11-08 14:23:57,071 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 74 states to 74 states and 105 transitions. [2024-11-08 14:23:57,074 INFO L78 Accepts]: Start accepts. Automaton has 74 states and 105 transitions. Word has length 35 [2024-11-08 14:23:57,075 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 14:23:57,075 INFO L471 AbstractCegarLoop]: Abstraction has 74 states and 105 transitions. [2024-11-08 14:23:57,075 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 4 states have (on average 3.75) internal successors, (15), 4 states have internal predecessors, (15), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (5), 1 states have call predecessors, (5), 1 states have call successors, (5) [2024-11-08 14:23:57,075 INFO L276 IsEmpty]: Start isEmpty. Operand 74 states and 105 transitions. [2024-11-08 14:23:57,076 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 39 [2024-11-08 14:23:57,077 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 14:23:57,077 INFO L215 NwaCegarLoop]: trace histogram [4, 3, 3, 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:23:57,077 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5 [2024-11-08 14:23:57,078 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 14:23:57,078 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 14:23:57,078 INFO L85 PathProgramCache]: Analyzing trace with hash 1689492770, now seen corresponding path program 1 times [2024-11-08 14:23:57,079 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 14:23:57,079 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [874530040] [2024-11-08 14:23:57,079 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:23:57,079 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 14:23:57,103 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:23:57,189 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-08 14:23:57,191 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:23:57,197 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2024-11-08 14:23:57,201 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:23:57,206 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 15 [2024-11-08 14:23:57,209 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:23:57,218 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 20 [2024-11-08 14:23:57,219 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:23:57,226 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 25 [2024-11-08 14:23:57,232 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:23:57,239 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 6 proven. 2 refuted. 0 times theorem prover too weak. 16 trivial. 0 not checked. [2024-11-08 14:23:57,239 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 14:23:57,240 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [874530040] [2024-11-08 14:23:57,240 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [874530040] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-08 14:23:57,240 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [680806832] [2024-11-08 14:23:57,240 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:23:57,240 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 14:23:57,241 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-08 14:23:57,244 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:23:57,246 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:23:57,301 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:23:57,302 INFO L255 TraceCheckSpWp]: Trace formula consists of 111 conjuncts, 5 conjuncts are in the unsatisfiable core [2024-11-08 14:23:57,304 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-08 14:23:57,367 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 6 proven. 2 refuted. 0 times theorem prover too weak. 16 trivial. 0 not checked. [2024-11-08 14:23:57,367 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-08 14:23:57,433 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 6 proven. 2 refuted. 0 times theorem prover too weak. 16 trivial. 0 not checked. [2024-11-08 14:23:57,434 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [680806832] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-08 14:23:57,434 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-08 14:23:57,434 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 4, 5] total 5 [2024-11-08 14:23:57,434 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1058146510] [2024-11-08 14:23:57,435 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-08 14:23:57,435 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-08 14:23:57,435 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 14:23:57,436 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-08 14:23:57,436 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2024-11-08 14:23:57,436 INFO L87 Difference]: Start difference. First operand 74 states and 105 transitions. Second operand has 5 states, 5 states have (on average 4.8) internal successors, (24), 5 states have internal predecessors, (24), 3 states have call successors, (11), 4 states have call predecessors, (11), 3 states have return successors, (10), 2 states have call predecessors, (10), 2 states have call successors, (10) [2024-11-08 14:23:57,478 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 14:23:57,478 INFO L93 Difference]: Finished difference Result 117 states and 148 transitions. [2024-11-08 14:23:57,478 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2024-11-08 14:23:57,479 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 4.8) internal successors, (24), 5 states have internal predecessors, (24), 3 states have call successors, (11), 4 states have call predecessors, (11), 3 states have return successors, (10), 2 states have call predecessors, (10), 2 states have call successors, (10) Word has length 38 [2024-11-08 14:23:57,479 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 14:23:57,480 INFO L225 Difference]: With dead ends: 117 [2024-11-08 14:23:57,480 INFO L226 Difference]: Without dead ends: 98 [2024-11-08 14:23:57,481 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 89 GetRequests, 82 SyntacticMatches, 3 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=12, Invalid=18, Unknown=0, NotChecked=0, Total=30 [2024-11-08 14:23:57,482 INFO L432 NwaCegarLoop]: 35 mSDtfsCounter, 7 mSDsluCounter, 72 mSDsCounter, 0 mSdLazyCounter, 19 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 7 SdHoareTripleChecker+Valid, 107 SdHoareTripleChecker+Invalid, 19 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 19 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-08 14:23:57,482 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [7 Valid, 107 Invalid, 19 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 19 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-08 14:23:57,483 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 98 states. [2024-11-08 14:23:57,495 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 98 to 96. [2024-11-08 14:23:57,495 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 96 states, 56 states have (on average 1.2142857142857142) internal successors, (68), 62 states have internal predecessors, (68), 29 states have call successors, (29), 11 states have call predecessors, (29), 10 states have return successors, (26), 22 states have call predecessors, (26), 26 states have call successors, (26) [2024-11-08 14:23:57,496 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 96 states to 96 states and 123 transitions. [2024-11-08 14:23:57,497 INFO L78 Accepts]: Start accepts. Automaton has 96 states and 123 transitions. Word has length 38 [2024-11-08 14:23:57,497 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 14:23:57,497 INFO L471 AbstractCegarLoop]: Abstraction has 96 states and 123 transitions. [2024-11-08 14:23:57,497 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 4.8) internal successors, (24), 5 states have internal predecessors, (24), 3 states have call successors, (11), 4 states have call predecessors, (11), 3 states have return successors, (10), 2 states have call predecessors, (10), 2 states have call successors, (10) [2024-11-08 14:23:57,497 INFO L276 IsEmpty]: Start isEmpty. Operand 96 states and 123 transitions. [2024-11-08 14:23:57,498 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 39 [2024-11-08 14:23:57,498 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 14:23:57,498 INFO L215 NwaCegarLoop]: trace histogram [4, 3, 3, 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:23:57,515 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:23:57,699 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 14:23:57,699 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 14:23:57,699 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 14:23:57,700 INFO L85 PathProgramCache]: Analyzing trace with hash 1691161066, now seen corresponding path program 1 times [2024-11-08 14:23:57,700 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 14:23:57,700 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1466010932] [2024-11-08 14:23:57,700 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:23:57,700 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 14:23:57,725 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-08 14:23:57,726 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1509375616] [2024-11-08 14:23:57,726 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:23:57,726 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 14:23:57,727 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-08 14:23:57,730 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:23:57,732 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:23:57,778 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:23:57,779 INFO L255 TraceCheckSpWp]: Trace formula consists of 111 conjuncts, 11 conjuncts are in the unsatisfiable core [2024-11-08 14:23:57,781 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-08 14:23:57,861 INFO L134 CoverageAnalysis]: Checked inductivity of 25 backedges. 6 proven. 0 refuted. 0 times theorem prover too weak. 19 trivial. 0 not checked. [2024-11-08 14:23:57,861 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-08 14:23:57,861 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 14:23:57,862 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1466010932] [2024-11-08 14:23:57,862 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-08 14:23:57,862 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1509375616] [2024-11-08 14:23:57,862 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1509375616] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-08 14:23:57,862 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-08 14:23:57,862 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-08 14:23:57,862 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [32292373] [2024-11-08 14:23:57,863 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-08 14:23:57,863 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-08 14:23:57,863 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 14:23:57,863 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-08 14:23:57,864 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-08 14:23:57,864 INFO L87 Difference]: Start difference. First operand 96 states and 123 transitions. Second operand has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 2 states have call successors, (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:23:57,931 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 14:23:57,932 INFO L93 Difference]: Finished difference Result 102 states and 128 transitions. [2024-11-08 14:23:57,932 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-08 14:23:57,932 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 2 states have call successors, (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 38 [2024-11-08 14:23:57,933 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 14:23:57,934 INFO L225 Difference]: With dead ends: 102 [2024-11-08 14:23:57,936 INFO L226 Difference]: Without dead ends: 99 [2024-11-08 14:23:57,936 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 38 GetRequests, 34 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2024-11-08 14:23:57,937 INFO L432 NwaCegarLoop]: 30 mSDtfsCounter, 5 mSDsluCounter, 82 mSDsCounter, 0 mSdLazyCounter, 27 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 7 SdHoareTripleChecker+Valid, 112 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:23:57,937 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [7 Valid, 112 Invalid, 28 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 27 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-08 14:23:57,938 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 99 states. [2024-11-08 14:23:57,957 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 99 to 99. [2024-11-08 14:23:57,958 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 99 states, 59 states have (on average 1.2033898305084745) internal successors, (71), 65 states have internal predecessors, (71), 28 states have call successors, (28), 12 states have call predecessors, (28), 11 states have return successors, (25), 21 states have call predecessors, (25), 25 states have call successors, (25) [2024-11-08 14:23:57,960 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 99 states to 99 states and 124 transitions. [2024-11-08 14:23:57,961 INFO L78 Accepts]: Start accepts. Automaton has 99 states and 124 transitions. Word has length 38 [2024-11-08 14:23:57,961 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 14:23:57,961 INFO L471 AbstractCegarLoop]: Abstraction has 99 states and 124 transitions. [2024-11-08 14:23:57,961 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 2 states have call successors, (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:23:57,961 INFO L276 IsEmpty]: Start isEmpty. Operand 99 states and 124 transitions. [2024-11-08 14:23:57,962 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 41 [2024-11-08 14:23:57,962 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 14:23:57,962 INFO L215 NwaCegarLoop]: trace histogram [5, 4, 4, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-08 14:23:57,975 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Ended with exit code 0 [2024-11-08 14:23:58,163 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 14:23:58,163 INFO L396 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 14:23:58,163 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 14:23:58,163 INFO L85 PathProgramCache]: Analyzing trace with hash 1925895455, now seen corresponding path program 1 times [2024-11-08 14:23:58,164 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 14:23:58,164 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [482143139] [2024-11-08 14:23:58,164 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:23:58,164 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 14:23:58,180 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:23:58,363 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-08 14:23:58,364 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:23:58,366 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2024-11-08 14:23:58,367 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:23:58,368 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 15 [2024-11-08 14:23:58,369 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:23:58,370 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 20 [2024-11-08 14:23:58,372 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:23:58,393 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 25 [2024-11-08 14:23:58,395 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:23:58,397 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 31 [2024-11-08 14:23:58,399 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:23:58,401 INFO L134 CoverageAnalysis]: Checked inductivity of 36 backedges. 10 proven. 7 refuted. 0 times theorem prover too weak. 19 trivial. 0 not checked. [2024-11-08 14:23:58,402 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 14:23:58,402 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [482143139] [2024-11-08 14:23:58,402 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [482143139] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-08 14:23:58,403 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1449899577] [2024-11-08 14:23:58,403 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:23:58,403 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 14:23:58,403 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-08 14:23:58,405 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:23:58,406 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:23:58,451 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:23:58,457 INFO L255 TraceCheckSpWp]: Trace formula consists of 109 conjuncts, 11 conjuncts are in the unsatisfiable core [2024-11-08 14:23:58,459 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-08 14:23:58,556 INFO L134 CoverageAnalysis]: Checked inductivity of 36 backedges. 8 proven. 0 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2024-11-08 14:23:58,556 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-08 14:23:58,557 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1449899577] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-08 14:23:58,557 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-08 14:23:58,557 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [8] total 12 [2024-11-08 14:23:58,557 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [801991337] [2024-11-08 14:23:58,557 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-08 14:23:58,558 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2024-11-08 14:23:58,558 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 14:23:58,558 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2024-11-08 14:23:58,558 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=27, Invalid=105, Unknown=0, NotChecked=0, Total=132 [2024-11-08 14:23:58,559 INFO L87 Difference]: Start difference. First operand 99 states and 124 transitions. Second operand has 6 states, 5 states have (on average 3.0) internal successors, (15), 5 states have internal predecessors, (15), 3 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 3 states have call predecessors, (6), 3 states have call successors, (6) [2024-11-08 14:23:58,648 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 14:23:58,648 INFO L93 Difference]: Finished difference Result 113 states and 138 transitions. [2024-11-08 14:23:58,648 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2024-11-08 14:23:58,649 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 5 states have (on average 3.0) internal successors, (15), 5 states have internal predecessors, (15), 3 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 3 states have call predecessors, (6), 3 states have call successors, (6) Word has length 40 [2024-11-08 14:23:58,649 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 14:23:58,650 INFO L225 Difference]: With dead ends: 113 [2024-11-08 14:23:58,650 INFO L226 Difference]: Without dead ends: 103 [2024-11-08 14:23:58,651 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 62 GetRequests, 50 SyntacticMatches, 0 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 26 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=40, Invalid=142, Unknown=0, NotChecked=0, Total=182 [2024-11-08 14:23:58,651 INFO L432 NwaCegarLoop]: 30 mSDtfsCounter, 7 mSDsluCounter, 106 mSDsCounter, 0 mSdLazyCounter, 58 mSolverCounterSat, 7 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 10 SdHoareTripleChecker+Valid, 136 SdHoareTripleChecker+Invalid, 65 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 7 IncrementalHoareTripleChecker+Valid, 58 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-08 14:23:58,652 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [10 Valid, 136 Invalid, 65 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [7 Valid, 58 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-08 14:23:58,652 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 103 states. [2024-11-08 14:23:58,668 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 103 to 100. [2024-11-08 14:23:58,671 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 100 states, 60 states have (on average 1.1833333333333333) internal successors, (71), 66 states have internal predecessors, (71), 27 states have call successors, (27), 12 states have call predecessors, (27), 12 states have return successors, (25), 21 states have call predecessors, (25), 25 states have call successors, (25) [2024-11-08 14:23:58,672 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 100 states to 100 states and 123 transitions. [2024-11-08 14:23:58,672 INFO L78 Accepts]: Start accepts. Automaton has 100 states and 123 transitions. Word has length 40 [2024-11-08 14:23:58,672 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 14:23:58,672 INFO L471 AbstractCegarLoop]: Abstraction has 100 states and 123 transitions. [2024-11-08 14:23:58,672 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 5 states have (on average 3.0) internal successors, (15), 5 states have internal predecessors, (15), 3 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 3 states have call predecessors, (6), 3 states have call successors, (6) [2024-11-08 14:23:58,672 INFO L276 IsEmpty]: Start isEmpty. Operand 100 states and 123 transitions. [2024-11-08 14:23:58,673 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 44 [2024-11-08 14:23:58,673 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 14:23:58,673 INFO L215 NwaCegarLoop]: trace histogram [5, 4, 4, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-08 14:23:58,693 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Forceful destruction successful, exit code 0 [2024-11-08 14:23:58,874 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 14:23:58,875 INFO L396 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 14:23:58,876 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 14:23:58,876 INFO L85 PathProgramCache]: Analyzing trace with hash 968731240, now seen corresponding path program 2 times [2024-11-08 14:23:58,876 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 14:23:58,876 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1050447509] [2024-11-08 14:23:58,876 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:23:58,877 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 14:23:58,893 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-08 14:23:58,894 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1649092566] [2024-11-08 14:23:58,894 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-08 14:23:58,894 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 14:23:58,898 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-08 14:23:58,901 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:23:58,903 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:23:58,953 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-08 14:23:58,954 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-08 14:23:58,955 INFO L255 TraceCheckSpWp]: Trace formula consists of 120 conjuncts, 35 conjuncts are in the unsatisfiable core [2024-11-08 14:23:58,957 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-08 14:23:59,295 INFO L134 CoverageAnalysis]: Checked inductivity of 40 backedges. 19 proven. 5 refuted. 0 times theorem prover too weak. 16 trivial. 0 not checked. [2024-11-08 14:23:59,295 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-08 14:23:59,874 INFO L134 CoverageAnalysis]: Checked inductivity of 40 backedges. 16 proven. 5 refuted. 0 times theorem prover too weak. 19 trivial. 0 not checked. [2024-11-08 14:23:59,874 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 14:23:59,874 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1050447509] [2024-11-08 14:23:59,874 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-08 14:23:59,874 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1649092566] [2024-11-08 14:23:59,875 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1649092566] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-08 14:23:59,875 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-08 14:23:59,875 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 8] total 17 [2024-11-08 14:23:59,875 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [87862341] [2024-11-08 14:23:59,875 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-08 14:23:59,876 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 17 states [2024-11-08 14:23:59,876 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 14:23:59,876 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2024-11-08 14:23:59,876 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=48, Invalid=224, Unknown=0, NotChecked=0, Total=272 [2024-11-08 14:23:59,877 INFO L87 Difference]: Start difference. First operand 100 states and 123 transitions. Second operand has 17 states, 15 states have (on average 2.3333333333333335) internal successors, (35), 13 states have internal predecessors, (35), 7 states have call successors, (12), 3 states have call predecessors, (12), 3 states have return successors, (11), 6 states have call predecessors, (11), 5 states have call successors, (11) [2024-11-08 14:24:04,165 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:24:04,456 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 14:24:04,456 INFO L93 Difference]: Finished difference Result 151 states and 206 transitions. [2024-11-08 14:24:04,457 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 17 states. [2024-11-08 14:24:04,457 INFO L78 Accepts]: Start accepts. Automaton has has 17 states, 15 states have (on average 2.3333333333333335) internal successors, (35), 13 states have internal predecessors, (35), 7 states have call successors, (12), 3 states have call predecessors, (12), 3 states have return successors, (11), 6 states have call predecessors, (11), 5 states have call successors, (11) Word has length 43 [2024-11-08 14:24:04,457 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 14:24:04,459 INFO L225 Difference]: With dead ends: 151 [2024-11-08 14:24:04,459 INFO L226 Difference]: Without dead ends: 149 [2024-11-08 14:24:04,460 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 91 GetRequests, 69 SyntacticMatches, 0 SemanticMatches, 22 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 73 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=113, Invalid=439, Unknown=0, NotChecked=0, Total=552 [2024-11-08 14:24:04,460 INFO L432 NwaCegarLoop]: 26 mSDtfsCounter, 50 mSDsluCounter, 196 mSDsCounter, 0 mSdLazyCounter, 256 mSolverCounterSat, 57 mSolverCounterUnsat, 1 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 4.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 54 SdHoareTripleChecker+Valid, 222 SdHoareTripleChecker+Invalid, 314 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 57 IncrementalHoareTripleChecker+Valid, 256 IncrementalHoareTripleChecker+Invalid, 1 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 4.3s IncrementalHoareTripleChecker+Time [2024-11-08 14:24:04,461 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [54 Valid, 222 Invalid, 314 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [57 Valid, 256 Invalid, 1 Unknown, 0 Unchecked, 4.3s Time] [2024-11-08 14:24:04,461 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 149 states. [2024-11-08 14:24:04,495 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 149 to 104. [2024-11-08 14:24:04,496 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 104 states, 63 states have (on average 1.1746031746031746) internal successors, (74), 69 states have internal predecessors, (74), 27 states have call successors, (27), 13 states have call predecessors, (27), 13 states have return successors, (25), 21 states have call predecessors, (25), 25 states have call successors, (25) [2024-11-08 14:24:04,497 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 104 states to 104 states and 126 transitions. [2024-11-08 14:24:04,497 INFO L78 Accepts]: Start accepts. Automaton has 104 states and 126 transitions. Word has length 43 [2024-11-08 14:24:04,497 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 14:24:04,497 INFO L471 AbstractCegarLoop]: Abstraction has 104 states and 126 transitions. [2024-11-08 14:24:04,498 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 17 states, 15 states have (on average 2.3333333333333335) internal successors, (35), 13 states have internal predecessors, (35), 7 states have call successors, (12), 3 states have call predecessors, (12), 3 states have return successors, (11), 6 states have call predecessors, (11), 5 states have call successors, (11) [2024-11-08 14:24:04,498 INFO L276 IsEmpty]: Start isEmpty. Operand 104 states and 126 transitions. [2024-11-08 14:24:04,499 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 49 [2024-11-08 14:24:04,499 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 14:24:04,499 INFO L215 NwaCegarLoop]: trace histogram [6, 5, 5, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-08 14:24:04,516 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:24:04,703 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable9,8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 14:24:04,704 INFO L396 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 14:24:04,704 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 14:24:04,704 INFO L85 PathProgramCache]: Analyzing trace with hash -740326292, now seen corresponding path program 1 times [2024-11-08 14:24:04,704 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 14:24:04,704 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [960500523] [2024-11-08 14:24:04,704 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:24:04,705 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 14:24:04,730 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-08 14:24:04,731 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1126970004] [2024-11-08 14:24:04,731 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:24:04,731 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 14:24:04,731 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-08 14:24:04,733 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:24:04,735 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:24:04,783 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:24:04,785 INFO L255 TraceCheckSpWp]: Trace formula consists of 129 conjuncts, 33 conjuncts are in the unsatisfiable core [2024-11-08 14:24:04,787 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-08 14:24:05,095 INFO L134 CoverageAnalysis]: Checked inductivity of 59 backedges. 9 proven. 21 refuted. 0 times theorem prover too weak. 29 trivial. 0 not checked. [2024-11-08 14:24:05,096 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-08 14:24:05,407 INFO L134 CoverageAnalysis]: Checked inductivity of 59 backedges. 9 proven. 18 refuted. 0 times theorem prover too weak. 32 trivial. 0 not checked. [2024-11-08 14:24:05,407 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 14:24:05,407 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [960500523] [2024-11-08 14:24:05,407 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-08 14:24:05,407 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1126970004] [2024-11-08 14:24:05,407 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1126970004] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-08 14:24:05,408 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-08 14:24:05,408 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 10] total 17 [2024-11-08 14:24:05,408 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [195826583] [2024-11-08 14:24:05,408 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-08 14:24:05,408 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 17 states [2024-11-08 14:24:05,408 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 14:24:05,409 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2024-11-08 14:24:05,409 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=51, Invalid=221, Unknown=0, NotChecked=0, Total=272 [2024-11-08 14:24:05,409 INFO L87 Difference]: Start difference. First operand 104 states and 126 transitions. Second operand has 17 states, 17 states have (on average 1.9411764705882353) internal successors, (33), 14 states have internal predecessors, (33), 7 states have call successors, (15), 2 states have call predecessors, (15), 3 states have return successors, (14), 6 states have call predecessors, (14), 7 states have call successors, (14) [2024-11-08 14:24:06,366 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 14:24:06,366 INFO L93 Difference]: Finished difference Result 140 states and 187 transitions. [2024-11-08 14:24:06,366 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 17 states. [2024-11-08 14:24:06,367 INFO L78 Accepts]: Start accepts. Automaton has has 17 states, 17 states have (on average 1.9411764705882353) internal successors, (33), 14 states have internal predecessors, (33), 7 states have call successors, (15), 2 states have call predecessors, (15), 3 states have return successors, (14), 6 states have call predecessors, (14), 7 states have call successors, (14) Word has length 48 [2024-11-08 14:24:06,367 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 14:24:06,370 INFO L225 Difference]: With dead ends: 140 [2024-11-08 14:24:06,370 INFO L226 Difference]: Without dead ends: 122 [2024-11-08 14:24:06,371 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 100 GetRequests, 77 SyntacticMatches, 2 SemanticMatches, 21 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 79 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=106, Invalid=400, Unknown=0, NotChecked=0, Total=506 [2024-11-08 14:24:06,372 INFO L432 NwaCegarLoop]: 27 mSDtfsCounter, 31 mSDsluCounter, 246 mSDsCounter, 0 mSdLazyCounter, 269 mSolverCounterSat, 62 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.7s Time, 0 mProtectedPredicate, 0 mProtectedAction, 32 SdHoareTripleChecker+Valid, 273 SdHoareTripleChecker+Invalid, 331 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 62 IncrementalHoareTripleChecker+Valid, 269 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.7s IncrementalHoareTripleChecker+Time [2024-11-08 14:24:06,373 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [32 Valid, 273 Invalid, 331 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [62 Valid, 269 Invalid, 0 Unknown, 0 Unchecked, 0.7s Time] [2024-11-08 14:24:06,374 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 122 states. [2024-11-08 14:24:06,406 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 122 to 94. [2024-11-08 14:24:06,406 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 94 states, 60 states have (on average 1.1666666666666667) internal successors, (70), 64 states have internal predecessors, (70), 21 states have call successors, (21), 12 states have call predecessors, (21), 12 states have return successors, (19), 17 states have call predecessors, (19), 19 states have call successors, (19) [2024-11-08 14:24:06,407 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 94 states to 94 states and 110 transitions. [2024-11-08 14:24:06,408 INFO L78 Accepts]: Start accepts. Automaton has 94 states and 110 transitions. Word has length 48 [2024-11-08 14:24:06,408 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 14:24:06,409 INFO L471 AbstractCegarLoop]: Abstraction has 94 states and 110 transitions. [2024-11-08 14:24:06,409 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 17 states, 17 states have (on average 1.9411764705882353) internal successors, (33), 14 states have internal predecessors, (33), 7 states have call successors, (15), 2 states have call predecessors, (15), 3 states have return successors, (14), 6 states have call predecessors, (14), 7 states have call successors, (14) [2024-11-08 14:24:06,409 INFO L276 IsEmpty]: Start isEmpty. Operand 94 states and 110 transitions. [2024-11-08 14:24:06,410 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 58 [2024-11-08 14:24:06,413 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 14:24:06,413 INFO L215 NwaCegarLoop]: trace histogram [7, 6, 6, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-08 14:24:06,430 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:24:06,617 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,SelfDestructingSolverStorable10 [2024-11-08 14:24:06,618 INFO L396 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 14:24:06,618 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 14:24:06,618 INFO L85 PathProgramCache]: Analyzing trace with hash 1803285070, now seen corresponding path program 2 times [2024-11-08 14:24:06,618 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 14:24:06,619 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [140709448] [2024-11-08 14:24:06,619 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:24:06,619 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 14:24:06,636 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-08 14:24:06,637 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1900236980] [2024-11-08 14:24:06,639 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-08 14:24:06,639 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 14:24:06,639 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-08 14:24:06,641 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:24:06,642 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:24:06,695 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-08 14:24:06,695 INFO L228 tOrderPrioritization]: Conjunction of SSA is sat [2024-11-08 14:24:06,696 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-08 14:24:06,712 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-08 14:24:06,759 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-08 14:24:06,760 INFO L325 BasicCegarLoop]: Counterexample is feasible [2024-11-08 14:24:06,761 INFO L782 garLoopResultBuilder]: Registering result UNSAFE for location __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION (0 of 1 remaining) [2024-11-08 14:24:06,779 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:24:06,966 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable11,10 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 14:24:06,969 INFO L407 BasicCegarLoop]: Path program histogram: [2, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-08 14:24:07,009 INFO L170 ceAbstractionStarter]: Computing trace abstraction results [2024-11-08 14:24:07,012 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 08.11 02:24:07 BoogieIcfgContainer [2024-11-08 14:24:07,012 INFO L131 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2024-11-08 14:24:07,012 INFO L112 PluginConnector]: ------------------------Witness Printer---------------------------- [2024-11-08 14:24:07,012 INFO L270 PluginConnector]: Initializing Witness Printer... [2024-11-08 14:24:07,012 INFO L274 PluginConnector]: Witness Printer initialized [2024-11-08 14:24:07,013 INFO L184 PluginConnector]: Executing the observer RCFGCatcher from plugin Witness Printer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 08.11 02:23:54" (3/4) ... [2024-11-08 14:24:07,013 INFO L136 WitnessPrinter]: Generating witness for reachability counterexample [2024-11-08 14:24:07,067 INFO L149 WitnessManager]: Wrote witness to /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/witness.graphml [2024-11-08 14:24:07,068 INFO L131 PluginConnector]: ------------------------ END Witness Printer---------------------------- [2024-11-08 14:24:07,068 INFO L158 Benchmark]: Toolchain (without parser) took 13088.10ms. Allocated memory was 178.3MB in the beginning and 220.2MB in the end (delta: 41.9MB). Free memory was 98.6MB in the beginning and 132.9MB in the end (delta: -34.3MB). Peak memory consumption was 9.2MB. Max. memory is 16.1GB. [2024-11-08 14:24:07,068 INFO L158 Benchmark]: CDTParser took 0.12ms. Allocated memory is still 178.3MB. Free memory is still 145.3MB. There was no memory consumed. Max. memory is 16.1GB. [2024-11-08 14:24:07,069 INFO L158 Benchmark]: CACSL2BoogieTranslator took 312.22ms. Allocated memory is still 178.3MB. Free memory was 98.5MB in the beginning and 142.8MB in the end (delta: -44.4MB). Peak memory consumption was 7.5MB. Max. memory is 16.1GB. [2024-11-08 14:24:07,069 INFO L158 Benchmark]: Boogie Procedure Inliner took 30.07ms. Allocated memory is still 178.3MB. Free memory was 142.8MB in the beginning and 140.9MB in the end (delta: 1.9MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. [2024-11-08 14:24:07,069 INFO L158 Benchmark]: Boogie Preprocessor took 28.34ms. Allocated memory is still 178.3MB. Free memory was 140.9MB in the beginning and 138.9MB in the end (delta: 2.0MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. [2024-11-08 14:24:07,070 INFO L158 Benchmark]: RCFGBuilder took 276.20ms. Allocated memory is still 178.3MB. Free memory was 138.9MB in the beginning and 144.6MB in the end (delta: -5.8MB). Peak memory consumption was 10.5MB. Max. memory is 16.1GB. [2024-11-08 14:24:07,070 INFO L158 Benchmark]: TraceAbstraction took 12378.26ms. Allocated memory was 178.3MB in the beginning and 220.2MB in the end (delta: 41.9MB). Free memory was 144.6MB in the beginning and 136.1MB in the end (delta: 8.6MB). Peak memory consumption was 52.6MB. Max. memory is 16.1GB. [2024-11-08 14:24:07,070 INFO L158 Benchmark]: Witness Printer took 55.70ms. Allocated memory is still 220.2MB. Free memory was 136.1MB in the beginning and 132.9MB in the end (delta: 3.1MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. [2024-11-08 14:24:07,071 INFO L338 ainManager$Toolchain]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * CDTParser took 0.12ms. Allocated memory is still 178.3MB. Free memory is still 145.3MB. There was no memory consumed. Max. memory is 16.1GB. * CACSL2BoogieTranslator took 312.22ms. Allocated memory is still 178.3MB. Free memory was 98.5MB in the beginning and 142.8MB in the end (delta: -44.4MB). Peak memory consumption was 7.5MB. Max. memory is 16.1GB. * Boogie Procedure Inliner took 30.07ms. Allocated memory is still 178.3MB. Free memory was 142.8MB in the beginning and 140.9MB in the end (delta: 1.9MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. * Boogie Preprocessor took 28.34ms. Allocated memory is still 178.3MB. Free memory was 140.9MB in the beginning and 138.9MB in the end (delta: 2.0MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. * RCFGBuilder took 276.20ms. Allocated memory is still 178.3MB. Free memory was 138.9MB in the beginning and 144.6MB in the end (delta: -5.8MB). Peak memory consumption was 10.5MB. Max. memory is 16.1GB. * TraceAbstraction took 12378.26ms. Allocated memory was 178.3MB in the beginning and 220.2MB in the end (delta: 41.9MB). Free memory was 144.6MB in the beginning and 136.1MB in the end (delta: 8.6MB). Peak memory consumption was 52.6MB. Max. memory is 16.1GB. * Witness Printer took 55.70ms. Allocated memory is still 220.2MB. Free memory was 136.1MB in the beginning and 132.9MB in the end (delta: 3.1MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - StatisticsResult: ErrorAutomatonStatistics NumberErrorTraces: 0, NumberStatementsAllTraces: 0, NumberRelevantStatements: 0, 0.0s ErrorAutomatonConstructionTimeTotal, 0.0s FaulLocalizationTime, NumberStatementsFirstTrace: -1, TraceLengthAvg: 0, 0.0s ErrorAutomatonConstructionTimeAvg, 0.0s ErrorAutomatonDifferenceTimeAvg, 0.0s ErrorAutomatonDifferenceTimeTotal, NumberOfNoEnhancement: 0, NumberOfFiniteEnhancement: 0, NumberOfInfiniteEnhancement: 0 - CounterExampleResult [Line: 13]: a call to reach_error is reachable a call to reach_error is reachable We found a FailurePath: [L18] int counter = 0; VAL [counter=0] [L20] long long a, b, p, q, r, s; [L21] int x, y; [L22] x = __VERIFIER_nondet_int() [L23] y = __VERIFIER_nondet_int() [L24] CALL assume_abort_if_not(x >= 1) VAL [\old(cond)=1, counter=0] [L8] COND FALSE !(!cond) VAL [\old(cond)=1, counter=0] [L24] RET assume_abort_if_not(x >= 1) VAL [counter=0, x=4, y=1] [L25] CALL assume_abort_if_not(y >= 1) VAL [\old(cond)=1, counter=0] [L8] COND FALSE !(!cond) VAL [\old(cond)=1, counter=0] [L25] RET assume_abort_if_not(y >= 1) VAL [counter=0, x=4, y=1] [L27] a = x [L28] b = y [L29] p = 1 [L30] q = 0 [L31] r = 0 [L32] s = 1 VAL [a=4, b=1, counter=0, p=1, q=0, r=0, s=1, x=4, y=1] [L34] EXPR counter++ VAL [a=4, b=1, counter=1, p=1, q=0, r=0, s=1, x=4, y=1] [L34] COND TRUE counter++<2 [L35] CALL __VERIFIER_assert(1 == p * s - r * q) VAL [\old(cond)=1, counter=1] [L11] COND FALSE !(!(cond)) VAL [\old(cond)=1, counter=1] [L35] RET __VERIFIER_assert(1 == p * s - r * q) VAL [a=4, b=1, counter=1, p=1, q=0, r=0, s=1, x=4, y=1] [L36] CALL __VERIFIER_assert(a == y * r + x * p) VAL [\old(cond)=1, counter=1] [L11] COND FALSE !(!(cond)) VAL [\old(cond)=1, counter=1] [L36] RET __VERIFIER_assert(a == y * r + x * p) VAL [a=4, b=1, counter=1, p=1, q=0, r=0, s=1, x=4, y=1] [L37] CALL __VERIFIER_assert(b == x * q + y * s) VAL [\old(cond)=1, counter=1] [L11] COND FALSE !(!(cond)) VAL [\old(cond)=1, counter=1] [L37] RET __VERIFIER_assert(b == x * q + y * s) VAL [a=4, b=1, counter=1, p=1, q=0, r=0, s=1, x=4, y=1] [L39] COND FALSE !(!(a != b)) VAL [a=4, b=1, counter=1, p=1, q=0, r=0, s=1, x=4, y=1] [L42] COND TRUE a > b [L43] a = a - b [L44] p = p - q [L45] r = r - s VAL [a=3, b=1, counter=1, p=1, q=0, r=-1, s=1, x=4, y=1] [L34] EXPR counter++ VAL [a=3, b=1, counter=2, p=1, q=0, r=-1, s=1, x=4, y=1] [L34] COND TRUE counter++<2 [L35] CALL __VERIFIER_assert(1 == p * s - r * q) VAL [\old(cond)=1, counter=2] [L11] COND FALSE !(!(cond)) VAL [\old(cond)=1, counter=2] [L35] RET __VERIFIER_assert(1 == p * s - r * q) VAL [a=3, b=1, counter=2, p=1, q=0, r=-1, s=1, x=4, y=1] [L36] CALL __VERIFIER_assert(a == y * r + x * p) VAL [\old(cond)=1, counter=2] [L11] COND FALSE !(!(cond)) VAL [\old(cond)=1, counter=2] [L36] RET __VERIFIER_assert(a == y * r + x * p) VAL [a=3, b=1, counter=2, p=1, q=0, r=-1, s=1, x=4, y=1] [L37] CALL __VERIFIER_assert(b == x * q + y * s) VAL [\old(cond)=1, counter=2] [L11] COND FALSE !(!(cond)) VAL [\old(cond)=1, counter=2] [L37] RET __VERIFIER_assert(b == x * q + y * s) VAL [a=3, b=1, counter=2, p=1, q=0, r=-1, s=1, x=4, y=1] [L39] COND FALSE !(!(a != b)) VAL [a=3, b=1, counter=2, p=1, q=0, r=-1, s=1, x=4, y=1] [L42] COND TRUE a > b [L43] a = a - b [L44] p = p - q [L45] r = r - s VAL [a=2, b=1, counter=2, p=1, q=0, r=-2, s=1, x=4, y=1] [L34] EXPR counter++ VAL [a=2, b=1, counter=3, p=1, q=0, r=-2, s=1, x=4, y=1] [L34] COND FALSE !(counter++<2) [L53] CALL __VERIFIER_assert(a - b == 0) VAL [\old(cond)=0, counter=3] [L11] COND TRUE !(cond) VAL [\old(cond)=0, counter=3] [L13] reach_error() VAL [\old(cond)=0, counter=3] - StatisticsResult: Ultimate Automizer benchmark data CFG has 3 procedures, 30 locations, 1 error locations. Started 1 CEGAR loops. OverallTime: 12.3s, OverallIterations: 12, TraceHistogramMax: 7, PathProgramHistogramMax: 2, EmptinessCheckTime: 0.0s, AutomataDifference: 6.2s, DeadEndRemovalTime: 0.0s, HoareAnnotationTime: 0.0s, InitialAbstractionConstructionTime: 0.0s, HoareTripleCheckerStatistics: 1 mSolverCounterUnknown, 156 SdHoareTripleChecker+Valid, 5.4s IncrementalHoareTripleChecker+Time, 0 mSdLazyCounter, 128 mSDsluCounter, 1472 SdHoareTripleChecker+Invalid, 5.2s Time, 0 mProtectedAction, 0 SdHoareTripleChecker+Unchecked, 0 IncrementalHoareTripleChecker+Unchecked, 1112 mSDsCounter, 130 IncrementalHoareTripleChecker+Valid, 0 mProtectedPredicate, 769 IncrementalHoareTripleChecker+Invalid, 900 SdHoareTripleChecker+Unknown, 0 mSolverCounterNotChecked, 130 mSolverCounterUnsat, 360 mSDtfsCounter, 769 mSolverCounterSat, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Unknown, PredicateUnifierStatistics: 0 DeclaredPredicates, 484 GetRequests, 398 SyntacticMatches, 5 SemanticMatches, 81 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 181 ImplicationChecksByTransitivity, 1.1s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=104occurred in iteration=10, InterpolantAutomatonStates: 77, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 0.0s DumpTime, AutomataMinimizationStatistics: 0.2s AutomataMinimizationTime, 11 MinimizatonAttempts, 87 StatesRemovedByMinimization, 7 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TRACE_CHECK: 0.1s SsaConstructionTime, 0.4s SatisfiabilityAnalysisTime, 2.9s InterpolantComputationTime, 744 NumberOfCodeBlocks, 744 NumberOfCodeBlocksAsserted, 23 NumberOfCheckSat, 542 ConstructedInterpolants, 0 QuantifiedInterpolants, 2132 SizeOfPredicates, 15 NumberOfNonLiveVariables, 820 ConjunctsInSsa, 125 ConjunctsInUnsatCore, 16 InterpolantComputations, 8 PerfectInterpolantSequences, 357/419 InterpolantCoveringCapability, INVARIANT_SYNTHESIS: No data available, INTERPOLANT_CONSOLIDATION: No data available, ABSTRACT_INTERPRETATION: No data available, PDR: No data available, ACCELERATED_INTERPOLATION: No data available, SIFA: No data available, ReuseStatistics: No data available RESULT: Ultimate proved your program to be incorrect! [2024-11-08 14:24:07,093 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (1)] Ended with exit code 0 Received shutdown request... --- End real Ultimate output --- Execution finished normally Writing output log to file Ultimate.log Writing human readable error path to file UltimateCounterExample.errorpath Result: FALSE