/usr/lib/jvm/java-1.11.0-openjdk-amd64/bin/java -Xmx16000000000 -Xss4m -jar ./plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata ./data -tc ../../../trunk/examples/toolchains/AutomizerCInline.xml -s ../../../trunk/examples/settings/automizer/concurrent/svcomp-Reach-32bit-Automizer_Default-noMmResRef-PN-NoLbe.epf --traceabstraction.compute.hoare.annotation.of.negated.interpolant.automaton,.abstraction.and.cfg true --cacsl2boogietranslator.check.unreachability.of.reach_error.function false --cacsl2boogietranslator.pointer.base.address.is.valid.at.dereference ASSERTandASSUME --cacsl2boogietranslator.pointer.to.allocated.memory.at.dereference ASSERTandASSUME --cacsl2boogietranslator.check.array.bounds.for.arrays.that.are.off.heap ASSERTandASSUME --cacsl2boogietranslator.check.if.freed.pointer.was.valid true --cacsl2boogietranslator.adapt.memory.model.on.pointer.casts.if.necessary true -i ../../../trunk/examples/svcomp/goblint-regression/28-race_reach_19-callback_racing.i -------------------------------------------------------------------------------- This is Ultimate 0.2.4-wip.dk.empire-owicki-175f719-m [2023-11-30 05:14:36,280 INFO L188 SettingsManager]: Resetting all preferences to default values... [2023-11-30 05:14:36,338 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/automizer/concurrent/svcomp-Reach-32bit-Automizer_Default-noMmResRef-PN-NoLbe.epf [2023-11-30 05:14:36,367 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2023-11-30 05:14:36,368 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2023-11-30 05:14:36,368 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2023-11-30 05:14:36,369 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2023-11-30 05:14:36,369 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2023-11-30 05:14:36,369 INFO L153 SettingsManager]: * Use SBE=true [2023-11-30 05:14:36,369 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2023-11-30 05:14:36,370 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2023-11-30 05:14:36,370 INFO L153 SettingsManager]: * sizeof long=4 [2023-11-30 05:14:36,370 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2023-11-30 05:14:36,370 INFO L153 SettingsManager]: * sizeof POINTER=4 [2023-11-30 05:14:36,371 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2023-11-30 05:14:36,371 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2023-11-30 05:14:36,371 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2023-11-30 05:14:36,371 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2023-11-30 05:14:36,372 INFO L153 SettingsManager]: * sizeof long double=12 [2023-11-30 05:14:36,372 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2023-11-30 05:14:36,372 INFO L153 SettingsManager]: * Use constant arrays=true [2023-11-30 05:14:36,372 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2023-11-30 05:14:36,373 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2023-11-30 05:14:36,373 INFO L153 SettingsManager]: * To the following directory=./dump/ [2023-11-30 05:14:36,373 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2023-11-30 05:14:36,373 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2023-11-30 05:14:36,374 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2023-11-30 05:14:36,374 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2023-11-30 05:14:36,374 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2023-11-30 05:14:36,374 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2023-11-30 05:14:36,375 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2023-11-30 05:14:36,375 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2023-11-30 05:14:36,375 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2023-11-30 05:14:36,375 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode 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.traceabstraction: Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG -> true Applying setting for plugin de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator: Check unreachability of reach_error function -> false Applying setting for plugin de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator: Pointer base address is valid at dereference -> ASSERTandASSUME Applying setting for plugin de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator: Pointer to allocated memory at dereference -> ASSERTandASSUME Applying setting for plugin de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator: Check array bounds for arrays that are off heap -> ASSERTandASSUME Applying setting for plugin de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator: Check if freed pointer was valid -> true Applying setting for plugin de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator: Adapt memory model on pointer casts if necessary -> true [2023-11-30 05:14:36,567 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2023-11-30 05:14:36,583 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2023-11-30 05:14:36,585 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2023-11-30 05:14:36,586 INFO L270 PluginConnector]: Initializing CDTParser... [2023-11-30 05:14:36,586 INFO L274 PluginConnector]: CDTParser initialized [2023-11-30 05:14:36,587 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/svcomp/goblint-regression/28-race_reach_19-callback_racing.i [2023-11-30 05:14:37,508 INFO L533 CDTParser]: Created temporary CDT project at NULL [2023-11-30 05:14:37,691 INFO L384 CDTParser]: Found 1 translation units. [2023-11-30 05:14:37,691 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/trunk/examples/svcomp/goblint-regression/28-race_reach_19-callback_racing.i [2023-11-30 05:14:37,699 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/87e05b989/34a49b2cee1b4d22a529ef55b3e53261/FLAGa20b29fc4 [2023-11-30 05:14:37,707 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/87e05b989/34a49b2cee1b4d22a529ef55b3e53261 [2023-11-30 05:14:37,709 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2023-11-30 05:14:37,710 INFO L133 ToolchainWalker]: Walking toolchain with 5 elements. [2023-11-30 05:14:37,710 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2023-11-30 05:14:37,710 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2023-11-30 05:14:37,713 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2023-11-30 05:14:37,714 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 30.11 05:14:37" (1/1) ... [2023-11-30 05:14:37,714 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@58e6301f and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 30.11 05:14:37, skipping insertion in model container [2023-11-30 05:14:37,714 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 30.11 05:14:37" (1/1) ... [2023-11-30 05:14:37,748 INFO L177 MainTranslator]: Built tables and reachable declarations [2023-11-30 05:14:37,983 INFO L209 PostProcessor]: Analyzing one entry point: main [2023-11-30 05:14:37,993 INFO L202 MainTranslator]: Completed pre-run [2023-11-30 05:14:38,037 INFO L209 PostProcessor]: Analyzing one entry point: main [2023-11-30 05:14:38,058 WARN L675 CHandler]: The function callback is called, but not defined or handled by StandardFunctionHandler. [2023-11-30 05:14:38,062 INFO L206 MainTranslator]: Completed translation [2023-11-30 05:14:38,063 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 30.11 05:14:38 WrapperNode [2023-11-30 05:14:38,063 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2023-11-30 05:14:38,064 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2023-11-30 05:14:38,064 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2023-11-30 05:14:38,064 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2023-11-30 05:14:38,068 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 30.11 05:14:38" (1/1) ... [2023-11-30 05:14:38,077 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 30.11 05:14:38" (1/1) ... [2023-11-30 05:14:38,093 INFO L138 Inliner]: procedures = 174, calls = 45, calls flagged for inlining = 7, calls inlined = 7, statements flattened = 154 [2023-11-30 05:14:38,094 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2023-11-30 05:14:38,094 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2023-11-30 05:14:38,094 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2023-11-30 05:14:38,094 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2023-11-30 05:14:38,105 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 30.11 05:14:38" (1/1) ... [2023-11-30 05:14:38,106 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 30.11 05:14:38" (1/1) ... [2023-11-30 05:14:38,109 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 30.11 05:14:38" (1/1) ... [2023-11-30 05:14:38,109 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 30.11 05:14:38" (1/1) ... [2023-11-30 05:14:38,113 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 30.11 05:14:38" (1/1) ... [2023-11-30 05:14:38,116 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 30.11 05:14:38" (1/1) ... [2023-11-30 05:14:38,117 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 30.11 05:14:38" (1/1) ... [2023-11-30 05:14:38,117 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 30.11 05:14:38" (1/1) ... [2023-11-30 05:14:38,119 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2023-11-30 05:14:38,120 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2023-11-30 05:14:38,120 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2023-11-30 05:14:38,148 INFO L274 PluginConnector]: RCFGBuilder initialized [2023-11-30 05:14:38,149 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 30.11 05:14:38" (1/1) ... [2023-11-30 05:14:38,152 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2023-11-30 05:14:38,172 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-11-30 05:14:38,183 INFO L229 MonitoredProcess]: Starting monitored process 1 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) [2023-11-30 05:14:38,185 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Waiting until timeout for monitored process [2023-11-30 05:14:38,215 INFO L130 BoogieDeclarations]: Found specification of procedure read~int [2023-11-30 05:14:38,215 INFO L130 BoogieDeclarations]: Found specification of procedure write~int [2023-11-30 05:14:38,216 INFO L130 BoogieDeclarations]: Found specification of procedure #PthreadsMutexLock [2023-11-30 05:14:38,216 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2023-11-30 05:14:38,216 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnStack [2023-11-30 05:14:38,216 INFO L130 BoogieDeclarations]: Found specification of procedure t_fun [2023-11-30 05:14:38,216 INFO L138 BoogieDeclarations]: Found implementation of procedure t_fun [2023-11-30 05:14:38,216 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2023-11-30 05:14:38,216 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2023-11-30 05:14:38,216 INFO L130 BoogieDeclarations]: Found specification of procedure #PthreadsMutexUnlock [2023-11-30 05:14:38,216 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2023-11-30 05:14:38,216 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2023-11-30 05:14:38,217 WARN L213 CfgBuilder]: User set CodeBlockSize to SequenceOfStatements but program contains fork statements. Overwriting the user preferences and setting CodeBlockSize to OneNontrivialStatement [2023-11-30 05:14:38,313 INFO L241 CfgBuilder]: Building ICFG [2023-11-30 05:14:38,314 INFO L267 CfgBuilder]: Building CFG for each procedure with an implementation [2023-11-30 05:14:38,470 INFO L282 CfgBuilder]: Performing block encoding [2023-11-30 05:14:38,491 INFO L304 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2023-11-30 05:14:38,491 INFO L309 CfgBuilder]: Removed 11 assume(true) statements. [2023-11-30 05:14:38,492 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 30.11 05:14:38 BoogieIcfgContainer [2023-11-30 05:14:38,492 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2023-11-30 05:14:38,493 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2023-11-30 05:14:38,493 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2023-11-30 05:14:38,495 INFO L274 PluginConnector]: TraceAbstraction initialized [2023-11-30 05:14:38,495 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 30.11 05:14:37" (1/3) ... [2023-11-30 05:14:38,496 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@22acd59c and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 30.11 05:14:38, skipping insertion in model container [2023-11-30 05:14:38,496 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 30.11 05:14:38" (2/3) ... [2023-11-30 05:14:38,496 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@22acd59c and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 30.11 05:14:38, skipping insertion in model container [2023-11-30 05:14:38,496 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 30.11 05:14:38" (3/3) ... [2023-11-30 05:14:38,497 INFO L112 eAbstractionObserver]: Analyzing ICFG 28-race_reach_19-callback_racing.i [2023-11-30 05:14:38,508 INFO L197 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2023-11-30 05:14:38,508 INFO L156 ceAbstractionStarter]: Applying trace abstraction to program that has 4 error locations. [2023-11-30 05:14:38,508 INFO L508 ceAbstractionStarter]: Constructing petrified ICFG for 1 thread instances. [2023-11-30 05:14:38,565 INFO L144 ThreadInstanceAdder]: Constructed 1 joinOtherThreadTransitions. [2023-11-30 05:14:38,591 INFO L73 FinitePrefix]: Start finitePrefix. Operand has 145 places, 158 transitions, 323 flow [2023-11-30 05:14:38,637 INFO L124 PetriNetUnfolderBase]: 27/244 cut-off events. [2023-11-30 05:14:38,637 INFO L125 PetriNetUnfolderBase]: For 1/1 co-relation queries the response was YES. [2023-11-30 05:14:38,642 INFO L83 FinitePrefix]: Finished finitePrefix Result has 249 conditions, 244 events. 27/244 cut-off events. For 1/1 co-relation queries the response was YES. Maximal size of possible extension queue 10. Compared 741 event pairs, 0 based on Foata normal form. 0/206 useless extension candidates. Maximal degree in co-relation 119. Up to 6 conditions per place. [2023-11-30 05:14:38,643 INFO L82 GeneralOperation]: Start removeDead. Operand has 145 places, 158 transitions, 323 flow [2023-11-30 05:14:38,646 INFO L88 GeneralOperation]: Finished RemoveDead, result has has 145 places, 158 transitions, 323 flow [2023-11-30 05:14:38,651 INFO L361 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2023-11-30 05:14:38,655 INFO L362 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, mHoare=true, 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;@439001fb, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2023-11-30 05:14:38,655 INFO L363 AbstractCegarLoop]: Starting to check reachability of 5 error locations. [2023-11-30 05:14:38,661 INFO L185 PetriNetUnfolderBase]: Found word, exiting Unfolder. [2023-11-30 05:14:38,661 INFO L124 PetriNetUnfolderBase]: 1/40 cut-off events. [2023-11-30 05:14:38,661 INFO L125 PetriNetUnfolderBase]: For 0/0 co-relation queries the response was YES. [2023-11-30 05:14:38,661 INFO L224 CegarLoopForPetriNet]: Found error trace [2023-11-30 05:14:38,661 INFO L232 CegarLoopForPetriNet]: trace histogram [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, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-30 05:14:38,662 INFO L425 AbstractCegarLoop]: === Iteration 1 === Targeting ULTIMATE.startErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE === [ULTIMATE.startErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr2REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 2 more)] === [2023-11-30 05:14:38,665 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-30 05:14:38,665 INFO L85 PathProgramCache]: Analyzing trace with hash 1661380366, now seen corresponding path program 1 times [2023-11-30 05:14:38,670 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-11-30 05:14:38,670 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [535672694] [2023-11-30 05:14:38,670 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-30 05:14:38,671 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-30 05:14:38,738 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-30 05:14:38,920 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-11-30 05:14:38,920 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-11-30 05:14:38,921 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [535672694] [2023-11-30 05:14:38,921 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [535672694] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-30 05:14:38,921 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-11-30 05:14:38,922 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2023-11-30 05:14:38,922 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [437917497] [2023-11-30 05:14:38,925 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-30 05:14:38,930 INFO L576 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2023-11-30 05:14:38,933 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-11-30 05:14:38,953 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2023-11-30 05:14:38,954 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2023-11-30 05:14:38,958 INFO L497 CegarLoopForPetriNet]: Number of universal loopers: 115 out of 158 [2023-11-30 05:14:38,961 INFO L103 encePairwiseOnDemand]: Start differencePairwiseOnDemand. First operand has 145 places, 158 transitions, 323 flow. Second operand has 3 states, 3 states have (on average 118.0) internal successors, (354), 3 states have internal predecessors, (354), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-11-30 05:14:38,962 INFO L112 encePairwiseOnDemand]: Universal subtrahend loopers provided by user. [2023-11-30 05:14:38,962 INFO L113 encePairwiseOnDemand]: Number of universal subtrahend loopers: 115 of 158 [2023-11-30 05:14:38,962 INFO L73 FinitePrefix]: Start finitePrefix. Operand will be constructed on-demand [2023-11-30 05:14:39,088 INFO L124 PetriNetUnfolderBase]: 57/487 cut-off events. [2023-11-30 05:14:39,088 INFO L125 PetriNetUnfolderBase]: For 3/3 co-relation queries the response was YES. [2023-11-30 05:14:39,092 INFO L83 FinitePrefix]: Finished finitePrefix Result has 637 conditions, 487 events. 57/487 cut-off events. For 3/3 co-relation queries the response was YES. Maximal size of possible extension queue 23. Compared 2511 event pairs, 40 based on Foata normal form. 75/510 useless extension candidates. Maximal degree in co-relation 494. Up to 107 conditions per place. [2023-11-30 05:14:39,094 INFO L140 encePairwiseOnDemand]: 141/158 looper letters, 23 selfloop transitions, 1 changer transitions 12/144 dead transitions. [2023-11-30 05:14:39,094 INFO L145 encePairwiseOnDemand]: Finished differencePairwiseOnDemand. Result has 142 places, 144 transitions, 357 flow [2023-11-30 05:14:39,095 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2023-11-30 05:14:39,097 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 3 states. [2023-11-30 05:14:39,103 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 3 states to 3 states and 395 transitions. [2023-11-30 05:14:39,104 INFO L542 CegarLoopForPetriNet]: DFA transition density 0.8333333333333334 [2023-11-30 05:14:39,105 INFO L72 ComplementDD]: Start complementDD. Operand 3 states and 395 transitions. [2023-11-30 05:14:39,105 INFO L73 IsDeterministic]: Start isDeterministic. Operand 3 states and 395 transitions. [2023-11-30 05:14:39,106 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2023-11-30 05:14:39,107 INFO L117 ReachableStatesCopy]: Start reachableStatesCopy. Operand 3 states and 395 transitions. [2023-11-30 05:14:39,110 INFO L343 DoubleDeckerVisitor]: Before removal of dead ends has 4 states, 3 states have (on average 131.66666666666666) internal successors, (395), 3 states have internal predecessors, (395), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-11-30 05:14:39,115 INFO L131 ReachableStatesCopy]: Finished reachableStatesCopy Result has 4 states, 4 states have (on average 158.0) internal successors, (632), 4 states have internal predecessors, (632), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-11-30 05:14:39,115 INFO L81 ComplementDD]: Finished complementDD. Result has 4 states, 4 states have (on average 158.0) internal successors, (632), 4 states have internal predecessors, (632), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-11-30 05:14:39,117 INFO L307 CegarLoopForPetriNet]: 145 programPoint places, -3 predicate places. [2023-11-30 05:14:39,118 INFO L500 AbstractCegarLoop]: Abstraction has has 142 places, 144 transitions, 357 flow [2023-11-30 05:14:39,118 INFO L501 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 118.0) internal successors, (354), 3 states have internal predecessors, (354), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-11-30 05:14:39,118 INFO L224 CegarLoopForPetriNet]: Found error trace [2023-11-30 05:14:39,118 INFO L232 CegarLoopForPetriNet]: trace histogram [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, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-30 05:14:39,118 WARN L482 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2023-11-30 05:14:39,118 INFO L425 AbstractCegarLoop]: === Iteration 2 === Targeting ULTIMATE.startErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE === [ULTIMATE.startErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr2REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 2 more)] === [2023-11-30 05:14:39,119 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-30 05:14:39,119 INFO L85 PathProgramCache]: Analyzing trace with hash 1661380367, now seen corresponding path program 1 times [2023-11-30 05:14:39,119 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-11-30 05:14:39,119 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1897122068] [2023-11-30 05:14:39,119 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-30 05:14:39,119 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-30 05:14:39,134 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-30 05:14:39,270 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-11-30 05:14:39,270 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-11-30 05:14:39,271 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1897122068] [2023-11-30 05:14:39,271 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1897122068] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-30 05:14:39,271 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-11-30 05:14:39,271 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2023-11-30 05:14:39,272 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2111553067] [2023-11-30 05:14:39,272 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-30 05:14:39,273 INFO L576 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2023-11-30 05:14:39,274 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-11-30 05:14:39,274 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2023-11-30 05:14:39,274 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=6, Invalid=6, Unknown=0, NotChecked=0, Total=12 [2023-11-30 05:14:39,276 INFO L497 CegarLoopForPetriNet]: Number of universal loopers: 110 out of 158 [2023-11-30 05:14:39,276 INFO L103 encePairwiseOnDemand]: Start differencePairwiseOnDemand. First operand has 142 places, 144 transitions, 357 flow. Second operand has 4 states, 4 states have (on average 112.5) internal successors, (450), 4 states have internal predecessors, (450), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-11-30 05:14:39,276 INFO L112 encePairwiseOnDemand]: Universal subtrahend loopers provided by user. [2023-11-30 05:14:39,276 INFO L113 encePairwiseOnDemand]: Number of universal subtrahend loopers: 110 of 158 [2023-11-30 05:14:39,277 INFO L73 FinitePrefix]: Start finitePrefix. Operand will be constructed on-demand [2023-11-30 05:14:39,384 INFO L124 PetriNetUnfolderBase]: 82/559 cut-off events. [2023-11-30 05:14:39,384 INFO L125 PetriNetUnfolderBase]: For 86/100 co-relation queries the response was YES. [2023-11-30 05:14:39,385 INFO L83 FinitePrefix]: Finished finitePrefix Result has 906 conditions, 559 events. 82/559 cut-off events. For 86/100 co-relation queries the response was YES. Maximal size of possible extension queue 21. Compared 2789 event pairs, 4 based on Foata normal form. 0/519 useless extension candidates. Maximal degree in co-relation 808. Up to 140 conditions per place. [2023-11-30 05:14:39,387 INFO L140 encePairwiseOnDemand]: 152/158 looper letters, 32 selfloop transitions, 3 changer transitions 13/154 dead transitions. [2023-11-30 05:14:39,387 INFO L145 encePairwiseOnDemand]: Finished differencePairwiseOnDemand. Result has 145 places, 154 transitions, 487 flow [2023-11-30 05:14:39,388 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2023-11-30 05:14:39,388 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 4 states. [2023-11-30 05:14:39,390 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 4 states to 4 states and 484 transitions. [2023-11-30 05:14:39,391 INFO L542 CegarLoopForPetriNet]: DFA transition density 0.7658227848101266 [2023-11-30 05:14:39,391 INFO L72 ComplementDD]: Start complementDD. Operand 4 states and 484 transitions. [2023-11-30 05:14:39,391 INFO L73 IsDeterministic]: Start isDeterministic. Operand 4 states and 484 transitions. [2023-11-30 05:14:39,391 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2023-11-30 05:14:39,392 INFO L117 ReachableStatesCopy]: Start reachableStatesCopy. Operand 4 states and 484 transitions. [2023-11-30 05:14:39,393 INFO L343 DoubleDeckerVisitor]: Before removal of dead ends has 5 states, 4 states have (on average 121.0) internal successors, (484), 4 states have internal predecessors, (484), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-11-30 05:14:39,394 INFO L131 ReachableStatesCopy]: Finished reachableStatesCopy Result has 5 states, 5 states have (on average 158.0) internal successors, (790), 5 states have internal predecessors, (790), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-11-30 05:14:39,394 INFO L81 ComplementDD]: Finished complementDD. Result has 5 states, 5 states have (on average 158.0) internal successors, (790), 5 states have internal predecessors, (790), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-11-30 05:14:39,395 INFO L307 CegarLoopForPetriNet]: 145 programPoint places, 0 predicate places. [2023-11-30 05:14:39,395 INFO L500 AbstractCegarLoop]: Abstraction has has 145 places, 154 transitions, 487 flow [2023-11-30 05:14:39,395 INFO L501 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 112.5) internal successors, (450), 4 states have internal predecessors, (450), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-11-30 05:14:39,395 INFO L224 CegarLoopForPetriNet]: Found error trace [2023-11-30 05:14:39,396 INFO L232 CegarLoopForPetriNet]: trace histogram [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, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-30 05:14:39,396 WARN L482 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2023-11-30 05:14:39,396 INFO L425 AbstractCegarLoop]: === Iteration 3 === Targeting ULTIMATE.startErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE === [ULTIMATE.startErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr2REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 2 more)] === [2023-11-30 05:14:39,402 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-30 05:14:39,403 INFO L85 PathProgramCache]: Analyzing trace with hash -1149742340, now seen corresponding path program 1 times [2023-11-30 05:14:39,403 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-11-30 05:14:39,403 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1807630064] [2023-11-30 05:14:39,403 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-30 05:14:39,403 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-30 05:14:39,429 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-30 05:14:39,602 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-11-30 05:14:39,603 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-11-30 05:14:39,603 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1807630064] [2023-11-30 05:14:39,603 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1807630064] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-30 05:14:39,603 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [900810342] [2023-11-30 05:14:39,603 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-30 05:14:39,603 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-30 05:14:39,603 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-11-30 05:14:39,610 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) [2023-11-30 05:14:39,625 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2023-11-30 05:14:39,676 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-30 05:14:39,677 INFO L262 TraceCheckSpWp]: Trace formula consists of 121 conjuncts, 11 conjunts are in the unsatisfiable core [2023-11-30 05:14:39,688 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-30 05:14:39,735 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 1 [2023-11-30 05:14:39,843 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-11-30 05:14:39,843 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-30 05:14:39,931 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-11-30 05:14:39,932 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [900810342] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-30 05:14:39,932 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2023-11-30 05:14:39,932 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 5, 5] total 13 [2023-11-30 05:14:39,932 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [438880378] [2023-11-30 05:14:39,932 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2023-11-30 05:14:39,932 INFO L576 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2023-11-30 05:14:39,933 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-11-30 05:14:39,933 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2023-11-30 05:14:39,933 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=56, Invalid=126, Unknown=0, NotChecked=0, Total=182 [2023-11-30 05:14:39,935 INFO L497 CegarLoopForPetriNet]: Number of universal loopers: 109 out of 158 [2023-11-30 05:14:39,936 INFO L103 encePairwiseOnDemand]: Start differencePairwiseOnDemand. First operand has 145 places, 154 transitions, 487 flow. Second operand has 14 states, 14 states have (on average 111.57142857142857) internal successors, (1562), 14 states have internal predecessors, (1562), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-11-30 05:14:39,936 INFO L112 encePairwiseOnDemand]: Universal subtrahend loopers provided by user. [2023-11-30 05:14:39,936 INFO L113 encePairwiseOnDemand]: Number of universal subtrahend loopers: 109 of 158 [2023-11-30 05:14:39,936 INFO L73 FinitePrefix]: Start finitePrefix. Operand will be constructed on-demand [2023-11-30 05:14:40,010 INFO L124 PetriNetUnfolderBase]: 20/135 cut-off events. [2023-11-30 05:14:40,010 INFO L125 PetriNetUnfolderBase]: For 83/102 co-relation queries the response was YES. [2023-11-30 05:14:40,011 INFO L83 FinitePrefix]: Finished finitePrefix Result has 296 conditions, 135 events. 20/135 cut-off events. For 83/102 co-relation queries the response was YES. Maximal size of possible extension queue 8. Compared 322 event pairs, 4 based on Foata normal form. 4/135 useless extension candidates. Maximal degree in co-relation 215. Up to 32 conditions per place. [2023-11-30 05:14:40,011 INFO L140 encePairwiseOnDemand]: 151/158 looper letters, 27 selfloop transitions, 5 changer transitions 0/78 dead transitions. [2023-11-30 05:14:40,011 INFO L145 encePairwiseOnDemand]: Finished differencePairwiseOnDemand. Result has 78 places, 78 transitions, 340 flow [2023-11-30 05:14:40,012 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2023-11-30 05:14:40,012 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 7 states. [2023-11-30 05:14:40,013 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 7 states to 7 states and 797 transitions. [2023-11-30 05:14:40,013 INFO L542 CegarLoopForPetriNet]: DFA transition density 0.720614828209765 [2023-11-30 05:14:40,013 INFO L72 ComplementDD]: Start complementDD. Operand 7 states and 797 transitions. [2023-11-30 05:14:40,013 INFO L73 IsDeterministic]: Start isDeterministic. Operand 7 states and 797 transitions. [2023-11-30 05:14:40,014 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2023-11-30 05:14:40,014 INFO L117 ReachableStatesCopy]: Start reachableStatesCopy. Operand 7 states and 797 transitions. [2023-11-30 05:14:40,015 INFO L343 DoubleDeckerVisitor]: Before removal of dead ends has 8 states, 7 states have (on average 113.85714285714286) internal successors, (797), 7 states have internal predecessors, (797), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-11-30 05:14:40,016 INFO L131 ReachableStatesCopy]: Finished reachableStatesCopy Result has 8 states, 8 states have (on average 158.0) internal successors, (1264), 8 states have internal predecessors, (1264), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-11-30 05:14:40,017 INFO L81 ComplementDD]: Finished complementDD. Result has 8 states, 8 states have (on average 158.0) internal successors, (1264), 8 states have internal predecessors, (1264), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-11-30 05:14:40,017 INFO L307 CegarLoopForPetriNet]: 145 programPoint places, -67 predicate places. [2023-11-30 05:14:40,017 INFO L500 AbstractCegarLoop]: Abstraction has has 78 places, 78 transitions, 340 flow [2023-11-30 05:14:40,018 INFO L501 AbstractCegarLoop]: INTERPOLANT automaton has has 14 states, 14 states have (on average 111.57142857142857) internal successors, (1562), 14 states have internal predecessors, (1562), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-11-30 05:14:40,018 INFO L224 CegarLoopForPetriNet]: Found error trace [2023-11-30 05:14:40,019 INFO L232 CegarLoopForPetriNet]: trace histogram [2, 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, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-30 05:14:40,036 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Ended with exit code 0 [2023-11-30 05:14:40,223 WARN L482 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2,2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-30 05:14:40,223 INFO L425 AbstractCegarLoop]: === Iteration 4 === Targeting ULTIMATE.startErr0INUSE_VIOLATIONSUFFICIENT_THREAD_INSTANCES === [ULTIMATE.startErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr2REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 2 more)] === [2023-11-30 05:14:40,224 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-30 05:14:40,224 INFO L85 PathProgramCache]: Analyzing trace with hash -1282273779, now seen corresponding path program 1 times [2023-11-30 05:14:40,224 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-11-30 05:14:40,224 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1650956968] [2023-11-30 05:14:40,224 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-30 05:14:40,224 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-30 05:14:40,235 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2023-11-30 05:14:40,235 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2023-11-30 05:14:40,240 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2023-11-30 05:14:40,260 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2023-11-30 05:14:40,261 INFO L372 BasicCegarLoop]: Counterexample is feasible [2023-11-30 05:14:40,262 INFO L810 garLoopResultBuilder]: Registering result UNSAFE for location ULTIMATE.startErr0INUSE_VIOLATIONSUFFICIENT_THREAD_INSTANCES (4 of 5 remaining) [2023-11-30 05:14:40,263 INFO L810 garLoopResultBuilder]: Registering result UNKNOWN for location ULTIMATE.startErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE (3 of 5 remaining) [2023-11-30 05:14:40,263 INFO L810 garLoopResultBuilder]: Registering result UNKNOWN for location ULTIMATE.startErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE (2 of 5 remaining) [2023-11-30 05:14:40,263 INFO L810 garLoopResultBuilder]: Registering result UNKNOWN for location ULTIMATE.startErr2REQUIRES_VIOLATIONMEMORY_DEREFERENCE (1 of 5 remaining) [2023-11-30 05:14:40,263 INFO L810 garLoopResultBuilder]: Registering result UNKNOWN for location ULTIMATE.startErr3REQUIRES_VIOLATIONMEMORY_DEREFERENCE (0 of 5 remaining) [2023-11-30 05:14:40,264 WARN L482 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3 [2023-11-30 05:14:40,264 INFO L457 BasicCegarLoop]: Path program histogram: [1, 1, 1, 1] [2023-11-30 05:14:40,265 WARN L227 ceAbstractionStarter]: 1 thread instances were not sufficient, I will increase this number and restart the analysis [2023-11-30 05:14:40,265 INFO L508 ceAbstractionStarter]: Constructing petrified ICFG for 2 thread instances. [2023-11-30 05:14:40,288 INFO L144 ThreadInstanceAdder]: Constructed 2 joinOtherThreadTransitions. [2023-11-30 05:14:40,292 INFO L73 FinitePrefix]: Start finitePrefix. Operand has 172 places, 188 transitions, 392 flow [2023-11-30 05:14:40,317 INFO L124 PetriNetUnfolderBase]: 45/388 cut-off events. [2023-11-30 05:14:40,317 INFO L125 PetriNetUnfolderBase]: For 6/6 co-relation queries the response was YES. [2023-11-30 05:14:40,318 INFO L83 FinitePrefix]: Finished finitePrefix Result has 400 conditions, 388 events. 45/388 cut-off events. For 6/6 co-relation queries the response was YES. Maximal size of possible extension queue 13. Compared 1498 event pairs, 0 based on Foata normal form. 0/325 useless extension candidates. Maximal degree in co-relation 246. Up to 9 conditions per place. [2023-11-30 05:14:40,319 INFO L82 GeneralOperation]: Start removeDead. Operand has 172 places, 188 transitions, 392 flow [2023-11-30 05:14:40,321 INFO L88 GeneralOperation]: Finished RemoveDead, result has has 172 places, 188 transitions, 392 flow [2023-11-30 05:14:40,322 INFO L361 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2023-11-30 05:14:40,324 INFO L362 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, mHoare=true, 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;@439001fb, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2023-11-30 05:14:40,324 INFO L363 AbstractCegarLoop]: Starting to check reachability of 5 error locations. [2023-11-30 05:14:40,328 INFO L185 PetriNetUnfolderBase]: Found word, exiting Unfolder. [2023-11-30 05:14:40,328 INFO L124 PetriNetUnfolderBase]: 1/40 cut-off events. [2023-11-30 05:14:40,328 INFO L125 PetriNetUnfolderBase]: For 0/0 co-relation queries the response was YES. [2023-11-30 05:14:40,328 INFO L224 CegarLoopForPetriNet]: Found error trace [2023-11-30 05:14:40,328 INFO L232 CegarLoopForPetriNet]: trace histogram [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, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-30 05:14:40,328 INFO L425 AbstractCegarLoop]: === Iteration 1 === Targeting ULTIMATE.startErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE === [ULTIMATE.startErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr2REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 2 more)] === [2023-11-30 05:14:40,328 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-30 05:14:40,329 INFO L85 PathProgramCache]: Analyzing trace with hash -567054834, now seen corresponding path program 1 times [2023-11-30 05:14:40,329 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-11-30 05:14:40,329 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [547687336] [2023-11-30 05:14:40,329 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-30 05:14:40,329 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-30 05:14:40,337 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-30 05:14:40,371 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-11-30 05:14:40,371 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-11-30 05:14:40,372 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [547687336] [2023-11-30 05:14:40,372 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [547687336] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-30 05:14:40,372 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-11-30 05:14:40,372 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2023-11-30 05:14:40,372 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1744352741] [2023-11-30 05:14:40,372 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-30 05:14:40,372 INFO L576 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2023-11-30 05:14:40,373 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-11-30 05:14:40,373 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2023-11-30 05:14:40,373 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2023-11-30 05:14:40,374 INFO L497 CegarLoopForPetriNet]: Number of universal loopers: 134 out of 188 [2023-11-30 05:14:40,374 INFO L103 encePairwiseOnDemand]: Start differencePairwiseOnDemand. First operand has 172 places, 188 transitions, 392 flow. Second operand has 3 states, 3 states have (on average 137.0) internal successors, (411), 3 states have internal predecessors, (411), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-11-30 05:14:40,374 INFO L112 encePairwiseOnDemand]: Universal subtrahend loopers provided by user. [2023-11-30 05:14:40,374 INFO L113 encePairwiseOnDemand]: Number of universal subtrahend loopers: 134 of 188 [2023-11-30 05:14:40,374 INFO L73 FinitePrefix]: Start finitePrefix. Operand will be constructed on-demand [2023-11-30 05:14:40,668 INFO L124 PetriNetUnfolderBase]: 649/2803 cut-off events. [2023-11-30 05:14:40,668 INFO L125 PetriNetUnfolderBase]: For 50/50 co-relation queries the response was YES. [2023-11-30 05:14:40,672 INFO L83 FinitePrefix]: Finished finitePrefix Result has 3946 conditions, 2803 events. 649/2803 cut-off events. For 50/50 co-relation queries the response was YES. Maximal size of possible extension queue 112. Compared 24868 event pairs, 476 based on Foata normal form. 646/3144 useless extension candidates. Maximal degree in co-relation 663. Up to 847 conditions per place. [2023-11-30 05:14:40,678 INFO L140 encePairwiseOnDemand]: 167/188 looper letters, 29 selfloop transitions, 1 changer transitions 13/171 dead transitions. [2023-11-30 05:14:40,678 INFO L145 encePairwiseOnDemand]: Finished differencePairwiseOnDemand. Result has 166 places, 171 transitions, 440 flow [2023-11-30 05:14:40,679 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2023-11-30 05:14:40,679 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 3 states. [2023-11-30 05:14:40,679 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 3 states to 3 states and 470 transitions. [2023-11-30 05:14:40,680 INFO L542 CegarLoopForPetriNet]: DFA transition density 0.8333333333333334 [2023-11-30 05:14:40,680 INFO L72 ComplementDD]: Start complementDD. Operand 3 states and 470 transitions. [2023-11-30 05:14:40,680 INFO L73 IsDeterministic]: Start isDeterministic. Operand 3 states and 470 transitions. [2023-11-30 05:14:40,680 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2023-11-30 05:14:40,680 INFO L117 ReachableStatesCopy]: Start reachableStatesCopy. Operand 3 states and 470 transitions. [2023-11-30 05:14:40,681 INFO L343 DoubleDeckerVisitor]: Before removal of dead ends has 4 states, 3 states have (on average 156.66666666666666) internal successors, (470), 3 states have internal predecessors, (470), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-11-30 05:14:40,682 INFO L131 ReachableStatesCopy]: Finished reachableStatesCopy Result has 4 states, 4 states have (on average 188.0) internal successors, (752), 4 states have internal predecessors, (752), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-11-30 05:14:40,682 INFO L81 ComplementDD]: Finished complementDD. Result has 4 states, 4 states have (on average 188.0) internal successors, (752), 4 states have internal predecessors, (752), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-11-30 05:14:40,683 INFO L307 CegarLoopForPetriNet]: 172 programPoint places, -6 predicate places. [2023-11-30 05:14:40,683 INFO L500 AbstractCegarLoop]: Abstraction has has 166 places, 171 transitions, 440 flow [2023-11-30 05:14:40,683 INFO L501 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 137.0) internal successors, (411), 3 states have internal predecessors, (411), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-11-30 05:14:40,683 INFO L224 CegarLoopForPetriNet]: Found error trace [2023-11-30 05:14:40,683 INFO L232 CegarLoopForPetriNet]: trace histogram [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, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-30 05:14:40,683 WARN L482 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4 [2023-11-30 05:14:40,683 INFO L425 AbstractCegarLoop]: === Iteration 2 === Targeting ULTIMATE.startErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE === [ULTIMATE.startErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr2REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 2 more)] === [2023-11-30 05:14:40,684 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-30 05:14:40,684 INFO L85 PathProgramCache]: Analyzing trace with hash -567054833, now seen corresponding path program 1 times [2023-11-30 05:14:40,684 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-11-30 05:14:40,684 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2092289187] [2023-11-30 05:14:40,684 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-30 05:14:40,684 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-30 05:14:40,689 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-30 05:14:40,726 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-11-30 05:14:40,726 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-11-30 05:14:40,726 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2092289187] [2023-11-30 05:14:40,726 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2092289187] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-30 05:14:40,726 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-11-30 05:14:40,726 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2023-11-30 05:14:40,726 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [585726793] [2023-11-30 05:14:40,726 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-30 05:14:40,726 INFO L576 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2023-11-30 05:14:40,727 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-11-30 05:14:40,727 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2023-11-30 05:14:40,727 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=6, Invalid=6, Unknown=0, NotChecked=0, Total=12 [2023-11-30 05:14:40,728 INFO L497 CegarLoopForPetriNet]: Number of universal loopers: 129 out of 188 [2023-11-30 05:14:40,728 INFO L103 encePairwiseOnDemand]: Start differencePairwiseOnDemand. First operand has 166 places, 171 transitions, 440 flow. Second operand has 4 states, 4 states have (on average 131.5) internal successors, (526), 4 states have internal predecessors, (526), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-11-30 05:14:40,728 INFO L112 encePairwiseOnDemand]: Universal subtrahend loopers provided by user. [2023-11-30 05:14:40,728 INFO L113 encePairwiseOnDemand]: Number of universal subtrahend loopers: 129 of 188 [2023-11-30 05:14:40,728 INFO L73 FinitePrefix]: Start finitePrefix. Operand will be constructed on-demand [2023-11-30 05:14:41,083 INFO L124 PetriNetUnfolderBase]: 906/3603 cut-off events. [2023-11-30 05:14:41,083 INFO L125 PetriNetUnfolderBase]: For 607/701 co-relation queries the response was YES. [2023-11-30 05:14:41,088 INFO L83 FinitePrefix]: Finished finitePrefix Result has 6410 conditions, 3603 events. 906/3603 cut-off events. For 607/701 co-relation queries the response was YES. Maximal size of possible extension queue 116. Compared 31988 event pairs, 316 based on Foata normal form. 0/3358 useless extension candidates. Maximal degree in co-relation 1114. Up to 1271 conditions per place. [2023-11-30 05:14:41,097 INFO L140 encePairwiseOnDemand]: 182/188 looper letters, 40 selfloop transitions, 3 changer transitions 21/187 dead transitions. [2023-11-30 05:14:41,097 INFO L145 encePairwiseOnDemand]: Finished differencePairwiseOnDemand. Result has 169 places, 187 transitions, 622 flow [2023-11-30 05:14:41,097 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2023-11-30 05:14:41,098 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 4 states. [2023-11-30 05:14:41,098 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 4 states to 4 states and 572 transitions. [2023-11-30 05:14:41,099 INFO L542 CegarLoopForPetriNet]: DFA transition density 0.7606382978723404 [2023-11-30 05:14:41,099 INFO L72 ComplementDD]: Start complementDD. Operand 4 states and 572 transitions. [2023-11-30 05:14:41,099 INFO L73 IsDeterministic]: Start isDeterministic. Operand 4 states and 572 transitions. [2023-11-30 05:14:41,099 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2023-11-30 05:14:41,099 INFO L117 ReachableStatesCopy]: Start reachableStatesCopy. Operand 4 states and 572 transitions. [2023-11-30 05:14:41,100 INFO L343 DoubleDeckerVisitor]: Before removal of dead ends has 5 states, 4 states have (on average 143.0) internal successors, (572), 4 states have internal predecessors, (572), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-11-30 05:14:41,101 INFO L131 ReachableStatesCopy]: Finished reachableStatesCopy Result has 5 states, 5 states have (on average 188.0) internal successors, (940), 5 states have internal predecessors, (940), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-11-30 05:14:41,101 INFO L81 ComplementDD]: Finished complementDD. Result has 5 states, 5 states have (on average 188.0) internal successors, (940), 5 states have internal predecessors, (940), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-11-30 05:14:41,102 INFO L307 CegarLoopForPetriNet]: 172 programPoint places, -3 predicate places. [2023-11-30 05:14:41,102 INFO L500 AbstractCegarLoop]: Abstraction has has 169 places, 187 transitions, 622 flow [2023-11-30 05:14:41,102 INFO L501 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 131.5) internal successors, (526), 4 states have internal predecessors, (526), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-11-30 05:14:41,102 INFO L224 CegarLoopForPetriNet]: Found error trace [2023-11-30 05:14:41,102 INFO L232 CegarLoopForPetriNet]: trace histogram [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, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-30 05:14:41,103 WARN L482 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5 [2023-11-30 05:14:41,103 INFO L425 AbstractCegarLoop]: === Iteration 3 === Targeting ULTIMATE.startErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE === [ULTIMATE.startErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr2REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 2 more)] === [2023-11-30 05:14:41,103 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-30 05:14:41,103 INFO L85 PathProgramCache]: Analyzing trace with hash 1690463968, now seen corresponding path program 1 times [2023-11-30 05:14:41,103 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-11-30 05:14:41,103 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2050331233] [2023-11-30 05:14:41,103 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-30 05:14:41,103 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-30 05:14:41,117 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-30 05:14:41,195 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-11-30 05:14:41,195 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-11-30 05:14:41,195 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2050331233] [2023-11-30 05:14:41,195 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2050331233] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-30 05:14:41,195 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [846556571] [2023-11-30 05:14:41,195 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-30 05:14:41,196 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-30 05:14:41,196 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-11-30 05:14:41,233 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) [2023-11-30 05:14:41,343 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2023-11-30 05:14:41,393 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-30 05:14:41,403 INFO L262 TraceCheckSpWp]: Trace formula consists of 121 conjuncts, 11 conjunts are in the unsatisfiable core [2023-11-30 05:14:41,405 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-30 05:14:41,414 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 1 [2023-11-30 05:14:41,507 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-11-30 05:14:41,507 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-30 05:14:41,629 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-11-30 05:14:41,630 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [846556571] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-30 05:14:41,630 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2023-11-30 05:14:41,630 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 5, 5] total 13 [2023-11-30 05:14:41,630 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [496095480] [2023-11-30 05:14:41,630 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2023-11-30 05:14:41,648 INFO L576 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2023-11-30 05:14:41,649 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-11-30 05:14:41,649 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2023-11-30 05:14:41,649 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=56, Invalid=126, Unknown=0, NotChecked=0, Total=182 [2023-11-30 05:14:41,651 INFO L497 CegarLoopForPetriNet]: Number of universal loopers: 128 out of 188 [2023-11-30 05:14:41,713 INFO L103 encePairwiseOnDemand]: Start differencePairwiseOnDemand. First operand has 169 places, 187 transitions, 622 flow. Second operand has 14 states, 14 states have (on average 130.57142857142858) internal successors, (1828), 14 states have internal predecessors, (1828), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-11-30 05:14:41,713 INFO L112 encePairwiseOnDemand]: Universal subtrahend loopers provided by user. [2023-11-30 05:14:41,713 INFO L113 encePairwiseOnDemand]: Number of universal subtrahend loopers: 128 of 188 [2023-11-30 05:14:41,713 INFO L73 FinitePrefix]: Start finitePrefix. Operand will be constructed on-demand [2023-11-30 05:14:42,099 INFO L124 PetriNetUnfolderBase]: 240/690 cut-off events. [2023-11-30 05:14:42,099 INFO L125 PetriNetUnfolderBase]: For 506/608 co-relation queries the response was YES. [2023-11-30 05:14:42,100 INFO L83 FinitePrefix]: Finished finitePrefix Result has 1852 conditions, 690 events. 240/690 cut-off events. For 506/608 co-relation queries the response was YES. Maximal size of possible extension queue 40. Compared 3974 event pairs, 34 based on Foata normal form. 4/676 useless extension candidates. Maximal degree in co-relation 335. Up to 377 conditions per place. [2023-11-30 05:14:42,103 INFO L140 encePairwiseOnDemand]: 181/188 looper letters, 58 selfloop transitions, 8 changer transitions 0/129 dead transitions. [2023-11-30 05:14:42,103 INFO L145 encePairwiseOnDemand]: Finished differencePairwiseOnDemand. Result has 105 places, 129 transitions, 642 flow [2023-11-30 05:14:42,103 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2023-11-30 05:14:42,103 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 10 states. [2023-11-30 05:14:42,121 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 10 states to 10 states and 1350 transitions. [2023-11-30 05:14:42,122 INFO L542 CegarLoopForPetriNet]: DFA transition density 0.7180851063829787 [2023-11-30 05:14:42,122 INFO L72 ComplementDD]: Start complementDD. Operand 10 states and 1350 transitions. [2023-11-30 05:14:42,122 INFO L73 IsDeterministic]: Start isDeterministic. Operand 10 states and 1350 transitions. [2023-11-30 05:14:42,122 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2023-11-30 05:14:42,123 INFO L117 ReachableStatesCopy]: Start reachableStatesCopy. Operand 10 states and 1350 transitions. [2023-11-30 05:14:42,125 INFO L343 DoubleDeckerVisitor]: Before removal of dead ends has 11 states, 10 states have (on average 135.0) internal successors, (1350), 10 states have internal predecessors, (1350), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-11-30 05:14:42,127 INFO L131 ReachableStatesCopy]: Finished reachableStatesCopy Result has 11 states, 11 states have (on average 188.0) internal successors, (2068), 11 states have internal predecessors, (2068), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-11-30 05:14:42,127 INFO L81 ComplementDD]: Finished complementDD. Result has 11 states, 11 states have (on average 188.0) internal successors, (2068), 11 states have internal predecessors, (2068), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-11-30 05:14:42,128 INFO L307 CegarLoopForPetriNet]: 172 programPoint places, -67 predicate places. [2023-11-30 05:14:42,128 INFO L500 AbstractCegarLoop]: Abstraction has has 105 places, 129 transitions, 642 flow [2023-11-30 05:14:42,129 INFO L501 AbstractCegarLoop]: INTERPOLANT automaton has has 14 states, 14 states have (on average 130.57142857142858) internal successors, (1828), 14 states have internal predecessors, (1828), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-11-30 05:14:42,129 INFO L224 CegarLoopForPetriNet]: Found error trace [2023-11-30 05:14:42,129 INFO L232 CegarLoopForPetriNet]: trace histogram [3, 3, 3, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-30 05:14:42,148 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2023-11-30 05:14:42,333 WARN L482 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 3 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable6 [2023-11-30 05:14:42,334 INFO L425 AbstractCegarLoop]: === Iteration 4 === Targeting ULTIMATE.startErr0INUSE_VIOLATIONSUFFICIENT_THREAD_INSTANCES === [ULTIMATE.startErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr2REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 2 more)] === [2023-11-30 05:14:42,334 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-30 05:14:42,334 INFO L85 PathProgramCache]: Analyzing trace with hash 713630929, now seen corresponding path program 1 times [2023-11-30 05:14:42,334 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-11-30 05:14:42,334 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [456113891] [2023-11-30 05:14:42,334 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-30 05:14:42,334 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-30 05:14:42,349 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2023-11-30 05:14:42,349 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2023-11-30 05:14:42,377 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2023-11-30 05:14:42,383 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2023-11-30 05:14:42,384 INFO L372 BasicCegarLoop]: Counterexample is feasible [2023-11-30 05:14:42,384 INFO L810 garLoopResultBuilder]: Registering result UNSAFE for location ULTIMATE.startErr0INUSE_VIOLATIONSUFFICIENT_THREAD_INSTANCES (4 of 5 remaining) [2023-11-30 05:14:42,385 INFO L810 garLoopResultBuilder]: Registering result UNKNOWN for location ULTIMATE.startErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE (3 of 5 remaining) [2023-11-30 05:14:42,386 INFO L810 garLoopResultBuilder]: Registering result UNKNOWN for location ULTIMATE.startErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE (2 of 5 remaining) [2023-11-30 05:14:42,387 INFO L810 garLoopResultBuilder]: Registering result UNKNOWN for location ULTIMATE.startErr2REQUIRES_VIOLATIONMEMORY_DEREFERENCE (1 of 5 remaining) [2023-11-30 05:14:42,387 INFO L810 garLoopResultBuilder]: Registering result UNKNOWN for location ULTIMATE.startErr3REQUIRES_VIOLATIONMEMORY_DEREFERENCE (0 of 5 remaining) [2023-11-30 05:14:42,387 WARN L482 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7 [2023-11-30 05:14:42,387 INFO L457 BasicCegarLoop]: Path program histogram: [1, 1, 1, 1] [2023-11-30 05:14:42,388 WARN L227 ceAbstractionStarter]: 2 thread instances were not sufficient, I will increase this number and restart the analysis [2023-11-30 05:14:42,388 INFO L508 ceAbstractionStarter]: Constructing petrified ICFG for 3 thread instances. [2023-11-30 05:14:42,434 INFO L144 ThreadInstanceAdder]: Constructed 3 joinOtherThreadTransitions. [2023-11-30 05:14:42,436 INFO L73 FinitePrefix]: Start finitePrefix. Operand has 199 places, 218 transitions, 463 flow [2023-11-30 05:14:42,599 INFO L124 PetriNetUnfolderBase]: 68/571 cut-off events. [2023-11-30 05:14:42,599 INFO L125 PetriNetUnfolderBase]: For 19/19 co-relation queries the response was YES. [2023-11-30 05:14:42,602 INFO L83 FinitePrefix]: Finished finitePrefix Result has 596 conditions, 571 events. 68/571 cut-off events. For 19/19 co-relation queries the response was YES. Maximal size of possible extension queue 15. Compared 2473 event pairs, 1 based on Foata normal form. 0/475 useless extension candidates. Maximal degree in co-relation 396. Up to 16 conditions per place. [2023-11-30 05:14:42,602 INFO L82 GeneralOperation]: Start removeDead. Operand has 199 places, 218 transitions, 463 flow [2023-11-30 05:14:42,606 INFO L88 GeneralOperation]: Finished RemoveDead, result has has 199 places, 218 transitions, 463 flow [2023-11-30 05:14:42,608 INFO L361 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2023-11-30 05:14:42,608 INFO L362 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, mHoare=true, 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;@439001fb, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2023-11-30 05:14:42,609 INFO L363 AbstractCegarLoop]: Starting to check reachability of 5 error locations. [2023-11-30 05:14:42,611 INFO L185 PetriNetUnfolderBase]: Found word, exiting Unfolder. [2023-11-30 05:14:42,611 INFO L124 PetriNetUnfolderBase]: 1/40 cut-off events. [2023-11-30 05:14:42,611 INFO L125 PetriNetUnfolderBase]: For 0/0 co-relation queries the response was YES. [2023-11-30 05:14:42,611 INFO L224 CegarLoopForPetriNet]: Found error trace [2023-11-30 05:14:42,611 INFO L232 CegarLoopForPetriNet]: trace histogram [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, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-30 05:14:42,612 INFO L425 AbstractCegarLoop]: === Iteration 1 === Targeting ULTIMATE.startErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE === [ULTIMATE.startErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr2REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 2 more)] === [2023-11-30 05:14:42,612 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-30 05:14:42,612 INFO L85 PathProgramCache]: Analyzing trace with hash 1829243022, now seen corresponding path program 1 times [2023-11-30 05:14:42,612 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-11-30 05:14:42,612 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1473427505] [2023-11-30 05:14:42,612 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-30 05:14:42,613 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-30 05:14:42,618 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-30 05:14:42,665 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-11-30 05:14:42,666 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-11-30 05:14:42,666 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1473427505] [2023-11-30 05:14:42,666 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1473427505] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-30 05:14:42,666 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-11-30 05:14:42,667 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2023-11-30 05:14:42,667 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1497632998] [2023-11-30 05:14:42,667 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-30 05:14:42,667 INFO L576 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2023-11-30 05:14:42,667 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-11-30 05:14:42,667 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2023-11-30 05:14:42,668 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2023-11-30 05:14:42,669 INFO L497 CegarLoopForPetriNet]: Number of universal loopers: 153 out of 218 [2023-11-30 05:14:42,669 INFO L103 encePairwiseOnDemand]: Start differencePairwiseOnDemand. First operand has 199 places, 218 transitions, 463 flow. Second operand has 3 states, 3 states have (on average 156.0) internal successors, (468), 3 states have internal predecessors, (468), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-11-30 05:14:42,669 INFO L112 encePairwiseOnDemand]: Universal subtrahend loopers provided by user. [2023-11-30 05:14:42,669 INFO L113 encePairwiseOnDemand]: Number of universal subtrahend loopers: 153 of 218 [2023-11-30 05:14:42,669 INFO L73 FinitePrefix]: Start finitePrefix. Operand will be constructed on-demand [2023-11-30 05:14:44,150 INFO L124 PetriNetUnfolderBase]: 5424/16678 cut-off events. [2023-11-30 05:14:44,150 INFO L125 PetriNetUnfolderBase]: For 481/481 co-relation queries the response was YES. [2023-11-30 05:14:44,180 INFO L83 FinitePrefix]: Finished finitePrefix Result has 24843 conditions, 16678 events. 5424/16678 cut-off events. For 481/481 co-relation queries the response was YES. Maximal size of possible extension queue 556. Compared 189134 event pairs, 3973 based on Foata normal form. 4874/19967 useless extension candidates. Maximal degree in co-relation 3937. Up to 5960 conditions per place. [2023-11-30 05:14:44,217 INFO L140 encePairwiseOnDemand]: 193/218 looper letters, 35 selfloop transitions, 1 changer transitions 17/198 dead transitions. [2023-11-30 05:14:44,218 INFO L145 encePairwiseOnDemand]: Finished differencePairwiseOnDemand. Result has 190 places, 198 transitions, 525 flow [2023-11-30 05:14:44,218 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2023-11-30 05:14:44,218 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 3 states. [2023-11-30 05:14:44,219 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 3 states to 3 states and 545 transitions. [2023-11-30 05:14:44,219 INFO L542 CegarLoopForPetriNet]: DFA transition density 0.8333333333333334 [2023-11-30 05:14:44,219 INFO L72 ComplementDD]: Start complementDD. Operand 3 states and 545 transitions. [2023-11-30 05:14:44,219 INFO L73 IsDeterministic]: Start isDeterministic. Operand 3 states and 545 transitions. [2023-11-30 05:14:44,220 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2023-11-30 05:14:44,220 INFO L117 ReachableStatesCopy]: Start reachableStatesCopy. Operand 3 states and 545 transitions. [2023-11-30 05:14:44,220 INFO L343 DoubleDeckerVisitor]: Before removal of dead ends has 4 states, 3 states have (on average 181.66666666666666) internal successors, (545), 3 states have internal predecessors, (545), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-11-30 05:14:44,221 INFO L131 ReachableStatesCopy]: Finished reachableStatesCopy Result has 4 states, 4 states have (on average 218.0) internal successors, (872), 4 states have internal predecessors, (872), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-11-30 05:14:44,222 INFO L81 ComplementDD]: Finished complementDD. Result has 4 states, 4 states have (on average 218.0) internal successors, (872), 4 states have internal predecessors, (872), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-11-30 05:14:44,222 INFO L307 CegarLoopForPetriNet]: 199 programPoint places, -9 predicate places. [2023-11-30 05:14:44,222 INFO L500 AbstractCegarLoop]: Abstraction has has 190 places, 198 transitions, 525 flow [2023-11-30 05:14:44,222 INFO L501 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 156.0) internal successors, (468), 3 states have internal predecessors, (468), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-11-30 05:14:44,222 INFO L224 CegarLoopForPetriNet]: Found error trace [2023-11-30 05:14:44,222 INFO L232 CegarLoopForPetriNet]: trace histogram [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, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-30 05:14:44,222 WARN L482 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8 [2023-11-30 05:14:44,222 INFO L425 AbstractCegarLoop]: === Iteration 2 === Targeting ULTIMATE.startErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE === [ULTIMATE.startErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr2REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 2 more)] === [2023-11-30 05:14:44,223 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-30 05:14:44,223 INFO L85 PathProgramCache]: Analyzing trace with hash 1829243023, now seen corresponding path program 1 times [2023-11-30 05:14:44,223 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-11-30 05:14:44,223 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [187595726] [2023-11-30 05:14:44,223 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-30 05:14:44,223 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-30 05:14:44,228 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-30 05:14:44,262 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-11-30 05:14:44,262 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-11-30 05:14:44,262 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [187595726] [2023-11-30 05:14:44,262 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [187595726] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-30 05:14:44,262 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-11-30 05:14:44,263 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2023-11-30 05:14:44,263 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [357500074] [2023-11-30 05:14:44,263 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-30 05:14:44,263 INFO L576 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2023-11-30 05:14:44,263 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-11-30 05:14:44,263 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2023-11-30 05:14:44,263 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=6, Invalid=6, Unknown=0, NotChecked=0, Total=12 [2023-11-30 05:14:44,264 INFO L497 CegarLoopForPetriNet]: Number of universal loopers: 148 out of 218 [2023-11-30 05:14:44,264 INFO L103 encePairwiseOnDemand]: Start differencePairwiseOnDemand. First operand has 190 places, 198 transitions, 525 flow. Second operand has 4 states, 4 states have (on average 150.5) internal successors, (602), 4 states have internal predecessors, (602), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-11-30 05:14:44,264 INFO L112 encePairwiseOnDemand]: Universal subtrahend loopers provided by user. [2023-11-30 05:14:44,264 INFO L113 encePairwiseOnDemand]: Number of universal subtrahend loopers: 148 of 218 [2023-11-30 05:14:44,264 INFO L73 FinitePrefix]: Start finitePrefix. Operand will be constructed on-demand [2023-11-30 05:14:46,069 INFO L124 PetriNetUnfolderBase]: 7141/21318 cut-off events. [2023-11-30 05:14:46,069 INFO L125 PetriNetUnfolderBase]: For 3463/4679 co-relation queries the response was YES. [2023-11-30 05:14:46,125 INFO L83 FinitePrefix]: Finished finitePrefix Result has 41477 conditions, 21318 events. 7141/21318 cut-off events. For 3463/4679 co-relation queries the response was YES. Maximal size of possible extension queue 647. Compared 246840 event pairs, 3633 based on Foata normal form. 0/19748 useless extension candidates. Maximal degree in co-relation 6386. Up to 9033 conditions per place. [2023-11-30 05:14:46,190 INFO L140 encePairwiseOnDemand]: 212/218 looper letters, 46 selfloop transitions, 3 changer transitions 29/218 dead transitions. [2023-11-30 05:14:46,191 INFO L145 encePairwiseOnDemand]: Finished differencePairwiseOnDemand. Result has 193 places, 218 transitions, 751 flow [2023-11-30 05:14:46,191 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2023-11-30 05:14:46,191 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 4 states. [2023-11-30 05:14:46,192 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 4 states to 4 states and 658 transitions. [2023-11-30 05:14:46,192 INFO L542 CegarLoopForPetriNet]: DFA transition density 0.7545871559633027 [2023-11-30 05:14:46,192 INFO L72 ComplementDD]: Start complementDD. Operand 4 states and 658 transitions. [2023-11-30 05:14:46,192 INFO L73 IsDeterministic]: Start isDeterministic. Operand 4 states and 658 transitions. [2023-11-30 05:14:46,193 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2023-11-30 05:14:46,193 INFO L117 ReachableStatesCopy]: Start reachableStatesCopy. Operand 4 states and 658 transitions. [2023-11-30 05:14:46,309 INFO L343 DoubleDeckerVisitor]: Before removal of dead ends has 5 states, 4 states have (on average 164.5) internal successors, (658), 4 states have internal predecessors, (658), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-11-30 05:14:46,310 INFO L131 ReachableStatesCopy]: Finished reachableStatesCopy Result has 5 states, 5 states have (on average 218.0) internal successors, (1090), 5 states have internal predecessors, (1090), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-11-30 05:14:46,310 INFO L81 ComplementDD]: Finished complementDD. Result has 5 states, 5 states have (on average 218.0) internal successors, (1090), 5 states have internal predecessors, (1090), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-11-30 05:14:46,311 INFO L307 CegarLoopForPetriNet]: 199 programPoint places, -6 predicate places. [2023-11-30 05:14:46,311 INFO L500 AbstractCegarLoop]: Abstraction has has 193 places, 218 transitions, 751 flow [2023-11-30 05:14:46,311 INFO L501 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 150.5) internal successors, (602), 4 states have internal predecessors, (602), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-11-30 05:14:46,311 INFO L224 CegarLoopForPetriNet]: Found error trace [2023-11-30 05:14:46,311 INFO L232 CegarLoopForPetriNet]: trace histogram [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, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-30 05:14:46,312 WARN L482 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable9 [2023-11-30 05:14:46,312 INFO L425 AbstractCegarLoop]: === Iteration 3 === Targeting ULTIMATE.startErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE === [ULTIMATE.startErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr2REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 2 more)] === [2023-11-30 05:14:46,312 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-30 05:14:46,312 INFO L85 PathProgramCache]: Analyzing trace with hash -2088324860, now seen corresponding path program 1 times [2023-11-30 05:14:46,312 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-11-30 05:14:46,312 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1665450527] [2023-11-30 05:14:46,312 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-30 05:14:46,312 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-30 05:14:46,329 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-30 05:14:46,421 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-11-30 05:14:46,422 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-11-30 05:14:46,422 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1665450527] [2023-11-30 05:14:46,422 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1665450527] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-30 05:14:46,422 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [533295126] [2023-11-30 05:14:46,422 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-30 05:14:46,422 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-30 05:14:46,422 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-11-30 05:14:46,437 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) [2023-11-30 05:14:46,447 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2023-11-30 05:14:46,504 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-30 05:14:46,505 INFO L262 TraceCheckSpWp]: Trace formula consists of 121 conjuncts, 11 conjunts are in the unsatisfiable core [2023-11-30 05:14:46,506 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-30 05:14:46,514 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 1 [2023-11-30 05:14:46,586 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-11-30 05:14:46,586 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-30 05:14:46,667 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-11-30 05:14:46,667 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [533295126] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-30 05:14:46,667 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2023-11-30 05:14:46,668 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 5, 5] total 10 [2023-11-30 05:14:46,668 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [989387922] [2023-11-30 05:14:46,668 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2023-11-30 05:14:46,669 INFO L576 AbstractCegarLoop]: INTERPOLANT automaton has 11 states [2023-11-30 05:14:46,670 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-11-30 05:14:46,670 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2023-11-30 05:14:46,670 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=36, Invalid=74, Unknown=0, NotChecked=0, Total=110 [2023-11-30 05:14:46,671 INFO L497 CegarLoopForPetriNet]: Number of universal loopers: 147 out of 218 [2023-11-30 05:14:46,673 INFO L103 encePairwiseOnDemand]: Start differencePairwiseOnDemand. First operand has 193 places, 218 transitions, 751 flow. Second operand has 11 states, 11 states have (on average 149.72727272727272) internal successors, (1647), 11 states have internal predecessors, (1647), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-11-30 05:14:46,673 INFO L112 encePairwiseOnDemand]: Universal subtrahend loopers provided by user. [2023-11-30 05:14:46,673 INFO L113 encePairwiseOnDemand]: Number of universal subtrahend loopers: 147 of 218 [2023-11-30 05:14:46,673 INFO L73 FinitePrefix]: Start finitePrefix. Operand will be constructed on-demand [2023-11-30 05:14:48,843 INFO L124 PetriNetUnfolderBase]: 7594/21495 cut-off events. [2023-11-30 05:14:48,843 INFO L125 PetriNetUnfolderBase]: For 9299/11182 co-relation queries the response was YES. [2023-11-30 05:14:48,891 INFO L83 FinitePrefix]: Finished finitePrefix Result has 52766 conditions, 21495 events. 7594/21495 cut-off events. For 9299/11182 co-relation queries the response was YES. Maximal size of possible extension queue 618. Compared 239904 event pairs, 206 based on Foata normal form. 4/20249 useless extension candidates. Maximal degree in co-relation 7986. Up to 9231 conditions per place. [2023-11-30 05:14:48,989 INFO L140 encePairwiseOnDemand]: 208/218 looper letters, 93 selfloop transitions, 11 changer transitions 29/272 dead transitions. [2023-11-30 05:14:48,989 INFO L145 encePairwiseOnDemand]: Finished differencePairwiseOnDemand. Result has 202 places, 272 transitions, 1317 flow [2023-11-30 05:14:48,990 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2023-11-30 05:14:48,990 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 10 states. [2023-11-30 05:14:48,992 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 10 states to 10 states and 1592 transitions. [2023-11-30 05:14:48,992 INFO L542 CegarLoopForPetriNet]: DFA transition density 0.7302752293577982 [2023-11-30 05:14:48,992 INFO L72 ComplementDD]: Start complementDD. Operand 10 states and 1592 transitions. [2023-11-30 05:14:48,992 INFO L73 IsDeterministic]: Start isDeterministic. Operand 10 states and 1592 transitions. [2023-11-30 05:14:48,993 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2023-11-30 05:14:48,993 INFO L117 ReachableStatesCopy]: Start reachableStatesCopy. Operand 10 states and 1592 transitions. [2023-11-30 05:14:48,995 INFO L343 DoubleDeckerVisitor]: Before removal of dead ends has 11 states, 10 states have (on average 159.2) internal successors, (1592), 10 states have internal predecessors, (1592), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-11-30 05:14:48,998 INFO L131 ReachableStatesCopy]: Finished reachableStatesCopy Result has 11 states, 11 states have (on average 218.0) internal successors, (2398), 11 states have internal predecessors, (2398), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-11-30 05:14:48,998 INFO L81 ComplementDD]: Finished complementDD. Result has 11 states, 11 states have (on average 218.0) internal successors, (2398), 11 states have internal predecessors, (2398), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-11-30 05:14:48,998 INFO L307 CegarLoopForPetriNet]: 199 programPoint places, 3 predicate places. [2023-11-30 05:14:48,998 INFO L500 AbstractCegarLoop]: Abstraction has has 202 places, 272 transitions, 1317 flow [2023-11-30 05:14:48,999 INFO L501 AbstractCegarLoop]: INTERPOLANT automaton has has 11 states, 11 states have (on average 149.72727272727272) internal successors, (1647), 11 states have internal predecessors, (1647), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-11-30 05:14:48,999 INFO L224 CegarLoopForPetriNet]: Found error trace [2023-11-30 05:14:48,999 INFO L232 CegarLoopForPetriNet]: trace histogram [2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 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] [2023-11-30 05:14:49,004 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Ended with exit code 0 [2023-11-30 05:14:49,203 WARN L482 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable10,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-30 05:14:49,204 INFO L425 AbstractCegarLoop]: === Iteration 4 === Targeting ULTIMATE.startErr3REQUIRES_VIOLATIONMEMORY_DEREFERENCE === [ULTIMATE.startErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr2REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 2 more)] === [2023-11-30 05:14:49,204 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-30 05:14:49,204 INFO L85 PathProgramCache]: Analyzing trace with hash -1387505549, now seen corresponding path program 1 times [2023-11-30 05:14:49,204 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-11-30 05:14:49,204 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [448969238] [2023-11-30 05:14:49,204 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-30 05:14:49,204 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-30 05:14:49,214 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-30 05:14:49,251 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2023-11-30 05:14:49,251 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-11-30 05:14:49,251 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [448969238] [2023-11-30 05:14:49,251 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [448969238] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-30 05:14:49,251 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-11-30 05:14:49,252 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2023-11-30 05:14:49,252 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [673726058] [2023-11-30 05:14:49,252 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-30 05:14:49,252 INFO L576 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2023-11-30 05:14:49,252 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-11-30 05:14:49,252 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2023-11-30 05:14:49,252 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2023-11-30 05:14:49,253 INFO L497 CegarLoopForPetriNet]: Number of universal loopers: 162 out of 218 [2023-11-30 05:14:49,253 INFO L103 encePairwiseOnDemand]: Start differencePairwiseOnDemand. First operand has 202 places, 272 transitions, 1317 flow. Second operand has 3 states, 3 states have (on average 164.33333333333334) internal successors, (493), 3 states have internal predecessors, (493), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-11-30 05:14:49,253 INFO L112 encePairwiseOnDemand]: Universal subtrahend loopers provided by user. [2023-11-30 05:14:49,253 INFO L113 encePairwiseOnDemand]: Number of universal subtrahend loopers: 162 of 218 [2023-11-30 05:14:49,253 INFO L73 FinitePrefix]: Start finitePrefix. Operand will be constructed on-demand [2023-11-30 05:14:52,670 INFO L124 PetriNetUnfolderBase]: 13154/34188 cut-off events. [2023-11-30 05:14:52,672 INFO L125 PetriNetUnfolderBase]: For 44825/48688 co-relation queries the response was YES. [2023-11-30 05:14:52,763 INFO L83 FinitePrefix]: Finished finitePrefix Result has 100885 conditions, 34188 events. 13154/34188 cut-off events. For 44825/48688 co-relation queries the response was YES. Maximal size of possible extension queue 941. Compared 395603 event pairs, 966 based on Foata normal form. 0/32648 useless extension candidates. Maximal degree in co-relation 15108. Up to 15571 conditions per place. [2023-11-30 05:14:52,948 INFO L140 encePairwiseOnDemand]: 215/218 looper letters, 99 selfloop transitions, 2 changer transitions 29/293 dead transitions. [2023-11-30 05:14:52,949 INFO L145 encePairwiseOnDemand]: Finished differencePairwiseOnDemand. Result has 204 places, 293 transitions, 1717 flow [2023-11-30 05:14:52,949 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2023-11-30 05:14:52,949 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 3 states. [2023-11-30 05:14:52,950 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 3 states to 3 states and 540 transitions. [2023-11-30 05:14:52,951 INFO L542 CegarLoopForPetriNet]: DFA transition density 0.8256880733944955 [2023-11-30 05:14:52,951 INFO L72 ComplementDD]: Start complementDD. Operand 3 states and 540 transitions. [2023-11-30 05:14:52,951 INFO L73 IsDeterministic]: Start isDeterministic. Operand 3 states and 540 transitions. [2023-11-30 05:14:52,951 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2023-11-30 05:14:52,951 INFO L117 ReachableStatesCopy]: Start reachableStatesCopy. Operand 3 states and 540 transitions. [2023-11-30 05:14:52,952 INFO L343 DoubleDeckerVisitor]: Before removal of dead ends has 4 states, 3 states have (on average 180.0) internal successors, (540), 3 states have internal predecessors, (540), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-11-30 05:14:52,953 INFO L131 ReachableStatesCopy]: Finished reachableStatesCopy Result has 4 states, 4 states have (on average 218.0) internal successors, (872), 4 states have internal predecessors, (872), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-11-30 05:14:52,953 INFO L81 ComplementDD]: Finished complementDD. Result has 4 states, 4 states have (on average 218.0) internal successors, (872), 4 states have internal predecessors, (872), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-11-30 05:14:52,954 INFO L307 CegarLoopForPetriNet]: 199 programPoint places, 5 predicate places. [2023-11-30 05:14:52,954 INFO L500 AbstractCegarLoop]: Abstraction has has 204 places, 293 transitions, 1717 flow [2023-11-30 05:14:52,954 INFO L501 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 164.33333333333334) internal successors, (493), 3 states have internal predecessors, (493), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-11-30 05:14:52,954 INFO L224 CegarLoopForPetriNet]: Found error trace [2023-11-30 05:14:52,954 INFO L232 CegarLoopForPetriNet]: trace histogram [4, 4, 4, 3, 3, 3, 3, 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, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-30 05:14:52,954 WARN L482 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable11 [2023-11-30 05:14:52,954 INFO L425 AbstractCegarLoop]: === Iteration 5 === Targeting ULTIMATE.startErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE === [ULTIMATE.startErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr2REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 2 more)] === [2023-11-30 05:14:52,955 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-30 05:14:52,955 INFO L85 PathProgramCache]: Analyzing trace with hash 353411019, now seen corresponding path program 1 times [2023-11-30 05:14:52,955 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-11-30 05:14:52,955 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1160176760] [2023-11-30 05:14:52,955 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-30 05:14:52,955 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-30 05:14:52,972 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-30 05:14:53,151 INFO L134 CoverageAnalysis]: Checked inductivity of 42 backedges. 0 proven. 42 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-11-30 05:14:53,152 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-11-30 05:14:53,152 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1160176760] [2023-11-30 05:14:53,152 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1160176760] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-30 05:14:53,152 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1344211678] [2023-11-30 05:14:53,152 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-30 05:14:53,152 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-30 05:14:53,152 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-11-30 05:14:53,153 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) [2023-11-30 05:14:53,167 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2023-11-30 05:14:53,220 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-30 05:14:53,221 INFO L262 TraceCheckSpWp]: Trace formula consists of 173 conjuncts, 19 conjunts are in the unsatisfiable core [2023-11-30 05:14:53,226 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-30 05:14:53,232 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 1 [2023-11-30 05:14:53,404 INFO L134 CoverageAnalysis]: Checked inductivity of 42 backedges. 0 proven. 42 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-11-30 05:14:53,404 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-30 05:14:53,576 INFO L134 CoverageAnalysis]: Checked inductivity of 42 backedges. 0 proven. 42 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-11-30 05:14:53,576 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1344211678] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-30 05:14:53,576 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2023-11-30 05:14:53,576 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9, 9] total 22 [2023-11-30 05:14:53,576 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [938110354] [2023-11-30 05:14:53,576 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2023-11-30 05:14:53,577 INFO L576 AbstractCegarLoop]: INTERPOLANT automaton has 23 states [2023-11-30 05:14:53,577 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-11-30 05:14:53,577 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 23 interpolants. [2023-11-30 05:14:53,577 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=116, Invalid=390, Unknown=0, NotChecked=0, Total=506 [2023-11-30 05:14:53,579 INFO L497 CegarLoopForPetriNet]: Number of universal loopers: 147 out of 218 [2023-11-30 05:14:53,582 INFO L103 encePairwiseOnDemand]: Start differencePairwiseOnDemand. First operand has 204 places, 293 transitions, 1717 flow. Second operand has 23 states, 23 states have (on average 149.8695652173913) internal successors, (3447), 23 states have internal predecessors, (3447), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-11-30 05:14:53,582 INFO L112 encePairwiseOnDemand]: Universal subtrahend loopers provided by user. [2023-11-30 05:14:53,582 INFO L113 encePairwiseOnDemand]: Number of universal subtrahend loopers: 147 of 218 [2023-11-30 05:14:53,582 INFO L73 FinitePrefix]: Start finitePrefix. Operand will be constructed on-demand [2023-11-30 05:14:54,399 INFO L124 PetriNetUnfolderBase]: 1940/4253 cut-off events. [2023-11-30 05:14:54,399 INFO L125 PetriNetUnfolderBase]: For 9568/10922 co-relation queries the response was YES. [2023-11-30 05:14:54,408 INFO L83 FinitePrefix]: Finished finitePrefix Result has 17218 conditions, 4253 events. 1940/4253 cut-off events. For 9568/10922 co-relation queries the response was YES. Maximal size of possible extension queue 198. Compared 33540 event pairs, 42 based on Foata normal form. 184/4344 useless extension candidates. Maximal degree in co-relation 2559. Up to 2702 conditions per place. [2023-11-30 05:14:54,438 INFO L140 encePairwiseOnDemand]: 211/218 looper letters, 113 selfloop transitions, 11 changer transitions 0/204 dead transitions. [2023-11-30 05:14:54,438 INFO L145 encePairwiseOnDemand]: Finished differencePairwiseOnDemand. Result has 142 places, 204 transitions, 1584 flow [2023-11-30 05:14:54,438 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2023-11-30 05:14:54,438 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 13 states. [2023-11-30 05:14:54,441 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 13 states to 13 states and 2026 transitions. [2023-11-30 05:14:54,441 INFO L542 CegarLoopForPetriNet]: DFA transition density 0.7148906139731828 [2023-11-30 05:14:54,441 INFO L72 ComplementDD]: Start complementDD. Operand 13 states and 2026 transitions. [2023-11-30 05:14:54,441 INFO L73 IsDeterministic]: Start isDeterministic. Operand 13 states and 2026 transitions. [2023-11-30 05:14:54,442 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2023-11-30 05:14:54,442 INFO L117 ReachableStatesCopy]: Start reachableStatesCopy. Operand 13 states and 2026 transitions. [2023-11-30 05:14:54,445 INFO L343 DoubleDeckerVisitor]: Before removal of dead ends has 14 states, 13 states have (on average 155.84615384615384) internal successors, (2026), 13 states have internal predecessors, (2026), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-11-30 05:14:54,448 INFO L131 ReachableStatesCopy]: Finished reachableStatesCopy Result has 14 states, 14 states have (on average 218.0) internal successors, (3052), 14 states have internal predecessors, (3052), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-11-30 05:14:54,449 INFO L81 ComplementDD]: Finished complementDD. Result has 14 states, 14 states have (on average 218.0) internal successors, (3052), 14 states have internal predecessors, (3052), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-11-30 05:14:54,449 INFO L307 CegarLoopForPetriNet]: 199 programPoint places, -57 predicate places. [2023-11-30 05:14:54,449 INFO L500 AbstractCegarLoop]: Abstraction has has 142 places, 204 transitions, 1584 flow [2023-11-30 05:14:54,450 INFO L501 AbstractCegarLoop]: INTERPOLANT automaton has has 23 states, 23 states have (on average 149.8695652173913) internal successors, (3447), 23 states have internal predecessors, (3447), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-11-30 05:14:54,450 INFO L224 CegarLoopForPetriNet]: Found error trace [2023-11-30 05:14:54,450 INFO L232 CegarLoopForPetriNet]: trace histogram [4, 4, 4, 4, 3, 3, 3, 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, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-30 05:14:54,469 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Ended with exit code 0 [2023-11-30 05:14:54,654 WARN L482 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable12,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-30 05:14:54,654 INFO L425 AbstractCegarLoop]: === Iteration 6 === Targeting ULTIMATE.startErr0INUSE_VIOLATIONSUFFICIENT_THREAD_INSTANCES === [ULTIMATE.startErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr2REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 2 more)] === [2023-11-30 05:14:54,654 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-30 05:14:54,655 INFO L85 PathProgramCache]: Analyzing trace with hash -1929159444, now seen corresponding path program 1 times [2023-11-30 05:14:54,655 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-11-30 05:14:54,655 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1137091829] [2023-11-30 05:14:54,655 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-30 05:14:54,655 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-30 05:14:54,670 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2023-11-30 05:14:54,671 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2023-11-30 05:14:54,685 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2023-11-30 05:14:54,690 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2023-11-30 05:14:54,691 INFO L372 BasicCegarLoop]: Counterexample is feasible [2023-11-30 05:14:54,691 INFO L810 garLoopResultBuilder]: Registering result UNSAFE for location ULTIMATE.startErr0INUSE_VIOLATIONSUFFICIENT_THREAD_INSTANCES (4 of 5 remaining) [2023-11-30 05:14:54,691 INFO L810 garLoopResultBuilder]: Registering result UNKNOWN for location ULTIMATE.startErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE (3 of 5 remaining) [2023-11-30 05:14:54,691 INFO L810 garLoopResultBuilder]: Registering result UNKNOWN for location ULTIMATE.startErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE (2 of 5 remaining) [2023-11-30 05:14:54,691 INFO L810 garLoopResultBuilder]: Registering result UNKNOWN for location ULTIMATE.startErr2REQUIRES_VIOLATIONMEMORY_DEREFERENCE (1 of 5 remaining) [2023-11-30 05:14:54,691 INFO L810 garLoopResultBuilder]: Registering result UNKNOWN for location ULTIMATE.startErr3REQUIRES_VIOLATIONMEMORY_DEREFERENCE (0 of 5 remaining) [2023-11-30 05:14:54,691 WARN L482 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable13 [2023-11-30 05:14:54,691 INFO L457 BasicCegarLoop]: Path program histogram: [1, 1, 1, 1, 1, 1] [2023-11-30 05:14:54,692 WARN L227 ceAbstractionStarter]: 3 thread instances were not sufficient, I will increase this number and restart the analysis [2023-11-30 05:14:54,692 INFO L508 ceAbstractionStarter]: Constructing petrified ICFG for 4 thread instances. [2023-11-30 05:14:54,708 INFO L144 ThreadInstanceAdder]: Constructed 4 joinOtherThreadTransitions. [2023-11-30 05:14:54,710 INFO L73 FinitePrefix]: Start finitePrefix. Operand has 226 places, 248 transitions, 536 flow [2023-11-30 05:14:54,768 INFO L124 PetriNetUnfolderBase]: 103/834 cut-off events. [2023-11-30 05:14:54,769 INFO L125 PetriNetUnfolderBase]: For 48/48 co-relation queries the response was YES. [2023-11-30 05:14:54,774 INFO L83 FinitePrefix]: Finished finitePrefix Result has 885 conditions, 834 events. 103/834 cut-off events. For 48/48 co-relation queries the response was YES. Maximal size of possible extension queue 17. Compared 3967 event pairs, 6 based on Foata normal form. 0/689 useless extension candidates. Maximal degree in co-relation 591. Up to 32 conditions per place. [2023-11-30 05:14:54,774 INFO L82 GeneralOperation]: Start removeDead. Operand has 226 places, 248 transitions, 536 flow [2023-11-30 05:14:54,779 INFO L88 GeneralOperation]: Finished RemoveDead, result has has 226 places, 248 transitions, 536 flow [2023-11-30 05:14:54,781 INFO L361 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2023-11-30 05:14:54,781 INFO L362 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, mHoare=true, 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;@439001fb, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2023-11-30 05:14:54,781 INFO L363 AbstractCegarLoop]: Starting to check reachability of 5 error locations. [2023-11-30 05:14:54,783 INFO L185 PetriNetUnfolderBase]: Found word, exiting Unfolder. [2023-11-30 05:14:54,783 INFO L124 PetriNetUnfolderBase]: 1/40 cut-off events. [2023-11-30 05:14:54,783 INFO L125 PetriNetUnfolderBase]: For 0/0 co-relation queries the response was YES. [2023-11-30 05:14:54,783 INFO L224 CegarLoopForPetriNet]: Found error trace [2023-11-30 05:14:54,783 INFO L232 CegarLoopForPetriNet]: trace histogram [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, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-30 05:14:54,783 INFO L425 AbstractCegarLoop]: === Iteration 1 === Targeting ULTIMATE.startErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE === [ULTIMATE.startErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr2REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 2 more)] === [2023-11-30 05:14:54,783 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-30 05:14:54,783 INFO L85 PathProgramCache]: Analyzing trace with hash 260339342, now seen corresponding path program 1 times [2023-11-30 05:14:54,783 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-11-30 05:14:54,783 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [382952213] [2023-11-30 05:14:54,783 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-30 05:14:54,784 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-30 05:14:54,788 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-30 05:14:54,802 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-11-30 05:14:54,802 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-11-30 05:14:54,803 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [382952213] [2023-11-30 05:14:54,803 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [382952213] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-30 05:14:54,803 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-11-30 05:14:54,803 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2023-11-30 05:14:54,803 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [291658213] [2023-11-30 05:14:54,803 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-30 05:14:54,803 INFO L576 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2023-11-30 05:14:54,803 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-11-30 05:14:54,803 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2023-11-30 05:14:54,804 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2023-11-30 05:14:54,804 INFO L497 CegarLoopForPetriNet]: Number of universal loopers: 172 out of 248 [2023-11-30 05:14:54,804 INFO L103 encePairwiseOnDemand]: Start differencePairwiseOnDemand. First operand has 226 places, 248 transitions, 536 flow. Second operand has 3 states, 3 states have (on average 175.0) internal successors, (525), 3 states have internal predecessors, (525), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-11-30 05:14:54,804 INFO L112 encePairwiseOnDemand]: Universal subtrahend loopers provided by user. [2023-11-30 05:14:54,804 INFO L113 encePairwiseOnDemand]: Number of universal subtrahend loopers: 172 of 248 [2023-11-30 05:14:54,805 INFO L73 FinitePrefix]: Start finitePrefix. Operand will be constructed on-demand [2023-11-30 05:15:05,486 INFO L124 PetriNetUnfolderBase]: 40119/99753 cut-off events. [2023-11-30 05:15:05,487 INFO L125 PetriNetUnfolderBase]: For 3912/3912 co-relation queries the response was YES. [2023-11-30 05:15:06,004 INFO L83 FinitePrefix]: Finished finitePrefix Result has 155325 conditions, 99753 events. 40119/99753 cut-off events. For 3912/3912 co-relation queries the response was YES. Maximal size of possible extension queue 2936. Compared 1312729 event pairs, 28930 based on Foata normal form. 34312/125945 useless extension candidates. Maximal degree in co-relation 24834. Up to 39573 conditions per place. [2023-11-30 05:15:06,549 INFO L140 encePairwiseOnDemand]: 219/248 looper letters, 41 selfloop transitions, 1 changer transitions 21/225 dead transitions. [2023-11-30 05:15:06,549 INFO L145 encePairwiseOnDemand]: Finished differencePairwiseOnDemand. Result has 214 places, 225 transitions, 612 flow [2023-11-30 05:15:06,560 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2023-11-30 05:15:06,560 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 3 states. [2023-11-30 05:15:06,561 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 3 states to 3 states and 620 transitions. [2023-11-30 05:15:06,561 INFO L542 CegarLoopForPetriNet]: DFA transition density 0.8333333333333334 [2023-11-30 05:15:06,561 INFO L72 ComplementDD]: Start complementDD. Operand 3 states and 620 transitions. [2023-11-30 05:15:06,561 INFO L73 IsDeterministic]: Start isDeterministic. Operand 3 states and 620 transitions. [2023-11-30 05:15:06,562 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2023-11-30 05:15:06,562 INFO L117 ReachableStatesCopy]: Start reachableStatesCopy. Operand 3 states and 620 transitions. [2023-11-30 05:15:06,563 INFO L343 DoubleDeckerVisitor]: Before removal of dead ends has 4 states, 3 states have (on average 206.66666666666666) internal successors, (620), 3 states have internal predecessors, (620), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-11-30 05:15:06,564 INFO L131 ReachableStatesCopy]: Finished reachableStatesCopy Result has 4 states, 4 states have (on average 248.0) internal successors, (992), 4 states have internal predecessors, (992), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-11-30 05:15:06,564 INFO L81 ComplementDD]: Finished complementDD. Result has 4 states, 4 states have (on average 248.0) internal successors, (992), 4 states have internal predecessors, (992), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-11-30 05:15:06,564 INFO L307 CegarLoopForPetriNet]: 226 programPoint places, -12 predicate places. [2023-11-30 05:15:06,564 INFO L500 AbstractCegarLoop]: Abstraction has has 214 places, 225 transitions, 612 flow [2023-11-30 05:15:06,565 INFO L501 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 175.0) internal successors, (525), 3 states have internal predecessors, (525), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-11-30 05:15:06,565 INFO L224 CegarLoopForPetriNet]: Found error trace [2023-11-30 05:15:06,565 INFO L232 CegarLoopForPetriNet]: trace histogram [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, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-30 05:15:06,565 WARN L482 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable14 [2023-11-30 05:15:06,565 INFO L425 AbstractCegarLoop]: === Iteration 2 === Targeting ULTIMATE.startErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE === [ULTIMATE.startErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr2REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 2 more)] === [2023-11-30 05:15:06,565 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-30 05:15:06,565 INFO L85 PathProgramCache]: Analyzing trace with hash 260339343, now seen corresponding path program 1 times [2023-11-30 05:15:06,565 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-11-30 05:15:06,565 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1971162341] [2023-11-30 05:15:06,565 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-30 05:15:06,565 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-30 05:15:06,570 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-30 05:15:06,602 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-11-30 05:15:06,602 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-11-30 05:15:06,602 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1971162341] [2023-11-30 05:15:06,602 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1971162341] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-30 05:15:06,602 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-11-30 05:15:06,602 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2023-11-30 05:15:06,602 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2032986387] [2023-11-30 05:15:06,602 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-30 05:15:06,603 INFO L576 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2023-11-30 05:15:06,603 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-11-30 05:15:06,603 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2023-11-30 05:15:06,603 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=6, Invalid=6, Unknown=0, NotChecked=0, Total=12 [2023-11-30 05:15:06,603 INFO L497 CegarLoopForPetriNet]: Number of universal loopers: 167 out of 248 [2023-11-30 05:15:06,604 INFO L103 encePairwiseOnDemand]: Start differencePairwiseOnDemand. First operand has 214 places, 225 transitions, 612 flow. Second operand has 4 states, 4 states have (on average 169.5) internal successors, (678), 4 states have internal predecessors, (678), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-11-30 05:15:06,604 INFO L112 encePairwiseOnDemand]: Universal subtrahend loopers provided by user. [2023-11-30 05:15:06,604 INFO L113 encePairwiseOnDemand]: Number of universal subtrahend loopers: 167 of 248 [2023-11-30 05:15:06,604 INFO L73 FinitePrefix]: Start finitePrefix. Operand will be constructed on-demand [2023-11-30 05:15:20,063 INFO L124 PetriNetUnfolderBase]: 51836/126893 cut-off events. [2023-11-30 05:15:20,063 INFO L125 PetriNetUnfolderBase]: For 20559/27755 co-relation queries the response was YES. [2023-11-30 05:15:20,668 INFO L83 FinitePrefix]: Finished finitePrefix Result has 263609 conditions, 126893 events. 51836/126893 cut-off events. For 20559/27755 co-relation queries the response was YES. Maximal size of possible extension queue 3327. Compared 1695471 event pairs, 29830 based on Foata normal form. 0/118138 useless extension candidates. Maximal degree in co-relation 41757. Up to 59975 conditions per place. [2023-11-30 05:15:21,123 INFO L140 encePairwiseOnDemand]: 242/248 looper letters, 52 selfloop transitions, 3 changer transitions 37/249 dead transitions. [2023-11-30 05:15:21,124 INFO L145 encePairwiseOnDemand]: Finished differencePairwiseOnDemand. Result has 217 places, 249 transitions, 882 flow [2023-11-30 05:15:21,314 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2023-11-30 05:15:21,315 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 4 states. [2023-11-30 05:15:21,316 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 4 states to 4 states and 744 transitions. [2023-11-30 05:15:21,316 INFO L542 CegarLoopForPetriNet]: DFA transition density 0.75 [2023-11-30 05:15:21,316 INFO L72 ComplementDD]: Start complementDD. Operand 4 states and 744 transitions. [2023-11-30 05:15:21,316 INFO L73 IsDeterministic]: Start isDeterministic. Operand 4 states and 744 transitions. [2023-11-30 05:15:21,316 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2023-11-30 05:15:21,316 INFO L117 ReachableStatesCopy]: Start reachableStatesCopy. Operand 4 states and 744 transitions. [2023-11-30 05:15:21,317 INFO L343 DoubleDeckerVisitor]: Before removal of dead ends has 5 states, 4 states have (on average 186.0) internal successors, (744), 4 states have internal predecessors, (744), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-11-30 05:15:21,319 INFO L131 ReachableStatesCopy]: Finished reachableStatesCopy Result has 5 states, 5 states have (on average 248.0) internal successors, (1240), 5 states have internal predecessors, (1240), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-11-30 05:15:21,319 INFO L81 ComplementDD]: Finished complementDD. Result has 5 states, 5 states have (on average 248.0) internal successors, (1240), 5 states have internal predecessors, (1240), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-11-30 05:15:21,319 INFO L307 CegarLoopForPetriNet]: 226 programPoint places, -9 predicate places. [2023-11-30 05:15:21,319 INFO L500 AbstractCegarLoop]: Abstraction has has 217 places, 249 transitions, 882 flow [2023-11-30 05:15:21,320 INFO L501 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 169.5) internal successors, (678), 4 states have internal predecessors, (678), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-11-30 05:15:21,320 INFO L224 CegarLoopForPetriNet]: Found error trace [2023-11-30 05:15:21,320 INFO L232 CegarLoopForPetriNet]: trace histogram [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, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-30 05:15:21,320 WARN L482 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable15 [2023-11-30 05:15:21,320 INFO L425 AbstractCegarLoop]: === Iteration 3 === Targeting ULTIMATE.startErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE === [ULTIMATE.startErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr2REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 2 more)] === [2023-11-30 05:15:21,320 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-30 05:15:21,320 INFO L85 PathProgramCache]: Analyzing trace with hash 398793064, now seen corresponding path program 1 times [2023-11-30 05:15:21,320 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-11-30 05:15:21,320 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [145693932] [2023-11-30 05:15:21,320 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-30 05:15:21,320 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-30 05:15:21,351 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-30 05:15:21,409 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-11-30 05:15:21,409 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-11-30 05:15:21,409 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [145693932] [2023-11-30 05:15:21,409 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [145693932] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-30 05:15:21,409 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [277599413] [2023-11-30 05:15:21,409 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-30 05:15:21,409 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-30 05:15:21,409 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-11-30 05:15:21,410 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) [2023-11-30 05:15:21,412 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2023-11-30 05:15:21,484 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-30 05:15:21,485 INFO L262 TraceCheckSpWp]: Trace formula consists of 121 conjuncts, 11 conjunts are in the unsatisfiable core [2023-11-30 05:15:21,490 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-30 05:15:21,495 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 1 [2023-11-30 05:15:21,564 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-11-30 05:15:21,564 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-30 05:15:21,637 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-11-30 05:15:21,638 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [277599413] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-30 05:15:21,638 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2023-11-30 05:15:21,638 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 5, 5] total 13 [2023-11-30 05:15:21,638 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1876990536] [2023-11-30 05:15:21,638 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2023-11-30 05:15:21,639 INFO L576 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2023-11-30 05:15:21,639 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-11-30 05:15:21,639 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2023-11-30 05:15:21,639 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=56, Invalid=126, Unknown=0, NotChecked=0, Total=182 [2023-11-30 05:15:21,640 INFO L497 CegarLoopForPetriNet]: Number of universal loopers: 166 out of 248 [2023-11-30 05:15:21,645 INFO L103 encePairwiseOnDemand]: Start differencePairwiseOnDemand. First operand has 217 places, 249 transitions, 882 flow. Second operand has 14 states, 14 states have (on average 168.57142857142858) internal successors, (2360), 14 states have internal predecessors, (2360), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-11-30 05:15:21,646 INFO L112 encePairwiseOnDemand]: Universal subtrahend loopers provided by user. [2023-11-30 05:15:21,646 INFO L113 encePairwiseOnDemand]: Number of universal subtrahend loopers: 166 of 248 [2023-11-30 05:15:21,646 INFO L73 FinitePrefix]: Start finitePrefix. Operand will be constructed on-demand [2023-11-30 05:15:35,410 INFO L124 PetriNetUnfolderBase]: 54694/129480 cut-off events. [2023-11-30 05:15:35,410 INFO L125 PetriNetUnfolderBase]: For 53727/62035 co-relation queries the response was YES. [2023-11-30 05:15:36,231 INFO L83 FinitePrefix]: Finished finitePrefix Result has 340673 conditions, 129480 events. 54694/129480 cut-off events. For 53727/62035 co-relation queries the response was YES. Maximal size of possible extension queue 3247. Compared 1686387 event pairs, 2802 based on Foata normal form. 4/122499 useless extension candidates. Maximal degree in co-relation 53359. Up to 61353 conditions per place. [2023-11-30 05:15:36,970 INFO L140 encePairwiseOnDemand]: 239/248 looper letters, 102 selfloop transitions, 10 changer transitions 37/305 dead transitions. [2023-11-30 05:15:36,970 INFO L145 encePairwiseOnDemand]: Finished differencePairwiseOnDemand. Result has 226 places, 305 transitions, 1496 flow [2023-11-30 05:15:36,971 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2023-11-30 05:15:36,971 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 10 states. [2023-11-30 05:15:36,973 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 10 states to 10 states and 1795 transitions. [2023-11-30 05:15:36,973 INFO L542 CegarLoopForPetriNet]: DFA transition density 0.7237903225806451 [2023-11-30 05:15:36,973 INFO L72 ComplementDD]: Start complementDD. Operand 10 states and 1795 transitions. [2023-11-30 05:15:36,973 INFO L73 IsDeterministic]: Start isDeterministic. Operand 10 states and 1795 transitions. [2023-11-30 05:15:36,974 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2023-11-30 05:15:36,974 INFO L117 ReachableStatesCopy]: Start reachableStatesCopy. Operand 10 states and 1795 transitions. [2023-11-30 05:15:36,976 INFO L343 DoubleDeckerVisitor]: Before removal of dead ends has 11 states, 10 states have (on average 179.5) internal successors, (1795), 10 states have internal predecessors, (1795), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-11-30 05:15:36,979 INFO L131 ReachableStatesCopy]: Finished reachableStatesCopy Result has 11 states, 11 states have (on average 248.0) internal successors, (2728), 11 states have internal predecessors, (2728), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-11-30 05:15:36,979 INFO L81 ComplementDD]: Finished complementDD. Result has 11 states, 11 states have (on average 248.0) internal successors, (2728), 11 states have internal predecessors, (2728), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-11-30 05:15:36,979 INFO L307 CegarLoopForPetriNet]: 226 programPoint places, 0 predicate places. [2023-11-30 05:15:36,979 INFO L500 AbstractCegarLoop]: Abstraction has has 226 places, 305 transitions, 1496 flow [2023-11-30 05:15:36,980 INFO L501 AbstractCegarLoop]: INTERPOLANT automaton has has 14 states, 14 states have (on average 168.57142857142858) internal successors, (2360), 14 states have internal predecessors, (2360), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-11-30 05:15:36,980 INFO L224 CegarLoopForPetriNet]: Found error trace [2023-11-30 05:15:36,980 INFO L232 CegarLoopForPetriNet]: trace histogram [4, 4, 4, 3, 3, 3, 3, 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, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-30 05:15:36,984 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Forceful destruction successful, exit code 0 [2023-11-30 05:15:37,184 WARN L482 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable16 [2023-11-30 05:15:37,184 INFO L425 AbstractCegarLoop]: === Iteration 4 === Targeting ULTIMATE.startErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE === [ULTIMATE.startErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr2REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 2 more)] === [2023-11-30 05:15:37,185 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-30 05:15:37,185 INFO L85 PathProgramCache]: Analyzing trace with hash 1886860791, now seen corresponding path program 1 times [2023-11-30 05:15:37,185 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-11-30 05:15:37,185 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1428408789] [2023-11-30 05:15:37,185 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-30 05:15:37,185 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-30 05:15:37,197 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-30 05:15:37,630 INFO L134 CoverageAnalysis]: Checked inductivity of 42 backedges. 20 proven. 22 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-11-30 05:15:37,630 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-11-30 05:15:37,631 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1428408789] [2023-11-30 05:15:37,631 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1428408789] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-30 05:15:37,631 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [342088629] [2023-11-30 05:15:37,631 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-30 05:15:37,631 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-30 05:15:37,631 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-11-30 05:15:37,632 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) [2023-11-30 05:15:37,634 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2023-11-30 05:15:37,719 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-30 05:15:37,720 INFO L262 TraceCheckSpWp]: Trace formula consists of 173 conjuncts, 19 conjunts are in the unsatisfiable core [2023-11-30 05:15:37,721 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-30 05:15:37,725 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 1 [2023-11-30 05:15:37,908 INFO L134 CoverageAnalysis]: Checked inductivity of 42 backedges. 0 proven. 42 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-11-30 05:15:37,908 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-30 05:15:38,099 INFO L134 CoverageAnalysis]: Checked inductivity of 42 backedges. 0 proven. 42 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-11-30 05:15:38,100 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [342088629] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-30 05:15:38,100 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2023-11-30 05:15:38,100 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 9, 9] total 26 [2023-11-30 05:15:38,100 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1487187839] [2023-11-30 05:15:38,100 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2023-11-30 05:15:38,100 INFO L576 AbstractCegarLoop]: INTERPOLANT automaton has 27 states [2023-11-30 05:15:38,100 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-11-30 05:15:38,101 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 27 interpolants. [2023-11-30 05:15:38,101 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=134, Invalid=568, Unknown=0, NotChecked=0, Total=702 [2023-11-30 05:15:38,103 INFO L497 CegarLoopForPetriNet]: Number of universal loopers: 166 out of 248 [2023-11-30 05:15:38,105 INFO L103 encePairwiseOnDemand]: Start differencePairwiseOnDemand. First operand has 226 places, 305 transitions, 1496 flow. Second operand has 27 states, 27 states have (on average 168.66666666666666) internal successors, (4554), 27 states have internal predecessors, (4554), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-11-30 05:15:38,105 INFO L112 encePairwiseOnDemand]: Universal subtrahend loopers provided by user. [2023-11-30 05:15:38,105 INFO L113 encePairwiseOnDemand]: Number of universal subtrahend loopers: 166 of 248 [2023-11-30 05:15:38,106 INFO L73 FinitePrefix]: Start finitePrefix. Operand will be constructed on-demand [2023-11-30 05:15:41,117 INFO L124 PetriNetUnfolderBase]: 13440/23610 cut-off events. [2023-11-30 05:15:41,118 INFO L125 PetriNetUnfolderBase]: For 30448/36047 co-relation queries the response was YES. [2023-11-30 05:15:41,186 INFO L83 FinitePrefix]: Finished finitePrefix Result has 92980 conditions, 23610 events. 13440/23610 cut-off events. For 30448/36047 co-relation queries the response was YES. Maximal size of possible extension queue 949. Compared 205604 event pairs, 99 based on Foata normal form. 682/23949 useless extension candidates. Maximal degree in co-relation 14971. Up to 17327 conditions per place. [2023-11-30 05:15:41,331 INFO L140 encePairwiseOnDemand]: 241/248 looper letters, 184 selfloop transitions, 14 changer transitions 0/295 dead transitions. [2023-11-30 05:15:41,331 INFO L145 encePairwiseOnDemand]: Finished differencePairwiseOnDemand. Result has 168 places, 295 transitions, 2160 flow [2023-11-30 05:15:41,331 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2023-11-30 05:15:41,331 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 16 states. [2023-11-30 05:15:41,334 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 16 states to 16 states and 2830 transitions. [2023-11-30 05:15:41,335 INFO L542 CegarLoopForPetriNet]: DFA transition density 0.7132056451612904 [2023-11-30 05:15:41,335 INFO L72 ComplementDD]: Start complementDD. Operand 16 states and 2830 transitions. [2023-11-30 05:15:41,335 INFO L73 IsDeterministic]: Start isDeterministic. Operand 16 states and 2830 transitions. [2023-11-30 05:15:41,336 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2023-11-30 05:15:41,336 INFO L117 ReachableStatesCopy]: Start reachableStatesCopy. Operand 16 states and 2830 transitions. [2023-11-30 05:15:41,339 INFO L343 DoubleDeckerVisitor]: Before removal of dead ends has 17 states, 16 states have (on average 176.875) internal successors, (2830), 16 states have internal predecessors, (2830), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-11-30 05:15:41,342 INFO L131 ReachableStatesCopy]: Finished reachableStatesCopy Result has 17 states, 17 states have (on average 248.0) internal successors, (4216), 17 states have internal predecessors, (4216), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-11-30 05:15:41,343 INFO L81 ComplementDD]: Finished complementDD. Result has 17 states, 17 states have (on average 248.0) internal successors, (4216), 17 states have internal predecessors, (4216), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-11-30 05:15:41,343 INFO L307 CegarLoopForPetriNet]: 226 programPoint places, -58 predicate places. [2023-11-30 05:15:41,343 INFO L500 AbstractCegarLoop]: Abstraction has has 168 places, 295 transitions, 2160 flow [2023-11-30 05:15:41,344 INFO L501 AbstractCegarLoop]: INTERPOLANT automaton has has 27 states, 27 states have (on average 168.66666666666666) internal successors, (4554), 27 states have internal predecessors, (4554), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-11-30 05:15:41,344 INFO L224 CegarLoopForPetriNet]: Found error trace [2023-11-30 05:15:41,344 INFO L232 CegarLoopForPetriNet]: trace histogram [5, 5, 5, 5, 4, 4, 4, 4, 4, 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, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-30 05:15:41,348 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Forceful destruction successful, exit code 0 [2023-11-30 05:15:41,548 WARN L482 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable17 [2023-11-30 05:15:41,548 INFO L425 AbstractCegarLoop]: === Iteration 5 === Targeting ULTIMATE.startErr0INUSE_VIOLATIONSUFFICIENT_THREAD_INSTANCES === [ULTIMATE.startErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr2REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 2 more)] === [2023-11-30 05:15:41,549 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-30 05:15:41,549 INFO L85 PathProgramCache]: Analyzing trace with hash 1038565342, now seen corresponding path program 1 times [2023-11-30 05:15:41,549 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-11-30 05:15:41,549 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [857543094] [2023-11-30 05:15:41,549 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-30 05:15:41,550 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-30 05:15:41,577 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2023-11-30 05:15:41,578 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2023-11-30 05:15:41,583 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2023-11-30 05:15:41,589 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2023-11-30 05:15:41,589 INFO L372 BasicCegarLoop]: Counterexample is feasible [2023-11-30 05:15:41,589 INFO L810 garLoopResultBuilder]: Registering result UNSAFE for location ULTIMATE.startErr0INUSE_VIOLATIONSUFFICIENT_THREAD_INSTANCES (4 of 5 remaining) [2023-11-30 05:15:41,589 INFO L810 garLoopResultBuilder]: Registering result UNKNOWN for location ULTIMATE.startErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE (3 of 5 remaining) [2023-11-30 05:15:41,589 INFO L810 garLoopResultBuilder]: Registering result UNKNOWN for location ULTIMATE.startErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE (2 of 5 remaining) [2023-11-30 05:15:41,589 INFO L810 garLoopResultBuilder]: Registering result UNKNOWN for location ULTIMATE.startErr2REQUIRES_VIOLATIONMEMORY_DEREFERENCE (1 of 5 remaining) [2023-11-30 05:15:41,590 INFO L810 garLoopResultBuilder]: Registering result UNKNOWN for location ULTIMATE.startErr3REQUIRES_VIOLATIONMEMORY_DEREFERENCE (0 of 5 remaining) [2023-11-30 05:15:41,590 WARN L482 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable18 [2023-11-30 05:15:41,590 INFO L457 BasicCegarLoop]: Path program histogram: [1, 1, 1, 1, 1] [2023-11-30 05:15:41,590 WARN L227 ceAbstractionStarter]: 4 thread instances were not sufficient, I will increase this number and restart the analysis [2023-11-30 05:15:41,590 INFO L508 ceAbstractionStarter]: Constructing petrified ICFG for 5 thread instances. [2023-11-30 05:15:41,622 INFO L144 ThreadInstanceAdder]: Constructed 5 joinOtherThreadTransitions. [2023-11-30 05:15:41,624 INFO L73 FinitePrefix]: Start finitePrefix. Operand has 253 places, 278 transitions, 611 flow [2023-11-30 05:15:41,769 INFO L124 PetriNetUnfolderBase]: 166/1261 cut-off events. [2023-11-30 05:15:41,769 INFO L125 PetriNetUnfolderBase]: For 110/110 co-relation queries the response was YES. [2023-11-30 05:15:41,780 INFO L83 FinitePrefix]: Finished finitePrefix Result has 1367 conditions, 1261 events. 166/1261 cut-off events. For 110/110 co-relation queries the response was YES. Maximal size of possible extension queue 26. Compared 6780 event pairs, 23 based on Foata normal form. 0/1035 useless extension candidates. Maximal degree in co-relation 879. Up to 80 conditions per place. [2023-11-30 05:15:41,780 INFO L82 GeneralOperation]: Start removeDead. Operand has 253 places, 278 transitions, 611 flow [2023-11-30 05:15:41,786 INFO L88 GeneralOperation]: Finished RemoveDead, result has has 253 places, 278 transitions, 611 flow [2023-11-30 05:15:41,787 INFO L361 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2023-11-30 05:15:41,787 INFO L362 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, mHoare=true, 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;@439001fb, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2023-11-30 05:15:41,787 INFO L363 AbstractCegarLoop]: Starting to check reachability of 5 error locations. [2023-11-30 05:15:41,788 INFO L185 PetriNetUnfolderBase]: Found word, exiting Unfolder. [2023-11-30 05:15:41,788 INFO L124 PetriNetUnfolderBase]: 1/40 cut-off events. [2023-11-30 05:15:41,788 INFO L125 PetriNetUnfolderBase]: For 0/0 co-relation queries the response was YES. [2023-11-30 05:15:41,788 INFO L224 CegarLoopForPetriNet]: Found error trace [2023-11-30 05:15:41,789 INFO L232 CegarLoopForPetriNet]: trace histogram [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, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-30 05:15:41,789 INFO L425 AbstractCegarLoop]: === Iteration 1 === Targeting ULTIMATE.startErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE === [ULTIMATE.startErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr2REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 2 more)] === [2023-11-30 05:15:41,789 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-30 05:15:41,789 INFO L85 PathProgramCache]: Analyzing trace with hash -978798578, now seen corresponding path program 1 times [2023-11-30 05:15:41,789 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-11-30 05:15:41,789 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1763180267] [2023-11-30 05:15:41,789 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-30 05:15:41,789 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-30 05:15:41,793 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-30 05:15:41,822 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-11-30 05:15:41,822 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-11-30 05:15:41,823 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1763180267] [2023-11-30 05:15:41,823 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1763180267] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-30 05:15:41,823 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-11-30 05:15:41,823 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2023-11-30 05:15:41,823 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2072088458] [2023-11-30 05:15:41,823 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-30 05:15:41,823 INFO L576 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2023-11-30 05:15:41,823 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-11-30 05:15:41,824 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2023-11-30 05:15:41,824 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2023-11-30 05:15:41,824 INFO L497 CegarLoopForPetriNet]: Number of universal loopers: 191 out of 278 [2023-11-30 05:15:41,824 INFO L103 encePairwiseOnDemand]: Start differencePairwiseOnDemand. First operand has 253 places, 278 transitions, 611 flow. Second operand has 3 states, 3 states have (on average 194.0) internal successors, (582), 3 states have internal predecessors, (582), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-11-30 05:15:41,825 INFO L112 encePairwiseOnDemand]: Universal subtrahend loopers provided by user. [2023-11-30 05:15:41,825 INFO L113 encePairwiseOnDemand]: Number of universal subtrahend loopers: 191 of 278 [2023-11-30 05:15:41,825 INFO L73 FinitePrefix]: Start finitePrefix. Operand will be constructed on-demand [2023-11-30 05:17:10,517 INFO L124 PetriNetUnfolderBase]: 278914/599728 cut-off events. [2023-11-30 05:17:10,518 INFO L125 PetriNetUnfolderBase]: For 29878/29878 co-relation queries the response was YES. [2023-11-30 05:17:14,999 INFO L83 FinitePrefix]: Finished finitePrefix Result has 966592 conditions, 599728 events. 278914/599728 cut-off events. For 29878/29878 co-relation queries the response was YES. Maximal size of possible extension queue 15281. Compared 8698026 event pairs, 196787 based on Foata normal form. 230730/787053 useless extension candidates. Maximal degree in co-relation 155440. Up to 254166 conditions per place. [2023-11-30 05:17:18,008 INFO L140 encePairwiseOnDemand]: 245/278 looper letters, 47 selfloop transitions, 1 changer transitions 25/252 dead transitions. [2023-11-30 05:17:18,008 INFO L145 encePairwiseOnDemand]: Finished differencePairwiseOnDemand. Result has 238 places, 252 transitions, 701 flow [2023-11-30 05:17:18,008 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2023-11-30 05:17:18,008 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 3 states. [2023-11-30 05:17:18,009 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 3 states to 3 states and 695 transitions. [2023-11-30 05:17:18,010 INFO L542 CegarLoopForPetriNet]: DFA transition density 0.8333333333333334 [2023-11-30 05:17:18,010 INFO L72 ComplementDD]: Start complementDD. Operand 3 states and 695 transitions. [2023-11-30 05:17:18,010 INFO L73 IsDeterministic]: Start isDeterministic. Operand 3 states and 695 transitions. [2023-11-30 05:17:18,010 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2023-11-30 05:17:18,010 INFO L117 ReachableStatesCopy]: Start reachableStatesCopy. Operand 3 states and 695 transitions. [2023-11-30 05:17:18,011 INFO L343 DoubleDeckerVisitor]: Before removal of dead ends has 4 states, 3 states have (on average 231.66666666666666) internal successors, (695), 3 states have internal predecessors, (695), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-11-30 05:17:18,012 INFO L131 ReachableStatesCopy]: Finished reachableStatesCopy Result has 4 states, 4 states have (on average 278.0) internal successors, (1112), 4 states have internal predecessors, (1112), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-11-30 05:17:18,012 INFO L81 ComplementDD]: Finished complementDD. Result has 4 states, 4 states have (on average 278.0) internal successors, (1112), 4 states have internal predecessors, (1112), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-11-30 05:17:18,012 INFO L307 CegarLoopForPetriNet]: 253 programPoint places, -15 predicate places. [2023-11-30 05:17:18,012 INFO L500 AbstractCegarLoop]: Abstraction has has 238 places, 252 transitions, 701 flow [2023-11-30 05:17:18,012 INFO L501 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 194.0) internal successors, (582), 3 states have internal predecessors, (582), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-11-30 05:17:18,013 INFO L224 CegarLoopForPetriNet]: Found error trace [2023-11-30 05:17:18,013 INFO L232 CegarLoopForPetriNet]: trace histogram [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, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-30 05:17:18,013 WARN L482 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable19 [2023-11-30 05:17:18,013 INFO L425 AbstractCegarLoop]: === Iteration 2 === Targeting ULTIMATE.startErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE === [ULTIMATE.startErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr2REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 2 more)] === [2023-11-30 05:17:18,013 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-30 05:17:18,013 INFO L85 PathProgramCache]: Analyzing trace with hash -978798577, now seen corresponding path program 1 times [2023-11-30 05:17:18,013 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-11-30 05:17:18,013 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [797034978] [2023-11-30 05:17:18,013 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-30 05:17:18,013 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-30 05:17:18,019 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-30 05:17:18,050 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-11-30 05:17:18,050 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-11-30 05:17:18,050 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [797034978] [2023-11-30 05:17:18,050 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [797034978] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-30 05:17:18,051 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-11-30 05:17:18,051 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2023-11-30 05:17:18,051 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1818410475] [2023-11-30 05:17:18,051 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-30 05:17:18,051 INFO L576 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2023-11-30 05:17:18,051 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-11-30 05:17:18,051 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2023-11-30 05:17:18,051 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=6, Invalid=6, Unknown=0, NotChecked=0, Total=12 [2023-11-30 05:17:18,052 INFO L497 CegarLoopForPetriNet]: Number of universal loopers: 186 out of 278 [2023-11-30 05:17:18,052 INFO L103 encePairwiseOnDemand]: Start differencePairwiseOnDemand. First operand has 238 places, 252 transitions, 701 flow. Second operand has 4 states, 4 states have (on average 188.5) internal successors, (754), 4 states have internal predecessors, (754), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-11-30 05:17:18,052 INFO L112 encePairwiseOnDemand]: Universal subtrahend loopers provided by user. [2023-11-30 05:17:18,052 INFO L113 encePairwiseOnDemand]: Number of universal subtrahend loopers: 186 of 278 [2023-11-30 05:17:18,052 INFO L73 FinitePrefix]: Start finitePrefix. Operand will be constructed on-demand