./Ultimate.py --spec /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/properties/unreach-call.prp --file /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/egcd2-ll_unwindbound5.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version a046e57d Calling Ultimate with: /root/.sdkman/candidates/java/current/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 /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/egcd2-ll_unwindbound5.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 74e9855722264d342377b8ab219a69c32c582cc628f82167488f3dea5640534c --- Real Ultimate output --- This is Ultimate 0.2.5-tmp.dk.eval-mul-div-a046e57-m [2024-10-12 18:50:25,993 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-10-12 18:50:26,047 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf [2024-10-12 18:50:26,055 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-10-12 18:50:26,055 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-10-12 18:50:26,078 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-10-12 18:50:26,078 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-10-12 18:50:26,078 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-10-12 18:50:26,079 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2024-10-12 18:50:26,079 INFO L153 SettingsManager]: * Use memory slicer=true [2024-10-12 18:50:26,079 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2024-10-12 18:50:26,079 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2024-10-12 18:50:26,080 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2024-10-12 18:50:26,080 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2024-10-12 18:50:26,080 INFO L153 SettingsManager]: * Use SBE=true [2024-10-12 18:50:26,080 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-10-12 18:50:26,081 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2024-10-12 18:50:26,081 INFO L153 SettingsManager]: * sizeof long=4 [2024-10-12 18:50:26,081 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2024-10-12 18:50:26,081 INFO L153 SettingsManager]: * sizeof POINTER=4 [2024-10-12 18:50:26,082 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-10-12 18:50:26,083 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2024-10-12 18:50:26,083 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2024-10-12 18:50:26,083 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2024-10-12 18:50:26,084 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-10-12 18:50:26,084 INFO L153 SettingsManager]: * sizeof long double=12 [2024-10-12 18:50:26,084 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-10-12 18:50:26,084 INFO L153 SettingsManager]: * Use constant arrays=true [2024-10-12 18:50:26,084 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2024-10-12 18:50:26,085 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2024-10-12 18:50:26,085 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2024-10-12 18:50:26,085 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2024-10-12 18:50:26,085 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-10-12 18:50:26,085 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-10-12 18:50:26,086 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2024-10-12 18:50:26,086 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2024-10-12 18:50:26,086 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2024-10-12 18:50:26,090 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2024-10-12 18:50:26,090 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2024-10-12 18:50:26,090 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2024-10-12 18:50:26,091 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2024-10-12 18:50:26,091 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2024-10-12 18:50:26,092 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 -> 74e9855722264d342377b8ab219a69c32c582cc628f82167488f3dea5640534c [2024-10-12 18:50:26,282 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-10-12 18:50:26,304 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-10-12 18:50:26,308 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-10-12 18:50:26,309 INFO L270 PluginConnector]: Initializing CDTParser... [2024-10-12 18:50:26,309 INFO L274 PluginConnector]: CDTParser initialized [2024-10-12 18:50:26,310 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/egcd2-ll_unwindbound5.c [2024-10-12 18:50:27,622 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-10-12 18:50:27,771 INFO L384 CDTParser]: Found 1 translation units. [2024-10-12 18:50:27,772 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/egcd2-ll_unwindbound5.c [2024-10-12 18:50:27,781 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/a7ce9a84c/7dec3ddab01e4be48e0fdbc847a96b1e/FLAGcd640b5f0 [2024-10-12 18:50:27,794 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/a7ce9a84c/7dec3ddab01e4be48e0fdbc847a96b1e [2024-10-12 18:50:27,796 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-10-12 18:50:27,797 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2024-10-12 18:50:27,798 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-10-12 18:50:27,798 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-10-12 18:50:27,802 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-10-12 18:50:27,802 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 12.10 06:50:27" (1/1) ... [2024-10-12 18:50:27,803 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@526d93f4 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.10 06:50:27, skipping insertion in model container [2024-10-12 18:50:27,803 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 12.10 06:50:27" (1/1) ... [2024-10-12 18:50:27,819 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-10-12 18:50:27,983 WARN L248 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/egcd2-ll_unwindbound5.c[490,503] [2024-10-12 18:50:27,998 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-10-12 18:50:28,004 INFO L200 MainTranslator]: Completed pre-run [2024-10-12 18:50:28,013 WARN L248 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/egcd2-ll_unwindbound5.c[490,503] [2024-10-12 18:50:28,019 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-10-12 18:50:28,030 INFO L204 MainTranslator]: Completed translation [2024-10-12 18:50:28,031 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.10 06:50:28 WrapperNode [2024-10-12 18:50:28,031 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-10-12 18:50:28,032 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-10-12 18:50:28,032 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-10-12 18:50:28,032 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-10-12 18:50:28,037 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.10 06:50:28" (1/1) ... [2024-10-12 18:50:28,045 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.10 06:50:28" (1/1) ... [2024-10-12 18:50:28,060 INFO L138 Inliner]: procedures = 14, calls = 17, calls flagged for inlining = 2, calls inlined = 2, statements flattened = 86 [2024-10-12 18:50:28,060 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-10-12 18:50:28,061 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-10-12 18:50:28,061 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-10-12 18:50:28,061 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-10-12 18:50:28,072 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.10 06:50:28" (1/1) ... [2024-10-12 18:50:28,072 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.10 06:50:28" (1/1) ... [2024-10-12 18:50:28,073 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.10 06:50:28" (1/1) ... [2024-10-12 18:50:28,085 INFO L175 MemorySlicer]: Split 2 memory accesses to 1 slices as follows [2]. 100 percent of accesses are in the largest equivalence class. The 2 initializations are split as follows [2]. The 0 writes are split as follows [0]. [2024-10-12 18:50:28,089 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.10 06:50:28" (1/1) ... [2024-10-12 18:50:28,089 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.10 06:50:28" (1/1) ... [2024-10-12 18:50:28,091 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.10 06:50:28" (1/1) ... [2024-10-12 18:50:28,097 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.10 06:50:28" (1/1) ... [2024-10-12 18:50:28,098 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.10 06:50:28" (1/1) ... [2024-10-12 18:50:28,098 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.10 06:50:28" (1/1) ... [2024-10-12 18:50:28,099 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-10-12 18:50:28,104 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2024-10-12 18:50:28,104 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2024-10-12 18:50:28,104 INFO L274 PluginConnector]: RCFGBuilder initialized [2024-10-12 18:50:28,104 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.10 06:50:28" (1/1) ... [2024-10-12 18:50:28,110 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-10-12 18:50:28,119 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-12 18:50:28,134 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-10-12 18:50:28,137 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-10-12 18:50:28,171 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2024-10-12 18:50:28,171 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2024-10-12 18:50:28,171 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2024-10-12 18:50:28,171 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2024-10-12 18:50:28,171 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-10-12 18:50:28,171 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-10-12 18:50:28,172 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2024-10-12 18:50:28,172 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2024-10-12 18:50:28,224 INFO L238 CfgBuilder]: Building ICFG [2024-10-12 18:50:28,226 INFO L264 CfgBuilder]: Building CFG for each procedure with an implementation [2024-10-12 18:50:28,372 INFO L? ?]: Removed 11 outVars from TransFormulas that were not future-live. [2024-10-12 18:50:28,373 INFO L287 CfgBuilder]: Performing block encoding [2024-10-12 18:50:28,395 INFO L309 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-10-12 18:50:28,395 INFO L314 CfgBuilder]: Removed 2 assume(true) statements. [2024-10-12 18:50:28,396 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 12.10 06:50:28 BoogieIcfgContainer [2024-10-12 18:50:28,396 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2024-10-12 18:50:28,397 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2024-10-12 18:50:28,398 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2024-10-12 18:50:28,400 INFO L274 PluginConnector]: TraceAbstraction initialized [2024-10-12 18:50:28,400 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 12.10 06:50:27" (1/3) ... [2024-10-12 18:50:28,401 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@bffa62d and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 12.10 06:50:28, skipping insertion in model container [2024-10-12 18:50:28,401 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.10 06:50:28" (2/3) ... [2024-10-12 18:50:28,401 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@bffa62d and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 12.10 06:50:28, skipping insertion in model container [2024-10-12 18:50:28,402 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 12.10 06:50:28" (3/3) ... [2024-10-12 18:50:28,402 INFO L112 eAbstractionObserver]: Analyzing ICFG egcd2-ll_unwindbound5.c [2024-10-12 18:50:28,414 INFO L209 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2024-10-12 18:50:28,414 INFO L149 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2024-10-12 18:50:28,460 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2024-10-12 18:50:28,466 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;@5c8fc62d, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2024-10-12 18:50:28,467 INFO L334 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2024-10-12 18:50:28,470 INFO L276 IsEmpty]: Start isEmpty. Operand has 31 states, 17 states have (on average 1.5294117647058822) internal successors, (26), 19 states have internal predecessors, (26), 10 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2024-10-12 18:50:28,475 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 28 [2024-10-12 18:50:28,475 INFO L207 NwaCegarLoop]: Found error trace [2024-10-12 18:50:28,476 INFO L215 NwaCegarLoop]: trace histogram [4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-12 18:50:28,476 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-12 18:50:28,480 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-12 18:50:28,481 INFO L85 PathProgramCache]: Analyzing trace with hash -689848145, now seen corresponding path program 1 times [2024-10-12 18:50:28,487 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-12 18:50:28,487 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [595804576] [2024-10-12 18:50:28,488 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-12 18:50:28,488 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-12 18:50:28,562 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:50:28,604 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 1 [2024-10-12 18:50:28,606 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:50:28,611 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2024-10-12 18:50:28,614 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:50:28,620 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 12 [2024-10-12 18:50:28,621 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:50:28,627 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 17 [2024-10-12 18:50:28,628 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:50:28,631 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2024-10-12 18:50:28,632 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-12 18:50:28,632 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [595804576] [2024-10-12 18:50:28,632 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [595804576] provided 1 perfect and 0 imperfect interpolant sequences [2024-10-12 18:50:28,633 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-10-12 18:50:28,633 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2024-10-12 18:50:28,640 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1621625830] [2024-10-12 18:50:28,640 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-10-12 18:50:28,644 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2024-10-12 18:50:28,644 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-12 18:50:28,660 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2024-10-12 18:50:28,661 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2024-10-12 18:50:28,663 INFO L87 Difference]: Start difference. First operand has 31 states, 17 states have (on average 1.5294117647058822) internal successors, (26), 19 states have internal predecessors, (26), 10 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) Second operand has 2 states, 2 states have (on average 4.5) internal successors, (9), 2 states have internal predecessors, (9), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 2 states have call successors, (4) [2024-10-12 18:50:28,689 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-12 18:50:28,689 INFO L93 Difference]: Finished difference Result 60 states and 99 transitions. [2024-10-12 18:50:28,690 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2024-10-12 18:50:28,691 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 4.5) internal successors, (9), 2 states have internal predecessors, (9), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 2 states have call successors, (4) Word has length 27 [2024-10-12 18:50:28,691 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-12 18:50:28,696 INFO L225 Difference]: With dead ends: 60 [2024-10-12 18:50:28,696 INFO L226 Difference]: Without dead ends: 29 [2024-10-12 18:50:28,698 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 14 GetRequests, 14 SyntacticMatches, 0 SemanticMatches, 0 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2024-10-12 18:50:28,701 INFO L432 NwaCegarLoop]: 40 mSDtfsCounter, 0 mSDsluCounter, 0 mSDsCounter, 0 mSdLazyCounter, 2 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 40 SdHoareTripleChecker+Invalid, 2 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 2 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-10-12 18:50:28,701 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 40 Invalid, 2 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 2 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-10-12 18:50:28,712 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 29 states. [2024-10-12 18:50:28,723 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 29 to 29. [2024-10-12 18:50:28,724 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 29 states, 16 states have (on average 1.3125) internal successors, (21), 18 states have internal predecessors, (21), 10 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2024-10-12 18:50:28,725 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 29 states to 29 states and 40 transitions. [2024-10-12 18:50:28,726 INFO L78 Accepts]: Start accepts. Automaton has 29 states and 40 transitions. Word has length 27 [2024-10-12 18:50:28,727 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-12 18:50:28,727 INFO L471 AbstractCegarLoop]: Abstraction has 29 states and 40 transitions. [2024-10-12 18:50:28,727 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 2 states have (on average 4.5) internal successors, (9), 2 states have internal predecessors, (9), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 2 states have call successors, (4) [2024-10-12 18:50:28,727 INFO L276 IsEmpty]: Start isEmpty. Operand 29 states and 40 transitions. [2024-10-12 18:50:28,728 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 29 [2024-10-12 18:50:28,729 INFO L207 NwaCegarLoop]: Found error trace [2024-10-12 18:50:28,729 INFO L215 NwaCegarLoop]: trace histogram [4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-12 18:50:28,729 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2024-10-12 18:50:28,730 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-12 18:50:28,730 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-12 18:50:28,731 INFO L85 PathProgramCache]: Analyzing trace with hash -1989097615, now seen corresponding path program 1 times [2024-10-12 18:50:28,731 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-12 18:50:28,731 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [643855311] [2024-10-12 18:50:28,731 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-12 18:50:28,732 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-12 18:50:28,769 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:50:28,949 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 1 [2024-10-12 18:50:28,954 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:50:28,961 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2024-10-12 18:50:28,963 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:50:28,969 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 12 [2024-10-12 18:50:28,971 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:50:28,976 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 17 [2024-10-12 18:50:28,977 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:50:28,981 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2024-10-12 18:50:28,981 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-12 18:50:28,981 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [643855311] [2024-10-12 18:50:28,981 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [643855311] provided 1 perfect and 0 imperfect interpolant sequences [2024-10-12 18:50:28,981 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-10-12 18:50:28,982 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2024-10-12 18:50:28,982 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [677384978] [2024-10-12 18:50:28,982 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-10-12 18:50:28,983 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2024-10-12 18:50:28,983 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-12 18:50:28,983 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2024-10-12 18:50:28,984 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2024-10-12 18:50:28,984 INFO L87 Difference]: Start difference. First operand 29 states and 40 transitions. Second operand has 4 states, 4 states have (on average 2.5) internal successors, (10), 4 states have internal predecessors, (10), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2024-10-12 18:50:29,000 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-12 18:50:29,000 INFO L93 Difference]: Finished difference Result 39 states and 51 transitions. [2024-10-12 18:50:29,000 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2024-10-12 18:50:29,001 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 2.5) internal successors, (10), 4 states have internal predecessors, (10), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) Word has length 28 [2024-10-12 18:50:29,001 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-12 18:50:29,001 INFO L225 Difference]: With dead ends: 39 [2024-10-12 18:50:29,002 INFO L226 Difference]: Without dead ends: 31 [2024-10-12 18:50:29,002 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 11 GetRequests, 9 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2024-10-12 18:50:29,003 INFO L432 NwaCegarLoop]: 37 mSDtfsCounter, 7 mSDsluCounter, 60 mSDsCounter, 0 mSdLazyCounter, 10 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 7 SdHoareTripleChecker+Valid, 97 SdHoareTripleChecker+Invalid, 10 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 10 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-10-12 18:50:29,003 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [7 Valid, 97 Invalid, 10 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 10 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-10-12 18:50:29,004 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 31 states. [2024-10-12 18:50:29,007 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 31 to 31. [2024-10-12 18:50:29,008 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 31 states, 18 states have (on average 1.2777777777777777) internal successors, (23), 19 states have internal predecessors, (23), 10 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2024-10-12 18:50:29,008 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 31 states to 31 states and 42 transitions. [2024-10-12 18:50:29,009 INFO L78 Accepts]: Start accepts. Automaton has 31 states and 42 transitions. Word has length 28 [2024-10-12 18:50:29,009 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-12 18:50:29,009 INFO L471 AbstractCegarLoop]: Abstraction has 31 states and 42 transitions. [2024-10-12 18:50:29,009 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 2.5) internal successors, (10), 4 states have internal predecessors, (10), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2024-10-12 18:50:29,010 INFO L276 IsEmpty]: Start isEmpty. Operand 31 states and 42 transitions. [2024-10-12 18:50:29,010 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 30 [2024-10-12 18:50:29,010 INFO L207 NwaCegarLoop]: Found error trace [2024-10-12 18:50:29,010 INFO L215 NwaCegarLoop]: trace histogram [4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-12 18:50:29,011 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2024-10-12 18:50:29,011 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-12 18:50:29,011 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-12 18:50:29,011 INFO L85 PathProgramCache]: Analyzing trace with hash -1539070609, now seen corresponding path program 1 times [2024-10-12 18:50:29,011 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-12 18:50:29,012 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1226842090] [2024-10-12 18:50:29,012 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-12 18:50:29,012 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-12 18:50:29,028 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:50:29,123 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 1 [2024-10-12 18:50:29,124 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:50:29,130 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2024-10-12 18:50:29,132 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:50:29,173 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 12 [2024-10-12 18:50:29,176 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:50:29,183 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 17 [2024-10-12 18:50:29,185 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:50:29,188 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 3 proven. 6 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2024-10-12 18:50:29,188 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-12 18:50:29,188 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1226842090] [2024-10-12 18:50:29,188 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1226842090] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-12 18:50:29,188 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [292151755] [2024-10-12 18:50:29,189 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-12 18:50:29,189 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-12 18:50:29,189 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-12 18:50:29,191 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-10-12 18:50:29,192 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-10-12 18:50:29,256 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:50:29,259 INFO L255 TraceCheckSpWp]: Trace formula consists of 99 conjuncts, 11 conjuncts are in the unsatisfiable core [2024-10-12 18:50:29,263 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-12 18:50:29,378 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2024-10-12 18:50:29,378 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-10-12 18:50:29,378 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [292151755] provided 1 perfect and 0 imperfect interpolant sequences [2024-10-12 18:50:29,378 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-10-12 18:50:29,379 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [6] total 10 [2024-10-12 18:50:29,379 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [75947815] [2024-10-12 18:50:29,379 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-10-12 18:50:29,379 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2024-10-12 18:50:29,379 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-12 18:50:29,380 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2024-10-12 18:50:29,380 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=17, Invalid=73, Unknown=0, NotChecked=0, Total=90 [2024-10-12 18:50:29,380 INFO L87 Difference]: Start difference. First operand 31 states and 42 transitions. Second operand has 6 states, 5 states have (on average 2.2) internal successors, (11), 5 states have internal predecessors, (11), 3 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2024-10-12 18:50:29,452 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-12 18:50:29,452 INFO L93 Difference]: Finished difference Result 48 states and 66 transitions. [2024-10-12 18:50:29,452 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2024-10-12 18:50:29,453 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 5 states have (on average 2.2) internal successors, (11), 5 states have internal predecessors, (11), 3 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) Word has length 29 [2024-10-12 18:50:29,453 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-12 18:50:29,453 INFO L225 Difference]: With dead ends: 48 [2024-10-12 18:50:29,454 INFO L226 Difference]: Without dead ends: 46 [2024-10-12 18:50:29,454 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 42 GetRequests, 33 SyntacticMatches, 0 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=21, Invalid=89, Unknown=0, NotChecked=0, Total=110 [2024-10-12 18:50:29,455 INFO L432 NwaCegarLoop]: 30 mSDtfsCounter, 9 mSDsluCounter, 108 mSDsCounter, 0 mSdLazyCounter, 59 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 14 SdHoareTripleChecker+Valid, 138 SdHoareTripleChecker+Invalid, 60 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 59 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-10-12 18:50:29,455 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [14 Valid, 138 Invalid, 60 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 59 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-10-12 18:50:29,456 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 46 states. [2024-10-12 18:50:29,462 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 46 to 44. [2024-10-12 18:50:29,463 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 44 states, 25 states have (on average 1.32) internal successors, (33), 27 states have internal predecessors, (33), 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-10-12 18:50:29,464 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 44 states to 44 states and 62 transitions. [2024-10-12 18:50:29,464 INFO L78 Accepts]: Start accepts. Automaton has 44 states and 62 transitions. Word has length 29 [2024-10-12 18:50:29,465 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-12 18:50:29,465 INFO L471 AbstractCegarLoop]: Abstraction has 44 states and 62 transitions. [2024-10-12 18:50:29,465 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 5 states have (on average 2.2) internal successors, (11), 5 states have internal predecessors, (11), 3 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2024-10-12 18:50:29,465 INFO L276 IsEmpty]: Start isEmpty. Operand 44 states and 62 transitions. [2024-10-12 18:50:29,466 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 32 [2024-10-12 18:50:29,466 INFO L207 NwaCegarLoop]: Found error trace [2024-10-12 18:50:29,466 INFO L215 NwaCegarLoop]: trace histogram [4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-12 18:50:29,483 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Ended with exit code 0 [2024-10-12 18:50:29,670 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-10-12 18:50:29,671 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-12 18:50:29,672 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-12 18:50:29,672 INFO L85 PathProgramCache]: Analyzing trace with hash -1634889762, now seen corresponding path program 1 times [2024-10-12 18:50:29,672 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-12 18:50:29,672 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [524041543] [2024-10-12 18:50:29,672 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-12 18:50:29,672 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-12 18:50:29,685 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-10-12 18:50:29,687 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1330766056] [2024-10-12 18:50:29,687 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-12 18:50:29,688 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-12 18:50:29,688 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-12 18:50:29,689 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-10-12 18:50:29,691 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-10-12 18:50:29,730 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:50:29,731 INFO L255 TraceCheckSpWp]: Trace formula consists of 107 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-10-12 18:50:29,733 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-12 18:50:29,776 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2024-10-12 18:50:29,776 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-10-12 18:50:29,776 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-12 18:50:29,777 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [524041543] [2024-10-12 18:50:29,777 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-10-12 18:50:29,777 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1330766056] [2024-10-12 18:50:29,777 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1330766056] provided 1 perfect and 0 imperfect interpolant sequences [2024-10-12 18:50:29,778 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-10-12 18:50:29,778 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-10-12 18:50:29,778 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [460884463] [2024-10-12 18:50:29,778 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-10-12 18:50:29,778 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-10-12 18:50:29,779 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-12 18:50:29,779 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-10-12 18:50:29,779 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-10-12 18:50:29,779 INFO L87 Difference]: Start difference. First operand 44 states and 62 transitions. Second operand has 5 states, 5 states have (on average 2.6) internal successors, (13), 4 states have internal predecessors, (13), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2024-10-12 18:50:29,828 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-12 18:50:29,828 INFO L93 Difference]: Finished difference Result 65 states and 94 transitions. [2024-10-12 18:50:29,829 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-10-12 18:50:29,829 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.6) internal successors, (13), 4 states have internal predecessors, (13), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) Word has length 31 [2024-10-12 18:50:29,829 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-12 18:50:29,831 INFO L225 Difference]: With dead ends: 65 [2024-10-12 18:50:29,831 INFO L226 Difference]: Without dead ends: 63 [2024-10-12 18:50:29,832 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 31 GetRequests, 27 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2024-10-12 18:50:29,832 INFO L432 NwaCegarLoop]: 36 mSDtfsCounter, 5 mSDsluCounter, 96 mSDsCounter, 0 mSdLazyCounter, 35 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 9 SdHoareTripleChecker+Valid, 132 SdHoareTripleChecker+Invalid, 35 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 35 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-10-12 18:50:29,833 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [9 Valid, 132 Invalid, 35 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 35 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-10-12 18:50:29,837 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 63 states. [2024-10-12 18:50:29,848 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 63 to 54. [2024-10-12 18:50:29,848 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 54 states, 32 states have (on average 1.3125) internal successors, (42), 36 states have internal predecessors, (42), 17 states have call successors, (17), 4 states have call predecessors, (17), 4 states have return successors, (16), 13 states have call predecessors, (16), 16 states have call successors, (16) [2024-10-12 18:50:29,849 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 54 states to 54 states and 75 transitions. [2024-10-12 18:50:29,850 INFO L78 Accepts]: Start accepts. Automaton has 54 states and 75 transitions. Word has length 31 [2024-10-12 18:50:29,850 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-12 18:50:29,850 INFO L471 AbstractCegarLoop]: Abstraction has 54 states and 75 transitions. [2024-10-12 18:50:29,850 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.6) internal successors, (13), 4 states have internal predecessors, (13), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2024-10-12 18:50:29,850 INFO L276 IsEmpty]: Start isEmpty. Operand 54 states and 75 transitions. [2024-10-12 18:50:29,851 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 35 [2024-10-12 18:50:29,851 INFO L207 NwaCegarLoop]: Found error trace [2024-10-12 18:50:29,851 INFO L215 NwaCegarLoop]: trace histogram [4, 4, 4, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-12 18:50:29,864 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Ended with exit code 0 [2024-10-12 18:50:30,055 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-10-12 18:50:30,056 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-12 18:50:30,057 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-12 18:50:30,057 INFO L85 PathProgramCache]: Analyzing trace with hash -254153455, now seen corresponding path program 1 times [2024-10-12 18:50:30,057 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-12 18:50:30,057 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [654733363] [2024-10-12 18:50:30,058 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-12 18:50:30,058 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-12 18:50:30,068 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:50:30,112 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 1 [2024-10-12 18:50:30,113 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:50:30,116 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2024-10-12 18:50:30,118 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:50:30,157 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 12 [2024-10-12 18:50:30,159 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:50:30,161 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 17 [2024-10-12 18:50:30,165 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:50:30,168 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 25 [2024-10-12 18:50:30,170 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:50:30,172 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 5 proven. 6 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2024-10-12 18:50:30,173 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-12 18:50:30,173 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [654733363] [2024-10-12 18:50:30,173 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [654733363] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-12 18:50:30,174 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2032779929] [2024-10-12 18:50:30,174 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-12 18:50:30,174 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-12 18:50:30,177 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-12 18:50:30,178 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-10-12 18:50:30,179 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-10-12 18:50:30,226 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:50:30,227 INFO L255 TraceCheckSpWp]: Trace formula consists of 108 conjuncts, 9 conjuncts are in the unsatisfiable core [2024-10-12 18:50:30,229 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-12 18:50:30,328 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2024-10-12 18:50:30,329 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-10-12 18:50:30,329 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2032779929] provided 1 perfect and 0 imperfect interpolant sequences [2024-10-12 18:50:30,329 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-10-12 18:50:30,329 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [6] total 9 [2024-10-12 18:50:30,330 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1030170456] [2024-10-12 18:50:30,330 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-10-12 18:50:30,330 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-10-12 18:50:30,330 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-12 18:50:30,330 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-10-12 18:50:30,331 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=15, Invalid=57, Unknown=0, NotChecked=0, Total=72 [2024-10-12 18:50:30,331 INFO L87 Difference]: Start difference. First operand 54 states and 75 transitions. Second operand has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2024-10-12 18:50:30,377 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-12 18:50:30,378 INFO L93 Difference]: Finished difference Result 62 states and 82 transitions. [2024-10-12 18:50:30,378 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-10-12 18:50:30,379 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) Word has length 34 [2024-10-12 18:50:30,379 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-12 18:50:30,379 INFO L225 Difference]: With dead ends: 62 [2024-10-12 18:50:30,380 INFO L226 Difference]: Without dead ends: 58 [2024-10-12 18:50:30,381 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 49 GetRequests, 41 SyntacticMatches, 0 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=19, Invalid=71, Unknown=0, NotChecked=0, Total=90 [2024-10-12 18:50:30,381 INFO L432 NwaCegarLoop]: 37 mSDtfsCounter, 9 mSDsluCounter, 98 mSDsCounter, 0 mSdLazyCounter, 30 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 13 SdHoareTripleChecker+Valid, 135 SdHoareTripleChecker+Invalid, 31 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 30 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-10-12 18:50:30,400 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [13 Valid, 135 Invalid, 31 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 30 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-10-12 18:50:30,400 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 58 states. [2024-10-12 18:50:30,409 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 58 to 57. [2024-10-12 18:50:30,410 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 57 states, 35 states have (on average 1.2571428571428571) internal successors, (44), 38 states have internal predecessors, (44), 16 states have call successors, (16), 5 states have call predecessors, (16), 5 states have return successors, (15), 13 states have call predecessors, (15), 15 states have call successors, (15) [2024-10-12 18:50:30,410 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 57 states to 57 states and 75 transitions. [2024-10-12 18:50:30,410 INFO L78 Accepts]: Start accepts. Automaton has 57 states and 75 transitions. Word has length 34 [2024-10-12 18:50:30,411 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-12 18:50:30,411 INFO L471 AbstractCegarLoop]: Abstraction has 57 states and 75 transitions. [2024-10-12 18:50:30,411 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2024-10-12 18:50:30,411 INFO L276 IsEmpty]: Start isEmpty. Operand 57 states and 75 transitions. [2024-10-12 18:50:30,411 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 35 [2024-10-12 18:50:30,411 INFO L207 NwaCegarLoop]: Found error trace [2024-10-12 18:50:30,412 INFO L215 NwaCegarLoop]: trace histogram [4, 4, 4, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-12 18:50:30,426 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Forceful destruction successful, exit code 0 [2024-10-12 18:50:30,612 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-10-12 18:50:30,612 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-12 18:50:30,613 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-12 18:50:30,613 INFO L85 PathProgramCache]: Analyzing trace with hash 753217482, now seen corresponding path program 1 times [2024-10-12 18:50:30,613 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-12 18:50:30,613 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [256208101] [2024-10-12 18:50:30,613 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-12 18:50:30,613 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-12 18:50:30,621 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:50:30,674 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 1 [2024-10-12 18:50:30,675 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:50:30,677 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2024-10-12 18:50:30,677 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:50:30,681 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 12 [2024-10-12 18:50:30,682 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:50:30,684 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 17 [2024-10-12 18:50:30,684 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:50:30,686 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2024-10-12 18:50:30,686 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-12 18:50:30,686 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [256208101] [2024-10-12 18:50:30,686 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [256208101] provided 1 perfect and 0 imperfect interpolant sequences [2024-10-12 18:50:30,686 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-10-12 18:50:30,686 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2024-10-12 18:50:30,687 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [817823623] [2024-10-12 18:50:30,687 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-10-12 18:50:30,688 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2024-10-12 18:50:30,688 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-12 18:50:30,689 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2024-10-12 18:50:30,689 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2024-10-12 18:50:30,689 INFO L87 Difference]: Start difference. First operand 57 states and 75 transitions. Second operand has 6 states, 6 states have (on average 2.6666666666666665) internal successors, (16), 6 states have internal predecessors, (16), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2024-10-12 18:50:30,723 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-12 18:50:30,723 INFO L93 Difference]: Finished difference Result 83 states and 110 transitions. [2024-10-12 18:50:30,724 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2024-10-12 18:50:30,724 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 2.6666666666666665) internal successors, (16), 6 states have internal predecessors, (16), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) Word has length 34 [2024-10-12 18:50:30,724 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-12 18:50:30,725 INFO L225 Difference]: With dead ends: 83 [2024-10-12 18:50:30,726 INFO L226 Difference]: Without dead ends: 57 [2024-10-12 18:50:30,726 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 13 GetRequests, 9 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2024-10-12 18:50:30,728 INFO L432 NwaCegarLoop]: 35 mSDtfsCounter, 10 mSDsluCounter, 85 mSDsCounter, 0 mSdLazyCounter, 30 mSolverCounterSat, 4 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 10 SdHoareTripleChecker+Valid, 120 SdHoareTripleChecker+Invalid, 34 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 4 IncrementalHoareTripleChecker+Valid, 30 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-10-12 18:50:30,728 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [10 Valid, 120 Invalid, 34 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [4 Valid, 30 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-10-12 18:50:30,729 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 57 states. [2024-10-12 18:50:30,736 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 57 to 57. [2024-10-12 18:50:30,737 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 57 states, 35 states have (on average 1.2285714285714286) internal successors, (43), 38 states have internal predecessors, (43), 16 states have call successors, (16), 5 states have call predecessors, (16), 5 states have return successors, (15), 13 states have call predecessors, (15), 15 states have call successors, (15) [2024-10-12 18:50:30,738 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 57 states to 57 states and 74 transitions. [2024-10-12 18:50:30,740 INFO L78 Accepts]: Start accepts. Automaton has 57 states and 74 transitions. Word has length 34 [2024-10-12 18:50:30,740 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-12 18:50:30,740 INFO L471 AbstractCegarLoop]: Abstraction has 57 states and 74 transitions. [2024-10-12 18:50:30,740 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 2.6666666666666665) internal successors, (16), 6 states have internal predecessors, (16), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2024-10-12 18:50:30,740 INFO L276 IsEmpty]: Start isEmpty. Operand 57 states and 74 transitions. [2024-10-12 18:50:30,741 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 47 [2024-10-12 18:50:30,741 INFO L207 NwaCegarLoop]: Found error trace [2024-10-12 18:50:30,741 INFO L215 NwaCegarLoop]: trace histogram [4, 4, 4, 4, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-12 18:50:30,741 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5 [2024-10-12 18:50:30,741 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-12 18:50:30,741 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-12 18:50:30,741 INFO L85 PathProgramCache]: Analyzing trace with hash 439925314, now seen corresponding path program 1 times [2024-10-12 18:50:30,742 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-12 18:50:30,742 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1947382132] [2024-10-12 18:50:30,742 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-12 18:50:30,742 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-12 18:50:30,758 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-10-12 18:50:30,760 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [648464268] [2024-10-12 18:50:30,762 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-12 18:50:30,763 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-12 18:50:30,763 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-12 18:50:30,764 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-10-12 18:50:30,765 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-10-12 18:50:30,807 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:50:30,808 INFO L255 TraceCheckSpWp]: Trace formula consists of 134 conjuncts, 11 conjuncts are in the unsatisfiable core [2024-10-12 18:50:30,810 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-12 18:50:30,930 INFO L134 CoverageAnalysis]: Checked inductivity of 42 backedges. 6 proven. 0 refuted. 0 times theorem prover too weak. 36 trivial. 0 not checked. [2024-10-12 18:50:30,930 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-10-12 18:50:30,930 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-12 18:50:30,931 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1947382132] [2024-10-12 18:50:30,931 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-10-12 18:50:30,931 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [648464268] [2024-10-12 18:50:30,931 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [648464268] provided 1 perfect and 0 imperfect interpolant sequences [2024-10-12 18:50:30,931 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-10-12 18:50:30,931 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-10-12 18:50:30,932 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1081441581] [2024-10-12 18:50:30,932 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-10-12 18:50:30,935 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-10-12 18:50:30,935 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-12 18:50:30,935 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-10-12 18:50:30,935 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-10-12 18:50:30,936 INFO L87 Difference]: Start difference. First operand 57 states and 74 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, (8), 2 states have call predecessors, (8), 1 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2024-10-12 18:50:30,982 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-12 18:50:30,983 INFO L93 Difference]: Finished difference Result 64 states and 80 transitions. [2024-10-12 18:50:30,983 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-10-12 18:50:30,983 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, (8), 2 states have call predecessors, (8), 1 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) Word has length 46 [2024-10-12 18:50:30,983 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-12 18:50:30,984 INFO L225 Difference]: With dead ends: 64 [2024-10-12 18:50:30,984 INFO L226 Difference]: Without dead ends: 62 [2024-10-12 18:50:30,984 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 46 GetRequests, 42 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2024-10-12 18:50:30,985 INFO L432 NwaCegarLoop]: 34 mSDtfsCounter, 6 mSDsluCounter, 89 mSDsCounter, 0 mSdLazyCounter, 42 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 7 SdHoareTripleChecker+Valid, 123 SdHoareTripleChecker+Invalid, 43 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 42 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-10-12 18:50:30,985 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [7 Valid, 123 Invalid, 43 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 42 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-10-12 18:50:30,985 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 62 states. [2024-10-12 18:50:30,991 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 62 to 61. [2024-10-12 18:50:30,991 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 61 states, 38 states have (on average 1.2105263157894737) internal successors, (46), 41 states have internal predecessors, (46), 16 states have call successors, (16), 6 states have call predecessors, (16), 6 states have return successors, (15), 13 states have call predecessors, (15), 15 states have call successors, (15) [2024-10-12 18:50:30,992 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 61 states to 61 states and 77 transitions. [2024-10-12 18:50:30,992 INFO L78 Accepts]: Start accepts. Automaton has 61 states and 77 transitions. Word has length 46 [2024-10-12 18:50:30,992 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-12 18:50:30,992 INFO L471 AbstractCegarLoop]: Abstraction has 61 states and 77 transitions. [2024-10-12 18:50:30,992 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, (8), 2 states have call predecessors, (8), 1 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2024-10-12 18:50:30,992 INFO L276 IsEmpty]: Start isEmpty. Operand 61 states and 77 transitions. [2024-10-12 18:50:30,993 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 55 [2024-10-12 18:50:30,993 INFO L207 NwaCegarLoop]: Found error trace [2024-10-12 18:50:30,993 INFO L215 NwaCegarLoop]: trace histogram [5, 4, 4, 4, 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, 1, 1] [2024-10-12 18:50:31,006 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Ended with exit code 0 [2024-10-12 18:50:31,197 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-10-12 18:50:31,197 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-12 18:50:31,198 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-12 18:50:31,198 INFO L85 PathProgramCache]: Analyzing trace with hash -982723610, now seen corresponding path program 1 times [2024-10-12 18:50:31,198 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-12 18:50:31,198 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1134074685] [2024-10-12 18:50:31,198 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-12 18:50:31,199 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-12 18:50:31,209 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-10-12 18:50:31,209 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [585893670] [2024-10-12 18:50:31,210 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-12 18:50:31,210 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-12 18:50:31,210 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-12 18:50:31,211 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-10-12 18:50:31,213 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-10-12 18:50:31,256 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:50:31,257 INFO L255 TraceCheckSpWp]: Trace formula consists of 153 conjuncts, 15 conjuncts are in the unsatisfiable core [2024-10-12 18:50:31,258 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-12 18:50:31,308 INFO L134 CoverageAnalysis]: Checked inductivity of 59 backedges. 8 proven. 3 refuted. 0 times theorem prover too weak. 48 trivial. 0 not checked. [2024-10-12 18:50:31,308 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-12 18:50:31,367 INFO L134 CoverageAnalysis]: Checked inductivity of 59 backedges. 8 proven. 0 refuted. 0 times theorem prover too weak. 51 trivial. 0 not checked. [2024-10-12 18:50:31,368 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-12 18:50:31,368 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1134074685] [2024-10-12 18:50:31,368 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-10-12 18:50:31,368 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [585893670] [2024-10-12 18:50:31,368 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [585893670] provided 1 perfect and 1 imperfect interpolant sequences [2024-10-12 18:50:31,368 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-10-12 18:50:31,368 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [6] total 7 [2024-10-12 18:50:31,368 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [555913613] [2024-10-12 18:50:31,369 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-10-12 18:50:31,369 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-10-12 18:50:31,369 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-12 18:50:31,369 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-10-12 18:50:31,369 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=29, Unknown=0, NotChecked=0, Total=42 [2024-10-12 18:50:31,369 INFO L87 Difference]: Start difference. First operand 61 states and 77 transitions. Second operand has 5 states, 5 states have (on average 3.4) internal successors, (17), 4 states have internal predecessors, (17), 2 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (8), 2 states have call predecessors, (8), 2 states have call successors, (8) [2024-10-12 18:50:31,402 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-12 18:50:31,402 INFO L93 Difference]: Finished difference Result 67 states and 82 transitions. [2024-10-12 18:50:31,402 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-10-12 18:50:31,402 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.4) internal successors, (17), 4 states have internal predecessors, (17), 2 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (8), 2 states have call predecessors, (8), 2 states have call successors, (8) Word has length 54 [2024-10-12 18:50:31,403 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-12 18:50:31,403 INFO L225 Difference]: With dead ends: 67 [2024-10-12 18:50:31,403 INFO L226 Difference]: Without dead ends: 65 [2024-10-12 18:50:31,403 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 107 GetRequests, 99 SyntacticMatches, 2 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=17, Invalid=39, Unknown=0, NotChecked=0, Total=56 [2024-10-12 18:50:31,404 INFO L432 NwaCegarLoop]: 33 mSDtfsCounter, 5 mSDsluCounter, 84 mSDsCounter, 0 mSdLazyCounter, 32 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 5 SdHoareTripleChecker+Valid, 117 SdHoareTripleChecker+Invalid, 32 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 32 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-10-12 18:50:31,404 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [5 Valid, 117 Invalid, 32 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 32 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-10-12 18:50:31,404 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 65 states. [2024-10-12 18:50:31,411 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 65 to 57. [2024-10-12 18:50:31,411 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 57 states, 36 states have (on average 1.1944444444444444) internal successors, (43), 37 states have internal predecessors, (43), 14 states have call successors, (14), 6 states have call predecessors, (14), 6 states have return successors, (13), 13 states have call predecessors, (13), 13 states have call successors, (13) [2024-10-12 18:50:31,411 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 57 states to 57 states and 70 transitions. [2024-10-12 18:50:31,411 INFO L78 Accepts]: Start accepts. Automaton has 57 states and 70 transitions. Word has length 54 [2024-10-12 18:50:31,412 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-12 18:50:31,412 INFO L471 AbstractCegarLoop]: Abstraction has 57 states and 70 transitions. [2024-10-12 18:50:31,412 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.4) internal successors, (17), 4 states have internal predecessors, (17), 2 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (8), 2 states have call predecessors, (8), 2 states have call successors, (8) [2024-10-12 18:50:31,412 INFO L276 IsEmpty]: Start isEmpty. Operand 57 states and 70 transitions. [2024-10-12 18:50:31,413 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 56 [2024-10-12 18:50:31,413 INFO L207 NwaCegarLoop]: Found error trace [2024-10-12 18:50:31,413 INFO L215 NwaCegarLoop]: trace histogram [5, 4, 4, 4, 4, 4, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-12 18:50:31,425 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Ended with exit code 0 [2024-10-12 18:50:31,617 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-10-12 18:50:31,618 INFO L396 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-12 18:50:31,618 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-12 18:50:31,619 INFO L85 PathProgramCache]: Analyzing trace with hash -1428774585, now seen corresponding path program 1 times [2024-10-12 18:50:31,619 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-12 18:50:31,619 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1047333981] [2024-10-12 18:50:31,619 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-12 18:50:31,619 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-12 18:50:31,626 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:50:31,706 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 1 [2024-10-12 18:50:31,707 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:50:31,709 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2024-10-12 18:50:31,710 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:50:31,711 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 12 [2024-10-12 18:50:31,712 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:50:31,714 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 17 [2024-10-12 18:50:31,714 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:50:31,716 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 27 [2024-10-12 18:50:31,717 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:50:31,718 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 32 [2024-10-12 18:50:31,719 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:50:31,721 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 37 [2024-10-12 18:50:31,722 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:50:31,724 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 42 [2024-10-12 18:50:31,725 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:50:31,727 INFO L134 CoverageAnalysis]: Checked inductivity of 58 backedges. 8 proven. 2 refuted. 0 times theorem prover too weak. 48 trivial. 0 not checked. [2024-10-12 18:50:31,727 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-12 18:50:31,727 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1047333981] [2024-10-12 18:50:31,727 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1047333981] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-12 18:50:31,728 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [67842040] [2024-10-12 18:50:31,728 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-12 18:50:31,728 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-12 18:50:31,728 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-12 18:50:31,729 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-10-12 18:50:31,730 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-10-12 18:50:31,773 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:50:31,774 INFO L255 TraceCheckSpWp]: Trace formula consists of 161 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-10-12 18:50:31,776 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-12 18:50:31,833 INFO L134 CoverageAnalysis]: Checked inductivity of 58 backedges. 8 proven. 2 refuted. 0 times theorem prover too weak. 48 trivial. 0 not checked. [2024-10-12 18:50:31,833 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-12 18:50:31,899 INFO L134 CoverageAnalysis]: Checked inductivity of 58 backedges. 8 proven. 2 refuted. 0 times theorem prover too weak. 48 trivial. 0 not checked. [2024-10-12 18:50:31,900 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [67842040] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-12 18:50:31,900 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-10-12 18:50:31,900 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 5, 6] total 11 [2024-10-12 18:50:31,900 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1568653032] [2024-10-12 18:50:31,900 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-10-12 18:50:31,901 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 11 states [2024-10-12 18:50:31,901 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-12 18:50:31,902 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2024-10-12 18:50:31,902 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=41, Invalid=69, Unknown=0, NotChecked=0, Total=110 [2024-10-12 18:50:31,902 INFO L87 Difference]: Start difference. First operand 57 states and 70 transitions. Second operand has 11 states, 11 states have (on average 3.727272727272727) internal successors, (41), 11 states have internal predecessors, (41), 5 states have call successors, (25), 4 states have call predecessors, (25), 3 states have return successors, (24), 4 states have call predecessors, (24), 4 states have call successors, (24) [2024-10-12 18:50:32,014 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-12 18:50:32,015 INFO L93 Difference]: Finished difference Result 168 states and 197 transitions. [2024-10-12 18:50:32,015 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2024-10-12 18:50:32,015 INFO L78 Accepts]: Start accepts. Automaton has has 11 states, 11 states have (on average 3.727272727272727) internal successors, (41), 11 states have internal predecessors, (41), 5 states have call successors, (25), 4 states have call predecessors, (25), 3 states have return successors, (24), 4 states have call predecessors, (24), 4 states have call successors, (24) Word has length 55 [2024-10-12 18:50:32,016 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-12 18:50:32,017 INFO L225 Difference]: With dead ends: 168 [2024-10-12 18:50:32,017 INFO L226 Difference]: Without dead ends: 160 [2024-10-12 18:50:32,017 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 132 GetRequests, 120 SyntacticMatches, 1 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 23 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=54, Invalid=102, Unknown=0, NotChecked=0, Total=156 [2024-10-12 18:50:32,018 INFO L432 NwaCegarLoop]: 36 mSDtfsCounter, 56 mSDsluCounter, 144 mSDsCounter, 0 mSdLazyCounter, 76 mSolverCounterSat, 9 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 56 SdHoareTripleChecker+Valid, 180 SdHoareTripleChecker+Invalid, 85 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 9 IncrementalHoareTripleChecker+Valid, 76 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-10-12 18:50:32,018 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [56 Valid, 180 Invalid, 85 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [9 Valid, 76 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-10-12 18:50:32,018 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 160 states. [2024-10-12 18:50:32,037 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 160 to 154. [2024-10-12 18:50:32,037 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 154 states, 99 states have (on average 1.1818181818181819) internal successors, (117), 102 states have internal predecessors, (117), 34 states have call successors, (34), 20 states have call predecessors, (34), 20 states have return successors, (31), 31 states have call predecessors, (31), 31 states have call successors, (31) [2024-10-12 18:50:32,038 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 154 states to 154 states and 182 transitions. [2024-10-12 18:50:32,038 INFO L78 Accepts]: Start accepts. Automaton has 154 states and 182 transitions. Word has length 55 [2024-10-12 18:50:32,038 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-12 18:50:32,038 INFO L471 AbstractCegarLoop]: Abstraction has 154 states and 182 transitions. [2024-10-12 18:50:32,039 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 11 states, 11 states have (on average 3.727272727272727) internal successors, (41), 11 states have internal predecessors, (41), 5 states have call successors, (25), 4 states have call predecessors, (25), 3 states have return successors, (24), 4 states have call predecessors, (24), 4 states have call successors, (24) [2024-10-12 18:50:32,039 INFO L276 IsEmpty]: Start isEmpty. Operand 154 states and 182 transitions. [2024-10-12 18:50:32,040 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 57 [2024-10-12 18:50:32,040 INFO L207 NwaCegarLoop]: Found error trace [2024-10-12 18:50:32,040 INFO L215 NwaCegarLoop]: trace histogram [5, 4, 4, 4, 4, 4, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-12 18:50:32,052 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Ended with exit code 0 [2024-10-12 18:50:32,244 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-10-12 18:50:32,244 INFO L396 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-12 18:50:32,245 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-12 18:50:32,245 INFO L85 PathProgramCache]: Analyzing trace with hash -1348925863, now seen corresponding path program 1 times [2024-10-12 18:50:32,245 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-12 18:50:32,245 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [615761643] [2024-10-12 18:50:32,245 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-12 18:50:32,245 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-12 18:50:32,254 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:50:32,328 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 1 [2024-10-12 18:50:32,329 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:50:32,344 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2024-10-12 18:50:32,346 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:50:32,347 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 12 [2024-10-12 18:50:32,348 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:50:32,349 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 17 [2024-10-12 18:50:32,350 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:50:32,354 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 27 [2024-10-12 18:50:32,355 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:50:32,356 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 32 [2024-10-12 18:50:32,356 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:50:32,362 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 37 [2024-10-12 18:50:32,363 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:50:32,364 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 42 [2024-10-12 18:50:32,365 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:50:32,367 INFO L134 CoverageAnalysis]: Checked inductivity of 59 backedges. 8 proven. 12 refuted. 0 times theorem prover too weak. 39 trivial. 0 not checked. [2024-10-12 18:50:32,369 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-12 18:50:32,369 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [615761643] [2024-10-12 18:50:32,369 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [615761643] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-12 18:50:32,369 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [582428555] [2024-10-12 18:50:32,369 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-12 18:50:32,369 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-12 18:50:32,370 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-12 18:50:32,371 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-10-12 18:50:32,372 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-10-12 18:50:32,413 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:50:32,414 INFO L255 TraceCheckSpWp]: Trace formula consists of 163 conjuncts, 9 conjuncts are in the unsatisfiable core [2024-10-12 18:50:32,415 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-12 18:50:32,443 INFO L134 CoverageAnalysis]: Checked inductivity of 59 backedges. 8 proven. 12 refuted. 0 times theorem prover too weak. 39 trivial. 0 not checked. [2024-10-12 18:50:32,444 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-12 18:50:32,513 INFO L134 CoverageAnalysis]: Checked inductivity of 59 backedges. 8 proven. 12 refuted. 0 times theorem prover too weak. 39 trivial. 0 not checked. [2024-10-12 18:50:32,513 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [582428555] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-12 18:50:32,513 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-10-12 18:50:32,513 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8, 8] total 9 [2024-10-12 18:50:32,514 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1103111506] [2024-10-12 18:50:32,514 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-10-12 18:50:32,514 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2024-10-12 18:50:32,514 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-12 18:50:32,514 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2024-10-12 18:50:32,515 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=17, Invalid=55, Unknown=0, NotChecked=0, Total=72 [2024-10-12 18:50:32,515 INFO L87 Difference]: Start difference. First operand 154 states and 182 transitions. Second operand has 9 states, 9 states have (on average 2.888888888888889) internal successors, (26), 8 states have internal predecessors, (26), 5 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (8), 3 states have call predecessors, (8), 4 states have call successors, (8) [2024-10-12 18:50:32,664 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-12 18:50:32,664 INFO L93 Difference]: Finished difference Result 220 states and 287 transitions. [2024-10-12 18:50:32,664 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2024-10-12 18:50:32,664 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 9 states have (on average 2.888888888888889) internal successors, (26), 8 states have internal predecessors, (26), 5 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (8), 3 states have call predecessors, (8), 4 states have call successors, (8) Word has length 56 [2024-10-12 18:50:32,665 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-12 18:50:32,666 INFO L225 Difference]: With dead ends: 220 [2024-10-12 18:50:32,666 INFO L226 Difference]: Without dead ends: 206 [2024-10-12 18:50:32,666 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 138 GetRequests, 122 SyntacticMatches, 4 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 6 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=48, Invalid=134, Unknown=0, NotChecked=0, Total=182 [2024-10-12 18:50:32,667 INFO L432 NwaCegarLoop]: 47 mSDtfsCounter, 57 mSDsluCounter, 282 mSDsCounter, 0 mSdLazyCounter, 108 mSolverCounterSat, 35 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 62 SdHoareTripleChecker+Valid, 329 SdHoareTripleChecker+Invalid, 143 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 35 IncrementalHoareTripleChecker+Valid, 108 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-10-12 18:50:32,667 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [62 Valid, 329 Invalid, 143 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [35 Valid, 108 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-10-12 18:50:32,667 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 206 states. [2024-10-12 18:50:32,696 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 206 to 184. [2024-10-12 18:50:32,697 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 184 states, 120 states have (on average 1.2166666666666666) internal successors, (146), 122 states have internal predecessors, (146), 44 states have call successors, (44), 19 states have call predecessors, (44), 19 states have return successors, (42), 42 states have call predecessors, (42), 42 states have call successors, (42) [2024-10-12 18:50:32,698 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 184 states to 184 states and 232 transitions. [2024-10-12 18:50:32,698 INFO L78 Accepts]: Start accepts. Automaton has 184 states and 232 transitions. Word has length 56 [2024-10-12 18:50:32,698 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-12 18:50:32,698 INFO L471 AbstractCegarLoop]: Abstraction has 184 states and 232 transitions. [2024-10-12 18:50:32,698 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 9 states have (on average 2.888888888888889) internal successors, (26), 8 states have internal predecessors, (26), 5 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (8), 3 states have call predecessors, (8), 4 states have call successors, (8) [2024-10-12 18:50:32,699 INFO L276 IsEmpty]: Start isEmpty. Operand 184 states and 232 transitions. [2024-10-12 18:50:32,699 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 59 [2024-10-12 18:50:32,699 INFO L207 NwaCegarLoop]: Found error trace [2024-10-12 18:50:32,699 INFO L215 NwaCegarLoop]: trace histogram [5, 4, 4, 4, 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, 1, 1, 1, 1, 1, 1] [2024-10-12 18:50:32,712 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Ended with exit code 0 [2024-10-12 18:50:32,900 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-10-12 18:50:32,901 INFO L396 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-12 18:50:32,901 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-12 18:50:32,901 INFO L85 PathProgramCache]: Analyzing trace with hash -848672706, now seen corresponding path program 1 times [2024-10-12 18:50:32,901 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-12 18:50:32,901 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [237211526] [2024-10-12 18:50:32,901 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-12 18:50:32,902 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-12 18:50:32,909 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:50:32,963 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 1 [2024-10-12 18:50:32,964 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:50:32,966 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2024-10-12 18:50:32,967 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:50:32,968 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 12 [2024-10-12 18:50:32,968 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:50:32,969 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 17 [2024-10-12 18:50:32,970 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:50:32,971 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 27 [2024-10-12 18:50:32,972 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:50:32,973 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 32 [2024-10-12 18:50:32,974 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:50:32,975 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 37 [2024-10-12 18:50:32,975 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:50:32,977 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 42 [2024-10-12 18:50:32,977 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:50:32,979 INFO L134 CoverageAnalysis]: Checked inductivity of 61 backedges. 11 proven. 2 refuted. 0 times theorem prover too weak. 48 trivial. 0 not checked. [2024-10-12 18:50:32,979 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-12 18:50:32,979 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [237211526] [2024-10-12 18:50:32,979 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [237211526] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-12 18:50:32,979 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [961677412] [2024-10-12 18:50:32,979 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-12 18:50:32,979 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-12 18:50:32,980 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-12 18:50:32,981 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-10-12 18:50:32,982 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-10-12 18:50:33,022 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:50:33,023 INFO L255 TraceCheckSpWp]: Trace formula consists of 172 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-10-12 18:50:33,024 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-12 18:50:33,071 INFO L134 CoverageAnalysis]: Checked inductivity of 61 backedges. 11 proven. 2 refuted. 0 times theorem prover too weak. 48 trivial. 0 not checked. [2024-10-12 18:50:33,071 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-12 18:50:33,127 INFO L134 CoverageAnalysis]: Checked inductivity of 61 backedges. 11 proven. 2 refuted. 0 times theorem prover too weak. 48 trivial. 0 not checked. [2024-10-12 18:50:33,128 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [961677412] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-12 18:50:33,128 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-10-12 18:50:33,128 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 5, 6] total 11 [2024-10-12 18:50:33,128 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [909878265] [2024-10-12 18:50:33,128 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-10-12 18:50:33,129 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 11 states [2024-10-12 18:50:33,129 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-12 18:50:33,129 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2024-10-12 18:50:33,129 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=39, Invalid=71, Unknown=0, NotChecked=0, Total=110 [2024-10-12 18:50:33,130 INFO L87 Difference]: Start difference. First operand 184 states and 232 transitions. Second operand has 11 states, 11 states have (on average 3.909090909090909) internal successors, (43), 11 states have internal predecessors, (43), 5 states have call successors, (25), 4 states have call predecessors, (25), 3 states have return successors, (24), 4 states have call predecessors, (24), 4 states have call successors, (24) [2024-10-12 18:50:33,230 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-12 18:50:33,230 INFO L93 Difference]: Finished difference Result 264 states and 345 transitions. [2024-10-12 18:50:33,231 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2024-10-12 18:50:33,231 INFO L78 Accepts]: Start accepts. Automaton has has 11 states, 11 states have (on average 3.909090909090909) internal successors, (43), 11 states have internal predecessors, (43), 5 states have call successors, (25), 4 states have call predecessors, (25), 3 states have return successors, (24), 4 states have call predecessors, (24), 4 states have call successors, (24) Word has length 58 [2024-10-12 18:50:33,231 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-12 18:50:33,232 INFO L225 Difference]: With dead ends: 264 [2024-10-12 18:50:33,232 INFO L226 Difference]: Without dead ends: 192 [2024-10-12 18:50:33,232 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 139 GetRequests, 126 SyntacticMatches, 1 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 25 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=59, Invalid=123, Unknown=0, NotChecked=0, Total=182 [2024-10-12 18:50:33,233 INFO L432 NwaCegarLoop]: 35 mSDtfsCounter, 43 mSDsluCounter, 105 mSDsCounter, 0 mSdLazyCounter, 84 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 43 SdHoareTripleChecker+Valid, 140 SdHoareTripleChecker+Invalid, 86 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 84 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-10-12 18:50:33,233 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [43 Valid, 140 Invalid, 86 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 84 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-10-12 18:50:33,233 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 192 states. [2024-10-12 18:50:33,247 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 192 to 190. [2024-10-12 18:50:33,247 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 190 states, 126 states have (on average 1.1825396825396826) internal successors, (149), 128 states have internal predecessors, (149), 44 states have call successors, (44), 19 states have call predecessors, (44), 19 states have return successors, (42), 42 states have call predecessors, (42), 42 states have call successors, (42) [2024-10-12 18:50:33,248 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 190 states to 190 states and 235 transitions. [2024-10-12 18:50:33,248 INFO L78 Accepts]: Start accepts. Automaton has 190 states and 235 transitions. Word has length 58 [2024-10-12 18:50:33,248 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-12 18:50:33,248 INFO L471 AbstractCegarLoop]: Abstraction has 190 states and 235 transitions. [2024-10-12 18:50:33,249 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 11 states, 11 states have (on average 3.909090909090909) internal successors, (43), 11 states have internal predecessors, (43), 5 states have call successors, (25), 4 states have call predecessors, (25), 3 states have return successors, (24), 4 states have call predecessors, (24), 4 states have call successors, (24) [2024-10-12 18:50:33,249 INFO L276 IsEmpty]: Start isEmpty. Operand 190 states and 235 transitions. [2024-10-12 18:50:33,249 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 64 [2024-10-12 18:50:33,249 INFO L207 NwaCegarLoop]: Found error trace [2024-10-12 18:50:33,250 INFO L215 NwaCegarLoop]: trace histogram [6, 5, 5, 4, 4, 4, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-12 18:50:33,262 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Ended with exit code 0 [2024-10-12 18:50:33,453 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-10-12 18:50:33,454 INFO L396 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-12 18:50:33,454 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-12 18:50:33,455 INFO L85 PathProgramCache]: Analyzing trace with hash -421956392, now seen corresponding path program 1 times [2024-10-12 18:50:33,455 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-12 18:50:33,455 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1808679722] [2024-10-12 18:50:33,455 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-12 18:50:33,455 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-12 18:50:33,475 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-10-12 18:50:33,476 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1462189500] [2024-10-12 18:50:33,476 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-12 18:50:33,476 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-12 18:50:33,476 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-12 18:50:33,478 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-10-12 18:50:33,487 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-10-12 18:50:33,534 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:50:33,535 INFO L255 TraceCheckSpWp]: Trace formula consists of 180 conjuncts, 27 conjuncts are in the unsatisfiable core [2024-10-12 18:50:33,537 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-12 18:50:33,814 INFO L134 CoverageAnalysis]: Checked inductivity of 81 backedges. 10 proven. 19 refuted. 0 times theorem prover too weak. 52 trivial. 0 not checked. [2024-10-12 18:50:33,814 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-12 18:50:33,923 INFO L134 CoverageAnalysis]: Checked inductivity of 81 backedges. 10 proven. 7 refuted. 0 times theorem prover too weak. 64 trivial. 0 not checked. [2024-10-12 18:50:33,923 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-12 18:50:33,923 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1808679722] [2024-10-12 18:50:33,923 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-10-12 18:50:33,923 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1462189500] [2024-10-12 18:50:33,923 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1462189500] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-12 18:50:33,924 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-10-12 18:50:33,924 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 6] total 12 [2024-10-12 18:50:33,924 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1931018793] [2024-10-12 18:50:33,924 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-10-12 18:50:33,924 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2024-10-12 18:50:33,924 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-12 18:50:33,925 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2024-10-12 18:50:33,925 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=28, Invalid=104, Unknown=0, NotChecked=0, Total=132 [2024-10-12 18:50:33,925 INFO L87 Difference]: Start difference. First operand 190 states and 235 transitions. Second operand has 12 states, 11 states have (on average 3.5454545454545454) internal successors, (39), 9 states have internal predecessors, (39), 6 states have call successors, (19), 2 states have call predecessors, (19), 2 states have return successors, (18), 7 states have call predecessors, (18), 6 states have call successors, (18) [2024-10-12 18:50:34,100 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-12 18:50:34,101 INFO L93 Difference]: Finished difference Result 222 states and 281 transitions. [2024-10-12 18:50:34,101 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2024-10-12 18:50:34,101 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 11 states have (on average 3.5454545454545454) internal successors, (39), 9 states have internal predecessors, (39), 6 states have call successors, (19), 2 states have call predecessors, (19), 2 states have return successors, (18), 7 states have call predecessors, (18), 6 states have call successors, (18) Word has length 63 [2024-10-12 18:50:34,102 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-12 18:50:34,103 INFO L225 Difference]: With dead ends: 222 [2024-10-12 18:50:34,103 INFO L226 Difference]: Without dead ends: 218 [2024-10-12 18:50:34,104 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 126 GetRequests, 112 SyntacticMatches, 2 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 23 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=39, Invalid=143, Unknown=0, NotChecked=0, Total=182 [2024-10-12 18:50:34,104 INFO L432 NwaCegarLoop]: 44 mSDtfsCounter, 41 mSDsluCounter, 263 mSDsCounter, 0 mSdLazyCounter, 160 mSolverCounterSat, 13 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 50 SdHoareTripleChecker+Valid, 307 SdHoareTripleChecker+Invalid, 173 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 13 IncrementalHoareTripleChecker+Valid, 160 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-10-12 18:50:34,104 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [50 Valid, 307 Invalid, 173 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [13 Valid, 160 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-10-12 18:50:34,105 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 218 states. [2024-10-12 18:50:34,123 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 218 to 216. [2024-10-12 18:50:34,123 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 216 states, 142 states have (on average 1.204225352112676) internal successors, (171), 145 states have internal predecessors, (171), 52 states have call successors, (52), 21 states have call predecessors, (52), 21 states have return successors, (49), 49 states have call predecessors, (49), 49 states have call successors, (49) [2024-10-12 18:50:34,124 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 216 states to 216 states and 272 transitions. [2024-10-12 18:50:34,124 INFO L78 Accepts]: Start accepts. Automaton has 216 states and 272 transitions. Word has length 63 [2024-10-12 18:50:34,125 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-12 18:50:34,125 INFO L471 AbstractCegarLoop]: Abstraction has 216 states and 272 transitions. [2024-10-12 18:50:34,125 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 11 states have (on average 3.5454545454545454) internal successors, (39), 9 states have internal predecessors, (39), 6 states have call successors, (19), 2 states have call predecessors, (19), 2 states have return successors, (18), 7 states have call predecessors, (18), 6 states have call successors, (18) [2024-10-12 18:50:34,125 INFO L276 IsEmpty]: Start isEmpty. Operand 216 states and 272 transitions. [2024-10-12 18:50:34,126 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 69 [2024-10-12 18:50:34,126 INFO L207 NwaCegarLoop]: Found error trace [2024-10-12 18:50:34,126 INFO L215 NwaCegarLoop]: trace histogram [7, 6, 6, 4, 4, 4, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-12 18:50:34,139 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Ended with exit code 0 [2024-10-12 18:50:34,326 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-10-12 18:50:34,327 INFO L396 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-12 18:50:34,327 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-12 18:50:34,327 INFO L85 PathProgramCache]: Analyzing trace with hash -245166072, now seen corresponding path program 2 times [2024-10-12 18:50:34,327 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-12 18:50:34,327 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1808092191] [2024-10-12 18:50:34,328 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-12 18:50:34,328 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-12 18:50:34,340 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-10-12 18:50:34,341 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1885820123] [2024-10-12 18:50:34,341 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-10-12 18:50:34,341 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-12 18:50:34,341 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-12 18:50:34,343 INFO L229 MonitoredProcess]: Starting monitored process 11 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-10-12 18:50:34,344 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Waiting until timeout for monitored process [2024-10-12 18:50:34,395 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-10-12 18:50:34,396 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2024-10-12 18:50:34,398 INFO L255 TraceCheckSpWp]: Trace formula consists of 189 conjuncts, 30 conjuncts are in the unsatisfiable core [2024-10-12 18:50:34,400 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-12 18:50:34,740 INFO L134 CoverageAnalysis]: Checked inductivity of 104 backedges. 12 proven. 17 refuted. 0 times theorem prover too weak. 75 trivial. 0 not checked. [2024-10-12 18:50:34,740 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-12 18:50:35,042 INFO L134 CoverageAnalysis]: Checked inductivity of 104 backedges. 12 proven. 8 refuted. 0 times theorem prover too weak. 84 trivial. 0 not checked. [2024-10-12 18:50:35,043 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-12 18:50:35,043 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1808092191] [2024-10-12 18:50:35,043 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-10-12 18:50:35,043 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1885820123] [2024-10-12 18:50:35,043 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1885820123] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-12 18:50:35,043 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-10-12 18:50:35,044 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 8] total 15 [2024-10-12 18:50:35,044 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [696184127] [2024-10-12 18:50:35,044 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-10-12 18:50:35,044 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 15 states [2024-10-12 18:50:35,044 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-12 18:50:35,045 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2024-10-12 18:50:35,045 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=38, Invalid=172, Unknown=0, NotChecked=0, Total=210 [2024-10-12 18:50:35,045 INFO L87 Difference]: Start difference. First operand 216 states and 272 transitions. Second operand has 15 states, 15 states have (on average 2.6) internal successors, (39), 13 states have internal predecessors, (39), 8 states have call successors, (21), 2 states have call predecessors, (21), 2 states have return successors, (20), 8 states have call predecessors, (20), 8 states have call successors, (20) [2024-10-12 18:50:36,408 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-12 18:50:36,408 INFO L93 Difference]: Finished difference Result 370 states and 515 transitions. [2024-10-12 18:50:36,411 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 21 states. [2024-10-12 18:50:36,412 INFO L78 Accepts]: Start accepts. Automaton has has 15 states, 15 states have (on average 2.6) internal successors, (39), 13 states have internal predecessors, (39), 8 states have call successors, (21), 2 states have call predecessors, (21), 2 states have return successors, (20), 8 states have call predecessors, (20), 8 states have call successors, (20) Word has length 68 [2024-10-12 18:50:36,412 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-12 18:50:36,414 INFO L225 Difference]: With dead ends: 370 [2024-10-12 18:50:36,415 INFO L226 Difference]: Without dead ends: 368 [2024-10-12 18:50:36,417 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 149 GetRequests, 119 SyntacticMatches, 2 SemanticMatches, 28 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 159 ImplicationChecksByTransitivity, 0.8s TimeCoverageRelationStatistics Valid=198, Invalid=672, Unknown=0, NotChecked=0, Total=870 [2024-10-12 18:50:36,418 INFO L432 NwaCegarLoop]: 41 mSDtfsCounter, 120 mSDsluCounter, 286 mSDsCounter, 0 mSdLazyCounter, 254 mSolverCounterSat, 91 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.6s Time, 0 mProtectedPredicate, 0 mProtectedAction, 125 SdHoareTripleChecker+Valid, 327 SdHoareTripleChecker+Invalid, 345 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 91 IncrementalHoareTripleChecker+Valid, 254 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.7s IncrementalHoareTripleChecker+Time [2024-10-12 18:50:36,418 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [125 Valid, 327 Invalid, 345 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [91 Valid, 254 Invalid, 0 Unknown, 0 Unchecked, 0.7s Time] [2024-10-12 18:50:36,419 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 368 states. [2024-10-12 18:50:36,499 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 368 to 323. [2024-10-12 18:50:36,500 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 323 states, 209 states have (on average 1.277511961722488) internal successors, (267), 212 states have internal predecessors, (267), 88 states have call successors, (88), 25 states have call predecessors, (88), 25 states have return successors, (85), 85 states have call predecessors, (85), 85 states have call successors, (85) [2024-10-12 18:50:36,502 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 323 states to 323 states and 440 transitions. [2024-10-12 18:50:36,503 INFO L78 Accepts]: Start accepts. Automaton has 323 states and 440 transitions. Word has length 68 [2024-10-12 18:50:36,504 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-12 18:50:36,504 INFO L471 AbstractCegarLoop]: Abstraction has 323 states and 440 transitions. [2024-10-12 18:50:36,504 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 15 states, 15 states have (on average 2.6) internal successors, (39), 13 states have internal predecessors, (39), 8 states have call successors, (21), 2 states have call predecessors, (21), 2 states have return successors, (20), 8 states have call predecessors, (20), 8 states have call successors, (20) [2024-10-12 18:50:36,504 INFO L276 IsEmpty]: Start isEmpty. Operand 323 states and 440 transitions. [2024-10-12 18:50:36,505 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 74 [2024-10-12 18:50:36,505 INFO L207 NwaCegarLoop]: Found error trace [2024-10-12 18:50:36,507 INFO L215 NwaCegarLoop]: trace histogram [8, 7, 7, 4, 4, 4, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-12 18:50:36,528 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Ended with exit code 0 [2024-10-12 18:50:36,707 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 11 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable12 [2024-10-12 18:50:36,708 INFO L396 AbstractCegarLoop]: === Iteration 14 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-12 18:50:36,709 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-12 18:50:36,709 INFO L85 PathProgramCache]: Analyzing trace with hash -441972072, now seen corresponding path program 3 times [2024-10-12 18:50:36,709 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-12 18:50:36,709 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1965818715] [2024-10-12 18:50:36,709 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-12 18:50:36,709 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-12 18:50:36,727 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-10-12 18:50:36,728 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1834744504] [2024-10-12 18:50:36,728 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-10-12 18:50:36,728 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-12 18:50:36,729 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-12 18:50:36,732 INFO L229 MonitoredProcess]: Starting monitored process 12 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-10-12 18:50:36,733 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Waiting until timeout for monitored process [2024-10-12 18:50:36,826 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2024-10-12 18:50:36,826 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2024-10-12 18:50:36,827 INFO L255 TraceCheckSpWp]: Trace formula consists of 162 conjuncts, 59 conjuncts are in the unsatisfiable core [2024-10-12 18:50:36,829 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-12 18:50:37,942 INFO L134 CoverageAnalysis]: Checked inductivity of 131 backedges. 42 proven. 23 refuted. 0 times theorem prover too weak. 66 trivial. 0 not checked. [2024-10-12 18:50:37,942 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-12 18:50:57,366 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-12 18:50:57,367 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1965818715] [2024-10-12 18:50:57,367 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-10-12 18:50:57,367 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1834744504] [2024-10-12 18:50:57,367 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1834744504] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-12 18:50:57,367 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-10-12 18:50:57,367 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [16] total 16 [2024-10-12 18:50:57,367 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [730198379] [2024-10-12 18:50:57,367 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-10-12 18:50:57,368 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2024-10-12 18:50:57,368 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-12 18:50:57,368 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2024-10-12 18:50:57,368 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=114, Invalid=536, Unknown=0, NotChecked=0, Total=650 [2024-10-12 18:50:57,369 INFO L87 Difference]: Start difference. First operand 323 states and 440 transitions. Second operand has 16 states, 15 states have (on average 1.9333333333333333) internal successors, (29), 13 states have internal predecessors, (29), 5 states have call successors, (12), 2 states have call predecessors, (12), 3 states have return successors, (11), 6 states have call predecessors, (11), 5 states have call successors, (11) [2024-10-12 18:50:58,089 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-12 18:50:58,090 INFO L93 Difference]: Finished difference Result 338 states and 453 transitions. [2024-10-12 18:50:58,090 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2024-10-12 18:50:58,090 INFO L78 Accepts]: Start accepts. Automaton has has 16 states, 15 states have (on average 1.9333333333333333) internal successors, (29), 13 states have internal predecessors, (29), 5 states have call successors, (12), 2 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 73 [2024-10-12 18:50:58,090 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-12 18:50:58,092 INFO L225 Difference]: With dead ends: 338 [2024-10-12 18:50:58,092 INFO L226 Difference]: Without dead ends: 334 [2024-10-12 18:50:58,092 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 128 GetRequests, 100 SyntacticMatches, 0 SemanticMatches, 28 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 179 ImplicationChecksByTransitivity, 3.5s TimeCoverageRelationStatistics Valid=167, Invalid=703, Unknown=0, NotChecked=0, Total=870 [2024-10-12 18:50:58,092 INFO L432 NwaCegarLoop]: 31 mSDtfsCounter, 47 mSDsluCounter, 243 mSDsCounter, 0 mSdLazyCounter, 327 mSolverCounterSat, 22 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 60 SdHoareTripleChecker+Valid, 274 SdHoareTripleChecker+Invalid, 349 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 22 IncrementalHoareTripleChecker+Valid, 327 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2024-10-12 18:50:58,092 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [60 Valid, 274 Invalid, 349 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [22 Valid, 327 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2024-10-12 18:50:58,093 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 334 states. [2024-10-12 18:50:58,125 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 334 to 333. [2024-10-12 18:50:58,126 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 333 states, 217 states have (on average 1.262672811059908) internal successors, (274), 219 states have internal predecessors, (274), 88 states have call successors, (88), 28 states have call predecessors, (88), 27 states have return successors, (85), 85 states have call predecessors, (85), 85 states have call successors, (85) [2024-10-12 18:50:58,127 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 333 states to 333 states and 447 transitions. [2024-10-12 18:50:58,127 INFO L78 Accepts]: Start accepts. Automaton has 333 states and 447 transitions. Word has length 73 [2024-10-12 18:50:58,127 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-12 18:50:58,127 INFO L471 AbstractCegarLoop]: Abstraction has 333 states and 447 transitions. [2024-10-12 18:50:58,128 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 16 states, 15 states have (on average 1.9333333333333333) internal successors, (29), 13 states have internal predecessors, (29), 5 states have call successors, (12), 2 states have call predecessors, (12), 3 states have return successors, (11), 6 states have call predecessors, (11), 5 states have call successors, (11) [2024-10-12 18:50:58,128 INFO L276 IsEmpty]: Start isEmpty. Operand 333 states and 447 transitions. [2024-10-12 18:50:58,128 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 80 [2024-10-12 18:50:58,128 INFO L207 NwaCegarLoop]: Found error trace [2024-10-12 18:50:58,128 INFO L215 NwaCegarLoop]: trace histogram [9, 8, 8, 4, 4, 4, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-12 18:50:58,143 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Ended with exit code 0 [2024-10-12 18:50:58,332 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 12 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable13 [2024-10-12 18:50:58,333 INFO L396 AbstractCegarLoop]: === Iteration 15 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-12 18:50:58,333 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-12 18:50:58,333 INFO L85 PathProgramCache]: Analyzing trace with hash 2054740817, now seen corresponding path program 1 times [2024-10-12 18:50:58,333 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-12 18:50:58,333 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1959644626] [2024-10-12 18:50:58,334 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-12 18:50:58,334 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-12 18:50:58,344 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-10-12 18:50:58,345 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1183901292] [2024-10-12 18:50:58,345 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-12 18:50:58,345 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-12 18:50:58,345 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-12 18:50:58,347 INFO L229 MonitoredProcess]: Starting monitored process 13 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-10-12 18:50:58,347 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Waiting until timeout for monitored process [2024-10-12 18:50:58,397 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:50:58,398 INFO L255 TraceCheckSpWp]: Trace formula consists of 209 conjuncts, 41 conjuncts are in the unsatisfiable core [2024-10-12 18:50:58,400 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-12 18:50:58,820 INFO L134 CoverageAnalysis]: Checked inductivity of 162 backedges. 16 proven. 19 refuted. 0 times theorem prover too weak. 127 trivial. 0 not checked. [2024-10-12 18:50:58,820 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-12 18:50:59,531 INFO L134 CoverageAnalysis]: Checked inductivity of 162 backedges. 16 proven. 10 refuted. 0 times theorem prover too weak. 136 trivial. 0 not checked. [2024-10-12 18:50:59,531 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-12 18:50:59,531 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1959644626] [2024-10-12 18:50:59,531 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-10-12 18:50:59,531 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1183901292] [2024-10-12 18:50:59,531 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1183901292] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-12 18:50:59,532 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-10-12 18:50:59,532 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 10] total 21 [2024-10-12 18:50:59,532 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1469494982] [2024-10-12 18:50:59,532 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-10-12 18:50:59,532 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 21 states [2024-10-12 18:50:59,532 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-12 18:50:59,533 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2024-10-12 18:50:59,533 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=64, Invalid=356, Unknown=0, NotChecked=0, Total=420 [2024-10-12 18:50:59,533 INFO L87 Difference]: Start difference. First operand 333 states and 447 transitions. Second operand has 21 states, 19 states have (on average 2.263157894736842) internal successors, (43), 18 states have internal predecessors, (43), 10 states have call successors, (25), 3 states have call predecessors, (25), 2 states have return successors, (24), 8 states have call predecessors, (24), 8 states have call successors, (24) [2024-10-12 18:51:02,379 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-12 18:51:02,379 INFO L93 Difference]: Finished difference Result 549 states and 802 transitions. [2024-10-12 18:51:02,380 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 27 states. [2024-10-12 18:51:02,380 INFO L78 Accepts]: Start accepts. Automaton has has 21 states, 19 states have (on average 2.263157894736842) internal successors, (43), 18 states have internal predecessors, (43), 10 states have call successors, (25), 3 states have call predecessors, (25), 2 states have return successors, (24), 8 states have call predecessors, (24), 8 states have call successors, (24) Word has length 79 [2024-10-12 18:51:02,381 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-12 18:51:02,383 INFO L225 Difference]: With dead ends: 549 [2024-10-12 18:51:02,383 INFO L226 Difference]: Without dead ends: 543 [2024-10-12 18:51:02,386 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 175 GetRequests, 137 SyntacticMatches, 0 SemanticMatches, 38 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 261 ImplicationChecksByTransitivity, 1.2s TimeCoverageRelationStatistics Valid=296, Invalid=1264, Unknown=0, NotChecked=0, Total=1560 [2024-10-12 18:51:02,386 INFO L432 NwaCegarLoop]: 58 mSDtfsCounter, 118 mSDsluCounter, 645 mSDsCounter, 0 mSdLazyCounter, 638 mSolverCounterSat, 99 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.7s Time, 0 mProtectedPredicate, 0 mProtectedAction, 123 SdHoareTripleChecker+Valid, 703 SdHoareTripleChecker+Invalid, 737 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 99 IncrementalHoareTripleChecker+Valid, 638 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.8s IncrementalHoareTripleChecker+Time [2024-10-12 18:51:02,387 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [123 Valid, 703 Invalid, 737 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [99 Valid, 638 Invalid, 0 Unknown, 0 Unchecked, 1.8s Time] [2024-10-12 18:51:02,388 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 543 states. [2024-10-12 18:51:02,483 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 543 to 496. [2024-10-12 18:51:02,484 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 496 states, 310 states have (on average 1.3451612903225807) internal successors, (417), 313 states have internal predecessors, (417), 156 states have call successors, (156), 29 states have call predecessors, (156), 29 states have return successors, (154), 153 states have call predecessors, (154), 154 states have call successors, (154) [2024-10-12 18:51:02,486 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 496 states to 496 states and 727 transitions. [2024-10-12 18:51:02,486 INFO L78 Accepts]: Start accepts. Automaton has 496 states and 727 transitions. Word has length 79 [2024-10-12 18:51:02,487 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-12 18:51:02,487 INFO L471 AbstractCegarLoop]: Abstraction has 496 states and 727 transitions. [2024-10-12 18:51:02,487 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 21 states, 19 states have (on average 2.263157894736842) internal successors, (43), 18 states have internal predecessors, (43), 10 states have call successors, (25), 3 states have call predecessors, (25), 2 states have return successors, (24), 8 states have call predecessors, (24), 8 states have call successors, (24) [2024-10-12 18:51:02,487 INFO L276 IsEmpty]: Start isEmpty. Operand 496 states and 727 transitions. [2024-10-12 18:51:02,488 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 89 [2024-10-12 18:51:02,488 INFO L207 NwaCegarLoop]: Found error trace [2024-10-12 18:51:02,488 INFO L215 NwaCegarLoop]: trace histogram [9, 8, 8, 4, 4, 4, 4, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-12 18:51:02,501 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Ended with exit code 0 [2024-10-12 18:51:02,688 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 13 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable14 [2024-10-12 18:51:02,689 INFO L396 AbstractCegarLoop]: === Iteration 16 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-12 18:51:02,689 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-12 18:51:02,689 INFO L85 PathProgramCache]: Analyzing trace with hash -1270806006, now seen corresponding path program 1 times [2024-10-12 18:51:02,689 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-12 18:51:02,689 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1810975178] [2024-10-12 18:51:02,690 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-12 18:51:02,690 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-12 18:51:02,699 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:51:02,752 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 1 [2024-10-12 18:51:02,753 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:51:02,754 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2024-10-12 18:51:02,754 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:51:02,755 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 12 [2024-10-12 18:51:02,755 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:51:02,756 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 17 [2024-10-12 18:51:02,756 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:51:02,757 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 27 [2024-10-12 18:51:02,757 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:51:02,758 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 32 [2024-10-12 18:51:02,759 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:51:02,759 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 37 [2024-10-12 18:51:02,760 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:51:02,760 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 42 [2024-10-12 18:51:02,761 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:51:02,761 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 54 [2024-10-12 18:51:02,762 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:51:02,763 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 59 [2024-10-12 18:51:02,764 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:51:02,765 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 64 [2024-10-12 18:51:02,766 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:51:02,767 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 69 [2024-10-12 18:51:02,768 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:51:02,769 INFO L134 CoverageAnalysis]: Checked inductivity of 181 backedges. 42 proven. 0 refuted. 0 times theorem prover too weak. 139 trivial. 0 not checked. [2024-10-12 18:51:02,769 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-12 18:51:02,769 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1810975178] [2024-10-12 18:51:02,769 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1810975178] provided 1 perfect and 0 imperfect interpolant sequences [2024-10-12 18:51:02,769 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-10-12 18:51:02,769 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-10-12 18:51:02,770 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [403053274] [2024-10-12 18:51:02,770 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-10-12 18:51:02,770 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-10-12 18:51:02,770 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-12 18:51:02,771 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-10-12 18:51:02,771 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-10-12 18:51:02,771 INFO L87 Difference]: Start difference. First operand 496 states and 727 transitions. Second operand has 5 states, 5 states have (on average 6.2) internal successors, (31), 5 states have internal predecessors, (31), 3 states have call successors, (13), 2 states have call predecessors, (13), 1 states have return successors, (12), 2 states have call predecessors, (12), 2 states have call successors, (12) [2024-10-12 18:51:03,042 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-12 18:51:03,043 INFO L93 Difference]: Finished difference Result 833 states and 1283 transitions. [2024-10-12 18:51:03,043 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2024-10-12 18:51:03,043 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 6.2) internal successors, (31), 5 states have internal predecessors, (31), 3 states have call successors, (13), 2 states have call predecessors, (13), 1 states have return successors, (12), 2 states have call predecessors, (12), 2 states have call successors, (12) Word has length 88 [2024-10-12 18:51:03,044 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-12 18:51:03,048 INFO L225 Difference]: With dead ends: 833 [2024-10-12 18:51:03,052 INFO L226 Difference]: Without dead ends: 575 [2024-10-12 18:51:03,055 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 32 GetRequests, 27 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=15, Invalid=27, Unknown=0, NotChecked=0, Total=42 [2024-10-12 18:51:03,056 INFO L432 NwaCegarLoop]: 52 mSDtfsCounter, 11 mSDsluCounter, 123 mSDsCounter, 0 mSdLazyCounter, 47 mSolverCounterSat, 4 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 16 SdHoareTripleChecker+Valid, 175 SdHoareTripleChecker+Invalid, 51 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 4 IncrementalHoareTripleChecker+Valid, 47 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-10-12 18:51:03,056 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [16 Valid, 175 Invalid, 51 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [4 Valid, 47 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-10-12 18:51:03,057 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 575 states. [2024-10-12 18:51:03,197 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 575 to 480. [2024-10-12 18:51:03,199 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 480 states, 298 states have (on average 1.3187919463087248) internal successors, (393), 301 states have internal predecessors, (393), 152 states have call successors, (152), 29 states have call predecessors, (152), 29 states have return successors, (150), 149 states have call predecessors, (150), 150 states have call successors, (150) [2024-10-12 18:51:03,201 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 480 states to 480 states and 695 transitions. [2024-10-12 18:51:03,203 INFO L78 Accepts]: Start accepts. Automaton has 480 states and 695 transitions. Word has length 88 [2024-10-12 18:51:03,206 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-12 18:51:03,206 INFO L471 AbstractCegarLoop]: Abstraction has 480 states and 695 transitions. [2024-10-12 18:51:03,206 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 6.2) internal successors, (31), 5 states have internal predecessors, (31), 3 states have call successors, (13), 2 states have call predecessors, (13), 1 states have return successors, (12), 2 states have call predecessors, (12), 2 states have call successors, (12) [2024-10-12 18:51:03,207 INFO L276 IsEmpty]: Start isEmpty. Operand 480 states and 695 transitions. [2024-10-12 18:51:03,207 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 97 [2024-10-12 18:51:03,208 INFO L207 NwaCegarLoop]: Found error trace [2024-10-12 18:51:03,208 INFO L215 NwaCegarLoop]: trace histogram [12, 11, 11, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-12 18:51:03,208 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable15 [2024-10-12 18:51:03,208 INFO L396 AbstractCegarLoop]: === Iteration 17 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-12 18:51:03,208 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-12 18:51:03,208 INFO L85 PathProgramCache]: Analyzing trace with hash -1858222944, now seen corresponding path program 1 times [2024-10-12 18:51:03,208 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-12 18:51:03,209 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1744731686] [2024-10-12 18:51:03,209 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-12 18:51:03,209 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-12 18:51:03,237 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-10-12 18:51:03,238 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [812099473] [2024-10-12 18:51:03,238 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-12 18:51:03,239 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-12 18:51:03,239 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-12 18:51:03,240 INFO L229 MonitoredProcess]: Starting monitored process 14 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-10-12 18:51:03,241 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Waiting until timeout for monitored process [2024-10-12 18:51:03,297 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:51:03,301 INFO L255 TraceCheckSpWp]: Trace formula consists of 244 conjuncts, 38 conjuncts are in the unsatisfiable core [2024-10-12 18:51:03,303 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-12 18:51:04,577 INFO L134 CoverageAnalysis]: Checked inductivity of 288 backedges. 51 proven. 32 refuted. 0 times theorem prover too weak. 205 trivial. 0 not checked. [2024-10-12 18:51:04,578 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-12 18:51:04,803 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-12 18:51:04,803 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1744731686] [2024-10-12 18:51:04,803 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-10-12 18:51:04,804 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [812099473] [2024-10-12 18:51:04,804 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [812099473] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-12 18:51:04,804 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-10-12 18:51:04,804 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [16] total 16 [2024-10-12 18:51:04,804 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1527467630] [2024-10-12 18:51:04,805 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-10-12 18:51:04,805 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2024-10-12 18:51:04,805 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-12 18:51:04,806 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2024-10-12 18:51:04,806 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=55, Invalid=287, Unknown=0, NotChecked=0, Total=342 [2024-10-12 18:51:04,810 INFO L87 Difference]: Start difference. First operand 480 states and 695 transitions. Second operand has 16 states, 15 states have (on average 2.1333333333333333) internal successors, (32), 13 states have internal predecessors, (32), 7 states have call successors, (16), 2 states have call predecessors, (16), 3 states have return successors, (15), 6 states have call predecessors, (15), 6 states have call successors, (15) [2024-10-12 18:51:05,752 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-12 18:51:05,752 INFO L93 Difference]: Finished difference Result 493 states and 706 transitions. [2024-10-12 18:51:05,753 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2024-10-12 18:51:05,753 INFO L78 Accepts]: Start accepts. Automaton has has 16 states, 15 states have (on average 2.1333333333333333) internal successors, (32), 13 states have internal predecessors, (32), 7 states have call successors, (16), 2 states have call predecessors, (16), 3 states have return successors, (15), 6 states have call predecessors, (15), 6 states have call successors, (15) Word has length 96 [2024-10-12 18:51:05,753 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-12 18:51:05,759 INFO L225 Difference]: With dead ends: 493 [2024-10-12 18:51:05,760 INFO L226 Difference]: Without dead ends: 491 [2024-10-12 18:51:05,760 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 104 GetRequests, 83 SyntacticMatches, 0 SemanticMatches, 21 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 75 ImplicationChecksByTransitivity, 1.0s TimeCoverageRelationStatistics Valid=84, Invalid=422, Unknown=0, NotChecked=0, Total=506 [2024-10-12 18:51:05,761 INFO L432 NwaCegarLoop]: 44 mSDtfsCounter, 37 mSDsluCounter, 358 mSDsCounter, 0 mSdLazyCounter, 494 mSolverCounterSat, 10 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.6s Time, 0 mProtectedPredicate, 0 mProtectedAction, 49 SdHoareTripleChecker+Valid, 402 SdHoareTripleChecker+Invalid, 504 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 10 IncrementalHoareTripleChecker+Valid, 494 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.7s IncrementalHoareTripleChecker+Time [2024-10-12 18:51:05,761 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [49 Valid, 402 Invalid, 504 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [10 Valid, 494 Invalid, 0 Unknown, 0 Unchecked, 0.7s Time] [2024-10-12 18:51:05,762 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 491 states. [2024-10-12 18:51:05,878 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 491 to 488. [2024-10-12 18:51:05,879 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 488 states, 304 states have (on average 1.3125) internal successors, (399), 307 states have internal predecessors, (399), 152 states have call successors, (152), 31 states have call predecessors, (152), 31 states have return successors, (150), 149 states have call predecessors, (150), 150 states have call successors, (150) [2024-10-12 18:51:05,881 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 488 states to 488 states and 701 transitions. [2024-10-12 18:51:05,882 INFO L78 Accepts]: Start accepts. Automaton has 488 states and 701 transitions. Word has length 96 [2024-10-12 18:51:05,882 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-12 18:51:05,882 INFO L471 AbstractCegarLoop]: Abstraction has 488 states and 701 transitions. [2024-10-12 18:51:05,882 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 16 states, 15 states have (on average 2.1333333333333333) internal successors, (32), 13 states have internal predecessors, (32), 7 states have call successors, (16), 2 states have call predecessors, (16), 3 states have return successors, (15), 6 states have call predecessors, (15), 6 states have call successors, (15) [2024-10-12 18:51:05,882 INFO L276 IsEmpty]: Start isEmpty. Operand 488 states and 701 transitions. [2024-10-12 18:51:05,883 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 106 [2024-10-12 18:51:05,883 INFO L207 NwaCegarLoop]: Found error trace [2024-10-12 18:51:05,883 INFO L215 NwaCegarLoop]: trace histogram [13, 12, 12, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-12 18:51:05,904 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Ended with exit code 0 [2024-10-12 18:51:06,087 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 14 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable16 [2024-10-12 18:51:06,088 INFO L396 AbstractCegarLoop]: === Iteration 18 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-12 18:51:06,088 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-12 18:51:06,088 INFO L85 PathProgramCache]: Analyzing trace with hash -615201371, now seen corresponding path program 1 times [2024-10-12 18:51:06,088 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-12 18:51:06,088 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1053852476] [2024-10-12 18:51:06,089 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-12 18:51:06,089 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-12 18:51:06,107 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-10-12 18:51:06,108 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [709301908] [2024-10-12 18:51:06,109 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-12 18:51:06,109 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-12 18:51:06,109 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-12 18:51:06,114 INFO L229 MonitoredProcess]: Starting monitored process 15 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-10-12 18:51:06,117 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Waiting until timeout for monitored process [2024-10-12 18:51:06,177 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-12 18:51:06,177 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-10-12 18:51:06,200 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-12 18:51:06,255 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-10-12 18:51:06,256 INFO L325 BasicCegarLoop]: Counterexample is feasible [2024-10-12 18:51:06,256 INFO L782 garLoopResultBuilder]: Registering result UNSAFE for location __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION (0 of 1 remaining) [2024-10-12 18:51:06,273 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Ended with exit code 0 [2024-10-12 18:51:06,458 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable17,15 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-12 18:51:06,463 INFO L407 BasicCegarLoop]: Path program histogram: [3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-12 18:51:06,506 INFO L165 ceAbstractionStarter]: Computing trace abstraction results [2024-10-12 18:51:06,508 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 12.10 06:51:06 BoogieIcfgContainer [2024-10-12 18:51:06,508 INFO L131 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2024-10-12 18:51:06,509 INFO L112 PluginConnector]: ------------------------Witness Printer---------------------------- [2024-10-12 18:51:06,509 INFO L270 PluginConnector]: Initializing Witness Printer... [2024-10-12 18:51:06,509 INFO L274 PluginConnector]: Witness Printer initialized [2024-10-12 18:51:06,510 INFO L184 PluginConnector]: Executing the observer RCFGCatcher from plugin Witness Printer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 12.10 06:50:28" (3/4) ... [2024-10-12 18:51:06,510 INFO L133 WitnessPrinter]: Generating witness for reachability counterexample [2024-10-12 18:51:06,556 INFO L149 WitnessManager]: Wrote witness to /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/witness.graphml [2024-10-12 18:51:06,556 INFO L131 PluginConnector]: ------------------------ END Witness Printer---------------------------- [2024-10-12 18:51:06,557 INFO L158 Benchmark]: Toolchain (without parser) took 38760.26ms. Allocated memory was 127.9MB in the beginning and 318.8MB in the end (delta: 190.8MB). Free memory was 57.2MB in the beginning and 153.7MB in the end (delta: -96.5MB). Peak memory consumption was 96.4MB. Max. memory is 16.1GB. [2024-10-12 18:51:06,557 INFO L158 Benchmark]: CDTParser took 0.12ms. Allocated memory is still 127.9MB. Free memory is still 87.0MB. There was no memory consumed. Max. memory is 16.1GB. [2024-10-12 18:51:06,557 INFO L158 Benchmark]: CACSL2BoogieTranslator took 233.59ms. Allocated memory was 127.9MB in the beginning and 197.1MB in the end (delta: 69.2MB). Free memory was 57.2MB in the beginning and 163.6MB in the end (delta: -106.4MB). Peak memory consumption was 14.2MB. Max. memory is 16.1GB. [2024-10-12 18:51:06,557 INFO L158 Benchmark]: Boogie Procedure Inliner took 28.41ms. Allocated memory is still 197.1MB. Free memory was 163.6MB in the beginning and 162.5MB in the end (delta: 1.1MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. [2024-10-12 18:51:06,558 INFO L158 Benchmark]: Boogie Preprocessor took 42.27ms. Allocated memory is still 197.1MB. Free memory was 162.5MB in the beginning and 160.4MB in the end (delta: 2.1MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. [2024-10-12 18:51:06,558 INFO L158 Benchmark]: RCFGBuilder took 292.52ms. Allocated memory is still 197.1MB. Free memory was 160.4MB in the beginning and 145.8MB in the end (delta: 14.7MB). Peak memory consumption was 14.7MB. Max. memory is 16.1GB. [2024-10-12 18:51:06,558 INFO L158 Benchmark]: TraceAbstraction took 38111.04ms. Allocated memory was 197.1MB in the beginning and 318.8MB in the end (delta: 121.6MB). Free memory was 144.7MB in the beginning and 158.9MB in the end (delta: -14.2MB). Peak memory consumption was 107.4MB. Max. memory is 16.1GB. [2024-10-12 18:51:06,558 INFO L158 Benchmark]: Witness Printer took 47.42ms. Allocated memory is still 318.8MB. Free memory was 158.9MB in the beginning and 153.7MB in the end (delta: 5.2MB). Peak memory consumption was 6.3MB. Max. memory is 16.1GB. [2024-10-12 18:51:06,559 INFO L338 ainManager$Toolchain]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * CDTParser took 0.12ms. Allocated memory is still 127.9MB. Free memory is still 87.0MB. There was no memory consumed. Max. memory is 16.1GB. * CACSL2BoogieTranslator took 233.59ms. Allocated memory was 127.9MB in the beginning and 197.1MB in the end (delta: 69.2MB). Free memory was 57.2MB in the beginning and 163.6MB in the end (delta: -106.4MB). Peak memory consumption was 14.2MB. Max. memory is 16.1GB. * Boogie Procedure Inliner took 28.41ms. Allocated memory is still 197.1MB. Free memory was 163.6MB in the beginning and 162.5MB in the end (delta: 1.1MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. * Boogie Preprocessor took 42.27ms. Allocated memory is still 197.1MB. Free memory was 162.5MB in the beginning and 160.4MB in the end (delta: 2.1MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. * RCFGBuilder took 292.52ms. Allocated memory is still 197.1MB. Free memory was 160.4MB in the beginning and 145.8MB in the end (delta: 14.7MB). Peak memory consumption was 14.7MB. Max. memory is 16.1GB. * TraceAbstraction took 38111.04ms. Allocated memory was 197.1MB in the beginning and 318.8MB in the end (delta: 121.6MB). Free memory was 144.7MB in the beginning and 158.9MB in the end (delta: -14.2MB). Peak memory consumption was 107.4MB. Max. memory is 16.1GB. * Witness Printer took 47.42ms. Allocated memory is still 318.8MB. Free memory was 158.9MB in the beginning and 153.7MB in the end (delta: 5.2MB). Peak memory consumption was 6.3MB. 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; [L20] int x, y; [L21] long long a, b, p, q, r, s, c, k, xy, yy; [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=3, y=4] [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=3, y=4] [L27] a = x [L28] b = y [L29] p = 1 [L30] q = 0 [L31] r = 0 [L32] s = 1 [L33] c = 0 [L34] k = 0 [L35] xy = (long long) x * y [L36] yy = (long long) y * y VAL [a=3, b=4, counter=0, p=1, q=0, r=0, s=1, x=3, xy=12, y=4, yy=16] [L37] CALL assume_abort_if_not(xy < 2147483647) VAL [\old(cond)=1, counter=0] [L8] COND FALSE !(!cond) VAL [\old(cond)=1, counter=0] [L37] RET assume_abort_if_not(xy < 2147483647) VAL [a=3, b=4, counter=0, p=1, q=0, r=0, s=1, x=3, xy=12, y=4, yy=16] [L38] CALL assume_abort_if_not(yy < 2147483647) VAL [\old(cond)=1, counter=0] [L8] COND FALSE !(!cond) VAL [\old(cond)=1, counter=0] [L38] RET assume_abort_if_not(yy < 2147483647) VAL [a=3, b=4, counter=0, p=1, q=0, r=0, s=1, x=3, xy=12, y=4, yy=16] [L40] EXPR counter++ VAL [a=3, b=4, counter=1, p=1, q=0, r=0, s=1, x=3, xy=12, y=4, yy=16] [L40] COND TRUE counter++<5 [L41] COND FALSE !(!(b != 0)) [L43] c = a [L44] k = 0 VAL [a=3, b=4, c=3, counter=1, k=0, p=1, q=0, r=0, s=1, x=3, xy=12, y=4, yy=16] [L46] EXPR counter++ VAL [a=3, b=4, c=3, counter=2, k=0, p=1, q=0, r=0, s=1, x=3, xy=12, y=4, yy=16] [L46] COND TRUE counter++<5 [L47] CALL __VERIFIER_assert(a == k * b + c) VAL [\old(cond)=1, counter=2] [L11] COND FALSE !(!(cond)) VAL [\old(cond)=1, counter=2] [L47] RET __VERIFIER_assert(a == k * b + c) VAL [a=3, b=4, c=3, counter=2, k=0, p=1, q=0, r=0, s=1, x=3, xy=12, y=4, yy=16] [L48] CALL __VERIFIER_assert(a == y*r + x*p) VAL [\old(cond)=1, counter=2] [L11] COND FALSE !(!(cond)) VAL [\old(cond)=1, counter=2] [L48] RET __VERIFIER_assert(a == y*r + x*p) VAL [a=3, b=4, c=3, counter=2, k=0, p=1, q=0, r=0, s=1, x=3, xy=12, y=4, yy=16] [L49] CALL __VERIFIER_assert(b == x * q + y * s) VAL [\old(cond)=1, counter=2] [L11] COND FALSE !(!(cond)) VAL [\old(cond)=1, counter=2] [L49] RET __VERIFIER_assert(b == x * q + y * s) VAL [a=3, b=4, c=3, counter=2, k=0, p=1, q=0, r=0, s=1, x=3, xy=12, y=4, yy=16] [L50] CALL __VERIFIER_assert(q*xy + s*yy - q*x - b*y - s*y + b == 0) VAL [\old(cond)=1, counter=2] [L11] COND FALSE !(!(cond)) VAL [\old(cond)=1, counter=2] [L50] RET __VERIFIER_assert(q*xy + s*yy - q*x - b*y - s*y + b == 0) VAL [a=3, b=4, c=3, counter=2, k=0, p=1, q=0, r=0, s=1, x=3, xy=12, y=4, yy=16] [L51] COND TRUE !(c >= b) VAL [a=3, b=4, c=3, counter=2, k=0, p=1, q=0, r=0, s=1, x=3, xy=12, y=4, yy=16] [L57] a = b [L58] b = c [L60] long long temp; [L61] temp = p [L62] p = q [L63] q = temp - q * k [L64] temp = r [L65] r = s [L66] s = temp - s * k [L40] EXPR counter++ VAL [a=4, b=3, counter=3, p=0, q=1, r=1, s=0, x=3, xy=12, y=4, yy=16] [L40] COND TRUE counter++<5 [L41] COND FALSE !(!(b != 0)) [L43] c = a [L44] k = 0 VAL [a=4, b=3, c=4, counter=3, k=0, p=0, q=1, r=1, s=0, x=3, xy=12, y=4, yy=16] [L46] EXPR counter++ VAL [a=4, b=3, c=4, counter=4, k=0, p=0, q=1, r=1, s=0, x=3, xy=12, y=4, yy=16] [L46] COND TRUE counter++<5 [L47] CALL __VERIFIER_assert(a == k * b + c) VAL [\old(cond)=1, counter=4] [L11] COND FALSE !(!(cond)) VAL [\old(cond)=1, counter=4] [L47] RET __VERIFIER_assert(a == k * b + c) VAL [a=4, b=3, c=4, counter=4, k=0, p=0, q=1, r=1, s=0, x=3, xy=12, y=4, yy=16] [L48] CALL __VERIFIER_assert(a == y*r + x*p) VAL [\old(cond)=1, counter=4] [L11] COND FALSE !(!(cond)) VAL [\old(cond)=1, counter=4] [L48] RET __VERIFIER_assert(a == y*r + x*p) VAL [a=4, b=3, c=4, counter=4, k=0, p=0, q=1, r=1, s=0, x=3, xy=12, y=4, yy=16] [L49] CALL __VERIFIER_assert(b == x * q + y * s) VAL [\old(cond)=1, counter=4] [L11] COND FALSE !(!(cond)) VAL [\old(cond)=1, counter=4] [L49] RET __VERIFIER_assert(b == x * q + y * s) VAL [a=4, b=3, c=4, counter=4, k=0, p=0, q=1, r=1, s=0, x=3, xy=12, y=4, yy=16] [L50] CALL __VERIFIER_assert(q*xy + s*yy - q*x - b*y - s*y + b == 0) VAL [\old(cond)=1, counter=4] [L11] COND FALSE !(!(cond)) VAL [\old(cond)=1, counter=4] [L50] RET __VERIFIER_assert(q*xy + s*yy - q*x - b*y - s*y + b == 0) VAL [a=4, b=3, c=4, counter=4, k=0, p=0, q=1, r=1, s=0, x=3, xy=12, y=4, yy=16] [L51] COND FALSE !(!(c >= b)) [L53] c = c - b [L54] k = k + 1 VAL [a=4, b=3, c=1, counter=4, k=1, p=0, q=1, r=1, s=0, x=3, xy=12, y=4, yy=16] [L46] EXPR counter++ VAL [a=4, b=3, c=1, counter=5, k=1, p=0, q=1, r=1, s=0, x=3, xy=12, y=4, yy=16] [L46] COND TRUE counter++<5 [L47] CALL __VERIFIER_assert(a == k * b + c) VAL [\old(cond)=1, counter=5] [L11] COND FALSE !(!(cond)) VAL [\old(cond)=1, counter=5] [L47] RET __VERIFIER_assert(a == k * b + c) VAL [a=4, b=3, c=1, counter=5, k=1, p=0, q=1, r=1, s=0, x=3, xy=12, y=4, yy=16] [L48] CALL __VERIFIER_assert(a == y*r + x*p) VAL [\old(cond)=1, counter=5] [L11] COND FALSE !(!(cond)) VAL [\old(cond)=1, counter=5] [L48] RET __VERIFIER_assert(a == y*r + x*p) VAL [a=4, b=3, c=1, counter=5, k=1, p=0, q=1, r=1, s=0, x=3, xy=12, y=4, yy=16] [L49] CALL __VERIFIER_assert(b == x * q + y * s) VAL [\old(cond)=1, counter=5] [L11] COND FALSE !(!(cond)) VAL [\old(cond)=1, counter=5] [L49] RET __VERIFIER_assert(b == x * q + y * s) VAL [a=4, b=3, c=1, counter=5, k=1, p=0, q=1, r=1, s=0, x=3, xy=12, y=4, yy=16] [L50] CALL __VERIFIER_assert(q*xy + s*yy - q*x - b*y - s*y + b == 0) VAL [\old(cond)=1, counter=5] [L11] COND FALSE !(!(cond)) VAL [\old(cond)=1, counter=5] [L50] RET __VERIFIER_assert(q*xy + s*yy - q*x - b*y - s*y + b == 0) VAL [a=4, b=3, c=1, counter=5, k=1, p=0, q=1, r=1, s=0, x=3, xy=12, y=4, yy=16] [L51] COND TRUE !(c >= b) VAL [a=4, b=3, c=1, counter=5, k=1, p=0, q=1, r=1, s=0, x=3, xy=12, y=4, yy=16] [L57] a = b [L58] b = c [L60] long long temp; [L61] temp = p [L62] p = q [L63] q = temp - q * k [L64] temp = r [L65] r = s [L66] s = temp - s * k [L40] EXPR counter++ VAL [a=3, b=1, counter=6, p=1, q=-1, r=0, s=1, x=3, xy=12, y=4, yy=16] [L40] COND FALSE !(counter++<5) [L70] CALL __VERIFIER_assert(q*x + s*y == 0) VAL [\old(cond)=0, counter=6] [L11] COND TRUE !(cond) VAL [\old(cond)=0, counter=6] [L13] reach_error() VAL [\old(cond)=0, counter=6] - StatisticsResult: Ultimate Automizer benchmark data CFG has 3 procedures, 31 locations, 1 error locations. Started 1 CEGAR loops. OverallTime: 38.0s, OverallIterations: 18, TraceHistogramMax: 13, PathProgramHistogramMax: 3, EmptinessCheckTime: 0.0s, AutomataDifference: 7.2s, DeadEndRemovalTime: 0.0s, HoareAnnotationTime: 0.0s, InitialAbstractionConstructionTime: 0.0s, HoareTripleCheckerStatistics: 0 mSolverCounterUnknown, 649 SdHoareTripleChecker+Valid, 4.2s IncrementalHoareTripleChecker+Time, 0 mSdLazyCounter, 581 mSDsluCounter, 3739 SdHoareTripleChecker+Invalid, 3.8s Time, 0 mProtectedAction, 0 SdHoareTripleChecker+Unchecked, 0 IncrementalHoareTripleChecker+Unchecked, 3069 mSDsCounter, 292 IncrementalHoareTripleChecker+Valid, 0 mProtectedPredicate, 2428 IncrementalHoareTripleChecker+Invalid, 2720 SdHoareTripleChecker+Unknown, 0 mSolverCounterNotChecked, 292 mSolverCounterUnsat, 670 mSDtfsCounter, 2428 mSolverCounterSat, 0.1s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Unknown, PredicateUnifierStatistics: 0 DeclaredPredicates, 1436 GetRequests, 1220 SyntacticMatches, 12 SemanticMatches, 204 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 753 ImplicationChecksByTransitivity, 7.0s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=496occurred in iteration=15, InterpolantAutomatonStates: 166, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 0.0s DumpTime, AutomataMinimizationStatistics: 0.6s AutomataMinimizationTime, 17 MinimizatonAttempts, 244 StatesRemovedByMinimization, 14 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TRACE_CHECK: 0.1s SsaConstructionTime, 0.5s SatisfiabilityAnalysisTime, 26.0s InterpolantComputationTime, 1871 NumberOfCodeBlocks, 1851 NumberOfCodeBlocksAsserted, 35 NumberOfCheckSat, 1555 ConstructedInterpolants, 0 QuantifiedInterpolants, 6687 SizeOfPredicates, 28 NumberOfNonLiveVariables, 2081 ConjunctsInSsa, 271 ConjunctsInUnsatCore, 29 InterpolantComputations, 9 PerfectInterpolantSequences, 1988/2186 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-10-12 18:51:06,599 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