./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 8be7027f 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-wip.dk.perfect-tracechecks-8be7027-m [2024-11-11 20:03:04,143 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-11-11 20:03:04,198 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf [2024-11-11 20:03:04,202 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-11-11 20:03:04,202 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-11-11 20:03:04,219 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-11-11 20:03:04,220 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-11-11 20:03:04,220 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-11-11 20:03:04,220 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2024-11-11 20:03:04,221 INFO L153 SettingsManager]: * Use memory slicer=true [2024-11-11 20:03:04,221 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2024-11-11 20:03:04,221 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2024-11-11 20:03:04,221 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2024-11-11 20:03:04,222 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2024-11-11 20:03:04,222 INFO L153 SettingsManager]: * Use SBE=true [2024-11-11 20:03:04,222 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-11-11 20:03:04,222 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2024-11-11 20:03:04,223 INFO L153 SettingsManager]: * sizeof long=4 [2024-11-11 20:03:04,223 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2024-11-11 20:03:04,223 INFO L153 SettingsManager]: * sizeof POINTER=4 [2024-11-11 20:03:04,223 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-11-11 20:03:04,225 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2024-11-11 20:03:04,225 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2024-11-11 20:03:04,226 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2024-11-11 20:03:04,228 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-11-11 20:03:04,229 INFO L153 SettingsManager]: * sizeof long double=12 [2024-11-11 20:03:04,229 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-11-11 20:03:04,229 INFO L153 SettingsManager]: * Use constant arrays=true [2024-11-11 20:03:04,229 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2024-11-11 20:03:04,229 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2024-11-11 20:03:04,229 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2024-11-11 20:03:04,229 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2024-11-11 20:03:04,230 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-11 20:03:04,230 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-11-11 20:03:04,230 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2024-11-11 20:03:04,230 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2024-11-11 20:03:04,230 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2024-11-11 20:03:04,230 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2024-11-11 20:03:04,230 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2024-11-11 20:03:04,230 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2024-11-11 20:03:04,230 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2024-11-11 20:03:04,231 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2024-11-11 20:03:04,231 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-11 20:03:04,419 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-11-11 20:03:04,437 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-11-11 20:03:04,439 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-11-11 20:03:04,440 INFO L270 PluginConnector]: Initializing CDTParser... [2024-11-11 20:03:04,440 INFO L274 PluginConnector]: CDTParser initialized [2024-11-11 20:03:04,441 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-11 20:03:05,657 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-11-11 20:03:05,789 INFO L384 CDTParser]: Found 1 translation units. [2024-11-11 20:03:05,789 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/egcd-ll_unwindbound2.c [2024-11-11 20:03:05,795 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/ee4c58adc/92a53f0e35df432f9a1757fcecb8f40a/FLAG8c29f8278 [2024-11-11 20:03:05,804 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/ee4c58adc/92a53f0e35df432f9a1757fcecb8f40a [2024-11-11 20:03:05,806 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-11-11 20:03:05,807 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2024-11-11 20:03:05,808 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-11-11 20:03:05,808 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-11-11 20:03:05,815 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-11-11 20:03:05,816 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 11.11 08:03:05" (1/1) ... [2024-11-11 20:03:05,816 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@575158e7 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.11 08:03:05, skipping insertion in model container [2024-11-11 20:03:05,817 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 11.11 08:03:05" (1/1) ... [2024-11-11 20:03:05,831 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-11-11 20:03:05,972 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-11 20:03:05,989 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-11 20:03:05,998 INFO L200 MainTranslator]: Completed pre-run [2024-11-11 20:03:06,008 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-11 20:03:06,017 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-11 20:03:06,031 INFO L204 MainTranslator]: Completed translation [2024-11-11 20:03:06,032 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.11 08:03:06 WrapperNode [2024-11-11 20:03:06,032 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-11-11 20:03:06,033 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-11-11 20:03:06,034 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-11-11 20:03:06,034 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-11-11 20:03:06,039 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.11 08:03:06" (1/1) ... [2024-11-11 20:03:06,065 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.11 08:03:06" (1/1) ... [2024-11-11 20:03:06,095 INFO L138 Inliner]: procedures = 14, calls = 16, calls flagged for inlining = 2, calls inlined = 2, statements flattened = 60 [2024-11-11 20:03:06,095 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-11-11 20:03:06,096 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-11-11 20:03:06,096 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-11-11 20:03:06,096 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-11-11 20:03:06,119 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.11 08:03:06" (1/1) ... [2024-11-11 20:03:06,119 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.11 08:03:06" (1/1) ... [2024-11-11 20:03:06,126 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.11 08:03:06" (1/1) ... [2024-11-11 20:03:06,136 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-11 20:03:06,139 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.11 08:03:06" (1/1) ... [2024-11-11 20:03:06,139 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.11 08:03:06" (1/1) ... [2024-11-11 20:03:06,141 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.11 08:03:06" (1/1) ... [2024-11-11 20:03:06,143 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.11 08:03:06" (1/1) ... [2024-11-11 20:03:06,145 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.11 08:03:06" (1/1) ... [2024-11-11 20:03:06,145 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.11 08:03:06" (1/1) ... [2024-11-11 20:03:06,146 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-11-11 20:03:06,151 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2024-11-11 20:03:06,151 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2024-11-11 20:03:06,151 INFO L274 PluginConnector]: RCFGBuilder initialized [2024-11-11 20:03:06,151 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.11 08:03:06" (1/1) ... [2024-11-11 20:03:06,155 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-11 20:03:06,163 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-11 20:03:06,178 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-11 20:03:06,180 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-11 20:03:06,218 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2024-11-11 20:03:06,218 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2024-11-11 20:03:06,219 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2024-11-11 20:03:06,219 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2024-11-11 20:03:06,219 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-11-11 20:03:06,219 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-11-11 20:03:06,219 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2024-11-11 20:03:06,220 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2024-11-11 20:03:06,272 INFO L238 CfgBuilder]: Building ICFG [2024-11-11 20:03:06,275 INFO L264 CfgBuilder]: Building CFG for each procedure with an implementation [2024-11-11 20:03:06,409 INFO L? ?]: Removed 5 outVars from TransFormulas that were not future-live. [2024-11-11 20:03:06,410 INFO L287 CfgBuilder]: Performing block encoding [2024-11-11 20:03:06,419 INFO L311 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-11-11 20:03:06,419 INFO L316 CfgBuilder]: Removed 1 assume(true) statements. [2024-11-11 20:03:06,419 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 11.11 08:03:06 BoogieIcfgContainer [2024-11-11 20:03:06,420 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2024-11-11 20:03:06,421 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2024-11-11 20:03:06,421 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2024-11-11 20:03:06,423 INFO L274 PluginConnector]: TraceAbstraction initialized [2024-11-11 20:03:06,423 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 11.11 08:03:05" (1/3) ... [2024-11-11 20:03:06,424 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@3c610d47 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 11.11 08:03:06, skipping insertion in model container [2024-11-11 20:03:06,424 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.11 08:03:06" (2/3) ... [2024-11-11 20:03:06,424 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@3c610d47 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 11.11 08:03:06, skipping insertion in model container [2024-11-11 20:03:06,424 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 11.11 08:03:06" (3/3) ... [2024-11-11 20:03:06,425 INFO L112 eAbstractionObserver]: Analyzing ICFG egcd-ll_unwindbound2.c [2024-11-11 20:03:06,436 INFO L214 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2024-11-11 20:03:06,436 INFO L154 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2024-11-11 20:03:06,477 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2024-11-11 20:03:06,481 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;@3d1d0883, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2024-11-11 20:03:06,482 INFO L334 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2024-11-11 20:03:06,485 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-11 20:03:06,489 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 19 [2024-11-11 20:03:06,489 INFO L210 NwaCegarLoop]: Found error trace [2024-11-11 20:03:06,490 INFO L218 NwaCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-11 20:03:06,491 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-11 20:03:06,495 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-11 20:03:06,495 INFO L85 PathProgramCache]: Analyzing trace with hash 1165920622, now seen corresponding path program 1 times [2024-11-11 20:03:06,503 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-11 20:03:06,504 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1715042251] [2024-11-11 20:03:06,504 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-11 20:03:06,504 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-11 20:03:06,593 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 20:03:06,634 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-11 20:03:06,638 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 20:03:06,644 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2024-11-11 20:03:06,649 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 20:03:06,656 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-11 20:03:06,656 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-11 20:03:06,656 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1715042251] [2024-11-11 20:03:06,657 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1715042251] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-11 20:03:06,658 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-11 20:03:06,658 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2024-11-11 20:03:06,659 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [13331645] [2024-11-11 20:03:06,660 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-11 20:03:06,663 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2024-11-11 20:03:06,664 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-11 20:03:06,682 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2024-11-11 20:03:06,683 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2024-11-11 20:03:06,684 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-11 20:03:06,702 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-11 20:03:06,702 INFO L93 Difference]: Finished difference Result 57 states and 89 transitions. [2024-11-11 20:03:06,703 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2024-11-11 20:03:06,704 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-11 20:03:06,704 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-11 20:03:06,709 INFO L225 Difference]: With dead ends: 57 [2024-11-11 20:03:06,710 INFO L226 Difference]: Without dead ends: 26 [2024-11-11 20:03:06,712 INFO L434 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-11 20:03:06,716 INFO L435 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-11 20:03:06,717 INFO L436 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-11 20:03:06,729 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 26 states. [2024-11-11 20:03:06,743 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 26 to 26. [2024-11-11 20:03:06,745 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-11 20:03:06,747 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 26 states to 26 states and 35 transitions. [2024-11-11 20:03:06,749 INFO L78 Accepts]: Start accepts. Automaton has 26 states and 35 transitions. Word has length 18 [2024-11-11 20:03:06,749 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-11 20:03:06,750 INFO L471 AbstractCegarLoop]: Abstraction has 26 states and 35 transitions. [2024-11-11 20:03:06,750 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-11 20:03:06,750 INFO L276 IsEmpty]: Start isEmpty. Operand 26 states and 35 transitions. [2024-11-11 20:03:06,751 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 20 [2024-11-11 20:03:06,751 INFO L210 NwaCegarLoop]: Found error trace [2024-11-11 20:03:06,751 INFO L218 NwaCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-11 20:03:06,751 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2024-11-11 20:03:06,751 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-11 20:03:06,752 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-11 20:03:06,752 INFO L85 PathProgramCache]: Analyzing trace with hash -542319922, now seen corresponding path program 1 times [2024-11-11 20:03:06,752 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-11 20:03:06,752 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1502387305] [2024-11-11 20:03:06,752 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-11 20:03:06,752 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-11 20:03:06,771 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 20:03:06,845 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-11 20:03:06,851 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 20:03:06,860 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2024-11-11 20:03:06,863 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 20:03:06,867 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-11 20:03:06,868 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-11 20:03:06,868 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1502387305] [2024-11-11 20:03:06,868 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1502387305] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-11 20:03:06,868 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-11 20:03:06,868 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2024-11-11 20:03:06,868 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1381297821] [2024-11-11 20:03:06,869 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-11 20:03:06,869 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2024-11-11 20:03:06,870 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-11 20:03:06,870 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2024-11-11 20:03:06,871 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2024-11-11 20:03:06,871 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-11 20:03:06,886 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-11 20:03:06,886 INFO L93 Difference]: Finished difference Result 38 states and 50 transitions. [2024-11-11 20:03:06,887 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2024-11-11 20:03:06,887 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-11 20:03:06,887 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-11 20:03:06,888 INFO L225 Difference]: With dead ends: 38 [2024-11-11 20:03:06,888 INFO L226 Difference]: Without dead ends: 28 [2024-11-11 20:03:06,888 INFO L434 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-11 20:03:06,889 INFO L435 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-11 20:03:06,889 INFO L436 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-11 20:03:06,890 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 28 states. [2024-11-11 20:03:06,893 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 28 to 28. [2024-11-11 20:03:06,893 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-11 20:03:06,897 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 28 states to 28 states and 37 transitions. [2024-11-11 20:03:06,897 INFO L78 Accepts]: Start accepts. Automaton has 28 states and 37 transitions. Word has length 19 [2024-11-11 20:03:06,898 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-11 20:03:06,898 INFO L471 AbstractCegarLoop]: Abstraction has 28 states and 37 transitions. [2024-11-11 20:03:06,898 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-11 20:03:06,899 INFO L276 IsEmpty]: Start isEmpty. Operand 28 states and 37 transitions. [2024-11-11 20:03:06,899 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 20 [2024-11-11 20:03:06,899 INFO L210 NwaCegarLoop]: Found error trace [2024-11-11 20:03:06,900 INFO L218 NwaCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-11 20:03:06,900 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2024-11-11 20:03:06,900 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-11 20:03:06,901 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-11 20:03:06,901 INFO L85 PathProgramCache]: Analyzing trace with hash -540651626, now seen corresponding path program 1 times [2024-11-11 20:03:06,901 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-11 20:03:06,901 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1470411786] [2024-11-11 20:03:06,902 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-11 20:03:06,902 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-11 20:03:06,929 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-11 20:03:06,930 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1415192130] [2024-11-11 20:03:06,930 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-11 20:03:06,930 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-11 20:03:06,931 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-11 20:03:06,933 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-11 20:03:06,934 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-11 20:03:06,983 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 20:03:06,986 INFO L256 TraceCheckSpWp]: Trace formula consists of 71 conjuncts, 9 conjuncts are in the unsatisfiable core [2024-11-11 20:03:06,990 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2024-11-11 20:03:07,088 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-11 20:03:07,090 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-11 20:03:07,090 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-11 20:03:07,090 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1470411786] [2024-11-11 20:03:07,091 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-11 20:03:07,092 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1415192130] [2024-11-11 20:03:07,092 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1415192130] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-11 20:03:07,093 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-11 20:03:07,093 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-11 20:03:07,093 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [792680130] [2024-11-11 20:03:07,094 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-11 20:03:07,096 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-11 20:03:07,096 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-11 20:03:07,097 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-11 20:03:07,097 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-11 20:03:07,097 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-11 20:03:07,157 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-11 20:03:07,157 INFO L93 Difference]: Finished difference Result 45 states and 62 transitions. [2024-11-11 20:03:07,158 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-11 20:03:07,158 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-11 20:03:07,158 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-11 20:03:07,159 INFO L225 Difference]: With dead ends: 45 [2024-11-11 20:03:07,159 INFO L226 Difference]: Without dead ends: 43 [2024-11-11 20:03:07,159 INFO L434 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-11 20:03:07,160 INFO L435 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-11 20:03:07,160 INFO L436 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-11 20:03:07,161 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 43 states. [2024-11-11 20:03:07,167 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 43 to 42. [2024-11-11 20:03:07,167 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-11 20:03:07,168 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 42 states to 42 states and 59 transitions. [2024-11-11 20:03:07,168 INFO L78 Accepts]: Start accepts. Automaton has 42 states and 59 transitions. Word has length 19 [2024-11-11 20:03:07,168 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-11 20:03:07,169 INFO L471 AbstractCegarLoop]: Abstraction has 42 states and 59 transitions. [2024-11-11 20:03:07,169 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-11 20:03:07,169 INFO L276 IsEmpty]: Start isEmpty. Operand 42 states and 59 transitions. [2024-11-11 20:03:07,169 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 25 [2024-11-11 20:03:07,169 INFO L210 NwaCegarLoop]: Found error trace [2024-11-11 20:03:07,169 INFO L218 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-11 20:03:07,183 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Forceful destruction successful, exit code 0 [2024-11-11 20:03:07,373 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-11 20:03:07,374 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-11 20:03:07,374 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-11 20:03:07,375 INFO L85 PathProgramCache]: Analyzing trace with hash -276555716, now seen corresponding path program 1 times [2024-11-11 20:03:07,375 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-11 20:03:07,375 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [290477409] [2024-11-11 20:03:07,375 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-11 20:03:07,375 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-11 20:03:07,390 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-11 20:03:07,392 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [816072187] [2024-11-11 20:03:07,392 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-11 20:03:07,392 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-11 20:03:07,392 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-11 20:03:07,394 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-11 20:03:07,395 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-11 20:03:07,433 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 20:03:07,434 INFO L256 TraceCheckSpWp]: Trace formula consists of 80 conjuncts, 9 conjuncts are in the unsatisfiable core [2024-11-11 20:03:07,435 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2024-11-11 20:03:07,491 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-11 20:03:07,491 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-11 20:03:07,491 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-11 20:03:07,492 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [290477409] [2024-11-11 20:03:07,492 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-11 20:03:07,492 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [816072187] [2024-11-11 20:03:07,492 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [816072187] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-11 20:03:07,492 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-11 20:03:07,492 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-11 20:03:07,492 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1313782957] [2024-11-11 20:03:07,493 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-11 20:03:07,493 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-11 20:03:07,493 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-11 20:03:07,494 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-11 20:03:07,494 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-11 20:03:07,494 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-11 20:03:07,536 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-11 20:03:07,537 INFO L93 Difference]: Finished difference Result 49 states and 65 transitions. [2024-11-11 20:03:07,537 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-11 20:03:07,537 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-11 20:03:07,537 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-11 20:03:07,538 INFO L225 Difference]: With dead ends: 49 [2024-11-11 20:03:07,538 INFO L226 Difference]: Without dead ends: 47 [2024-11-11 20:03:07,538 INFO L434 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-11 20:03:07,539 INFO L435 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.0s IncrementalHoareTripleChecker+Time [2024-11-11 20:03:07,539 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [12 Valid, 132 Invalid, 39 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 39 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-11 20:03:07,540 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 47 states. [2024-11-11 20:03:07,545 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 47 to 46. [2024-11-11 20:03:07,545 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-11 20:03:07,546 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 46 states to 46 states and 62 transitions. [2024-11-11 20:03:07,546 INFO L78 Accepts]: Start accepts. Automaton has 46 states and 62 transitions. Word has length 24 [2024-11-11 20:03:07,547 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-11 20:03:07,547 INFO L471 AbstractCegarLoop]: Abstraction has 46 states and 62 transitions. [2024-11-11 20:03:07,547 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-11 20:03:07,547 INFO L276 IsEmpty]: Start isEmpty. Operand 46 states and 62 transitions. [2024-11-11 20:03:07,548 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 30 [2024-11-11 20:03:07,548 INFO L210 NwaCegarLoop]: Found error trace [2024-11-11 20:03:07,548 INFO L218 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-11 20:03:07,563 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2024-11-11 20:03:07,751 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-11 20:03:07,752 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-11 20:03:07,752 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-11 20:03:07,752 INFO L85 PathProgramCache]: Analyzing trace with hash -1836785898, now seen corresponding path program 1 times [2024-11-11 20:03:07,752 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-11 20:03:07,752 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1858165158] [2024-11-11 20:03:07,753 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-11 20:03:07,753 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-11 20:03:07,776 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-11 20:03:07,777 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1773202083] [2024-11-11 20:03:07,777 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-11 20:03:07,777 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-11 20:03:07,777 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-11 20:03:07,781 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-11 20:03:07,783 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-11 20:03:07,824 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 20:03:07,825 INFO L256 TraceCheckSpWp]: Trace formula consists of 89 conjuncts, 12 conjuncts are in the unsatisfiable core [2024-11-11 20:03:07,827 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2024-11-11 20:03:07,888 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-11 20:03:07,888 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-11 20:03:07,888 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-11 20:03:07,889 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1858165158] [2024-11-11 20:03:07,889 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-11 20:03:07,889 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1773202083] [2024-11-11 20:03:07,889 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1773202083] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-11 20:03:07,889 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-11 20:03:07,890 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-11 20:03:07,890 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1370353383] [2024-11-11 20:03:07,890 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-11 20:03:07,890 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-11 20:03:07,890 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-11 20:03:07,891 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-11 20:03:07,891 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-11 20:03:07,892 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-11 20:03:07,945 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-11 20:03:07,945 INFO L93 Difference]: Finished difference Result 71 states and 103 transitions. [2024-11-11 20:03:07,945 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-11 20:03:07,945 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-11 20:03:07,946 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-11 20:03:07,947 INFO L225 Difference]: With dead ends: 71 [2024-11-11 20:03:07,948 INFO L226 Difference]: Without dead ends: 67 [2024-11-11 20:03:07,948 INFO L434 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-11 20:03:07,952 INFO L435 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-11 20:03:07,953 INFO L436 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-11 20:03:07,954 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 67 states. [2024-11-11 20:03:07,967 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 67 to 67. [2024-11-11 20:03:07,968 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-11 20:03:07,969 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 67 states to 67 states and 96 transitions. [2024-11-11 20:03:07,971 INFO L78 Accepts]: Start accepts. Automaton has 67 states and 96 transitions. Word has length 29 [2024-11-11 20:03:07,972 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-11 20:03:07,972 INFO L471 AbstractCegarLoop]: Abstraction has 67 states and 96 transitions. [2024-11-11 20:03:07,972 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-11 20:03:07,972 INFO L276 IsEmpty]: Start isEmpty. Operand 67 states and 96 transitions. [2024-11-11 20:03:07,972 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 36 [2024-11-11 20:03:07,972 INFO L210 NwaCegarLoop]: Found error trace [2024-11-11 20:03:07,972 INFO L218 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-11 20:03:07,984 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Ended with exit code 0 [2024-11-11 20:03:08,173 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-11 20:03:08,173 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-11 20:03:08,174 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-11 20:03:08,174 INFO L85 PathProgramCache]: Analyzing trace with hash 1071030291, now seen corresponding path program 1 times [2024-11-11 20:03:08,174 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-11 20:03:08,174 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [399749042] [2024-11-11 20:03:08,174 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-11 20:03:08,174 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-11 20:03:08,191 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 20:03:08,283 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-11 20:03:08,284 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 20:03:08,289 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2024-11-11 20:03:08,291 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 20:03:08,292 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 15 [2024-11-11 20:03:08,293 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 20:03:08,296 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 20 [2024-11-11 20:03:08,297 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 20:03:08,298 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 25 [2024-11-11 20:03:08,298 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 20:03:08,302 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-11 20:03:08,302 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-11 20:03:08,302 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [399749042] [2024-11-11 20:03:08,302 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [399749042] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-11 20:03:08,302 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-11 20:03:08,302 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-11 20:03:08,303 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2013141757] [2024-11-11 20:03:08,303 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-11 20:03:08,303 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-11 20:03:08,303 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-11 20:03:08,303 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-11 20:03:08,303 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-11 20:03:08,303 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-11 20:03:08,346 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-11 20:03:08,347 INFO L93 Difference]: Finished difference Result 83 states and 119 transitions. [2024-11-11 20:03:08,347 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-11 20:03:08,347 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-11 20:03:08,347 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-11 20:03:08,348 INFO L225 Difference]: With dead ends: 83 [2024-11-11 20:03:08,349 INFO L226 Difference]: Without dead ends: 81 [2024-11-11 20:03:08,350 INFO L434 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-11 20:03:08,350 INFO L435 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-11 20:03:08,351 INFO L436 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-11 20:03:08,352 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 81 states. [2024-11-11 20:03:08,366 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 81 to 74. [2024-11-11 20:03:08,367 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-11 20:03:08,368 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 74 states to 74 states and 105 transitions. [2024-11-11 20:03:08,369 INFO L78 Accepts]: Start accepts. Automaton has 74 states and 105 transitions. Word has length 35 [2024-11-11 20:03:08,369 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-11 20:03:08,369 INFO L471 AbstractCegarLoop]: Abstraction has 74 states and 105 transitions. [2024-11-11 20:03:08,370 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-11 20:03:08,370 INFO L276 IsEmpty]: Start isEmpty. Operand 74 states and 105 transitions. [2024-11-11 20:03:08,370 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 39 [2024-11-11 20:03:08,371 INFO L210 NwaCegarLoop]: Found error trace [2024-11-11 20:03:08,371 INFO L218 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-11 20:03:08,371 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5 [2024-11-11 20:03:08,372 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-11 20:03:08,372 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-11 20:03:08,372 INFO L85 PathProgramCache]: Analyzing trace with hash 1689492770, now seen corresponding path program 1 times [2024-11-11 20:03:08,372 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-11 20:03:08,372 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1605316993] [2024-11-11 20:03:08,373 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-11 20:03:08,373 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-11 20:03:08,388 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 20:03:08,445 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-11 20:03:08,447 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 20:03:08,451 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2024-11-11 20:03:08,452 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 20:03:08,453 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 15 [2024-11-11 20:03:08,455 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 20:03:08,457 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 20 [2024-11-11 20:03:08,458 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 20:03:08,460 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 25 [2024-11-11 20:03:08,461 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 20:03:08,463 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-11 20:03:08,463 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-11 20:03:08,463 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1605316993] [2024-11-11 20:03:08,464 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1605316993] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-11 20:03:08,464 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [388911175] [2024-11-11 20:03:08,464 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-11 20:03:08,464 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-11 20:03:08,464 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-11 20:03:08,465 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-11 20:03:08,466 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-11 20:03:08,506 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 20:03:08,507 INFO L256 TraceCheckSpWp]: Trace formula consists of 111 conjuncts, 5 conjuncts are in the unsatisfiable core [2024-11-11 20:03:08,508 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2024-11-11 20:03:08,549 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-11 20:03:08,550 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2024-11-11 20:03:08,610 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-11 20:03:08,612 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [388911175] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-11 20:03:08,612 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-11 20:03:08,612 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 4, 5] total 5 [2024-11-11 20:03:08,612 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [339227977] [2024-11-11 20:03:08,612 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-11 20:03:08,612 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-11 20:03:08,613 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-11 20:03:08,613 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-11 20:03:08,613 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2024-11-11 20:03:08,613 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-11 20:03:08,654 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-11 20:03:08,655 INFO L93 Difference]: Finished difference Result 117 states and 148 transitions. [2024-11-11 20:03:08,655 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2024-11-11 20:03:08,655 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-11 20:03:08,656 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-11 20:03:08,658 INFO L225 Difference]: With dead ends: 117 [2024-11-11 20:03:08,660 INFO L226 Difference]: Without dead ends: 98 [2024-11-11 20:03:08,661 INFO L434 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-11 20:03:08,661 INFO L435 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-11 20:03:08,661 INFO L436 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-11 20:03:08,662 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 98 states. [2024-11-11 20:03:08,675 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 98 to 96. [2024-11-11 20:03:08,675 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-11 20:03:08,676 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 96 states to 96 states and 123 transitions. [2024-11-11 20:03:08,680 INFO L78 Accepts]: Start accepts. Automaton has 96 states and 123 transitions. Word has length 38 [2024-11-11 20:03:08,680 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-11 20:03:08,680 INFO L471 AbstractCegarLoop]: Abstraction has 96 states and 123 transitions. [2024-11-11 20:03:08,680 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-11 20:03:08,680 INFO L276 IsEmpty]: Start isEmpty. Operand 96 states and 123 transitions. [2024-11-11 20:03:08,681 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 39 [2024-11-11 20:03:08,681 INFO L210 NwaCegarLoop]: Found error trace [2024-11-11 20:03:08,681 INFO L218 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-11 20:03:08,695 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-11 20:03:08,881 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-11 20:03:08,882 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-11 20:03:08,882 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-11 20:03:08,882 INFO L85 PathProgramCache]: Analyzing trace with hash 1691161066, now seen corresponding path program 1 times [2024-11-11 20:03:08,882 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-11 20:03:08,882 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [118517101] [2024-11-11 20:03:08,882 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-11 20:03:08,882 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-11 20:03:08,896 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-11 20:03:08,897 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1047836056] [2024-11-11 20:03:08,897 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-11 20:03:08,897 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-11 20:03:08,897 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-11 20:03:08,901 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-11 20:03:08,902 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-11 20:03:08,940 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 20:03:08,941 INFO L256 TraceCheckSpWp]: Trace formula consists of 111 conjuncts, 11 conjuncts are in the unsatisfiable core [2024-11-11 20:03:08,942 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2024-11-11 20:03:09,027 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-11 20:03:09,027 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-11 20:03:09,027 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-11 20:03:09,027 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [118517101] [2024-11-11 20:03:09,028 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-11 20:03:09,028 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1047836056] [2024-11-11 20:03:09,028 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1047836056] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-11 20:03:09,028 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-11 20:03:09,028 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-11 20:03:09,028 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [862773833] [2024-11-11 20:03:09,028 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-11 20:03:09,028 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-11 20:03:09,028 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-11 20:03:09,029 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-11 20:03:09,029 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-11 20:03:09,029 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-11 20:03:09,073 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-11 20:03:09,074 INFO L93 Difference]: Finished difference Result 102 states and 128 transitions. [2024-11-11 20:03:09,074 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-11 20:03:09,074 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-11 20:03:09,074 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-11 20:03:09,075 INFO L225 Difference]: With dead ends: 102 [2024-11-11 20:03:09,075 INFO L226 Difference]: Without dead ends: 99 [2024-11-11 20:03:09,075 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 38 GetRequests, 34 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2024-11-11 20:03:09,076 INFO L435 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-11 20:03:09,076 INFO L436 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-11 20:03:09,076 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 99 states. [2024-11-11 20:03:09,089 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 99 to 99. [2024-11-11 20:03:09,091 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-11 20:03:09,091 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 99 states to 99 states and 124 transitions. [2024-11-11 20:03:09,092 INFO L78 Accepts]: Start accepts. Automaton has 99 states and 124 transitions. Word has length 38 [2024-11-11 20:03:09,095 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-11 20:03:09,095 INFO L471 AbstractCegarLoop]: Abstraction has 99 states and 124 transitions. [2024-11-11 20:03:09,095 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-11 20:03:09,095 INFO L276 IsEmpty]: Start isEmpty. Operand 99 states and 124 transitions. [2024-11-11 20:03:09,095 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 41 [2024-11-11 20:03:09,095 INFO L210 NwaCegarLoop]: Found error trace [2024-11-11 20:03:09,095 INFO L218 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-11 20:03:09,108 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-11 20:03:09,296 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-11 20:03:09,296 INFO L396 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-11 20:03:09,296 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-11 20:03:09,296 INFO L85 PathProgramCache]: Analyzing trace with hash 1925895455, now seen corresponding path program 1 times [2024-11-11 20:03:09,297 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-11 20:03:09,298 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1504962887] [2024-11-11 20:03:09,298 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-11 20:03:09,298 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-11 20:03:09,307 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 20:03:09,437 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-11 20:03:09,438 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 20:03:09,439 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2024-11-11 20:03:09,440 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 20:03:09,442 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 15 [2024-11-11 20:03:09,442 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 20:03:09,443 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 20 [2024-11-11 20:03:09,448 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 20:03:09,461 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 25 [2024-11-11 20:03:09,462 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 20:03:09,464 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 31 [2024-11-11 20:03:09,465 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 20:03:09,467 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-11 20:03:09,467 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-11 20:03:09,467 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1504962887] [2024-11-11 20:03:09,467 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1504962887] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-11 20:03:09,468 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [760135117] [2024-11-11 20:03:09,468 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-11 20:03:09,468 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-11 20:03:09,468 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-11 20:03:09,469 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-11 20:03:09,470 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-11 20:03:09,505 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 20:03:09,506 INFO L256 TraceCheckSpWp]: Trace formula consists of 109 conjuncts, 11 conjuncts are in the unsatisfiable core [2024-11-11 20:03:09,507 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2024-11-11 20:03:09,594 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-11 20:03:09,594 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-11 20:03:09,594 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [760135117] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-11 20:03:09,594 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-11 20:03:09,594 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [8] total 12 [2024-11-11 20:03:09,595 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1265544660] [2024-11-11 20:03:09,595 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-11 20:03:09,595 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2024-11-11 20:03:09,595 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-11 20:03:09,595 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2024-11-11 20:03:09,595 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=27, Invalid=105, Unknown=0, NotChecked=0, Total=132 [2024-11-11 20:03:09,595 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-11 20:03:09,674 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-11 20:03:09,674 INFO L93 Difference]: Finished difference Result 113 states and 138 transitions. [2024-11-11 20:03:09,675 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2024-11-11 20:03:09,675 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-11 20:03:09,675 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-11 20:03:09,676 INFO L225 Difference]: With dead ends: 113 [2024-11-11 20:03:09,676 INFO L226 Difference]: Without dead ends: 103 [2024-11-11 20:03:09,676 INFO L434 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-11 20:03:09,676 INFO L435 NwaCegarLoop]: 30 mSDtfsCounter, 7 mSDsluCounter, 106 mSDsCounter, 0 mSdLazyCounter, 58 mSolverCounterSat, 7 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s 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-11 20:03:09,677 INFO L436 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-11 20:03:09,677 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 103 states. [2024-11-11 20:03:09,689 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 103 to 100. [2024-11-11 20:03:09,689 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-11 20:03:09,690 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 100 states to 100 states and 123 transitions. [2024-11-11 20:03:09,690 INFO L78 Accepts]: Start accepts. Automaton has 100 states and 123 transitions. Word has length 40 [2024-11-11 20:03:09,690 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-11 20:03:09,690 INFO L471 AbstractCegarLoop]: Abstraction has 100 states and 123 transitions. [2024-11-11 20:03:09,690 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-11 20:03:09,690 INFO L276 IsEmpty]: Start isEmpty. Operand 100 states and 123 transitions. [2024-11-11 20:03:09,690 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 44 [2024-11-11 20:03:09,690 INFO L210 NwaCegarLoop]: Found error trace [2024-11-11 20:03:09,691 INFO L218 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-11 20:03:09,713 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-11 20:03:09,891 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-11 20:03:09,891 INFO L396 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-11 20:03:09,892 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-11 20:03:09,892 INFO L85 PathProgramCache]: Analyzing trace with hash 968731240, now seen corresponding path program 2 times [2024-11-11 20:03:09,892 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-11 20:03:09,892 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [770644950] [2024-11-11 20:03:09,892 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-11 20:03:09,892 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-11 20:03:09,900 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-11 20:03:09,901 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [22545993] [2024-11-11 20:03:09,901 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-11 20:03:09,901 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-11 20:03:09,901 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-11 20:03:09,903 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-11 20:03:09,904 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-11 20:03:09,943 INFO L229 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-11 20:03:09,943 INFO L230 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-11 20:03:09,944 INFO L256 TraceCheckSpWp]: Trace formula consists of 120 conjuncts, 35 conjuncts are in the unsatisfiable core [2024-11-11 20:03:09,945 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2024-11-11 20:03:10,252 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-11 20:03:10,252 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2024-11-11 20:03:10,708 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-11 20:03:10,708 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-11 20:03:10,708 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [770644950] [2024-11-11 20:03:10,708 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-11 20:03:10,708 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [22545993] [2024-11-11 20:03:10,708 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [22545993] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-11 20:03:10,708 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-11 20:03:10,708 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 8] total 17 [2024-11-11 20:03:10,708 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [6726822] [2024-11-11 20:03:10,708 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-11 20:03:10,709 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 17 states [2024-11-11 20:03:10,709 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-11 20:03:10,709 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2024-11-11 20:03:10,709 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=48, Invalid=224, Unknown=0, NotChecked=0, Total=272 [2024-11-11 20:03:10,709 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-11 20:03:14,946 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.01s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-11 20:03:15,189 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-11 20:03:15,190 INFO L93 Difference]: Finished difference Result 151 states and 206 transitions. [2024-11-11 20:03:15,190 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 17 states. [2024-11-11 20:03:15,190 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-11 20:03:15,191 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-11 20:03:15,192 INFO L225 Difference]: With dead ends: 151 [2024-11-11 20:03:15,193 INFO L226 Difference]: Without dead ends: 149 [2024-11-11 20:03:15,193 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 91 GetRequests, 69 SyntacticMatches, 0 SemanticMatches, 22 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 73 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=113, Invalid=439, Unknown=0, NotChecked=0, Total=552 [2024-11-11 20:03:15,194 INFO L435 NwaCegarLoop]: 26 mSDtfsCounter, 50 mSDsluCounter, 196 mSDsCounter, 0 mSdLazyCounter, 256 mSolverCounterSat, 57 mSolverCounterUnsat, 1 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 4.2s 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-11 20:03:15,194 INFO L436 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-11 20:03:15,195 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 149 states. [2024-11-11 20:03:15,217 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 149 to 104. [2024-11-11 20:03:15,218 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-11 20:03:15,218 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 104 states to 104 states and 126 transitions. [2024-11-11 20:03:15,218 INFO L78 Accepts]: Start accepts. Automaton has 104 states and 126 transitions. Word has length 43 [2024-11-11 20:03:15,219 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-11 20:03:15,219 INFO L471 AbstractCegarLoop]: Abstraction has 104 states and 126 transitions. [2024-11-11 20:03:15,219 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-11 20:03:15,219 INFO L276 IsEmpty]: Start isEmpty. Operand 104 states and 126 transitions. [2024-11-11 20:03:15,219 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 49 [2024-11-11 20:03:15,219 INFO L210 NwaCegarLoop]: Found error trace [2024-11-11 20:03:15,219 INFO L218 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-11 20:03:15,232 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-11 20:03:15,420 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-11 20:03:15,420 INFO L396 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-11 20:03:15,420 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-11 20:03:15,420 INFO L85 PathProgramCache]: Analyzing trace with hash -740326292, now seen corresponding path program 1 times [2024-11-11 20:03:15,421 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-11 20:03:15,421 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1992304413] [2024-11-11 20:03:15,421 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-11 20:03:15,421 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-11 20:03:15,429 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-11 20:03:15,429 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [113983730] [2024-11-11 20:03:15,429 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-11 20:03:15,429 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-11 20:03:15,430 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-11 20:03:15,431 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-11 20:03:15,432 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-11 20:03:15,467 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 20:03:15,468 INFO L256 TraceCheckSpWp]: Trace formula consists of 129 conjuncts, 33 conjuncts are in the unsatisfiable core [2024-11-11 20:03:15,469 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2024-11-11 20:03:15,705 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-11 20:03:15,705 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2024-11-11 20:03:15,950 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-11 20:03:15,951 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-11 20:03:15,951 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1992304413] [2024-11-11 20:03:15,951 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-11 20:03:15,951 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [113983730] [2024-11-11 20:03:15,951 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [113983730] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-11 20:03:15,951 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-11 20:03:15,951 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 10] total 17 [2024-11-11 20:03:15,951 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1292030245] [2024-11-11 20:03:15,951 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-11 20:03:15,951 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 17 states [2024-11-11 20:03:15,951 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-11 20:03:15,952 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2024-11-11 20:03:15,952 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=51, Invalid=221, Unknown=0, NotChecked=0, Total=272 [2024-11-11 20:03:15,952 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-11 20:03:16,775 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-11 20:03:16,775 INFO L93 Difference]: Finished difference Result 140 states and 187 transitions. [2024-11-11 20:03:16,776 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 17 states. [2024-11-11 20:03:16,776 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-11 20:03:16,776 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-11 20:03:16,777 INFO L225 Difference]: With dead ends: 140 [2024-11-11 20:03:16,777 INFO L226 Difference]: Without dead ends: 122 [2024-11-11 20:03:16,778 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 100 GetRequests, 77 SyntacticMatches, 2 SemanticMatches, 21 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 79 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=106, Invalid=400, Unknown=0, NotChecked=0, Total=506 [2024-11-11 20:03:16,778 INFO L435 NwaCegarLoop]: 27 mSDtfsCounter, 31 mSDsluCounter, 246 mSDsCounter, 0 mSdLazyCounter, 269 mSolverCounterSat, 62 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.6s 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-11 20:03:16,778 INFO L436 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-11 20:03:16,779 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 122 states. [2024-11-11 20:03:16,805 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 122 to 94. [2024-11-11 20:03:16,806 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-11 20:03:16,806 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 94 states to 94 states and 110 transitions. [2024-11-11 20:03:16,806 INFO L78 Accepts]: Start accepts. Automaton has 94 states and 110 transitions. Word has length 48 [2024-11-11 20:03:16,806 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-11 20:03:16,807 INFO L471 AbstractCegarLoop]: Abstraction has 94 states and 110 transitions. [2024-11-11 20:03:16,807 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-11 20:03:16,807 INFO L276 IsEmpty]: Start isEmpty. Operand 94 states and 110 transitions. [2024-11-11 20:03:16,807 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 58 [2024-11-11 20:03:16,807 INFO L210 NwaCegarLoop]: Found error trace [2024-11-11 20:03:16,808 INFO L218 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-11 20:03:16,822 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-11 20:03:17,011 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-11 20:03:17,012 INFO L396 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-11 20:03:17,012 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-11 20:03:17,012 INFO L85 PathProgramCache]: Analyzing trace with hash 1803285070, now seen corresponding path program 2 times [2024-11-11 20:03:17,012 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-11 20:03:17,012 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [609532854] [2024-11-11 20:03:17,013 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-11 20:03:17,013 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-11 20:03:17,022 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-11 20:03:17,023 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [950351770] [2024-11-11 20:03:17,023 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-11 20:03:17,023 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-11 20:03:17,023 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-11 20:03:17,024 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-11 20:03:17,026 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-11 20:03:17,065 INFO L229 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-11 20:03:17,065 INFO L230 tOrderPrioritization]: Conjunction of SSA is sat [2024-11-11 20:03:17,066 INFO L357 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-11 20:03:17,078 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-11 20:03:17,098 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-11 20:03:17,099 INFO L339 BasicCegarLoop]: Counterexample is feasible [2024-11-11 20:03:17,099 INFO L782 garLoopResultBuilder]: Registering result UNSAFE for location __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION (0 of 1 remaining) [2024-11-11 20:03:17,116 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-11 20:03:17,302 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-11 20:03:17,305 INFO L421 BasicCegarLoop]: Path program histogram: [2, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-11 20:03:17,330 INFO L170 ceAbstractionStarter]: Computing trace abstraction results [2024-11-11 20:03:17,332 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 11.11 08:03:17 BoogieIcfgContainer [2024-11-11 20:03:17,332 INFO L131 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2024-11-11 20:03:17,332 INFO L112 PluginConnector]: ------------------------Witness Printer---------------------------- [2024-11-11 20:03:17,332 INFO L270 PluginConnector]: Initializing Witness Printer... [2024-11-11 20:03:17,332 INFO L274 PluginConnector]: Witness Printer initialized [2024-11-11 20:03:17,333 INFO L184 PluginConnector]: Executing the observer RCFGCatcher from plugin Witness Printer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 11.11 08:03:06" (3/4) ... [2024-11-11 20:03:17,333 INFO L136 WitnessPrinter]: Generating witness for reachability counterexample [2024-11-11 20:03:17,381 INFO L149 WitnessManager]: Wrote witness to /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/witness.graphml [2024-11-11 20:03:17,384 INFO L131 PluginConnector]: ------------------------ END Witness Printer---------------------------- [2024-11-11 20:03:17,384 INFO L158 Benchmark]: Toolchain (without parser) took 11577.40ms. Allocated memory was 174.1MB in the beginning and 228.6MB in the end (delta: 54.5MB). Free memory was 108.5MB in the beginning and 109.8MB in the end (delta: -1.3MB). Peak memory consumption was 54.5MB. Max. memory is 16.1GB. [2024-11-11 20:03:17,385 INFO L158 Benchmark]: CDTParser took 0.13ms. Allocated memory is still 104.9MB. Free memory is still 67.3MB. There was no memory consumed. Max. memory is 16.1GB. [2024-11-11 20:03:17,385 INFO L158 Benchmark]: CACSL2BoogieTranslator took 224.15ms. Allocated memory is still 174.1MB. Free memory was 108.3MB in the beginning and 95.6MB in the end (delta: 12.7MB). Peak memory consumption was 12.6MB. Max. memory is 16.1GB. [2024-11-11 20:03:17,385 INFO L158 Benchmark]: Boogie Procedure Inliner took 62.50ms. Allocated memory is still 174.1MB. Free memory was 95.4MB in the beginning and 147.6MB in the end (delta: -52.1MB). Peak memory consumption was 6.7MB. Max. memory is 16.1GB. [2024-11-11 20:03:17,385 INFO L158 Benchmark]: Boogie Preprocessor took 54.16ms. Allocated memory is still 174.1MB. Free memory was 147.6MB in the beginning and 145.7MB in the end (delta: 1.9MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. [2024-11-11 20:03:17,385 INFO L158 Benchmark]: RCFGBuilder took 269.09ms. Allocated memory is still 174.1MB. Free memory was 145.7MB in the beginning and 133.8MB in the end (delta: 11.9MB). Peak memory consumption was 12.6MB. Max. memory is 16.1GB. [2024-11-11 20:03:17,385 INFO L158 Benchmark]: TraceAbstraction took 10911.11ms. Allocated memory was 174.1MB in the beginning and 228.6MB in the end (delta: 54.5MB). Free memory was 133.1MB in the beginning and 113.0MB in the end (delta: 20.2MB). Peak memory consumption was 77.2MB. Max. memory is 16.1GB. [2024-11-11 20:03:17,386 INFO L158 Benchmark]: Witness Printer took 51.76ms. Allocated memory is still 228.6MB. Free memory was 113.0MB in the beginning and 109.8MB in the end (delta: 3.1MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. [2024-11-11 20:03:17,387 INFO L338 ainManager$Toolchain]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * CDTParser took 0.13ms. Allocated memory is still 104.9MB. Free memory is still 67.3MB. There was no memory consumed. Max. memory is 16.1GB. * CACSL2BoogieTranslator took 224.15ms. Allocated memory is still 174.1MB. Free memory was 108.3MB in the beginning and 95.6MB in the end (delta: 12.7MB). Peak memory consumption was 12.6MB. Max. memory is 16.1GB. * Boogie Procedure Inliner took 62.50ms. Allocated memory is still 174.1MB. Free memory was 95.4MB in the beginning and 147.6MB in the end (delta: -52.1MB). Peak memory consumption was 6.7MB. Max. memory is 16.1GB. * Boogie Preprocessor took 54.16ms. Allocated memory is still 174.1MB. Free memory was 147.6MB in the beginning and 145.7MB in the end (delta: 1.9MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. * RCFGBuilder took 269.09ms. Allocated memory is still 174.1MB. Free memory was 145.7MB in the beginning and 133.8MB in the end (delta: 11.9MB). Peak memory consumption was 12.6MB. Max. memory is 16.1GB. * TraceAbstraction took 10911.11ms. Allocated memory was 174.1MB in the beginning and 228.6MB in the end (delta: 54.5MB). Free memory was 133.1MB in the beginning and 113.0MB in the end (delta: 20.2MB). Peak memory consumption was 77.2MB. Max. memory is 16.1GB. * Witness Printer took 51.76ms. Allocated memory is still 228.6MB. Free memory was 113.0MB in the beginning and 109.8MB 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: 10.8s, OverallIterations: 12, TraceHistogramMax: 7, PathProgramHistogramMax: 2, EmptinessCheckTime: 0.0s, AutomataDifference: 5.8s, DeadEndRemovalTime: 0.0s, HoareAnnotationTime: 0.0s, InitialAbstractionConstructionTime: 0.0s, HoareTripleCheckerStatistics: 1 mSolverCounterUnknown, 156 SdHoareTripleChecker+Valid, 5.2s IncrementalHoareTripleChecker+Time, 0 mSdLazyCounter, 128 mSDsluCounter, 1472 SdHoareTripleChecker+Invalid, 5.1s 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, 0.9s 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.3s SatisfiabilityAnalysisTime, 2.3s 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-11 20:03:17,404 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