/usr/bin/java -Xmx16000000000 -Xss4m -jar ./plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata ./data -s ../../../trunk/examples/settings/automizer/concurrent/svcomp-Reach-32bit-Automizer_Default-noMmResRef-PN-VariableLbe.epf -tc ../../../trunk/examples/toolchains/AutomizerCInline.xml --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_06-cond_racing1.i -------------------------------------------------------------------------------- This is Ultimate 0.2.3-dev-ac9dbd0-m [2023-08-26 12:31:26,765 INFO L188 SettingsManager]: Resetting all preferences to default values... [2023-08-26 12:31:26,849 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-VariableLbe.epf [2023-08-26 12:31:26,853 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2023-08-26 12:31:26,854 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.Checked method. Library mode if empty. [2023-08-26 12:31:26,883 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2023-08-26 12:31:26,883 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2023-08-26 12:31:26,888 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2023-08-26 12:31:26,889 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2023-08-26 12:31:26,892 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2023-08-26 12:31:26,892 INFO L153 SettingsManager]: * Use SBE=true [2023-08-26 12:31:26,893 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2023-08-26 12:31:26,893 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2023-08-26 12:31:26,894 INFO L153 SettingsManager]: * sizeof long=4 [2023-08-26 12:31:26,894 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2023-08-26 12:31:26,894 INFO L153 SettingsManager]: * sizeof POINTER=4 [2023-08-26 12:31:26,894 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2023-08-26 12:31:26,895 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2023-08-26 12:31:26,895 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2023-08-26 12:31:26,895 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2023-08-26 12:31:26,895 INFO L153 SettingsManager]: * sizeof long double=12 [2023-08-26 12:31:26,896 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2023-08-26 12:31:26,896 INFO L153 SettingsManager]: * Use constant arrays=true [2023-08-26 12:31:26,896 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2023-08-26 12:31:26,896 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2023-08-26 12:31:26,897 INFO L153 SettingsManager]: * To the following directory=./dump/ [2023-08-26 12:31:26,897 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2023-08-26 12:31:26,897 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2023-08-26 12:31:26,897 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2023-08-26 12:31:26,898 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2023-08-26 12:31:26,898 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2023-08-26 12:31:26,899 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2023-08-26 12:31:26,899 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2023-08-26 12:31:26,899 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2023-08-26 12:31:26,899 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2023-08-26 12:31:26,899 INFO L153 SettingsManager]: * Independence relation used for large block encoding in concurrent analysis=SYNTACTIC WARNING: An illegal reflective access operation has occurred WARNING: Illegal reflective access by com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 (file:/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/com.sun.xml.bind_2.2.0.v201505121915.jar) to method java.lang.ClassLoader.defineClass(java.lang.String,byte[],int,int) WARNING: Please consider reporting this to the maintainers of com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 WARNING: Use --illegal-access=warn to enable warnings of further illegal reflective access operations WARNING: All illegal access operations will be denied in a future release Applying setting for plugin de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator: 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-08-26 12:31:27,198 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2023-08-26 12:31:27,215 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2023-08-26 12:31:27,217 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2023-08-26 12:31:27,218 INFO L270 PluginConnector]: Initializing CDTParser... [2023-08-26 12:31:27,218 INFO L274 PluginConnector]: CDTParser initialized [2023-08-26 12:31:27,220 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/svcomp/goblint-regression/28-race_reach_06-cond_racing1.i [2023-08-26 12:31:28,389 INFO L533 CDTParser]: Created temporary CDT project at NULL [2023-08-26 12:31:28,671 INFO L384 CDTParser]: Found 1 translation units. [2023-08-26 12:31:28,672 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/trunk/examples/svcomp/goblint-regression/28-race_reach_06-cond_racing1.i [2023-08-26 12:31:28,690 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/b9bc92dcb/64c3d17d4d904eaeb89074e4df15cf10/FLAG4a64aec37 [2023-08-26 12:31:28,705 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/b9bc92dcb/64c3d17d4d904eaeb89074e4df15cf10 [2023-08-26 12:31:28,709 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2023-08-26 12:31:28,711 INFO L133 ToolchainWalker]: Walking toolchain with 5 elements. [2023-08-26 12:31:28,713 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2023-08-26 12:31:28,713 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2023-08-26 12:31:28,716 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2023-08-26 12:31:28,716 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 26.08 12:31:28" (1/1) ... [2023-08-26 12:31:28,717 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@48dfa032 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 26.08 12:31:28, skipping insertion in model container [2023-08-26 12:31:28,717 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 26.08 12:31:28" (1/1) ... [2023-08-26 12:31:28,766 INFO L176 MainTranslator]: Built tables and reachable declarations [2023-08-26 12:31:29,148 INFO L209 PostProcessor]: Analyzing one entry point: main [2023-08-26 12:31:29,161 INFO L201 MainTranslator]: Completed pre-run [2023-08-26 12:31:29,171 WARN L75 lationResultReporter]: Unsoundness Warning: unspecified type, defaulting to int C: unsigned short [119] [2023-08-26 12:31:29,189 WARN L75 lationResultReporter]: Unsoundness Warning: unspecified type, defaulting to int C: short [481] [2023-08-26 12:31:29,189 WARN L75 lationResultReporter]: Unsoundness Warning: unspecified type, defaulting to int C: short [481] [2023-08-26 12:31:29,210 INFO L209 PostProcessor]: Analyzing one entry point: main [2023-08-26 12:31:29,262 INFO L206 MainTranslator]: Completed translation [2023-08-26 12:31:29,263 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 26.08 12:31:29 WrapperNode [2023-08-26 12:31:29,263 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2023-08-26 12:31:29,264 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2023-08-26 12:31:29,264 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2023-08-26 12:31:29,264 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2023-08-26 12:31:29,270 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 26.08 12:31:29" (1/1) ... [2023-08-26 12:31:29,287 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 26.08 12:31:29" (1/1) ... [2023-08-26 12:31:29,309 INFO L138 Inliner]: procedures = 270, calls = 37, calls flagged for inlining = 4, calls inlined = 4, statements flattened = 94 [2023-08-26 12:31:29,310 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2023-08-26 12:31:29,310 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2023-08-26 12:31:29,310 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2023-08-26 12:31:29,310 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2023-08-26 12:31:29,318 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 26.08 12:31:29" (1/1) ... [2023-08-26 12:31:29,318 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 26.08 12:31:29" (1/1) ... [2023-08-26 12:31:29,322 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 26.08 12:31:29" (1/1) ... [2023-08-26 12:31:29,322 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 26.08 12:31:29" (1/1) ... [2023-08-26 12:31:29,327 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 26.08 12:31:29" (1/1) ... [2023-08-26 12:31:29,330 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 26.08 12:31:29" (1/1) ... [2023-08-26 12:31:29,332 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 26.08 12:31:29" (1/1) ... [2023-08-26 12:31:29,333 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 26.08 12:31:29" (1/1) ... [2023-08-26 12:31:29,336 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2023-08-26 12:31:29,336 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2023-08-26 12:31:29,337 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2023-08-26 12:31:29,337 INFO L274 PluginConnector]: RCFGBuilder initialized [2023-08-26 12:31:29,337 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 26.08 12:31:29" (1/1) ... [2023-08-26 12:31:29,342 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2023-08-26 12:31:29,353 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-08-26 12:31:29,374 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-08-26 12:31:29,407 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-08-26 12:31:29,421 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnStack [2023-08-26 12:31:29,422 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2023-08-26 12:31:29,422 INFO L130 BoogieDeclarations]: Found specification of procedure read~int [2023-08-26 12:31:29,423 INFO L130 BoogieDeclarations]: Found specification of procedure write~int [2023-08-26 12:31:29,423 INFO L130 BoogieDeclarations]: Found specification of procedure #PthreadsMutexLock [2023-08-26 12:31:29,423 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2023-08-26 12:31:29,423 INFO L130 BoogieDeclarations]: Found specification of procedure t_fun [2023-08-26 12:31:29,423 INFO L138 BoogieDeclarations]: Found implementation of procedure t_fun [2023-08-26 12:31:29,423 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2023-08-26 12:31:29,424 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2023-08-26 12:31:29,424 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2023-08-26 12:31:29,425 WARN L210 CfgBuilder]: User set CodeBlockSize to SequenceOfStatements but program contains fork statements. Overwriting the user preferences and setting CodeBlockSize to OneNontrivialStatement [2023-08-26 12:31:29,543 INFO L236 CfgBuilder]: Building ICFG [2023-08-26 12:31:29,545 INFO L262 CfgBuilder]: Building CFG for each procedure with an implementation [2023-08-26 12:31:29,741 INFO L277 CfgBuilder]: Performing block encoding [2023-08-26 12:31:29,748 INFO L297 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2023-08-26 12:31:29,748 INFO L302 CfgBuilder]: Removed 10 assume(true) statements. [2023-08-26 12:31:29,750 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 26.08 12:31:29 BoogieIcfgContainer [2023-08-26 12:31:29,750 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2023-08-26 12:31:29,752 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2023-08-26 12:31:29,752 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2023-08-26 12:31:29,755 INFO L274 PluginConnector]: TraceAbstraction initialized [2023-08-26 12:31:29,755 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 26.08 12:31:28" (1/3) ... [2023-08-26 12:31:29,756 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@37b2fc0a and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 26.08 12:31:29, skipping insertion in model container [2023-08-26 12:31:29,756 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 26.08 12:31:29" (2/3) ... [2023-08-26 12:31:29,756 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@37b2fc0a and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 26.08 12:31:29, skipping insertion in model container [2023-08-26 12:31:29,756 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 26.08 12:31:29" (3/3) ... [2023-08-26 12:31:29,757 INFO L112 eAbstractionObserver]: Analyzing ICFG 28-race_reach_06-cond_racing1.i [2023-08-26 12:31:29,771 INFO L203 ceAbstractionStarter]: Automizer settings: Hoare:false NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2023-08-26 12:31:29,772 INFO L162 ceAbstractionStarter]: Applying trace abstraction to program that has 5 error locations. [2023-08-26 12:31:29,772 INFO L515 ceAbstractionStarter]: Constructing petrified ICFG for 1 thread instances. [2023-08-26 12:31:29,818 INFO L144 ThreadInstanceAdder]: Constructed 1 joinOtherThreadTransitions. [2023-08-26 12:31:29,848 INFO L73 FinitePrefix]: Start finitePrefix. Operand has 116 places, 129 transitions, 266 flow [2023-08-26 12:31:29,903 INFO L124 PetriNetUnfolderBase]: 25/181 cut-off events. [2023-08-26 12:31:29,903 INFO L125 PetriNetUnfolderBase]: For 1/1 co-relation queries the response was YES. [2023-08-26 12:31:29,909 INFO L83 FinitePrefix]: Finished finitePrefix Result has 187 conditions, 181 events. 25/181 cut-off events. For 1/1 co-relation queries the response was YES. Maximal size of possible extension queue 11. Compared 458 event pairs, 0 based on Foata normal form. 0/143 useless extension candidates. Maximal degree in co-relation 89. Up to 6 conditions per place. [2023-08-26 12:31:29,910 INFO L82 GeneralOperation]: Start removeDead. Operand has 116 places, 129 transitions, 266 flow [2023-08-26 12:31:29,914 INFO L88 GeneralOperation]: Finished RemoveDead, result has has 116 places, 129 transitions, 266 flow [2023-08-26 12:31:29,917 INFO L124 etLargeBlockEncoding]: Petri net LBE is using variable-based independence relation. [2023-08-26 12:31:29,925 INFO L131 etLargeBlockEncoding]: Starting large block encoding on Petri net that has 116 places, 129 transitions, 266 flow [2023-08-26 12:31:29,927 INFO L113 LiptonReduction]: Starting Lipton reduction on Petri net that has 116 places, 129 transitions, 266 flow [2023-08-26 12:31:29,927 INFO L73 FinitePrefix]: Start finitePrefix. Operand has 116 places, 129 transitions, 266 flow [2023-08-26 12:31:29,960 INFO L124 PetriNetUnfolderBase]: 25/181 cut-off events. [2023-08-26 12:31:29,960 INFO L125 PetriNetUnfolderBase]: For 1/1 co-relation queries the response was YES. [2023-08-26 12:31:29,961 INFO L83 FinitePrefix]: Finished finitePrefix Result has 187 conditions, 181 events. 25/181 cut-off events. For 1/1 co-relation queries the response was YES. Maximal size of possible extension queue 11. Compared 458 event pairs, 0 based on Foata normal form. 0/143 useless extension candidates. Maximal degree in co-relation 89. Up to 6 conditions per place. [2023-08-26 12:31:29,963 INFO L119 LiptonReduction]: Number of co-enabled transitions 3248 [2023-08-26 12:31:33,238 INFO L134 LiptonReduction]: Checked pairs total: 5659 [2023-08-26 12:31:33,239 INFO L136 LiptonReduction]: Total number of compositions: 122 [2023-08-26 12:31:33,250 INFO L356 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2023-08-26 12:31:33,256 INFO L357 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=false, mAutomataTypeConcurrency=PETRI_NET, mHoareTripleChecks=INCREMENTAL, mHoareAnnotationPositions=LoopsAndPotentialCycles, 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;@44a04137, mLbeIndependenceSettings=[IndependenceType=SYNTACTIC, AbstractionType=NONE, UseConditional=, UseSemiCommutativity=, Solver=, SolverTimeout=] [2023-08-26 12:31:33,256 INFO L358 AbstractCegarLoop]: Starting to check reachability of 6 error locations. [2023-08-26 12:31:33,258 INFO L185 PetriNetUnfolderBase]: Found word, exiting Unfolder. [2023-08-26 12:31:33,258 INFO L124 PetriNetUnfolderBase]: 0/2 cut-off events. [2023-08-26 12:31:33,258 INFO L125 PetriNetUnfolderBase]: For 0/0 co-relation queries the response was YES. [2023-08-26 12:31:33,258 INFO L200 CegarLoopForPetriNet]: Found error trace [2023-08-26 12:31:33,259 INFO L208 CegarLoopForPetriNet]: trace histogram [1, 1] [2023-08-26 12:31:33,259 INFO L420 AbstractCegarLoop]: === Iteration 1 === Targeting ULTIMATE.startErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE === [ULTIMATE.startErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr3REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 3 more)] === [2023-08-26 12:31:33,263 INFO L145 PredicateUnifier]: Initialized classic predicate unifier [2023-08-26 12:31:33,263 INFO L85 PathProgramCache]: Analyzing trace with hash 16221, now seen corresponding path program 1 times [2023-08-26 12:31:33,272 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-08-26 12:31:33,273 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [913337704] [2023-08-26 12:31:33,273 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-08-26 12:31:33,273 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-08-26 12:31:33,380 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-08-26 12:31:33,620 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-08-26 12:31:33,620 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-08-26 12:31:33,621 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [913337704] [2023-08-26 12:31:33,621 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [913337704] provided 1 perfect and 0 imperfect interpolant sequences [2023-08-26 12:31:33,622 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-08-26 12:31:33,622 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [1] imperfect sequences [] total 1 [2023-08-26 12:31:33,623 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1313016094] [2023-08-26 12:31:33,623 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-08-26 12:31:33,630 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2023-08-26 12:31:33,634 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-08-26 12:31:33,655 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2023-08-26 12:31:33,656 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2023-08-26 12:31:33,658 INFO L471 CegarLoopForPetriNet]: Number of universal loopers: 93 out of 251 [2023-08-26 12:31:33,663 INFO L103 encePairwiseOnDemand]: Start differencePairwiseOnDemand. First operand has 33 places, 42 transitions, 92 flow. Second operand has 3 states, 3 states have (on average 93.66666666666667) internal successors, (281), 3 states have internal predecessors, (281), 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-08-26 12:31:33,663 INFO L112 encePairwiseOnDemand]: Universal subtrahend loopers provided by user. [2023-08-26 12:31:33,663 INFO L113 encePairwiseOnDemand]: Number of universal subtrahend loopers: 93 of 251 [2023-08-26 12:31:33,664 INFO L73 FinitePrefix]: Start finitePrefix. Operand will be constructed on-demand [2023-08-26 12:31:33,787 INFO L124 PetriNetUnfolderBase]: 129/292 cut-off events. [2023-08-26 12:31:33,787 INFO L125 PetriNetUnfolderBase]: For 1/1 co-relation queries the response was YES. [2023-08-26 12:31:33,788 INFO L83 FinitePrefix]: Finished finitePrefix Result has 589 conditions, 292 events. 129/292 cut-off events. For 1/1 co-relation queries the response was YES. Maximal size of possible extension queue 22. Compared 1370 event pairs, 0 based on Foata normal form. 16/232 useless extension candidates. Maximal degree in co-relation 545. Up to 271 conditions per place. [2023-08-26 12:31:33,790 INFO L140 encePairwiseOnDemand]: 236/251 looper letters, 35 selfloop transitions, 2 changer transitions 1/40 dead transitions. [2023-08-26 12:31:33,791 INFO L145 encePairwiseOnDemand]: Finished differencePairwiseOnDemand. Result has 33 places, 40 transitions, 164 flow [2023-08-26 12:31:33,792 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2023-08-26 12:31:33,794 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 3 states. [2023-08-26 12:31:33,801 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 3 states to 3 states and 336 transitions. [2023-08-26 12:31:33,803 INFO L516 CegarLoopForPetriNet]: DFA transition density 0.44621513944223107 [2023-08-26 12:31:33,803 INFO L72 ComplementDD]: Start complementDD. Operand 3 states and 336 transitions. [2023-08-26 12:31:33,804 INFO L73 IsDeterministic]: Start isDeterministic. Operand 3 states and 336 transitions. [2023-08-26 12:31:33,805 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2023-08-26 12:31:33,807 INFO L117 ReachableStatesCopy]: Start reachableStatesCopy. Operand 3 states and 336 transitions. [2023-08-26 12:31:33,813 INFO L343 DoubleDeckerVisitor]: Before removal of dead ends has 4 states, 3 states have (on average 112.0) internal successors, (336), 3 states have internal predecessors, (336), 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-08-26 12:31:33,817 INFO L131 ReachableStatesCopy]: Finished reachableStatesCopy Result has 4 states, 4 states have (on average 251.0) internal successors, (1004), 4 states have internal predecessors, (1004), 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-08-26 12:31:33,818 INFO L81 ComplementDD]: Finished complementDD. Result has 4 states, 4 states have (on average 251.0) internal successors, (1004), 4 states have internal predecessors, (1004), 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-08-26 12:31:33,819 INFO L175 Difference]: Start difference. First operand has 33 places, 42 transitions, 92 flow. Second operand 3 states and 336 transitions. [2023-08-26 12:31:33,821 INFO L82 GeneralOperation]: Start removeRedundantFlow. Operand has 33 places, 40 transitions, 164 flow [2023-08-26 12:31:33,823 INFO L88 GeneralOperation]: Finished removeRedundantFlow, result has has 33 places, 40 transitions, 164 flow, removed 0 selfloop flow, removed 0 redundant places. [2023-08-26 12:31:33,825 INFO L231 Difference]: Finished difference. Result has 34 places, 29 transitions, 78 flow [2023-08-26 12:31:33,827 INFO L264 CegarLoopForPetriNet]: {PETRI_ALPHABET=251, PETRI_DIFFERENCE_MINUEND_FLOW=68, PETRI_DIFFERENCE_MINUEND_PLACES=31, PETRI_DIFFERENCE_MINUEND_TRANSITIONS=30, PETRI_DIFFERENCE_SUBTRAHEND_LETTERS_WITH_MORE_CHANGERS_THAN_LOOPERS=2, PETRI_DIFFERENCE_SUBTRAHEND_LOOPER_ONLY_LETTERS=28, PETRI_DIFFERENCE_SUBTRAHEND_STATES=3, PETRI_FLOW=78, PETRI_PLACES=34, PETRI_TRANSITIONS=29} [2023-08-26 12:31:33,830 INFO L281 CegarLoopForPetriNet]: 33 programPoint places, 1 predicate places. [2023-08-26 12:31:33,830 INFO L495 AbstractCegarLoop]: Abstraction has has 34 places, 29 transitions, 78 flow [2023-08-26 12:31:33,830 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 93.66666666666667) internal successors, (281), 3 states have internal predecessors, (281), 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-08-26 12:31:33,831 INFO L200 CegarLoopForPetriNet]: Found error trace [2023-08-26 12:31:33,831 INFO L208 CegarLoopForPetriNet]: trace histogram [1, 1] [2023-08-26 12:31:33,831 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2023-08-26 12:31:33,831 INFO L420 AbstractCegarLoop]: === Iteration 2 === Targeting ULTIMATE.startErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE === [ULTIMATE.startErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr3REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 3 more)] === [2023-08-26 12:31:33,832 INFO L145 PredicateUnifier]: Initialized classic predicate unifier [2023-08-26 12:31:33,832 INFO L85 PathProgramCache]: Analyzing trace with hash 16222, now seen corresponding path program 1 times [2023-08-26 12:31:33,832 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-08-26 12:31:33,832 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [944684015] [2023-08-26 12:31:33,832 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-08-26 12:31:33,833 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-08-26 12:31:33,859 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-08-26 12:31:33,914 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-08-26 12:31:33,914 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-08-26 12:31:33,914 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [944684015] [2023-08-26 12:31:33,914 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [944684015] provided 1 perfect and 0 imperfect interpolant sequences [2023-08-26 12:31:33,915 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-08-26 12:31:33,915 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [1] imperfect sequences [] total 1 [2023-08-26 12:31:33,915 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [552405644] [2023-08-26 12:31:33,915 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-08-26 12:31:33,916 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2023-08-26 12:31:33,916 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-08-26 12:31:33,917 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2023-08-26 12:31:33,917 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2023-08-26 12:31:33,917 INFO L471 CegarLoopForPetriNet]: Number of universal loopers: 98 out of 251 [2023-08-26 12:31:33,918 INFO L103 encePairwiseOnDemand]: Start differencePairwiseOnDemand. First operand has 34 places, 29 transitions, 78 flow. Second operand has 3 states, 3 states have (on average 98.66666666666667) internal successors, (296), 3 states have internal predecessors, (296), 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-08-26 12:31:33,918 INFO L112 encePairwiseOnDemand]: Universal subtrahend loopers provided by user. [2023-08-26 12:31:33,918 INFO L113 encePairwiseOnDemand]: Number of universal subtrahend loopers: 98 of 251 [2023-08-26 12:31:33,918 INFO L73 FinitePrefix]: Start finitePrefix. Operand will be constructed on-demand [2023-08-26 12:31:33,968 INFO L124 PetriNetUnfolderBase]: 105/232 cut-off events. [2023-08-26 12:31:33,968 INFO L125 PetriNetUnfolderBase]: For 17/17 co-relation queries the response was YES. [2023-08-26 12:31:33,969 INFO L83 FinitePrefix]: Finished finitePrefix Result has 515 conditions, 232 events. 105/232 cut-off events. For 17/17 co-relation queries the response was YES. Maximal size of possible extension queue 16. Compared 835 event pairs, 96 based on Foata normal form. 0/192 useless extension candidates. Maximal degree in co-relation 490. Up to 228 conditions per place. [2023-08-26 12:31:33,970 INFO L140 encePairwiseOnDemand]: 248/251 looper letters, 24 selfloop transitions, 1 changer transitions 0/27 dead transitions. [2023-08-26 12:31:33,970 INFO L145 encePairwiseOnDemand]: Finished differencePairwiseOnDemand. Result has 33 places, 27 transitions, 124 flow [2023-08-26 12:31:33,970 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2023-08-26 12:31:33,971 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 3 states. [2023-08-26 12:31:33,972 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 3 states to 3 states and 321 transitions. [2023-08-26 12:31:33,973 INFO L516 CegarLoopForPetriNet]: DFA transition density 0.4262948207171315 [2023-08-26 12:31:33,973 INFO L72 ComplementDD]: Start complementDD. Operand 3 states and 321 transitions. [2023-08-26 12:31:33,973 INFO L73 IsDeterministic]: Start isDeterministic. Operand 3 states and 321 transitions. [2023-08-26 12:31:33,974 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2023-08-26 12:31:33,974 INFO L117 ReachableStatesCopy]: Start reachableStatesCopy. Operand 3 states and 321 transitions. [2023-08-26 12:31:33,975 INFO L343 DoubleDeckerVisitor]: Before removal of dead ends has 4 states, 3 states have (on average 107.0) internal successors, (321), 3 states have internal predecessors, (321), 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-08-26 12:31:33,976 INFO L131 ReachableStatesCopy]: Finished reachableStatesCopy Result has 4 states, 4 states have (on average 251.0) internal successors, (1004), 4 states have internal predecessors, (1004), 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-08-26 12:31:33,977 INFO L81 ComplementDD]: Finished complementDD. Result has 4 states, 4 states have (on average 251.0) internal successors, (1004), 4 states have internal predecessors, (1004), 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-08-26 12:31:33,977 INFO L175 Difference]: Start difference. First operand has 34 places, 29 transitions, 78 flow. Second operand 3 states and 321 transitions. [2023-08-26 12:31:33,977 INFO L82 GeneralOperation]: Start removeRedundantFlow. Operand has 33 places, 27 transitions, 124 flow [2023-08-26 12:31:33,978 INFO L88 GeneralOperation]: Finished removeRedundantFlow, result has has 31 places, 27 transitions, 120 flow, removed 0 selfloop flow, removed 2 redundant places. [2023-08-26 12:31:33,979 INFO L231 Difference]: Finished difference. Result has 31 places, 27 transitions, 72 flow [2023-08-26 12:31:33,979 INFO L264 CegarLoopForPetriNet]: {PETRI_ALPHABET=251, PETRI_DIFFERENCE_MINUEND_FLOW=70, PETRI_DIFFERENCE_MINUEND_PLACES=29, PETRI_DIFFERENCE_MINUEND_TRANSITIONS=27, PETRI_DIFFERENCE_SUBTRAHEND_LETTERS_WITH_MORE_CHANGERS_THAN_LOOPERS=1, PETRI_DIFFERENCE_SUBTRAHEND_LOOPER_ONLY_LETTERS=26, PETRI_DIFFERENCE_SUBTRAHEND_STATES=3, PETRI_FLOW=72, PETRI_PLACES=31, PETRI_TRANSITIONS=27} [2023-08-26 12:31:33,980 INFO L281 CegarLoopForPetriNet]: 33 programPoint places, -2 predicate places. [2023-08-26 12:31:33,980 INFO L495 AbstractCegarLoop]: Abstraction has has 31 places, 27 transitions, 72 flow [2023-08-26 12:31:33,980 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 98.66666666666667) internal successors, (296), 3 states have internal predecessors, (296), 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-08-26 12:31:33,980 INFO L200 CegarLoopForPetriNet]: Found error trace [2023-08-26 12:31:33,980 INFO L208 CegarLoopForPetriNet]: trace histogram [1, 1, 1, 1, 1] [2023-08-26 12:31:33,981 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2023-08-26 12:31:33,981 INFO L420 AbstractCegarLoop]: === Iteration 3 === Targeting ULTIMATE.startErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE === [ULTIMATE.startErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr3REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 3 more)] === [2023-08-26 12:31:33,981 INFO L145 PredicateUnifier]: Initialized classic predicate unifier [2023-08-26 12:31:33,981 INFO L85 PathProgramCache]: Analyzing trace with hash 483655188, now seen corresponding path program 1 times [2023-08-26 12:31:33,982 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-08-26 12:31:33,982 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [555942741] [2023-08-26 12:31:33,982 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-08-26 12:31:33,982 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-08-26 12:31:33,993 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-08-26 12:31:34,065 INFO L134 CoverageAnalysis]: Checked inductivity of 1 backedges. 1 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-08-26 12:31:34,065 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-08-26 12:31:34,065 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [555942741] [2023-08-26 12:31:34,066 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [555942741] provided 1 perfect and 0 imperfect interpolant sequences [2023-08-26 12:31:34,066 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-08-26 12:31:34,066 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2023-08-26 12:31:34,066 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [8270782] [2023-08-26 12:31:34,066 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-08-26 12:31:34,067 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2023-08-26 12:31:34,067 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-08-26 12:31:34,067 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2023-08-26 12:31:34,068 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=6, Invalid=6, Unknown=0, NotChecked=0, Total=12 [2023-08-26 12:31:34,068 INFO L471 CegarLoopForPetriNet]: Number of universal loopers: 93 out of 251 [2023-08-26 12:31:34,069 INFO L103 encePairwiseOnDemand]: Start differencePairwiseOnDemand. First operand has 31 places, 27 transitions, 72 flow. Second operand has 4 states, 4 states have (on average 94.25) internal successors, (377), 4 states have internal predecessors, (377), 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-08-26 12:31:34,069 INFO L112 encePairwiseOnDemand]: Universal subtrahend loopers provided by user. [2023-08-26 12:31:34,069 INFO L113 encePairwiseOnDemand]: Number of universal subtrahend loopers: 93 of 251 [2023-08-26 12:31:34,069 INFO L73 FinitePrefix]: Start finitePrefix. Operand will be constructed on-demand [2023-08-26 12:31:34,172 INFO L124 PetriNetUnfolderBase]: 97/221 cut-off events. [2023-08-26 12:31:34,172 INFO L125 PetriNetUnfolderBase]: For 1/1 co-relation queries the response was YES. [2023-08-26 12:31:34,174 INFO L83 FinitePrefix]: Finished finitePrefix Result has 477 conditions, 221 events. 97/221 cut-off events. For 1/1 co-relation queries the response was YES. Maximal size of possible extension queue 15. Compared 950 event pairs, 0 based on Foata normal form. 0/193 useless extension candidates. Maximal degree in co-relation 469. Up to 167 conditions per place. [2023-08-26 12:31:34,175 INFO L140 encePairwiseOnDemand]: 246/251 looper letters, 37 selfloop transitions, 4 changer transitions 0/43 dead transitions. [2023-08-26 12:31:34,175 INFO L145 encePairwiseOnDemand]: Finished differencePairwiseOnDemand. Result has 33 places, 43 transitions, 184 flow [2023-08-26 12:31:34,175 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2023-08-26 12:31:34,175 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 4 states. [2023-08-26 12:31:34,176 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 4 states to 4 states and 414 transitions. [2023-08-26 12:31:34,177 INFO L516 CegarLoopForPetriNet]: DFA transition density 0.4123505976095618 [2023-08-26 12:31:34,177 INFO L72 ComplementDD]: Start complementDD. Operand 4 states and 414 transitions. [2023-08-26 12:31:34,177 INFO L73 IsDeterministic]: Start isDeterministic. Operand 4 states and 414 transitions. [2023-08-26 12:31:34,177 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2023-08-26 12:31:34,178 INFO L117 ReachableStatesCopy]: Start reachableStatesCopy. Operand 4 states and 414 transitions. [2023-08-26 12:31:34,179 INFO L343 DoubleDeckerVisitor]: Before removal of dead ends has 5 states, 4 states have (on average 103.5) internal successors, (414), 4 states have internal predecessors, (414), 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-08-26 12:31:34,182 INFO L131 ReachableStatesCopy]: Finished reachableStatesCopy Result has 5 states, 5 states have (on average 251.0) internal successors, (1255), 5 states have internal predecessors, (1255), 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-08-26 12:31:34,183 INFO L81 ComplementDD]: Finished complementDD. Result has 5 states, 5 states have (on average 251.0) internal successors, (1255), 5 states have internal predecessors, (1255), 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-08-26 12:31:34,183 INFO L175 Difference]: Start difference. First operand has 31 places, 27 transitions, 72 flow. Second operand 4 states and 414 transitions. [2023-08-26 12:31:34,183 INFO L82 GeneralOperation]: Start removeRedundantFlow. Operand has 33 places, 43 transitions, 184 flow [2023-08-26 12:31:34,185 INFO L88 GeneralOperation]: Finished removeRedundantFlow, result has has 32 places, 43 transitions, 183 flow, removed 0 selfloop flow, removed 1 redundant places. [2023-08-26 12:31:34,186 INFO L231 Difference]: Finished difference. Result has 32 places, 26 transitions, 75 flow [2023-08-26 12:31:34,186 INFO L264 CegarLoopForPetriNet]: {PETRI_ALPHABET=251, PETRI_DIFFERENCE_MINUEND_FLOW=67, PETRI_DIFFERENCE_MINUEND_PLACES=29, PETRI_DIFFERENCE_MINUEND_TRANSITIONS=26, PETRI_DIFFERENCE_SUBTRAHEND_LETTERS_WITH_MORE_CHANGERS_THAN_LOOPERS=4, PETRI_DIFFERENCE_SUBTRAHEND_LOOPER_ONLY_LETTERS=22, PETRI_DIFFERENCE_SUBTRAHEND_STATES=4, PETRI_FLOW=75, PETRI_PLACES=32, PETRI_TRANSITIONS=26} [2023-08-26 12:31:34,187 INFO L281 CegarLoopForPetriNet]: 33 programPoint places, -1 predicate places. [2023-08-26 12:31:34,190 INFO L495 AbstractCegarLoop]: Abstraction has has 32 places, 26 transitions, 75 flow [2023-08-26 12:31:34,191 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 94.25) internal successors, (377), 4 states have internal predecessors, (377), 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-08-26 12:31:34,192 INFO L200 CegarLoopForPetriNet]: Found error trace [2023-08-26 12:31:34,192 INFO L208 CegarLoopForPetriNet]: trace histogram [2, 1, 1, 1, 1] [2023-08-26 12:31:34,192 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2 [2023-08-26 12:31:34,192 INFO L420 AbstractCegarLoop]: === Iteration 4 === Targeting ULTIMATE.startErr0INUSE_VIOLATIONSUFFICIENT_THREAD_INSTANCES === [ULTIMATE.startErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr3REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 3 more)] === [2023-08-26 12:31:34,193 INFO L145 PredicateUnifier]: Initialized classic predicate unifier [2023-08-26 12:31:34,193 INFO L85 PathProgramCache]: Analyzing trace with hash 2108409356, now seen corresponding path program 1 times [2023-08-26 12:31:34,193 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-08-26 12:31:34,194 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1060451679] [2023-08-26 12:31:34,194 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-08-26 12:31:34,194 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-08-26 12:31:34,227 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2023-08-26 12:31:34,227 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2023-08-26 12:31:34,242 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2023-08-26 12:31:34,264 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2023-08-26 12:31:34,265 INFO L360 BasicCegarLoop]: Counterexample is feasible [2023-08-26 12:31:34,266 INFO L805 garLoopResultBuilder]: Registering result UNSAFE for location ULTIMATE.startErr0INUSE_VIOLATIONSUFFICIENT_THREAD_INSTANCES (5 of 6 remaining) [2023-08-26 12:31:34,269 INFO L805 garLoopResultBuilder]: Registering result UNKNOWN for location ULTIMATE.startErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE (4 of 6 remaining) [2023-08-26 12:31:34,270 INFO L805 garLoopResultBuilder]: Registering result UNKNOWN for location ULTIMATE.startErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE (3 of 6 remaining) [2023-08-26 12:31:34,270 INFO L805 garLoopResultBuilder]: Registering result UNKNOWN for location ULTIMATE.startErr3REQUIRES_VIOLATIONMEMORY_DEREFERENCE (2 of 6 remaining) [2023-08-26 12:31:34,270 INFO L805 garLoopResultBuilder]: Registering result UNKNOWN for location ULTIMATE.startErr4REQUIRES_VIOLATIONMEMORY_DEREFERENCE (1 of 6 remaining) [2023-08-26 12:31:34,272 INFO L805 garLoopResultBuilder]: Registering result UNKNOWN for location ULTIMATE.startErr2ASSERT_VIOLATIONASSERT (0 of 6 remaining) [2023-08-26 12:31:34,272 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3 [2023-08-26 12:31:34,272 INFO L445 BasicCegarLoop]: Path program histogram: [1, 1, 1, 1] [2023-08-26 12:31:34,275 WARN L233 ceAbstractionStarter]: 1 thread instances were not sufficient, I will increase this number and restart the analysis [2023-08-26 12:31:34,275 INFO L515 ceAbstractionStarter]: Constructing petrified ICFG for 2 thread instances. [2023-08-26 12:31:34,307 INFO L144 ThreadInstanceAdder]: Constructed 2 joinOtherThreadTransitions. [2023-08-26 12:31:34,323 INFO L73 FinitePrefix]: Start finitePrefix. Operand has 141 places, 159 transitions, 336 flow [2023-08-26 12:31:34,361 INFO L124 PetriNetUnfolderBase]: 43/290 cut-off events. [2023-08-26 12:31:34,361 INFO L125 PetriNetUnfolderBase]: For 6/6 co-relation queries the response was YES. [2023-08-26 12:31:34,364 INFO L83 FinitePrefix]: Finished finitePrefix Result has 304 conditions, 290 events. 43/290 cut-off events. For 6/6 co-relation queries the response was YES. Maximal size of possible extension queue 12. Compared 895 event pairs, 0 based on Foata normal form. 0/226 useless extension candidates. Maximal degree in co-relation 183. Up to 9 conditions per place. [2023-08-26 12:31:34,364 INFO L82 GeneralOperation]: Start removeDead. Operand has 141 places, 159 transitions, 336 flow [2023-08-26 12:31:34,366 INFO L88 GeneralOperation]: Finished RemoveDead, result has has 141 places, 159 transitions, 336 flow [2023-08-26 12:31:34,366 INFO L124 etLargeBlockEncoding]: Petri net LBE is using variable-based independence relation. [2023-08-26 12:31:34,367 INFO L131 etLargeBlockEncoding]: Starting large block encoding on Petri net that has 141 places, 159 transitions, 336 flow [2023-08-26 12:31:34,367 INFO L113 LiptonReduction]: Starting Lipton reduction on Petri net that has 141 places, 159 transitions, 336 flow [2023-08-26 12:31:34,367 INFO L73 FinitePrefix]: Start finitePrefix. Operand has 141 places, 159 transitions, 336 flow [2023-08-26 12:31:34,398 INFO L124 PetriNetUnfolderBase]: 43/290 cut-off events. [2023-08-26 12:31:34,398 INFO L125 PetriNetUnfolderBase]: For 6/6 co-relation queries the response was YES. [2023-08-26 12:31:34,400 INFO L83 FinitePrefix]: Finished finitePrefix Result has 304 conditions, 290 events. 43/290 cut-off events. For 6/6 co-relation queries the response was YES. Maximal size of possible extension queue 12. Compared 895 event pairs, 0 based on Foata normal form. 0/226 useless extension candidates. Maximal degree in co-relation 183. Up to 9 conditions per place. [2023-08-26 12:31:34,408 INFO L119 LiptonReduction]: Number of co-enabled transitions 8680 [2023-08-26 12:31:37,550 INFO L134 LiptonReduction]: Checked pairs total: 20028 [2023-08-26 12:31:37,550 INFO L136 LiptonReduction]: Total number of compositions: 133 [2023-08-26 12:31:37,552 INFO L356 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2023-08-26 12:31:37,553 INFO L357 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=false, mAutomataTypeConcurrency=PETRI_NET, mHoareTripleChecks=INCREMENTAL, mHoareAnnotationPositions=LoopsAndPotentialCycles, 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;@44a04137, mLbeIndependenceSettings=[IndependenceType=SYNTACTIC, AbstractionType=NONE, UseConditional=, UseSemiCommutativity=, Solver=, SolverTimeout=] [2023-08-26 12:31:37,553 INFO L358 AbstractCegarLoop]: Starting to check reachability of 6 error locations. [2023-08-26 12:31:37,554 INFO L185 PetriNetUnfolderBase]: Found word, exiting Unfolder. [2023-08-26 12:31:37,554 INFO L124 PetriNetUnfolderBase]: 0/1 cut-off events. [2023-08-26 12:31:37,554 INFO L125 PetriNetUnfolderBase]: For 0/0 co-relation queries the response was YES. [2023-08-26 12:31:37,555 INFO L200 CegarLoopForPetriNet]: Found error trace [2023-08-26 12:31:37,555 INFO L208 CegarLoopForPetriNet]: trace histogram [1, 1] [2023-08-26 12:31:37,555 INFO L420 AbstractCegarLoop]: === Iteration 1 === Targeting ULTIMATE.startErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE === [ULTIMATE.startErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr3REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 3 more)] === [2023-08-26 12:31:37,555 INFO L145 PredicateUnifier]: Initialized classic predicate unifier [2023-08-26 12:31:37,555 INFO L85 PathProgramCache]: Analyzing trace with hash 26519, now seen corresponding path program 1 times [2023-08-26 12:31:37,556 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-08-26 12:31:37,556 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1225050168] [2023-08-26 12:31:37,556 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-08-26 12:31:37,556 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-08-26 12:31:37,573 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-08-26 12:31:37,613 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-08-26 12:31:37,614 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-08-26 12:31:37,614 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1225050168] [2023-08-26 12:31:37,614 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1225050168] provided 1 perfect and 0 imperfect interpolant sequences [2023-08-26 12:31:37,614 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-08-26 12:31:37,614 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [1] imperfect sequences [] total 1 [2023-08-26 12:31:37,615 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1798521585] [2023-08-26 12:31:37,615 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-08-26 12:31:37,616 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2023-08-26 12:31:37,616 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-08-26 12:31:37,617 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2023-08-26 12:31:37,617 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2023-08-26 12:31:37,617 INFO L471 CegarLoopForPetriNet]: Number of universal loopers: 120 out of 292 [2023-08-26 12:31:37,618 INFO L103 encePairwiseOnDemand]: Start differencePairwiseOnDemand. First operand has 51 places, 65 transitions, 148 flow. Second operand has 3 states, 3 states have (on average 120.66666666666667) internal successors, (362), 3 states have internal predecessors, (362), 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-08-26 12:31:37,618 INFO L112 encePairwiseOnDemand]: Universal subtrahend loopers provided by user. [2023-08-26 12:31:37,618 INFO L113 encePairwiseOnDemand]: Number of universal subtrahend loopers: 120 of 292 [2023-08-26 12:31:37,618 INFO L73 FinitePrefix]: Start finitePrefix. Operand will be constructed on-demand [2023-08-26 12:31:37,902 INFO L124 PetriNetUnfolderBase]: 1688/3070 cut-off events. [2023-08-26 12:31:37,902 INFO L125 PetriNetUnfolderBase]: For 45/45 co-relation queries the response was YES. [2023-08-26 12:31:37,907 INFO L83 FinitePrefix]: Finished finitePrefix Result has 5857 conditions, 3070 events. 1688/3070 cut-off events. For 45/45 co-relation queries the response was YES. Maximal size of possible extension queue 133. Compared 19149 event pairs, 1484 based on Foata normal form. 347/2920 useless extension candidates. Maximal degree in co-relation 2992. Up to 2530 conditions per place. [2023-08-26 12:31:37,920 INFO L140 encePairwiseOnDemand]: 272/292 looper letters, 32 selfloop transitions, 1 changer transitions 15/59 dead transitions. [2023-08-26 12:31:37,921 INFO L145 encePairwiseOnDemand]: Finished differencePairwiseOnDemand. Result has 49 places, 59 transitions, 232 flow [2023-08-26 12:31:37,921 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2023-08-26 12:31:37,922 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 3 states. [2023-08-26 12:31:37,923 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 3 states to 3 states and 438 transitions. [2023-08-26 12:31:37,923 INFO L516 CegarLoopForPetriNet]: DFA transition density 0.5 [2023-08-26 12:31:37,926 INFO L72 ComplementDD]: Start complementDD. Operand 3 states and 438 transitions. [2023-08-26 12:31:37,927 INFO L73 IsDeterministic]: Start isDeterministic. Operand 3 states and 438 transitions. [2023-08-26 12:31:37,927 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2023-08-26 12:31:37,927 INFO L117 ReachableStatesCopy]: Start reachableStatesCopy. Operand 3 states and 438 transitions. [2023-08-26 12:31:37,928 INFO L343 DoubleDeckerVisitor]: Before removal of dead ends has 4 states, 3 states have (on average 146.0) internal successors, (438), 3 states have internal predecessors, (438), 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-08-26 12:31:37,930 INFO L131 ReachableStatesCopy]: Finished reachableStatesCopy Result has 4 states, 4 states have (on average 292.0) internal successors, (1168), 4 states have internal predecessors, (1168), 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-08-26 12:31:37,930 INFO L81 ComplementDD]: Finished complementDD. Result has 4 states, 4 states have (on average 292.0) internal successors, (1168), 4 states have internal predecessors, (1168), 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-08-26 12:31:37,931 INFO L175 Difference]: Start difference. First operand has 51 places, 65 transitions, 148 flow. Second operand 3 states and 438 transitions. [2023-08-26 12:31:37,931 INFO L82 GeneralOperation]: Start removeRedundantFlow. Operand has 49 places, 59 transitions, 232 flow [2023-08-26 12:31:37,933 INFO L88 GeneralOperation]: Finished removeRedundantFlow, result has has 49 places, 59 transitions, 232 flow, removed 0 selfloop flow, removed 0 redundant places. [2023-08-26 12:31:37,934 INFO L231 Difference]: Finished difference. Result has 49 places, 44 transitions, 108 flow [2023-08-26 12:31:37,934 INFO L264 CegarLoopForPetriNet]: {PETRI_ALPHABET=292, PETRI_DIFFERENCE_MINUEND_FLOW=108, PETRI_DIFFERENCE_MINUEND_PLACES=47, PETRI_DIFFERENCE_MINUEND_TRANSITIONS=45, PETRI_DIFFERENCE_SUBTRAHEND_LETTERS_WITH_MORE_CHANGERS_THAN_LOOPERS=1, PETRI_DIFFERENCE_SUBTRAHEND_LOOPER_ONLY_LETTERS=44, PETRI_DIFFERENCE_SUBTRAHEND_STATES=3, PETRI_FLOW=108, PETRI_PLACES=49, PETRI_TRANSITIONS=44} [2023-08-26 12:31:37,936 INFO L281 CegarLoopForPetriNet]: 51 programPoint places, -2 predicate places. [2023-08-26 12:31:37,937 INFO L495 AbstractCegarLoop]: Abstraction has has 49 places, 44 transitions, 108 flow [2023-08-26 12:31:37,937 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 120.66666666666667) internal successors, (362), 3 states have internal predecessors, (362), 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-08-26 12:31:37,937 INFO L200 CegarLoopForPetriNet]: Found error trace [2023-08-26 12:31:37,937 INFO L208 CegarLoopForPetriNet]: trace histogram [1, 1] [2023-08-26 12:31:37,937 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4 [2023-08-26 12:31:37,937 INFO L420 AbstractCegarLoop]: === Iteration 2 === Targeting ULTIMATE.startErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE === [ULTIMATE.startErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr3REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 3 more)] === [2023-08-26 12:31:37,938 INFO L145 PredicateUnifier]: Initialized classic predicate unifier [2023-08-26 12:31:37,938 INFO L85 PathProgramCache]: Analyzing trace with hash 26520, now seen corresponding path program 1 times [2023-08-26 12:31:37,938 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-08-26 12:31:37,938 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1895709043] [2023-08-26 12:31:37,938 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-08-26 12:31:37,938 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-08-26 12:31:37,951 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-08-26 12:31:38,016 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-08-26 12:31:38,016 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-08-26 12:31:38,016 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1895709043] [2023-08-26 12:31:38,016 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1895709043] provided 1 perfect and 0 imperfect interpolant sequences [2023-08-26 12:31:38,016 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-08-26 12:31:38,017 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [1] imperfect sequences [] total 1 [2023-08-26 12:31:38,017 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1018642914] [2023-08-26 12:31:38,017 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-08-26 12:31:38,017 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2023-08-26 12:31:38,017 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-08-26 12:31:38,018 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2023-08-26 12:31:38,018 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2023-08-26 12:31:38,018 INFO L471 CegarLoopForPetriNet]: Number of universal loopers: 115 out of 292 [2023-08-26 12:31:38,019 INFO L103 encePairwiseOnDemand]: Start differencePairwiseOnDemand. First operand has 49 places, 44 transitions, 108 flow. Second operand has 3 states, 3 states have (on average 115.66666666666667) internal successors, (347), 3 states have internal predecessors, (347), 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-08-26 12:31:38,019 INFO L112 encePairwiseOnDemand]: Universal subtrahend loopers provided by user. [2023-08-26 12:31:38,019 INFO L113 encePairwiseOnDemand]: Number of universal subtrahend loopers: 115 of 292 [2023-08-26 12:31:38,019 INFO L73 FinitePrefix]: Start finitePrefix. Operand will be constructed on-demand [2023-08-26 12:31:38,287 INFO L124 PetriNetUnfolderBase]: 1562/2796 cut-off events. [2023-08-26 12:31:38,287 INFO L125 PetriNetUnfolderBase]: For 39/39 co-relation queries the response was YES. [2023-08-26 12:31:38,290 INFO L83 FinitePrefix]: Finished finitePrefix Result has 5372 conditions, 2796 events. 1562/2796 cut-off events. For 39/39 co-relation queries the response was YES. Maximal size of possible extension queue 124. Compared 16887 event pairs, 1220 based on Foata normal form. 0/2390 useless extension candidates. Maximal degree in co-relation 5364. Up to 2513 conditions per place. [2023-08-26 12:31:38,302 INFO L140 encePairwiseOnDemand]: 287/292 looper letters, 39 selfloop transitions, 2 changer transitions 0/52 dead transitions. [2023-08-26 12:31:38,302 INFO L145 encePairwiseOnDemand]: Finished differencePairwiseOnDemand. Result has 50 places, 52 transitions, 206 flow [2023-08-26 12:31:38,302 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2023-08-26 12:31:38,302 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 3 states. [2023-08-26 12:31:38,303 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 3 states to 3 states and 389 transitions. [2023-08-26 12:31:38,304 INFO L516 CegarLoopForPetriNet]: DFA transition density 0.4440639269406393 [2023-08-26 12:31:38,304 INFO L72 ComplementDD]: Start complementDD. Operand 3 states and 389 transitions. [2023-08-26 12:31:38,304 INFO L73 IsDeterministic]: Start isDeterministic. Operand 3 states and 389 transitions. [2023-08-26 12:31:38,304 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2023-08-26 12:31:38,304 INFO L117 ReachableStatesCopy]: Start reachableStatesCopy. Operand 3 states and 389 transitions. [2023-08-26 12:31:38,305 INFO L343 DoubleDeckerVisitor]: Before removal of dead ends has 4 states, 3 states have (on average 129.66666666666666) internal successors, (389), 3 states have internal predecessors, (389), 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-08-26 12:31:38,307 INFO L131 ReachableStatesCopy]: Finished reachableStatesCopy Result has 4 states, 4 states have (on average 292.0) internal successors, (1168), 4 states have internal predecessors, (1168), 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-08-26 12:31:38,307 INFO L81 ComplementDD]: Finished complementDD. Result has 4 states, 4 states have (on average 292.0) internal successors, (1168), 4 states have internal predecessors, (1168), 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-08-26 12:31:38,308 INFO L175 Difference]: Start difference. First operand has 49 places, 44 transitions, 108 flow. Second operand 3 states and 389 transitions. [2023-08-26 12:31:38,308 INFO L82 GeneralOperation]: Start removeRedundantFlow. Operand has 50 places, 52 transitions, 206 flow [2023-08-26 12:31:38,310 INFO L88 GeneralOperation]: Finished removeRedundantFlow, result has has 49 places, 52 transitions, 205 flow, removed 0 selfloop flow, removed 1 redundant places. [2023-08-26 12:31:38,312 INFO L231 Difference]: Finished difference. Result has 50 places, 45 transitions, 123 flow [2023-08-26 12:31:38,312 INFO L264 CegarLoopForPetriNet]: {PETRI_ALPHABET=292, PETRI_DIFFERENCE_MINUEND_FLOW=107, PETRI_DIFFERENCE_MINUEND_PLACES=47, PETRI_DIFFERENCE_MINUEND_TRANSITIONS=44, PETRI_DIFFERENCE_SUBTRAHEND_LETTERS_WITH_MORE_CHANGERS_THAN_LOOPERS=1, PETRI_DIFFERENCE_SUBTRAHEND_LOOPER_ONLY_LETTERS=42, PETRI_DIFFERENCE_SUBTRAHEND_STATES=3, PETRI_FLOW=123, PETRI_PLACES=50, PETRI_TRANSITIONS=45} [2023-08-26 12:31:38,315 INFO L281 CegarLoopForPetriNet]: 51 programPoint places, -1 predicate places. [2023-08-26 12:31:38,315 INFO L495 AbstractCegarLoop]: Abstraction has has 50 places, 45 transitions, 123 flow [2023-08-26 12:31:38,316 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 115.66666666666667) internal successors, (347), 3 states have internal predecessors, (347), 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-08-26 12:31:38,316 INFO L200 CegarLoopForPetriNet]: Found error trace [2023-08-26 12:31:38,316 INFO L208 CegarLoopForPetriNet]: trace histogram [1, 1, 1, 1, 1, 1] [2023-08-26 12:31:38,317 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5 [2023-08-26 12:31:38,317 INFO L420 AbstractCegarLoop]: === Iteration 3 === Targeting ULTIMATE.startErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE === [ULTIMATE.startErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr3REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 3 more)] === [2023-08-26 12:31:38,317 INFO L145 PredicateUnifier]: Initialized classic predicate unifier [2023-08-26 12:31:38,317 INFO L85 PathProgramCache]: Analyzing trace with hash -1259542874, now seen corresponding path program 1 times [2023-08-26 12:31:38,317 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-08-26 12:31:38,317 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1706944846] [2023-08-26 12:31:38,318 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-08-26 12:31:38,318 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-08-26 12:31:38,328 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-08-26 12:31:38,412 INFO L134 CoverageAnalysis]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-08-26 12:31:38,413 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-08-26 12:31:38,413 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1706944846] [2023-08-26 12:31:38,417 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1706944846] provided 0 perfect and 1 imperfect interpolant sequences [2023-08-26 12:31:38,417 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [454236937] [2023-08-26 12:31:38,417 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-08-26 12:31:38,417 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-08-26 12:31:38,417 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-08-26 12:31:38,419 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-08-26 12:31:38,476 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-08-26 12:31:38,561 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-08-26 12:31:38,563 INFO L262 TraceCheckSpWp]: Trace formula consists of 120 conjuncts, 9 conjunts are in the unsatisfiable core [2023-08-26 12:31:38,564 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-08-26 12:31:38,620 INFO L351 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 6 treesize of output 5 [2023-08-26 12:31:38,662 INFO L134 CoverageAnalysis]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-08-26 12:31:38,663 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-08-26 12:31:38,710 INFO L134 CoverageAnalysis]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-08-26 12:31:38,710 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [454236937] provided 0 perfect and 2 imperfect interpolant sequences [2023-08-26 12:31:38,710 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2023-08-26 12:31:38,711 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [2, 2, 2] total 5 [2023-08-26 12:31:38,711 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [923012440] [2023-08-26 12:31:38,711 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2023-08-26 12:31:38,711 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2023-08-26 12:31:38,711 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-08-26 12:31:38,711 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2023-08-26 12:31:38,713 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=18, Invalid=24, Unknown=0, NotChecked=0, Total=42 [2023-08-26 12:31:38,713 INFO L471 CegarLoopForPetriNet]: Number of universal loopers: 115 out of 292 [2023-08-26 12:31:38,714 INFO L103 encePairwiseOnDemand]: Start differencePairwiseOnDemand. First operand has 50 places, 45 transitions, 123 flow. Second operand has 7 states, 7 states have (on average 116.71428571428571) internal successors, (817), 7 states have internal predecessors, (817), 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-08-26 12:31:38,714 INFO L112 encePairwiseOnDemand]: Universal subtrahend loopers provided by user. [2023-08-26 12:31:38,714 INFO L113 encePairwiseOnDemand]: Number of universal subtrahend loopers: 115 of 292 [2023-08-26 12:31:38,715 INFO L73 FinitePrefix]: Start finitePrefix. Operand will be constructed on-demand [2023-08-26 12:31:38,995 INFO L124 PetriNetUnfolderBase]: 1396/2357 cut-off events. [2023-08-26 12:31:38,995 INFO L125 PetriNetUnfolderBase]: For 168/168 co-relation queries the response was YES. [2023-08-26 12:31:38,999 INFO L83 FinitePrefix]: Finished finitePrefix Result has 4978 conditions, 2357 events. 1396/2357 cut-off events. For 168/168 co-relation queries the response was YES. Maximal size of possible extension queue 114. Compared 14241 event pairs, 41 based on Foata normal form. 7/2155 useless extension candidates. Maximal degree in co-relation 4968. Up to 1746 conditions per place. [2023-08-26 12:31:39,009 INFO L140 encePairwiseOnDemand]: 287/292 looper letters, 64 selfloop transitions, 5 changer transitions 0/80 dead transitions. [2023-08-26 12:31:39,009 INFO L145 encePairwiseOnDemand]: Finished differencePairwiseOnDemand. Result has 53 places, 80 transitions, 329 flow [2023-08-26 12:31:39,009 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2023-08-26 12:31:39,009 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 5 states. [2023-08-26 12:31:39,011 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 648 transitions. [2023-08-26 12:31:39,011 INFO L516 CegarLoopForPetriNet]: DFA transition density 0.4438356164383562 [2023-08-26 12:31:39,011 INFO L72 ComplementDD]: Start complementDD. Operand 5 states and 648 transitions. [2023-08-26 12:31:39,011 INFO L73 IsDeterministic]: Start isDeterministic. Operand 5 states and 648 transitions. [2023-08-26 12:31:39,014 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2023-08-26 12:31:39,014 INFO L117 ReachableStatesCopy]: Start reachableStatesCopy. Operand 5 states and 648 transitions. [2023-08-26 12:31:39,016 INFO L343 DoubleDeckerVisitor]: Before removal of dead ends has 6 states, 5 states have (on average 129.6) internal successors, (648), 5 states have internal predecessors, (648), 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-08-26 12:31:39,019 INFO L131 ReachableStatesCopy]: Finished reachableStatesCopy Result has 6 states, 6 states have (on average 292.0) internal successors, (1752), 6 states have internal predecessors, (1752), 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-08-26 12:31:39,019 INFO L81 ComplementDD]: Finished complementDD. Result has 6 states, 6 states have (on average 292.0) internal successors, (1752), 6 states have internal predecessors, (1752), 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-08-26 12:31:39,019 INFO L175 Difference]: Start difference. First operand has 50 places, 45 transitions, 123 flow. Second operand 5 states and 648 transitions. [2023-08-26 12:31:39,019 INFO L82 GeneralOperation]: Start removeRedundantFlow. Operand has 53 places, 80 transitions, 329 flow [2023-08-26 12:31:39,021 INFO L88 GeneralOperation]: Finished removeRedundantFlow, result has has 52 places, 80 transitions, 327 flow, removed 0 selfloop flow, removed 1 redundant places. [2023-08-26 12:31:39,022 INFO L231 Difference]: Finished difference. Result has 52 places, 44 transitions, 127 flow [2023-08-26 12:31:39,022 INFO L264 CegarLoopForPetriNet]: {PETRI_ALPHABET=292, PETRI_DIFFERENCE_MINUEND_FLOW=117, PETRI_DIFFERENCE_MINUEND_PLACES=48, PETRI_DIFFERENCE_MINUEND_TRANSITIONS=44, PETRI_DIFFERENCE_SUBTRAHEND_LETTERS_WITH_MORE_CHANGERS_THAN_LOOPERS=5, PETRI_DIFFERENCE_SUBTRAHEND_LOOPER_ONLY_LETTERS=39, PETRI_DIFFERENCE_SUBTRAHEND_STATES=5, PETRI_FLOW=127, PETRI_PLACES=52, PETRI_TRANSITIONS=44} [2023-08-26 12:31:39,023 INFO L281 CegarLoopForPetriNet]: 51 programPoint places, 1 predicate places. [2023-08-26 12:31:39,023 INFO L495 AbstractCegarLoop]: Abstraction has has 52 places, 44 transitions, 127 flow [2023-08-26 12:31:39,023 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 7 states have (on average 116.71428571428571) internal successors, (817), 7 states have internal predecessors, (817), 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-08-26 12:31:39,024 INFO L200 CegarLoopForPetriNet]: Found error trace [2023-08-26 12:31:39,024 INFO L208 CegarLoopForPetriNet]: trace histogram [3, 2, 2, 1, 1, 1, 1] [2023-08-26 12:31:39,032 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Forceful destruction successful, exit code 0 [2023-08-26 12:31:39,229 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-08-26 12:31:39,229 INFO L420 AbstractCegarLoop]: === Iteration 4 === Targeting ULTIMATE.startErr0INUSE_VIOLATIONSUFFICIENT_THREAD_INSTANCES === [ULTIMATE.startErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr3REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 3 more)] === [2023-08-26 12:31:39,229 INFO L145 PredicateUnifier]: Initialized classic predicate unifier [2023-08-26 12:31:39,229 INFO L85 PathProgramCache]: Analyzing trace with hash 917291430, now seen corresponding path program 1 times [2023-08-26 12:31:39,230 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-08-26 12:31:39,230 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1248031633] [2023-08-26 12:31:39,230 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-08-26 12:31:39,230 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-08-26 12:31:39,246 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2023-08-26 12:31:39,246 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2023-08-26 12:31:39,258 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2023-08-26 12:31:39,265 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2023-08-26 12:31:39,265 INFO L360 BasicCegarLoop]: Counterexample is feasible [2023-08-26 12:31:39,266 INFO L805 garLoopResultBuilder]: Registering result UNSAFE for location ULTIMATE.startErr0INUSE_VIOLATIONSUFFICIENT_THREAD_INSTANCES (5 of 6 remaining) [2023-08-26 12:31:39,266 INFO L805 garLoopResultBuilder]: Registering result UNKNOWN for location ULTIMATE.startErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE (4 of 6 remaining) [2023-08-26 12:31:39,266 INFO L805 garLoopResultBuilder]: Registering result UNKNOWN for location ULTIMATE.startErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE (3 of 6 remaining) [2023-08-26 12:31:39,266 INFO L805 garLoopResultBuilder]: Registering result UNKNOWN for location ULTIMATE.startErr3REQUIRES_VIOLATIONMEMORY_DEREFERENCE (2 of 6 remaining) [2023-08-26 12:31:39,266 INFO L805 garLoopResultBuilder]: Registering result UNKNOWN for location ULTIMATE.startErr4REQUIRES_VIOLATIONMEMORY_DEREFERENCE (1 of 6 remaining) [2023-08-26 12:31:39,266 INFO L805 garLoopResultBuilder]: Registering result UNKNOWN for location ULTIMATE.startErr2ASSERT_VIOLATIONASSERT (0 of 6 remaining) [2023-08-26 12:31:39,266 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7 [2023-08-26 12:31:39,266 INFO L445 BasicCegarLoop]: Path program histogram: [1, 1, 1, 1] [2023-08-26 12:31:39,268 WARN L233 ceAbstractionStarter]: 2 thread instances were not sufficient, I will increase this number and restart the analysis [2023-08-26 12:31:39,268 INFO L515 ceAbstractionStarter]: Constructing petrified ICFG for 3 thread instances. [2023-08-26 12:31:39,288 INFO L144 ThreadInstanceAdder]: Constructed 3 joinOtherThreadTransitions. [2023-08-26 12:31:39,293 INFO L73 FinitePrefix]: Start finitePrefix. Operand has 166 places, 189 transitions, 408 flow [2023-08-26 12:31:39,328 INFO L124 PetriNetUnfolderBase]: 66/436 cut-off events. [2023-08-26 12:31:39,328 INFO L125 PetriNetUnfolderBase]: For 19/19 co-relation queries the response was YES. [2023-08-26 12:31:39,330 INFO L83 FinitePrefix]: Finished finitePrefix Result has 464 conditions, 436 events. 66/436 cut-off events. For 19/19 co-relation queries the response was YES. Maximal size of possible extension queue 13. Compared 1530 event pairs, 1 based on Foata normal form. 0/338 useless extension candidates. Maximal degree in co-relation 298. Up to 16 conditions per place. [2023-08-26 12:31:39,330 INFO L82 GeneralOperation]: Start removeDead. Operand has 166 places, 189 transitions, 408 flow [2023-08-26 12:31:39,333 INFO L88 GeneralOperation]: Finished RemoveDead, result has has 166 places, 189 transitions, 408 flow [2023-08-26 12:31:39,333 INFO L124 etLargeBlockEncoding]: Petri net LBE is using variable-based independence relation. [2023-08-26 12:31:39,334 INFO L131 etLargeBlockEncoding]: Starting large block encoding on Petri net that has 166 places, 189 transitions, 408 flow [2023-08-26 12:31:39,334 INFO L113 LiptonReduction]: Starting Lipton reduction on Petri net that has 166 places, 189 transitions, 408 flow [2023-08-26 12:31:39,334 INFO L73 FinitePrefix]: Start finitePrefix. Operand has 166 places, 189 transitions, 408 flow [2023-08-26 12:31:39,371 INFO L124 PetriNetUnfolderBase]: 66/436 cut-off events. [2023-08-26 12:31:39,371 INFO L125 PetriNetUnfolderBase]: For 19/19 co-relation queries the response was YES. [2023-08-26 12:31:39,374 INFO L83 FinitePrefix]: Finished finitePrefix Result has 464 conditions, 436 events. 66/436 cut-off events. For 19/19 co-relation queries the response was YES. Maximal size of possible extension queue 13. Compared 1530 event pairs, 1 based on Foata normal form. 0/338 useless extension candidates. Maximal degree in co-relation 298. Up to 16 conditions per place. [2023-08-26 12:31:39,386 INFO L119 LiptonReduction]: Number of co-enabled transitions 15624 [2023-08-26 12:31:42,627 INFO L134 LiptonReduction]: Checked pairs total: 38073 [2023-08-26 12:31:42,628 INFO L136 LiptonReduction]: Total number of compositions: 148 [2023-08-26 12:31:42,629 INFO L356 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2023-08-26 12:31:42,630 INFO L357 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=false, mAutomataTypeConcurrency=PETRI_NET, mHoareTripleChecks=INCREMENTAL, mHoareAnnotationPositions=LoopsAndPotentialCycles, 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;@44a04137, mLbeIndependenceSettings=[IndependenceType=SYNTACTIC, AbstractionType=NONE, UseConditional=, UseSemiCommutativity=, Solver=, SolverTimeout=] [2023-08-26 12:31:42,630 INFO L358 AbstractCegarLoop]: Starting to check reachability of 6 error locations. [2023-08-26 12:31:42,631 INFO L185 PetriNetUnfolderBase]: Found word, exiting Unfolder. [2023-08-26 12:31:42,631 INFO L124 PetriNetUnfolderBase]: 0/1 cut-off events. [2023-08-26 12:31:42,631 INFO L125 PetriNetUnfolderBase]: For 0/0 co-relation queries the response was YES. [2023-08-26 12:31:42,631 INFO L200 CegarLoopForPetriNet]: Found error trace [2023-08-26 12:31:42,631 INFO L208 CegarLoopForPetriNet]: trace histogram [1, 1] [2023-08-26 12:31:42,631 INFO L420 AbstractCegarLoop]: === Iteration 1 === Targeting ULTIMATE.startErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE === [ULTIMATE.startErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr3REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 3 more)] === [2023-08-26 12:31:42,631 INFO L145 PredicateUnifier]: Initialized classic predicate unifier [2023-08-26 12:31:42,632 INFO L85 PathProgramCache]: Analyzing trace with hash 38255, now seen corresponding path program 1 times [2023-08-26 12:31:42,632 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-08-26 12:31:42,632 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1328831551] [2023-08-26 12:31:42,632 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-08-26 12:31:42,632 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-08-26 12:31:42,639 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-08-26 12:31:42,653 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-08-26 12:31:42,654 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-08-26 12:31:42,654 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1328831551] [2023-08-26 12:31:42,654 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1328831551] provided 1 perfect and 0 imperfect interpolant sequences [2023-08-26 12:31:42,654 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-08-26 12:31:42,654 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [1] imperfect sequences [] total 1 [2023-08-26 12:31:42,654 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1829614074] [2023-08-26 12:31:42,654 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-08-26 12:31:42,654 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2023-08-26 12:31:42,654 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-08-26 12:31:42,655 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2023-08-26 12:31:42,655 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2023-08-26 12:31:42,655 INFO L471 CegarLoopForPetriNet]: Number of universal loopers: 142 out of 337 [2023-08-26 12:31:42,656 INFO L103 encePairwiseOnDemand]: Start differencePairwiseOnDemand. First operand has 65 places, 84 transitions, 198 flow. Second operand has 3 states, 3 states have (on average 142.66666666666666) internal successors, (428), 3 states have internal predecessors, (428), 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-08-26 12:31:42,656 INFO L112 encePairwiseOnDemand]: Universal subtrahend loopers provided by user. [2023-08-26 12:31:42,656 INFO L113 encePairwiseOnDemand]: Number of universal subtrahend loopers: 142 of 337 [2023-08-26 12:31:42,656 INFO L73 FinitePrefix]: Start finitePrefix. Operand will be constructed on-demand [2023-08-26 12:31:44,940 INFO L124 PetriNetUnfolderBase]: 19020/29053 cut-off events. [2023-08-26 12:31:44,941 INFO L125 PetriNetUnfolderBase]: For 719/719 co-relation queries the response was YES. [2023-08-26 12:31:44,990 INFO L83 FinitePrefix]: Finished finitePrefix Result has 56509 conditions, 29053 events. 19020/29053 cut-off events. For 719/719 co-relation queries the response was YES. Maximal size of possible extension queue 941. Compared 212867 event pairs, 16947 based on Foata normal form. 6619/31649 useless extension candidates. Maximal degree in co-relation 10908. Up to 24786 conditions per place. [2023-08-26 12:31:45,234 INFO L140 encePairwiseOnDemand]: 311/337 looper letters, 40 selfloop transitions, 1 changer transitions 21/78 dead transitions. [2023-08-26 12:31:45,236 INFO L145 encePairwiseOnDemand]: Finished differencePairwiseOnDemand. Result has 63 places, 78 transitions, 310 flow [2023-08-26 12:31:45,236 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2023-08-26 12:31:45,236 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 3 states. [2023-08-26 12:31:45,237 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 3 states to 3 states and 530 transitions. [2023-08-26 12:31:45,238 INFO L516 CegarLoopForPetriNet]: DFA transition density 0.5242334322453017 [2023-08-26 12:31:45,238 INFO L72 ComplementDD]: Start complementDD. Operand 3 states and 530 transitions. [2023-08-26 12:31:45,238 INFO L73 IsDeterministic]: Start isDeterministic. Operand 3 states and 530 transitions. [2023-08-26 12:31:45,238 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2023-08-26 12:31:45,238 INFO L117 ReachableStatesCopy]: Start reachableStatesCopy. Operand 3 states and 530 transitions. [2023-08-26 12:31:45,239 INFO L343 DoubleDeckerVisitor]: Before removal of dead ends has 4 states, 3 states have (on average 176.66666666666666) internal successors, (530), 3 states have internal predecessors, (530), 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-08-26 12:31:45,241 INFO L131 ReachableStatesCopy]: Finished reachableStatesCopy Result has 4 states, 4 states have (on average 337.0) internal successors, (1348), 4 states have internal predecessors, (1348), 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-08-26 12:31:45,241 INFO L81 ComplementDD]: Finished complementDD. Result has 4 states, 4 states have (on average 337.0) internal successors, (1348), 4 states have internal predecessors, (1348), 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-08-26 12:31:45,241 INFO L175 Difference]: Start difference. First operand has 65 places, 84 transitions, 198 flow. Second operand 3 states and 530 transitions. [2023-08-26 12:31:45,241 INFO L82 GeneralOperation]: Start removeRedundantFlow. Operand has 63 places, 78 transitions, 310 flow [2023-08-26 12:31:45,244 INFO L88 GeneralOperation]: Finished removeRedundantFlow, result has has 63 places, 78 transitions, 310 flow, removed 0 selfloop flow, removed 0 redundant places. [2023-08-26 12:31:45,246 INFO L231 Difference]: Finished difference. Result has 63 places, 57 transitions, 146 flow [2023-08-26 12:31:45,246 INFO L264 CegarLoopForPetriNet]: {PETRI_ALPHABET=337, PETRI_DIFFERENCE_MINUEND_FLOW=146, PETRI_DIFFERENCE_MINUEND_PLACES=61, PETRI_DIFFERENCE_MINUEND_TRANSITIONS=58, PETRI_DIFFERENCE_SUBTRAHEND_LETTERS_WITH_MORE_CHANGERS_THAN_LOOPERS=1, PETRI_DIFFERENCE_SUBTRAHEND_LOOPER_ONLY_LETTERS=57, PETRI_DIFFERENCE_SUBTRAHEND_STATES=3, PETRI_FLOW=146, PETRI_PLACES=63, PETRI_TRANSITIONS=57} [2023-08-26 12:31:45,247 INFO L281 CegarLoopForPetriNet]: 65 programPoint places, -2 predicate places. [2023-08-26 12:31:45,247 INFO L495 AbstractCegarLoop]: Abstraction has has 63 places, 57 transitions, 146 flow [2023-08-26 12:31:45,248 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 142.66666666666666) internal successors, (428), 3 states have internal predecessors, (428), 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-08-26 12:31:45,248 INFO L200 CegarLoopForPetriNet]: Found error trace [2023-08-26 12:31:45,248 INFO L208 CegarLoopForPetriNet]: trace histogram [1, 1] [2023-08-26 12:31:45,248 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8 [2023-08-26 12:31:45,248 INFO L420 AbstractCegarLoop]: === Iteration 2 === Targeting ULTIMATE.startErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE === [ULTIMATE.startErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr3REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 3 more)] === [2023-08-26 12:31:45,248 INFO L145 PredicateUnifier]: Initialized classic predicate unifier [2023-08-26 12:31:45,248 INFO L85 PathProgramCache]: Analyzing trace with hash 38256, now seen corresponding path program 1 times [2023-08-26 12:31:45,248 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-08-26 12:31:45,249 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2013856863] [2023-08-26 12:31:45,249 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-08-26 12:31:45,249 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-08-26 12:31:45,255 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-08-26 12:31:45,288 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-08-26 12:31:45,288 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-08-26 12:31:45,289 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2013856863] [2023-08-26 12:31:45,289 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2013856863] provided 1 perfect and 0 imperfect interpolant sequences [2023-08-26 12:31:45,289 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-08-26 12:31:45,289 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [1] imperfect sequences [] total 1 [2023-08-26 12:31:45,289 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [643046373] [2023-08-26 12:31:45,289 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-08-26 12:31:45,290 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2023-08-26 12:31:45,290 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-08-26 12:31:45,291 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2023-08-26 12:31:45,291 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2023-08-26 12:31:45,291 INFO L471 CegarLoopForPetriNet]: Number of universal loopers: 137 out of 337 [2023-08-26 12:31:45,292 INFO L103 encePairwiseOnDemand]: Start differencePairwiseOnDemand. First operand has 63 places, 57 transitions, 146 flow. Second operand has 3 states, 3 states have (on average 137.66666666666666) internal successors, (413), 3 states have internal predecessors, (413), 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-08-26 12:31:45,292 INFO L112 encePairwiseOnDemand]: Universal subtrahend loopers provided by user. [2023-08-26 12:31:45,292 INFO L113 encePairwiseOnDemand]: Number of universal subtrahend loopers: 137 of 337 [2023-08-26 12:31:45,292 INFO L73 FinitePrefix]: Start finitePrefix. Operand will be constructed on-demand [2023-08-26 12:31:47,002 INFO L124 PetriNetUnfolderBase]: 17546/27164 cut-off events. [2023-08-26 12:31:47,002 INFO L125 PetriNetUnfolderBase]: For 799/799 co-relation queries the response was YES. [2023-08-26 12:31:47,037 INFO L83 FinitePrefix]: Finished finitePrefix Result has 52510 conditions, 27164 events. 17546/27164 cut-off events. For 799/799 co-relation queries the response was YES. Maximal size of possible extension queue 898. Compared 200375 event pairs, 11031 based on Foata normal form. 0/23992 useless extension candidates. Maximal degree in co-relation 52501. Up to 24769 conditions per place. [2023-08-26 12:31:47,141 INFO L140 encePairwiseOnDemand]: 332/337 looper letters, 47 selfloop transitions, 2 changer transitions 0/65 dead transitions. [2023-08-26 12:31:47,141 INFO L145 encePairwiseOnDemand]: Finished differencePairwiseOnDemand. Result has 64 places, 65 transitions, 260 flow [2023-08-26 12:31:47,141 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2023-08-26 12:31:47,142 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 3 states. [2023-08-26 12:31:47,143 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 3 states to 3 states and 463 transitions. [2023-08-26 12:31:47,143 INFO L516 CegarLoopForPetriNet]: DFA transition density 0.4579624134520277 [2023-08-26 12:31:47,143 INFO L72 ComplementDD]: Start complementDD. Operand 3 states and 463 transitions. [2023-08-26 12:31:47,143 INFO L73 IsDeterministic]: Start isDeterministic. Operand 3 states and 463 transitions. [2023-08-26 12:31:47,143 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2023-08-26 12:31:47,144 INFO L117 ReachableStatesCopy]: Start reachableStatesCopy. Operand 3 states and 463 transitions. [2023-08-26 12:31:47,144 INFO L343 DoubleDeckerVisitor]: Before removal of dead ends has 4 states, 3 states have (on average 154.33333333333334) internal successors, (463), 3 states have internal predecessors, (463), 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-08-26 12:31:47,146 INFO L131 ReachableStatesCopy]: Finished reachableStatesCopy Result has 4 states, 4 states have (on average 337.0) internal successors, (1348), 4 states have internal predecessors, (1348), 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-08-26 12:31:47,146 INFO L81 ComplementDD]: Finished complementDD. Result has 4 states, 4 states have (on average 337.0) internal successors, (1348), 4 states have internal predecessors, (1348), 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-08-26 12:31:47,146 INFO L175 Difference]: Start difference. First operand has 63 places, 57 transitions, 146 flow. Second operand 3 states and 463 transitions. [2023-08-26 12:31:47,147 INFO L82 GeneralOperation]: Start removeRedundantFlow. Operand has 64 places, 65 transitions, 260 flow [2023-08-26 12:31:47,149 INFO L88 GeneralOperation]: Finished removeRedundantFlow, result has has 63 places, 65 transitions, 259 flow, removed 0 selfloop flow, removed 1 redundant places. [2023-08-26 12:31:47,150 INFO L231 Difference]: Finished difference. Result has 64 places, 58 transitions, 161 flow [2023-08-26 12:31:47,150 INFO L264 CegarLoopForPetriNet]: {PETRI_ALPHABET=337, PETRI_DIFFERENCE_MINUEND_FLOW=145, PETRI_DIFFERENCE_MINUEND_PLACES=61, PETRI_DIFFERENCE_MINUEND_TRANSITIONS=57, PETRI_DIFFERENCE_SUBTRAHEND_LETTERS_WITH_MORE_CHANGERS_THAN_LOOPERS=1, PETRI_DIFFERENCE_SUBTRAHEND_LOOPER_ONLY_LETTERS=55, PETRI_DIFFERENCE_SUBTRAHEND_STATES=3, PETRI_FLOW=161, PETRI_PLACES=64, PETRI_TRANSITIONS=58} [2023-08-26 12:31:47,151 INFO L281 CegarLoopForPetriNet]: 65 programPoint places, -1 predicate places. [2023-08-26 12:31:47,151 INFO L495 AbstractCegarLoop]: Abstraction has has 64 places, 58 transitions, 161 flow [2023-08-26 12:31:47,151 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 137.66666666666666) internal successors, (413), 3 states have internal predecessors, (413), 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-08-26 12:31:47,151 INFO L200 CegarLoopForPetriNet]: Found error trace [2023-08-26 12:31:47,151 INFO L208 CegarLoopForPetriNet]: trace histogram [1, 1, 1, 1, 1, 1] [2023-08-26 12:31:47,152 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable9 [2023-08-26 12:31:47,152 INFO L420 AbstractCegarLoop]: === Iteration 3 === Targeting ULTIMATE.startErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE === [ULTIMATE.startErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr3REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 3 more)] === [2023-08-26 12:31:47,152 INFO L145 PredicateUnifier]: Initialized classic predicate unifier [2023-08-26 12:31:47,152 INFO L85 PathProgramCache]: Analyzing trace with hash 1002483519, now seen corresponding path program 1 times [2023-08-26 12:31:47,152 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-08-26 12:31:47,152 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [440916996] [2023-08-26 12:31:47,152 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-08-26 12:31:47,152 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-08-26 12:31:47,163 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-08-26 12:31:47,235 INFO L134 CoverageAnalysis]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-08-26 12:31:47,236 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-08-26 12:31:47,236 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [440916996] [2023-08-26 12:31:47,236 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [440916996] provided 0 perfect and 1 imperfect interpolant sequences [2023-08-26 12:31:47,236 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2038787056] [2023-08-26 12:31:47,236 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-08-26 12:31:47,236 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-08-26 12:31:47,236 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-08-26 12:31:47,238 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-08-26 12:31:47,265 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-08-26 12:31:47,309 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-08-26 12:31:47,310 INFO L262 TraceCheckSpWp]: Trace formula consists of 120 conjuncts, 9 conjunts are in the unsatisfiable core [2023-08-26 12:31:47,312 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-08-26 12:31:47,326 INFO L351 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 6 treesize of output 5 [2023-08-26 12:31:47,358 INFO L134 CoverageAnalysis]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-08-26 12:31:47,359 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-08-26 12:31:47,398 INFO L134 CoverageAnalysis]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-08-26 12:31:47,398 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2038787056] provided 0 perfect and 2 imperfect interpolant sequences [2023-08-26 12:31:47,398 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2023-08-26 12:31:47,398 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [2, 2, 2] total 5 [2023-08-26 12:31:47,398 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1926906155] [2023-08-26 12:31:47,398 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2023-08-26 12:31:47,399 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2023-08-26 12:31:47,399 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-08-26 12:31:47,399 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2023-08-26 12:31:47,399 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=18, Invalid=24, Unknown=0, NotChecked=0, Total=42 [2023-08-26 12:31:47,400 INFO L471 CegarLoopForPetriNet]: Number of universal loopers: 137 out of 337 [2023-08-26 12:31:47,401 INFO L103 encePairwiseOnDemand]: Start differencePairwiseOnDemand. First operand has 64 places, 58 transitions, 161 flow. Second operand has 7 states, 7 states have (on average 138.71428571428572) internal successors, (971), 7 states have internal predecessors, (971), 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-08-26 12:31:47,401 INFO L112 encePairwiseOnDemand]: Universal subtrahend loopers provided by user. [2023-08-26 12:31:47,401 INFO L113 encePairwiseOnDemand]: Number of universal subtrahend loopers: 137 of 337 [2023-08-26 12:31:47,401 INFO L73 FinitePrefix]: Start finitePrefix. Operand will be constructed on-demand [2023-08-26 12:31:49,008 INFO L124 PetriNetUnfolderBase]: 16232/23850 cut-off events. [2023-08-26 12:31:49,008 INFO L125 PetriNetUnfolderBase]: For 2051/2051 co-relation queries the response was YES. [2023-08-26 12:31:49,029 INFO L83 FinitePrefix]: Finished finitePrefix Result has 49424 conditions, 23850 events. 16232/23850 cut-off events. For 2051/2051 co-relation queries the response was YES. Maximal size of possible extension queue 772. Compared 168175 event pairs, 715 based on Foata normal form. 7/21922 useless extension candidates. Maximal degree in co-relation 49413. Up to 18024 conditions per place. [2023-08-26 12:31:49,110 INFO L140 encePairwiseOnDemand]: 332/337 looper letters, 99 selfloop transitions, 8 changer transitions 0/123 dead transitions. [2023-08-26 12:31:49,111 INFO L145 encePairwiseOnDemand]: Finished differencePairwiseOnDemand. Result has 68 places, 123 transitions, 509 flow [2023-08-26 12:31:49,111 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2023-08-26 12:31:49,111 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 6 states. [2023-08-26 12:31:49,113 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 934 transitions. [2023-08-26 12:31:49,114 INFO L516 CegarLoopForPetriNet]: DFA transition density 0.4619188921859545 [2023-08-26 12:31:49,114 INFO L72 ComplementDD]: Start complementDD. Operand 6 states and 934 transitions. [2023-08-26 12:31:49,114 INFO L73 IsDeterministic]: Start isDeterministic. Operand 6 states and 934 transitions. [2023-08-26 12:31:49,114 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2023-08-26 12:31:49,114 INFO L117 ReachableStatesCopy]: Start reachableStatesCopy. Operand 6 states and 934 transitions. [2023-08-26 12:31:49,116 INFO L343 DoubleDeckerVisitor]: Before removal of dead ends has 7 states, 6 states have (on average 155.66666666666666) internal successors, (934), 6 states have internal predecessors, (934), 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-08-26 12:31:49,120 INFO L131 ReachableStatesCopy]: Finished reachableStatesCopy Result has 7 states, 7 states have (on average 337.0) internal successors, (2359), 7 states have internal predecessors, (2359), 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-08-26 12:31:49,121 INFO L81 ComplementDD]: Finished complementDD. Result has 7 states, 7 states have (on average 337.0) internal successors, (2359), 7 states have internal predecessors, (2359), 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-08-26 12:31:49,121 INFO L175 Difference]: Start difference. First operand has 64 places, 58 transitions, 161 flow. Second operand 6 states and 934 transitions. [2023-08-26 12:31:49,121 INFO L82 GeneralOperation]: Start removeRedundantFlow. Operand has 68 places, 123 transitions, 509 flow [2023-08-26 12:31:49,124 INFO L88 GeneralOperation]: Finished removeRedundantFlow, result has has 67 places, 123 transitions, 507 flow, removed 0 selfloop flow, removed 1 redundant places. [2023-08-26 12:31:49,125 INFO L231 Difference]: Finished difference. Result has 67 places, 60 transitions, 183 flow [2023-08-26 12:31:49,126 INFO L264 CegarLoopForPetriNet]: {PETRI_ALPHABET=337, PETRI_DIFFERENCE_MINUEND_FLOW=155, PETRI_DIFFERENCE_MINUEND_PLACES=62, PETRI_DIFFERENCE_MINUEND_TRANSITIONS=57, PETRI_DIFFERENCE_SUBTRAHEND_LETTERS_WITH_MORE_CHANGERS_THAN_LOOPERS=5, PETRI_DIFFERENCE_SUBTRAHEND_LOOPER_ONLY_LETTERS=52, PETRI_DIFFERENCE_SUBTRAHEND_STATES=6, PETRI_FLOW=183, PETRI_PLACES=67, PETRI_TRANSITIONS=60} [2023-08-26 12:31:49,127 INFO L281 CegarLoopForPetriNet]: 65 programPoint places, 2 predicate places. [2023-08-26 12:31:49,127 INFO L495 AbstractCegarLoop]: Abstraction has has 67 places, 60 transitions, 183 flow [2023-08-26 12:31:49,127 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 7 states have (on average 138.71428571428572) internal successors, (971), 7 states have internal predecessors, (971), 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-08-26 12:31:49,127 INFO L200 CegarLoopForPetriNet]: Found error trace [2023-08-26 12:31:49,127 INFO L208 CegarLoopForPetriNet]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1] [2023-08-26 12:31:49,135 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-08-26 12:31:49,335 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 3 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable10 [2023-08-26 12:31:49,336 INFO L420 AbstractCegarLoop]: === Iteration 4 === Targeting ULTIMATE.startErr2ASSERT_VIOLATIONASSERT === [ULTIMATE.startErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr3REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 3 more)] === [2023-08-26 12:31:49,336 INFO L145 PredicateUnifier]: Initialized classic predicate unifier [2023-08-26 12:31:49,336 INFO L85 PathProgramCache]: Analyzing trace with hash -38067635, now seen corresponding path program 1 times [2023-08-26 12:31:49,336 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-08-26 12:31:49,336 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [507905642] [2023-08-26 12:31:49,336 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-08-26 12:31:49,336 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-08-26 12:31:49,348 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-08-26 12:31:49,409 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2023-08-26 12:31:49,409 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-08-26 12:31:49,409 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [507905642] [2023-08-26 12:31:49,410 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [507905642] provided 1 perfect and 0 imperfect interpolant sequences [2023-08-26 12:31:49,410 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-08-26 12:31:49,410 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [1] imperfect sequences [] total 1 [2023-08-26 12:31:49,410 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [569279854] [2023-08-26 12:31:49,410 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-08-26 12:31:49,410 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2023-08-26 12:31:49,411 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-08-26 12:31:49,411 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2023-08-26 12:31:49,411 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2023-08-26 12:31:49,411 INFO L471 CegarLoopForPetriNet]: Number of universal loopers: 144 out of 337 [2023-08-26 12:31:49,412 INFO L103 encePairwiseOnDemand]: Start differencePairwiseOnDemand. First operand has 67 places, 60 transitions, 183 flow. Second operand has 3 states, 3 states have (on average 146.66666666666666) internal successors, (440), 3 states have internal predecessors, (440), 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-08-26 12:31:49,412 INFO L112 encePairwiseOnDemand]: Universal subtrahend loopers provided by user. [2023-08-26 12:31:49,412 INFO L113 encePairwiseOnDemand]: Number of universal subtrahend loopers: 144 of 337 [2023-08-26 12:31:49,412 INFO L73 FinitePrefix]: Start finitePrefix. Operand will be constructed on-demand [2023-08-26 12:31:52,084 INFO L124 PetriNetUnfolderBase]: 32959/47679 cut-off events. [2023-08-26 12:31:52,085 INFO L125 PetriNetUnfolderBase]: For 7277/7277 co-relation queries the response was YES. [2023-08-26 12:31:52,136 INFO L83 FinitePrefix]: Finished finitePrefix Result has 100437 conditions, 47679 events. 32959/47679 cut-off events. For 7277/7277 co-relation queries the response was YES. Maximal size of possible extension queue 1241. Compared 314739 event pairs, 13040 based on Foata normal form. 0/44386 useless extension candidates. Maximal degree in co-relation 100425. Up to 44344 conditions per place. [2023-08-26 12:31:52,304 INFO L140 encePairwiseOnDemand]: 332/337 looper letters, 73 selfloop transitions, 4 changer transitions 0/87 dead transitions. [2023-08-26 12:31:52,304 INFO L145 encePairwiseOnDemand]: Finished differencePairwiseOnDemand. Result has 69 places, 87 transitions, 431 flow [2023-08-26 12:31:52,304 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2023-08-26 12:31:52,304 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 3 states. [2023-08-26 12:31:52,306 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 3 states to 3 states and 502 transitions. [2023-08-26 12:31:52,306 INFO L516 CegarLoopForPetriNet]: DFA transition density 0.49653808110781406 [2023-08-26 12:31:52,306 INFO L72 ComplementDD]: Start complementDD. Operand 3 states and 502 transitions. [2023-08-26 12:31:52,306 INFO L73 IsDeterministic]: Start isDeterministic. Operand 3 states and 502 transitions. [2023-08-26 12:31:52,306 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2023-08-26 12:31:52,307 INFO L117 ReachableStatesCopy]: Start reachableStatesCopy. Operand 3 states and 502 transitions. [2023-08-26 12:31:52,307 INFO L343 DoubleDeckerVisitor]: Before removal of dead ends has 4 states, 3 states have (on average 167.33333333333334) internal successors, (502), 3 states have internal predecessors, (502), 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-08-26 12:31:52,309 INFO L131 ReachableStatesCopy]: Finished reachableStatesCopy Result has 4 states, 4 states have (on average 337.0) internal successors, (1348), 4 states have internal predecessors, (1348), 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-08-26 12:31:52,309 INFO L81 ComplementDD]: Finished complementDD. Result has 4 states, 4 states have (on average 337.0) internal successors, (1348), 4 states have internal predecessors, (1348), 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-08-26 12:31:52,310 INFO L175 Difference]: Start difference. First operand has 67 places, 60 transitions, 183 flow. Second operand 3 states and 502 transitions. [2023-08-26 12:31:52,310 INFO L82 GeneralOperation]: Start removeRedundantFlow. Operand has 69 places, 87 transitions, 431 flow [2023-08-26 12:31:52,315 INFO L88 GeneralOperation]: Finished removeRedundantFlow, result has has 66 places, 87 transitions, 392 flow, removed 12 selfloop flow, removed 3 redundant places. [2023-08-26 12:31:52,319 INFO L231 Difference]: Finished difference. Result has 67 places, 63 transitions, 188 flow [2023-08-26 12:31:52,320 INFO L264 CegarLoopForPetriNet]: {PETRI_ALPHABET=337, PETRI_DIFFERENCE_MINUEND_FLOW=162, PETRI_DIFFERENCE_MINUEND_PLACES=64, PETRI_DIFFERENCE_MINUEND_TRANSITIONS=60, PETRI_DIFFERENCE_SUBTRAHEND_LETTERS_WITH_MORE_CHANGERS_THAN_LOOPERS=1, PETRI_DIFFERENCE_SUBTRAHEND_LOOPER_ONLY_LETTERS=56, PETRI_DIFFERENCE_SUBTRAHEND_STATES=3, PETRI_FLOW=188, PETRI_PLACES=67, PETRI_TRANSITIONS=63} [2023-08-26 12:31:52,321 INFO L281 CegarLoopForPetriNet]: 65 programPoint places, 2 predicate places. [2023-08-26 12:31:52,321 INFO L495 AbstractCegarLoop]: Abstraction has has 67 places, 63 transitions, 188 flow [2023-08-26 12:31:52,321 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 146.66666666666666) internal successors, (440), 3 states have internal predecessors, (440), 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-08-26 12:31:52,321 INFO L200 CegarLoopForPetriNet]: Found error trace [2023-08-26 12:31:52,322 INFO L208 CegarLoopForPetriNet]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1] [2023-08-26 12:31:52,322 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable11 [2023-08-26 12:31:52,322 INFO L420 AbstractCegarLoop]: === Iteration 5 === Targeting ULTIMATE.startErr4REQUIRES_VIOLATIONMEMORY_DEREFERENCE === [ULTIMATE.startErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr3REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 3 more)] === [2023-08-26 12:31:52,322 INFO L145 PredicateUnifier]: Initialized classic predicate unifier [2023-08-26 12:31:52,322 INFO L85 PathProgramCache]: Analyzing trace with hash -38072014, now seen corresponding path program 1 times [2023-08-26 12:31:52,322 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-08-26 12:31:52,322 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1376167527] [2023-08-26 12:31:52,323 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-08-26 12:31:52,323 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-08-26 12:31:52,337 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-08-26 12:31:52,404 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2023-08-26 12:31:52,405 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-08-26 12:31:52,405 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1376167527] [2023-08-26 12:31:52,405 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1376167527] provided 1 perfect and 0 imperfect interpolant sequences [2023-08-26 12:31:52,405 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-08-26 12:31:52,405 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2023-08-26 12:31:52,405 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [765859806] [2023-08-26 12:31:52,405 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-08-26 12:31:52,406 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2023-08-26 12:31:52,406 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-08-26 12:31:52,407 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2023-08-26 12:31:52,407 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=6, Invalid=6, Unknown=0, NotChecked=0, Total=12 [2023-08-26 12:31:52,408 INFO L471 CegarLoopForPetriNet]: Number of universal loopers: 137 out of 337 [2023-08-26 12:31:52,408 INFO L103 encePairwiseOnDemand]: Start differencePairwiseOnDemand. First operand has 67 places, 63 transitions, 188 flow. Second operand has 4 states, 4 states have (on average 139.0) internal successors, (556), 4 states have internal predecessors, (556), 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-08-26 12:31:52,408 INFO L112 encePairwiseOnDemand]: Universal subtrahend loopers provided by user. [2023-08-26 12:31:52,408 INFO L113 encePairwiseOnDemand]: Number of universal subtrahend loopers: 137 of 337 [2023-08-26 12:31:52,408 INFO L73 FinitePrefix]: Start finitePrefix. Operand will be constructed on-demand [2023-08-26 12:31:54,115 INFO L124 PetriNetUnfolderBase]: 17240/26012 cut-off events. [2023-08-26 12:31:54,115 INFO L125 PetriNetUnfolderBase]: For 3096/3108 co-relation queries the response was YES. [2023-08-26 12:31:54,148 INFO L83 FinitePrefix]: Finished finitePrefix Result has 53607 conditions, 26012 events. 17240/26012 cut-off events. For 3096/3108 co-relation queries the response was YES. Maximal size of possible extension queue 822. Compared 183038 event pairs, 12987 based on Foata normal form. 3/24621 useless extension candidates. Maximal degree in co-relation 53595. Up to 19199 conditions per place. [2023-08-26 12:31:54,209 INFO L140 encePairwiseOnDemand]: 332/337 looper letters, 67 selfloop transitions, 4 changer transitions 0/89 dead transitions. [2023-08-26 12:31:54,210 INFO L145 encePairwiseOnDemand]: Finished differencePairwiseOnDemand. Result has 70 places, 89 transitions, 396 flow [2023-08-26 12:31:54,210 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2023-08-26 12:31:54,210 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 4 states. [2023-08-26 12:31:54,211 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 4 states to 4 states and 614 transitions. [2023-08-26 12:31:54,212 INFO L516 CegarLoopForPetriNet]: DFA transition density 0.45548961424332346 [2023-08-26 12:31:54,212 INFO L72 ComplementDD]: Start complementDD. Operand 4 states and 614 transitions. [2023-08-26 12:31:54,212 INFO L73 IsDeterministic]: Start isDeterministic. Operand 4 states and 614 transitions. [2023-08-26 12:31:54,212 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2023-08-26 12:31:54,212 INFO L117 ReachableStatesCopy]: Start reachableStatesCopy. Operand 4 states and 614 transitions. [2023-08-26 12:31:54,213 INFO L343 DoubleDeckerVisitor]: Before removal of dead ends has 5 states, 4 states have (on average 153.5) internal successors, (614), 4 states have internal predecessors, (614), 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-08-26 12:31:54,215 INFO L131 ReachableStatesCopy]: Finished reachableStatesCopy Result has 5 states, 5 states have (on average 337.0) internal successors, (1685), 5 states have internal predecessors, (1685), 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-08-26 12:31:54,216 INFO L81 ComplementDD]: Finished complementDD. Result has 5 states, 5 states have (on average 337.0) internal successors, (1685), 5 states have internal predecessors, (1685), 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-08-26 12:31:54,216 INFO L175 Difference]: Start difference. First operand has 67 places, 63 transitions, 188 flow. Second operand 4 states and 614 transitions. [2023-08-26 12:31:54,216 INFO L82 GeneralOperation]: Start removeRedundantFlow. Operand has 70 places, 89 transitions, 396 flow [2023-08-26 12:31:54,219 INFO L88 GeneralOperation]: Finished removeRedundantFlow, result has has 69 places, 89 transitions, 391 flow, removed 0 selfloop flow, removed 1 redundant places. [2023-08-26 12:31:54,220 INFO L231 Difference]: Finished difference. Result has 70 places, 64 transitions, 201 flow [2023-08-26 12:31:54,220 INFO L264 CegarLoopForPetriNet]: {PETRI_ALPHABET=337, PETRI_DIFFERENCE_MINUEND_FLOW=184, PETRI_DIFFERENCE_MINUEND_PLACES=66, PETRI_DIFFERENCE_MINUEND_TRANSITIONS=63, PETRI_DIFFERENCE_SUBTRAHEND_LETTERS_WITH_MORE_CHANGERS_THAN_LOOPERS=3, PETRI_DIFFERENCE_SUBTRAHEND_LOOPER_ONLY_LETTERS=59, PETRI_DIFFERENCE_SUBTRAHEND_STATES=4, PETRI_FLOW=201, PETRI_PLACES=70, PETRI_TRANSITIONS=64} [2023-08-26 12:31:54,220 INFO L281 CegarLoopForPetriNet]: 65 programPoint places, 5 predicate places. [2023-08-26 12:31:54,220 INFO L495 AbstractCegarLoop]: Abstraction has has 70 places, 64 transitions, 201 flow [2023-08-26 12:31:54,221 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 139.0) internal successors, (556), 4 states have internal predecessors, (556), 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-08-26 12:31:54,221 INFO L200 CegarLoopForPetriNet]: Found error trace [2023-08-26 12:31:54,221 INFO L208 CegarLoopForPetriNet]: trace histogram [4, 3, 3, 1, 1, 1, 1, 1] [2023-08-26 12:31:54,221 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable12 [2023-08-26 12:31:54,221 INFO L420 AbstractCegarLoop]: === Iteration 6 === Targeting ULTIMATE.startErr0INUSE_VIOLATIONSUFFICIENT_THREAD_INSTANCES === [ULTIMATE.startErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr3REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 3 more)] === [2023-08-26 12:31:54,221 INFO L145 PredicateUnifier]: Initialized classic predicate unifier [2023-08-26 12:31:54,221 INFO L85 PathProgramCache]: Analyzing trace with hash -1492711078, now seen corresponding path program 1 times [2023-08-26 12:31:54,222 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-08-26 12:31:54,222 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1980668621] [2023-08-26 12:31:54,222 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-08-26 12:31:54,222 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-08-26 12:31:54,238 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2023-08-26 12:31:54,238 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2023-08-26 12:31:54,248 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2023-08-26 12:31:54,259 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2023-08-26 12:31:54,261 INFO L360 BasicCegarLoop]: Counterexample is feasible [2023-08-26 12:31:54,261 INFO L805 garLoopResultBuilder]: Registering result UNSAFE for location ULTIMATE.startErr0INUSE_VIOLATIONSUFFICIENT_THREAD_INSTANCES (5 of 6 remaining) [2023-08-26 12:31:54,261 INFO L805 garLoopResultBuilder]: Registering result UNKNOWN for location ULTIMATE.startErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE (4 of 6 remaining) [2023-08-26 12:31:54,261 INFO L805 garLoopResultBuilder]: Registering result UNKNOWN for location ULTIMATE.startErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE (3 of 6 remaining) [2023-08-26 12:31:54,261 INFO L805 garLoopResultBuilder]: Registering result UNKNOWN for location ULTIMATE.startErr3REQUIRES_VIOLATIONMEMORY_DEREFERENCE (2 of 6 remaining) [2023-08-26 12:31:54,261 INFO L805 garLoopResultBuilder]: Registering result UNKNOWN for location ULTIMATE.startErr4REQUIRES_VIOLATIONMEMORY_DEREFERENCE (1 of 6 remaining) [2023-08-26 12:31:54,262 INFO L805 garLoopResultBuilder]: Registering result UNKNOWN for location ULTIMATE.startErr2ASSERT_VIOLATIONASSERT (0 of 6 remaining) [2023-08-26 12:31:54,262 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable13 [2023-08-26 12:31:54,262 INFO L445 BasicCegarLoop]: Path program histogram: [1, 1, 1, 1, 1, 1] [2023-08-26 12:31:54,262 WARN L233 ceAbstractionStarter]: 3 thread instances were not sufficient, I will increase this number and restart the analysis [2023-08-26 12:31:54,262 INFO L515 ceAbstractionStarter]: Constructing petrified ICFG for 4 thread instances. [2023-08-26 12:31:54,282 INFO L144 ThreadInstanceAdder]: Constructed 4 joinOtherThreadTransitions. [2023-08-26 12:31:54,284 INFO L73 FinitePrefix]: Start finitePrefix. Operand has 191 places, 219 transitions, 482 flow [2023-08-26 12:31:54,340 INFO L124 PetriNetUnfolderBase]: 101/658 cut-off events. [2023-08-26 12:31:54,340 INFO L125 PetriNetUnfolderBase]: For 48/48 co-relation queries the response was YES. [2023-08-26 12:31:54,345 INFO L83 FinitePrefix]: Finished finitePrefix Result has 713 conditions, 658 events. 101/658 cut-off events. For 48/48 co-relation queries the response was YES. Maximal size of possible extension queue 15. Compared 2670 event pairs, 6 based on Foata normal form. 0/510 useless extension candidates. Maximal degree in co-relation 456. Up to 32 conditions per place. [2023-08-26 12:31:54,345 INFO L82 GeneralOperation]: Start removeDead. Operand has 191 places, 219 transitions, 482 flow [2023-08-26 12:31:54,349 INFO L88 GeneralOperation]: Finished RemoveDead, result has has 191 places, 219 transitions, 482 flow [2023-08-26 12:31:54,349 INFO L124 etLargeBlockEncoding]: Petri net LBE is using variable-based independence relation. [2023-08-26 12:31:54,349 INFO L131 etLargeBlockEncoding]: Starting large block encoding on Petri net that has 191 places, 219 transitions, 482 flow [2023-08-26 12:31:54,349 INFO L113 LiptonReduction]: Starting Lipton reduction on Petri net that has 191 places, 219 transitions, 482 flow [2023-08-26 12:31:54,349 INFO L73 FinitePrefix]: Start finitePrefix. Operand has 191 places, 219 transitions, 482 flow [2023-08-26 12:31:54,405 INFO L124 PetriNetUnfolderBase]: 101/658 cut-off events. [2023-08-26 12:31:54,405 INFO L125 PetriNetUnfolderBase]: For 48/48 co-relation queries the response was YES. [2023-08-26 12:31:54,410 INFO L83 FinitePrefix]: Finished finitePrefix Result has 713 conditions, 658 events. 101/658 cut-off events. For 48/48 co-relation queries the response was YES. Maximal size of possible extension queue 15. Compared 2670 event pairs, 6 based on Foata normal form. 0/510 useless extension candidates. Maximal degree in co-relation 456. Up to 32 conditions per place. [2023-08-26 12:31:54,427 INFO L119 LiptonReduction]: Number of co-enabled transitions 24304 [2023-08-26 12:31:57,753 INFO L134 LiptonReduction]: Checked pairs total: 64862 [2023-08-26 12:31:57,754 INFO L136 LiptonReduction]: Total number of compositions: 160 [2023-08-26 12:31:57,755 INFO L356 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2023-08-26 12:31:57,755 INFO L357 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=false, mAutomataTypeConcurrency=PETRI_NET, mHoareTripleChecks=INCREMENTAL, mHoareAnnotationPositions=LoopsAndPotentialCycles, 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;@44a04137, mLbeIndependenceSettings=[IndependenceType=SYNTACTIC, AbstractionType=NONE, UseConditional=, UseSemiCommutativity=, Solver=, SolverTimeout=] [2023-08-26 12:31:57,755 INFO L358 AbstractCegarLoop]: Starting to check reachability of 6 error locations. [2023-08-26 12:31:57,756 INFO L185 PetriNetUnfolderBase]: Found word, exiting Unfolder. [2023-08-26 12:31:57,756 INFO L124 PetriNetUnfolderBase]: 0/2 cut-off events. [2023-08-26 12:31:57,756 INFO L125 PetriNetUnfolderBase]: For 0/0 co-relation queries the response was YES. [2023-08-26 12:31:57,756 INFO L200 CegarLoopForPetriNet]: Found error trace [2023-08-26 12:31:57,757 INFO L208 CegarLoopForPetriNet]: trace histogram [1, 1] [2023-08-26 12:31:57,757 INFO L420 AbstractCegarLoop]: === Iteration 1 === Targeting ULTIMATE.startErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE === [ULTIMATE.startErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr3REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 3 more)] === [2023-08-26 12:31:57,757 INFO L145 PredicateUnifier]: Initialized classic predicate unifier [2023-08-26 12:31:57,757 INFO L85 PathProgramCache]: Analyzing trace with hash 51360, now seen corresponding path program 1 times [2023-08-26 12:31:57,757 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-08-26 12:31:57,757 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [965060959] [2023-08-26 12:31:57,757 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-08-26 12:31:57,758 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-08-26 12:31:57,768 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-08-26 12:31:57,784 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-08-26 12:31:57,784 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-08-26 12:31:57,784 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [965060959] [2023-08-26 12:31:57,784 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [965060959] provided 1 perfect and 0 imperfect interpolant sequences [2023-08-26 12:31:57,784 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-08-26 12:31:57,785 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [1] imperfect sequences [] total 1 [2023-08-26 12:31:57,785 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1209622976] [2023-08-26 12:31:57,785 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-08-26 12:31:57,785 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2023-08-26 12:31:57,785 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-08-26 12:31:57,785 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2023-08-26 12:31:57,785 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2023-08-26 12:31:57,786 INFO L471 CegarLoopForPetriNet]: Number of universal loopers: 164 out of 379 [2023-08-26 12:31:57,786 INFO L103 encePairwiseOnDemand]: Start differencePairwiseOnDemand. First operand has 79 places, 103 transitions, 250 flow. Second operand has 3 states, 3 states have (on average 164.66666666666666) internal successors, (494), 3 states have internal predecessors, (494), 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-08-26 12:31:57,787 INFO L112 encePairwiseOnDemand]: Universal subtrahend loopers provided by user. [2023-08-26 12:31:57,787 INFO L113 encePairwiseOnDemand]: Number of universal subtrahend loopers: 164 of 379 [2023-08-26 12:31:57,787 INFO L73 FinitePrefix]: Start finitePrefix. Operand will be constructed on-demand [2023-08-26 12:32:30,720 INFO L124 PetriNetUnfolderBase]: 372142/513275 cut-off events. [2023-08-26 12:32:30,721 INFO L125 PetriNetUnfolderBase]: For 14786/14786 co-relation queries the response was YES. [2023-08-26 12:32:31,417 INFO L83 FinitePrefix]: Finished finitePrefix Result has 1005172 conditions, 513275 events. 372142/513275 cut-off events. For 14786/14786 co-relation queries the response was YES. Maximal size of possible extension queue 11269. Compared 4109443 event pairs, 335960 based on Foata normal form. 90105/547591 useless extension candidates. Maximal degree in co-relation 87650. Up to 445990 conditions per place. [2023-08-26 12:32:32,979 INFO L140 encePairwiseOnDemand]: 347/379 looper letters, 53 selfloop transitions, 1 changer transitions 33/103 dead transitions. [2023-08-26 12:32:32,979 INFO L145 encePairwiseOnDemand]: Finished differencePairwiseOnDemand. Result has 78 places, 103 transitions, 424 flow [2023-08-26 12:32:32,980 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2023-08-26 12:32:32,980 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 3 states. [2023-08-26 12:32:32,981 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 3 states to 3 states and 633 transitions. [2023-08-26 12:32:32,982 INFO L516 CegarLoopForPetriNet]: DFA transition density 0.5567282321899736 [2023-08-26 12:32:32,982 INFO L72 ComplementDD]: Start complementDD. Operand 3 states and 633 transitions. [2023-08-26 12:32:32,982 INFO L73 IsDeterministic]: Start isDeterministic. Operand 3 states and 633 transitions. [2023-08-26 12:32:32,982 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2023-08-26 12:32:32,982 INFO L117 ReachableStatesCopy]: Start reachableStatesCopy. Operand 3 states and 633 transitions. [2023-08-26 12:32:32,984 INFO L343 DoubleDeckerVisitor]: Before removal of dead ends has 4 states, 3 states have (on average 211.0) internal successors, (633), 3 states have internal predecessors, (633), 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-08-26 12:32:32,986 INFO L131 ReachableStatesCopy]: Finished reachableStatesCopy Result has 4 states, 4 states have (on average 379.0) internal successors, (1516), 4 states have internal predecessors, (1516), 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-08-26 12:32:32,986 INFO L81 ComplementDD]: Finished complementDD. Result has 4 states, 4 states have (on average 379.0) internal successors, (1516), 4 states have internal predecessors, (1516), 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-08-26 12:32:32,986 INFO L175 Difference]: Start difference. First operand has 79 places, 103 transitions, 250 flow. Second operand 3 states and 633 transitions. [2023-08-26 12:32:32,986 INFO L82 GeneralOperation]: Start removeRedundantFlow. Operand has 78 places, 103 transitions, 424 flow [2023-08-26 12:32:32,993 INFO L88 GeneralOperation]: Finished removeRedundantFlow, result has has 78 places, 103 transitions, 424 flow, removed 0 selfloop flow, removed 0 redundant places. [2023-08-26 12:32:32,994 INFO L231 Difference]: Finished difference. Result has 78 places, 70 transitions, 186 flow [2023-08-26 12:32:32,994 INFO L264 CegarLoopForPetriNet]: {PETRI_ALPHABET=379, PETRI_DIFFERENCE_MINUEND_FLOW=188, PETRI_DIFFERENCE_MINUEND_PLACES=76, PETRI_DIFFERENCE_MINUEND_TRANSITIONS=72, PETRI_DIFFERENCE_SUBTRAHEND_LETTERS_WITH_MORE_CHANGERS_THAN_LOOPERS=1, PETRI_DIFFERENCE_SUBTRAHEND_LOOPER_ONLY_LETTERS=71, PETRI_DIFFERENCE_SUBTRAHEND_STATES=3, PETRI_FLOW=186, PETRI_PLACES=78, PETRI_TRANSITIONS=70} [2023-08-26 12:32:32,994 INFO L281 CegarLoopForPetriNet]: 79 programPoint places, -1 predicate places. [2023-08-26 12:32:32,994 INFO L495 AbstractCegarLoop]: Abstraction has has 78 places, 70 transitions, 186 flow [2023-08-26 12:32:32,995 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 164.66666666666666) internal successors, (494), 3 states have internal predecessors, (494), 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-08-26 12:32:32,995 INFO L200 CegarLoopForPetriNet]: Found error trace [2023-08-26 12:32:32,995 INFO L208 CegarLoopForPetriNet]: trace histogram [1, 1] [2023-08-26 12:32:32,995 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable14 [2023-08-26 12:32:32,995 INFO L420 AbstractCegarLoop]: === Iteration 2 === Targeting ULTIMATE.startErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE === [ULTIMATE.startErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr3REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 3 more)] === [2023-08-26 12:32:32,995 INFO L145 PredicateUnifier]: Initialized classic predicate unifier [2023-08-26 12:32:32,996 INFO L85 PathProgramCache]: Analyzing trace with hash 51358, now seen corresponding path program 1 times [2023-08-26 12:32:32,996 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-08-26 12:32:32,996 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1516970311] [2023-08-26 12:32:32,996 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-08-26 12:32:32,996 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-08-26 12:32:33,001 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-08-26 12:32:33,032 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-08-26 12:32:33,032 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-08-26 12:32:33,032 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1516970311] [2023-08-26 12:32:33,033 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1516970311] provided 1 perfect and 0 imperfect interpolant sequences [2023-08-26 12:32:33,033 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-08-26 12:32:33,033 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [1] imperfect sequences [] total 1 [2023-08-26 12:32:33,033 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [966193510] [2023-08-26 12:32:33,033 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-08-26 12:32:33,033 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2023-08-26 12:32:33,033 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-08-26 12:32:33,034 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2023-08-26 12:32:33,034 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2023-08-26 12:32:33,034 INFO L471 CegarLoopForPetriNet]: Number of universal loopers: 159 out of 379 [2023-08-26 12:32:33,035 INFO L103 encePairwiseOnDemand]: Start differencePairwiseOnDemand. First operand has 78 places, 70 transitions, 186 flow. Second operand has 3 states, 3 states have (on average 159.66666666666666) internal successors, (479), 3 states have internal predecessors, (479), 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-08-26 12:32:33,035 INFO L112 encePairwiseOnDemand]: Universal subtrahend loopers provided by user. [2023-08-26 12:32:33,035 INFO L113 encePairwiseOnDemand]: Number of universal subtrahend loopers: 159 of 379 [2023-08-26 12:32:33,035 INFO L73 FinitePrefix]: Start finitePrefix. Operand will be constructed on-demand [2023-08-26 12:33:00,039 INFO L124 PetriNetUnfolderBase]: 321014/445069 cut-off events. [2023-08-26 12:33:00,039 INFO L125 PetriNetUnfolderBase]: For 14778/14778 co-relation queries the response was YES. [2023-08-26 12:33:00,691 INFO L83 FinitePrefix]: Finished finitePrefix Result has 870262 conditions, 445069 events. 321014/445069 cut-off events. For 14778/14778 co-relation queries the response was YES. Maximal size of possible extension queue 9865. Compared 3520326 event pairs, 231426 based on Foata normal form. 0/405306 useless extension candidates. Maximal degree in co-relation 870252. Up to 416874 conditions per place. [2023-08-26 12:33:02,721 INFO L140 encePairwiseOnDemand]: 374/379 looper letters, 62 selfloop transitions, 2 changer transitions 0/80 dead transitions. [2023-08-26 12:33:02,721 INFO L145 encePairwiseOnDemand]: Finished differencePairwiseOnDemand. Result has 78 places, 80 transitions, 334 flow [2023-08-26 12:33:02,722 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2023-08-26 12:33:02,745 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 3 states. [2023-08-26 12:33:02,747 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 3 states to 3 states and 544 transitions. [2023-08-26 12:33:02,747 INFO L516 CegarLoopForPetriNet]: DFA transition density 0.47845206684256814 [2023-08-26 12:33:02,747 INFO L72 ComplementDD]: Start complementDD. Operand 3 states and 544 transitions. [2023-08-26 12:33:02,747 INFO L73 IsDeterministic]: Start isDeterministic. Operand 3 states and 544 transitions. [2023-08-26 12:33:02,748 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2023-08-26 12:33:02,748 INFO L117 ReachableStatesCopy]: Start reachableStatesCopy. Operand 3 states and 544 transitions. [2023-08-26 12:33:02,749 INFO L343 DoubleDeckerVisitor]: Before removal of dead ends has 4 states, 3 states have (on average 181.33333333333334) internal successors, (544), 3 states have internal predecessors, (544), 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-08-26 12:33:02,751 INFO L131 ReachableStatesCopy]: Finished reachableStatesCopy Result has 4 states, 4 states have (on average 379.0) internal successors, (1516), 4 states have internal predecessors, (1516), 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-08-26 12:33:02,752 INFO L81 ComplementDD]: Finished complementDD. Result has 4 states, 4 states have (on average 379.0) internal successors, (1516), 4 states have internal predecessors, (1516), 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-08-26 12:33:02,752 INFO L175 Difference]: Start difference. First operand has 78 places, 70 transitions, 186 flow. Second operand 3 states and 544 transitions. [2023-08-26 12:33:02,752 INFO L82 GeneralOperation]: Start removeRedundantFlow. Operand has 78 places, 80 transitions, 334 flow [2023-08-26 12:33:02,757 INFO L88 GeneralOperation]: Finished removeRedundantFlow, result has has 77 places, 80 transitions, 333 flow, removed 0 selfloop flow, removed 1 redundant places. [2023-08-26 12:33:02,758 INFO L231 Difference]: Finished difference. Result has 78 places, 71 transitions, 201 flow [2023-08-26 12:33:02,758 INFO L264 CegarLoopForPetriNet]: {PETRI_ALPHABET=379, PETRI_DIFFERENCE_MINUEND_FLOW=185, PETRI_DIFFERENCE_MINUEND_PLACES=75, PETRI_DIFFERENCE_MINUEND_TRANSITIONS=70, PETRI_DIFFERENCE_SUBTRAHEND_LETTERS_WITH_MORE_CHANGERS_THAN_LOOPERS=1, PETRI_DIFFERENCE_SUBTRAHEND_LOOPER_ONLY_LETTERS=68, PETRI_DIFFERENCE_SUBTRAHEND_STATES=3, PETRI_FLOW=201, PETRI_PLACES=78, PETRI_TRANSITIONS=71} [2023-08-26 12:33:02,774 INFO L281 CegarLoopForPetriNet]: 79 programPoint places, -1 predicate places. [2023-08-26 12:33:02,774 INFO L495 AbstractCegarLoop]: Abstraction has has 78 places, 71 transitions, 201 flow [2023-08-26 12:33:02,774 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 159.66666666666666) internal successors, (479), 3 states have internal predecessors, (479), 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-08-26 12:33:02,774 INFO L200 CegarLoopForPetriNet]: Found error trace [2023-08-26 12:33:02,774 INFO L208 CegarLoopForPetriNet]: trace histogram [1, 1, 1, 1, 1, 1] [2023-08-26 12:33:02,775 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable15 [2023-08-26 12:33:02,775 INFO L420 AbstractCegarLoop]: === Iteration 3 === Targeting ULTIMATE.startErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE === [ULTIMATE.startErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr3REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 3 more)] === [2023-08-26 12:33:02,775 INFO L145 PredicateUnifier]: Initialized classic predicate unifier [2023-08-26 12:33:02,775 INFO L85 PathProgramCache]: Analyzing trace with hash 229686976, now seen corresponding path program 1 times [2023-08-26 12:33:02,775 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-08-26 12:33:02,775 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [77607511] [2023-08-26 12:33:02,775 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-08-26 12:33:02,776 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-08-26 12:33:02,783 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-08-26 12:33:02,891 INFO L134 CoverageAnalysis]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-08-26 12:33:02,892 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-08-26 12:33:02,892 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [77607511] [2023-08-26 12:33:02,892 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [77607511] provided 0 perfect and 1 imperfect interpolant sequences [2023-08-26 12:33:02,892 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [376030266] [2023-08-26 12:33:02,892 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-08-26 12:33:02,892 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-08-26 12:33:02,892 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-08-26 12:33:02,921 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-08-26 12:33:02,977 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-08-26 12:33:03,062 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-08-26 12:33:03,077 INFO L262 TraceCheckSpWp]: Trace formula consists of 120 conjuncts, 9 conjunts are in the unsatisfiable core [2023-08-26 12:33:03,078 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-08-26 12:33:03,088 INFO L351 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 6 treesize of output 5 [2023-08-26 12:33:03,117 INFO L134 CoverageAnalysis]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-08-26 12:33:03,118 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-08-26 12:33:03,153 INFO L134 CoverageAnalysis]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-08-26 12:33:03,153 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [376030266] provided 0 perfect and 2 imperfect interpolant sequences [2023-08-26 12:33:03,153 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2023-08-26 12:33:03,153 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [2, 2, 2] total 5 [2023-08-26 12:33:03,153 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1293843995] [2023-08-26 12:33:03,153 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2023-08-26 12:33:03,154 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2023-08-26 12:33:03,154 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-08-26 12:33:03,155 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2023-08-26 12:33:03,155 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=18, Invalid=24, Unknown=0, NotChecked=0, Total=42 [2023-08-26 12:33:03,156 INFO L471 CegarLoopForPetriNet]: Number of universal loopers: 159 out of 379 [2023-08-26 12:33:03,157 INFO L103 encePairwiseOnDemand]: Start differencePairwiseOnDemand. First operand has 78 places, 71 transitions, 201 flow. Second operand has 7 states, 7 states have (on average 160.71428571428572) internal successors, (1125), 7 states have internal predecessors, (1125), 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-08-26 12:33:03,157 INFO L112 encePairwiseOnDemand]: Universal subtrahend loopers provided by user. [2023-08-26 12:33:03,157 INFO L113 encePairwiseOnDemand]: Number of universal subtrahend loopers: 159 of 379 [2023-08-26 12:33:03,157 INFO L73 FinitePrefix]: Start finitePrefix. Operand will be constructed on-demand [2023-08-26 12:33:31,405 INFO L124 PetriNetUnfolderBase]: 319077/422808 cut-off events. [2023-08-26 12:33:31,406 INFO L125 PetriNetUnfolderBase]: For 18523/18523 co-relation queries the response was YES. [2023-08-26 12:33:32,122 INFO L83 FinitePrefix]: Finished finitePrefix Result has 872391 conditions, 422808 events. 319077/422808 cut-off events. For 18523/18523 co-relation queries the response was YES. Maximal size of possible extension queue 9424. Compared 3152559 event pairs, 6012 based on Foata normal form. 9/394827 useless extension candidates. Maximal degree in co-relation 872379. Up to 359184 conditions per place. [2023-08-26 12:33:33,578 INFO L140 encePairwiseOnDemand]: 373/379 looper letters, 133 selfloop transitions, 10 changer transitions 0/159 dead transitions. [2023-08-26 12:33:33,578 INFO L145 encePairwiseOnDemand]: Finished differencePairwiseOnDemand. Result has 83 places, 159 transitions, 675 flow [2023-08-26 12:33:33,578 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2023-08-26 12:33:33,578 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 6 states. [2023-08-26 12:33:33,580 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 1102 transitions. [2023-08-26 12:33:33,581 INFO L516 CegarLoopForPetriNet]: DFA transition density 0.484608619173263 [2023-08-26 12:33:33,581 INFO L72 ComplementDD]: Start complementDD. Operand 6 states and 1102 transitions. [2023-08-26 12:33:33,581 INFO L73 IsDeterministic]: Start isDeterministic. Operand 6 states and 1102 transitions. [2023-08-26 12:33:33,581 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2023-08-26 12:33:33,582 INFO L117 ReachableStatesCopy]: Start reachableStatesCopy. Operand 6 states and 1102 transitions. [2023-08-26 12:33:33,584 INFO L343 DoubleDeckerVisitor]: Before removal of dead ends has 7 states, 6 states have (on average 183.66666666666666) internal successors, (1102), 6 states have internal predecessors, (1102), 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-08-26 12:33:33,587 INFO L131 ReachableStatesCopy]: Finished reachableStatesCopy Result has 7 states, 7 states have (on average 379.0) internal successors, (2653), 7 states have internal predecessors, (2653), 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-08-26 12:33:33,587 INFO L81 ComplementDD]: Finished complementDD. Result has 7 states, 7 states have (on average 379.0) internal successors, (2653), 7 states have internal predecessors, (2653), 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-08-26 12:33:33,587 INFO L175 Difference]: Start difference. First operand has 78 places, 71 transitions, 201 flow. Second operand 6 states and 1102 transitions. [2023-08-26 12:33:33,587 INFO L82 GeneralOperation]: Start removeRedundantFlow. Operand has 83 places, 159 transitions, 675 flow [2023-08-26 12:33:33,637 INFO L88 GeneralOperation]: Finished removeRedundantFlow, result has has 82 places, 159 transitions, 673 flow, removed 0 selfloop flow, removed 1 redundant places. [2023-08-26 12:33:33,638 INFO L231 Difference]: Finished difference. Result has 86 places, 78 transitions, 275 flow [2023-08-26 12:33:33,638 INFO L264 CegarLoopForPetriNet]: {PETRI_ALPHABET=379, PETRI_DIFFERENCE_MINUEND_FLOW=199, PETRI_DIFFERENCE_MINUEND_PLACES=77, PETRI_DIFFERENCE_MINUEND_TRANSITIONS=71, PETRI_DIFFERENCE_SUBTRAHEND_LETTERS_WITH_MORE_CHANGERS_THAN_LOOPERS=5, PETRI_DIFFERENCE_SUBTRAHEND_LOOPER_ONLY_LETTERS=65, PETRI_DIFFERENCE_SUBTRAHEND_STATES=6, PETRI_FLOW=275, PETRI_PLACES=86, PETRI_TRANSITIONS=78} [2023-08-26 12:33:33,639 INFO L281 CegarLoopForPetriNet]: 79 programPoint places, 7 predicate places. [2023-08-26 12:33:33,639 INFO L495 AbstractCegarLoop]: Abstraction has has 86 places, 78 transitions, 275 flow [2023-08-26 12:33:33,639 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 7 states have (on average 160.71428571428572) internal successors, (1125), 7 states have internal predecessors, (1125), 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-08-26 12:33:33,640 INFO L200 CegarLoopForPetriNet]: Found error trace [2023-08-26 12:33:33,640 INFO L208 CegarLoopForPetriNet]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1] [2023-08-26 12:33:33,645 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Ended with exit code 0 [2023-08-26 12:33:33,844 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable16,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-08-26 12:33:33,844 INFO L420 AbstractCegarLoop]: === Iteration 4 === Targeting ULTIMATE.startErr4REQUIRES_VIOLATIONMEMORY_DEREFERENCE === [ULTIMATE.startErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr3REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 3 more)] === [2023-08-26 12:33:33,845 INFO L145 PredicateUnifier]: Initialized classic predicate unifier [2023-08-26 12:33:33,845 INFO L85 PathProgramCache]: Analyzing trace with hash 2015720303, now seen corresponding path program 1 times [2023-08-26 12:33:33,845 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-08-26 12:33:33,845 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1294108975] [2023-08-26 12:33:33,845 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-08-26 12:33:33,845 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-08-26 12:33:33,855 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-08-26 12:33:33,930 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 0 proven. 5 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2023-08-26 12:33:33,930 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-08-26 12:33:33,930 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1294108975] [2023-08-26 12:33:33,930 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1294108975] provided 0 perfect and 1 imperfect interpolant sequences [2023-08-26 12:33:33,930 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2063427692] [2023-08-26 12:33:33,930 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-08-26 12:33:33,930 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-08-26 12:33:33,930 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-08-26 12:33:33,931 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-08-26 12:33:33,934 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-08-26 12:33:34,012 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-08-26 12:33:34,013 INFO L262 TraceCheckSpWp]: Trace formula consists of 147 conjuncts, 4 conjunts are in the unsatisfiable core [2023-08-26 12:33:34,014 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-08-26 12:33:34,044 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-08-26 12:33:34,044 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-08-26 12:33:34,091 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-08-26 12:33:34,091 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2063427692] provided 0 perfect and 2 imperfect interpolant sequences [2023-08-26 12:33:34,091 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2023-08-26 12:33:34,091 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 4, 4] total 11 [2023-08-26 12:33:34,092 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1055608611] [2023-08-26 12:33:34,092 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2023-08-26 12:33:34,092 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2023-08-26 12:33:34,093 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-08-26 12:33:34,093 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2023-08-26 12:33:34,094 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=51, Invalid=81, Unknown=0, NotChecked=0, Total=132 [2023-08-26 12:33:34,095 INFO L471 CegarLoopForPetriNet]: Number of universal loopers: 153 out of 379 [2023-08-26 12:33:34,096 INFO L103 encePairwiseOnDemand]: Start differencePairwiseOnDemand. First operand has 86 places, 78 transitions, 275 flow. Second operand has 12 states, 12 states have (on average 155.33333333333334) internal successors, (1864), 12 states have internal predecessors, (1864), 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-08-26 12:33:34,096 INFO L112 encePairwiseOnDemand]: Universal subtrahend loopers provided by user. [2023-08-26 12:33:34,097 INFO L113 encePairwiseOnDemand]: Number of universal subtrahend loopers: 153 of 379 [2023-08-26 12:33:34,097 INFO L73 FinitePrefix]: Start finitePrefix. Operand will be constructed on-demand [2023-08-26 12:33:41,416 INFO L124 PetriNetUnfolderBase]: 82402/116800 cut-off events. [2023-08-26 12:33:41,417 INFO L125 PetriNetUnfolderBase]: For 84403/84403 co-relation queries the response was YES. [2023-08-26 12:33:41,664 INFO L83 FinitePrefix]: Finished finitePrefix Result has 307114 conditions, 116800 events. 82402/116800 cut-off events. For 84403/84403 co-relation queries the response was YES. Maximal size of possible extension queue 3082. Compared 871385 event pairs, 70 based on Foata normal form. 6561/123359 useless extension candidates. Maximal degree in co-relation 307097. Up to 79461 conditions per place. [2023-08-26 12:33:41,995 INFO L140 encePairwiseOnDemand]: 375/379 looper letters, 119 selfloop transitions, 5 changer transitions 0/139 dead transitions. [2023-08-26 12:33:41,995 INFO L145 encePairwiseOnDemand]: Finished differencePairwiseOnDemand. Result has 81 places, 139 transitions, 607 flow [2023-08-26 12:33:41,995 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2023-08-26 12:33:41,996 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 7 states. [2023-08-26 12:33:41,997 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 7 states to 7 states and 1201 transitions. [2023-08-26 12:33:41,998 INFO L516 CegarLoopForPetriNet]: DFA transition density 0.45269506219374295 [2023-08-26 12:33:41,998 INFO L72 ComplementDD]: Start complementDD. Operand 7 states and 1201 transitions. [2023-08-26 12:33:41,998 INFO L73 IsDeterministic]: Start isDeterministic. Operand 7 states and 1201 transitions. [2023-08-26 12:33:41,999 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2023-08-26 12:33:41,999 INFO L117 ReachableStatesCopy]: Start reachableStatesCopy. Operand 7 states and 1201 transitions. [2023-08-26 12:33:42,001 INFO L343 DoubleDeckerVisitor]: Before removal of dead ends has 8 states, 7 states have (on average 171.57142857142858) internal successors, (1201), 7 states have internal predecessors, (1201), 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-08-26 12:33:42,005 INFO L131 ReachableStatesCopy]: Finished reachableStatesCopy Result has 8 states, 8 states have (on average 379.0) internal successors, (3032), 8 states have internal predecessors, (3032), 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-08-26 12:33:42,005 INFO L81 ComplementDD]: Finished complementDD. Result has 8 states, 8 states have (on average 379.0) internal successors, (3032), 8 states have internal predecessors, (3032), 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-08-26 12:33:42,005 INFO L175 Difference]: Start difference. First operand has 86 places, 78 transitions, 275 flow. Second operand 7 states and 1201 transitions. [2023-08-26 12:33:42,006 INFO L82 GeneralOperation]: Start removeRedundantFlow. Operand has 81 places, 139 transitions, 607 flow [2023-08-26 12:33:42,139 INFO L88 GeneralOperation]: Finished removeRedundantFlow, result has has 80 places, 139 transitions, 587 flow, removed 9 selfloop flow, removed 1 redundant places. [2023-08-26 12:33:42,141 INFO L231 Difference]: Finished difference. Result has 80 places, 58 transitions, 181 flow [2023-08-26 12:33:42,141 INFO L264 CegarLoopForPetriNet]: {PETRI_ALPHABET=379, PETRI_DIFFERENCE_MINUEND_FLOW=171, PETRI_DIFFERENCE_MINUEND_PLACES=74, PETRI_DIFFERENCE_MINUEND_TRANSITIONS=58, PETRI_DIFFERENCE_SUBTRAHEND_LETTERS_WITH_MORE_CHANGERS_THAN_LOOPERS=5, PETRI_DIFFERENCE_SUBTRAHEND_LOOPER_ONLY_LETTERS=53, PETRI_DIFFERENCE_SUBTRAHEND_STATES=7, PETRI_FLOW=181, PETRI_PLACES=80, PETRI_TRANSITIONS=58} [2023-08-26 12:33:42,141 INFO L281 CegarLoopForPetriNet]: 79 programPoint places, 1 predicate places. [2023-08-26 12:33:42,141 INFO L495 AbstractCegarLoop]: Abstraction has has 80 places, 58 transitions, 181 flow [2023-08-26 12:33:42,142 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 12 states have (on average 155.33333333333334) internal successors, (1864), 12 states have internal predecessors, (1864), 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-08-26 12:33:42,142 INFO L200 CegarLoopForPetriNet]: Found error trace [2023-08-26 12:33:42,142 INFO L208 CegarLoopForPetriNet]: trace histogram [4, 4, 4, 1, 1, 1, 1, 1, 1] [2023-08-26 12:33:42,150 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Forceful destruction successful, exit code 0 [2023-08-26 12:33:42,348 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable17 [2023-08-26 12:33:42,349 INFO L420 AbstractCegarLoop]: === Iteration 5 === Targeting ULTIMATE.startErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE === [ULTIMATE.startErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr3REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 3 more)] === [2023-08-26 12:33:42,349 INFO L145 PredicateUnifier]: Initialized classic predicate unifier [2023-08-26 12:33:42,349 INFO L85 PathProgramCache]: Analyzing trace with hash 118536032, now seen corresponding path program 1 times [2023-08-26 12:33:42,349 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-08-26 12:33:42,349 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [255929999] [2023-08-26 12:33:42,349 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-08-26 12:33:42,350 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-08-26 12:33:42,365 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-08-26 12:33:42,507 INFO L134 CoverageAnalysis]: Checked inductivity of 28 backedges. 0 proven. 28 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-08-26 12:33:42,507 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-08-26 12:33:42,508 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [255929999] [2023-08-26 12:33:42,508 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [255929999] provided 0 perfect and 1 imperfect interpolant sequences [2023-08-26 12:33:42,508 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1941662891] [2023-08-26 12:33:42,508 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-08-26 12:33:42,508 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-08-26 12:33:42,508 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-08-26 12:33:42,509 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-08-26 12:33:42,511 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-08-26 12:33:42,592 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-08-26 12:33:42,593 INFO L262 TraceCheckSpWp]: Trace formula consists of 186 conjuncts, 15 conjunts are in the unsatisfiable core [2023-08-26 12:33:42,594 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-08-26 12:33:42,601 INFO L351 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 6 treesize of output 5 [2023-08-26 12:33:42,724 INFO L134 CoverageAnalysis]: Checked inductivity of 28 backedges. 0 proven. 28 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-08-26 12:33:42,724 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-08-26 12:33:42,867 INFO L134 CoverageAnalysis]: Checked inductivity of 28 backedges. 0 proven. 28 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-08-26 12:33:42,867 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1941662891] provided 0 perfect and 2 imperfect interpolant sequences [2023-08-26 12:33:42,867 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2023-08-26 12:33:42,867 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 5, 5] total 14 [2023-08-26 12:33:42,868 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [489243324] [2023-08-26 12:33:42,869 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2023-08-26 12:33:42,869 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2023-08-26 12:33:42,869 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-08-26 12:33:42,870 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2023-08-26 12:33:42,870 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=78, Invalid=162, Unknown=0, NotChecked=0, Total=240 [2023-08-26 12:33:42,871 INFO L471 CegarLoopForPetriNet]: Number of universal loopers: 159 out of 379 [2023-08-26 12:33:42,873 INFO L103 encePairwiseOnDemand]: Start differencePairwiseOnDemand. First operand has 80 places, 58 transitions, 181 flow. Second operand has 16 states, 16 states have (on average 161.4375) internal successors, (2583), 16 states have internal predecessors, (2583), 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-08-26 12:33:42,873 INFO L112 encePairwiseOnDemand]: Universal subtrahend loopers provided by user. [2023-08-26 12:33:42,874 INFO L113 encePairwiseOnDemand]: Number of universal subtrahend loopers: 159 of 379 [2023-08-26 12:33:42,874 INFO L73 FinitePrefix]: Start finitePrefix. Operand will be constructed on-demand [2023-08-26 12:33:48,560 INFO L124 PetriNetUnfolderBase]: 61747/90184 cut-off events. [2023-08-26 12:33:48,560 INFO L125 PetriNetUnfolderBase]: For 57825/57825 co-relation queries the response was YES. [2023-08-26 12:33:48,786 INFO L83 FinitePrefix]: Finished finitePrefix Result has 211820 conditions, 90184 events. 61747/90184 cut-off events. For 57825/57825 co-relation queries the response was YES. Maximal size of possible extension queue 2427. Compared 685246 event pairs, 567 based on Foata normal form. 5832/95989 useless extension candidates. Maximal degree in co-relation 211802. Up to 52974 conditions per place. [2023-08-26 12:33:49,264 INFO L140 encePairwiseOnDemand]: 376/379 looper letters, 118 selfloop transitions, 5 changer transitions 0/138 dead transitions. [2023-08-26 12:33:49,264 INFO L145 encePairwiseOnDemand]: Finished differencePairwiseOnDemand. Result has 85 places, 138 transitions, 585 flow [2023-08-26 12:33:49,264 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2023-08-26 12:33:49,264 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 7 states. [2023-08-26 12:33:49,266 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 7 states to 7 states and 1237 transitions. [2023-08-26 12:33:49,266 INFO L516 CegarLoopForPetriNet]: DFA transition density 0.4662646061062948 [2023-08-26 12:33:49,267 INFO L72 ComplementDD]: Start complementDD. Operand 7 states and 1237 transitions. [2023-08-26 12:33:49,267 INFO L73 IsDeterministic]: Start isDeterministic. Operand 7 states and 1237 transitions. [2023-08-26 12:33:49,267 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2023-08-26 12:33:49,268 INFO L117 ReachableStatesCopy]: Start reachableStatesCopy. Operand 7 states and 1237 transitions. [2023-08-26 12:33:49,270 INFO L343 DoubleDeckerVisitor]: Before removal of dead ends has 8 states, 7 states have (on average 176.71428571428572) internal successors, (1237), 7 states have internal predecessors, (1237), 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-08-26 12:33:49,273 INFO L131 ReachableStatesCopy]: Finished reachableStatesCopy Result has 8 states, 8 states have (on average 379.0) internal successors, (3032), 8 states have internal predecessors, (3032), 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-08-26 12:33:49,274 INFO L81 ComplementDD]: Finished complementDD. Result has 8 states, 8 states have (on average 379.0) internal successors, (3032), 8 states have internal predecessors, (3032), 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-08-26 12:33:49,274 INFO L175 Difference]: Start difference. First operand has 80 places, 58 transitions, 181 flow. Second operand 7 states and 1237 transitions. [2023-08-26 12:33:49,274 INFO L82 GeneralOperation]: Start removeRedundantFlow. Operand has 85 places, 138 transitions, 585 flow [2023-08-26 12:33:49,299 INFO L88 GeneralOperation]: Finished removeRedundantFlow, result has has 76 places, 138 transitions, 566 flow, removed 0 selfloop flow, removed 9 redundant places. [2023-08-26 12:33:49,301 INFO L231 Difference]: Finished difference. Result has 76 places, 57 transitions, 162 flow [2023-08-26 12:33:49,301 INFO L264 CegarLoopForPetriNet]: {PETRI_ALPHABET=379, PETRI_DIFFERENCE_MINUEND_FLOW=152, PETRI_DIFFERENCE_MINUEND_PLACES=70, PETRI_DIFFERENCE_MINUEND_TRANSITIONS=57, PETRI_DIFFERENCE_SUBTRAHEND_LETTERS_WITH_MORE_CHANGERS_THAN_LOOPERS=5, PETRI_DIFFERENCE_SUBTRAHEND_LOOPER_ONLY_LETTERS=52, PETRI_DIFFERENCE_SUBTRAHEND_STATES=7, PETRI_FLOW=162, PETRI_PLACES=76, PETRI_TRANSITIONS=57} [2023-08-26 12:33:49,301 INFO L281 CegarLoopForPetriNet]: 79 programPoint places, -3 predicate places. [2023-08-26 12:33:49,301 INFO L495 AbstractCegarLoop]: Abstraction has has 76 places, 57 transitions, 162 flow [2023-08-26 12:33:49,303 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 16 states, 16 states have (on average 161.4375) internal successors, (2583), 16 states have internal predecessors, (2583), 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-08-26 12:33:49,303 INFO L200 CegarLoopForPetriNet]: Found error trace [2023-08-26 12:33:49,303 INFO L208 CegarLoopForPetriNet]: trace histogram [5, 4, 4, 1, 1, 1, 1, 1, 1] [2023-08-26 12:33:49,312 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-08-26 12:33:49,509 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable18,6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-08-26 12:33:49,509 INFO L420 AbstractCegarLoop]: === Iteration 6 === Targeting ULTIMATE.startErr0INUSE_VIOLATIONSUFFICIENT_THREAD_INSTANCES === [ULTIMATE.startErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr3REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 3 more)] === [2023-08-26 12:33:49,510 INFO L145 PredicateUnifier]: Initialized classic predicate unifier [2023-08-26 12:33:49,510 INFO L85 PathProgramCache]: Analyzing trace with hash -620348865, now seen corresponding path program 1 times [2023-08-26 12:33:49,510 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-08-26 12:33:49,510 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [296757448] [2023-08-26 12:33:49,510 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-08-26 12:33:49,510 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-08-26 12:33:49,526 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2023-08-26 12:33:49,526 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2023-08-26 12:33:49,535 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2023-08-26 12:33:49,544 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2023-08-26 12:33:49,544 INFO L360 BasicCegarLoop]: Counterexample is feasible [2023-08-26 12:33:49,544 INFO L805 garLoopResultBuilder]: Registering result UNSAFE for location ULTIMATE.startErr0INUSE_VIOLATIONSUFFICIENT_THREAD_INSTANCES (5 of 6 remaining) [2023-08-26 12:33:49,544 INFO L805 garLoopResultBuilder]: Registering result UNKNOWN for location ULTIMATE.startErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE (4 of 6 remaining) [2023-08-26 12:33:49,544 INFO L805 garLoopResultBuilder]: Registering result UNKNOWN for location ULTIMATE.startErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE (3 of 6 remaining) [2023-08-26 12:33:49,544 INFO L805 garLoopResultBuilder]: Registering result UNKNOWN for location ULTIMATE.startErr3REQUIRES_VIOLATIONMEMORY_DEREFERENCE (2 of 6 remaining) [2023-08-26 12:33:49,545 INFO L805 garLoopResultBuilder]: Registering result UNKNOWN for location ULTIMATE.startErr4REQUIRES_VIOLATIONMEMORY_DEREFERENCE (1 of 6 remaining) [2023-08-26 12:33:49,545 INFO L805 garLoopResultBuilder]: Registering result UNKNOWN for location ULTIMATE.startErr2ASSERT_VIOLATIONASSERT (0 of 6 remaining) [2023-08-26 12:33:49,545 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable19 [2023-08-26 12:33:49,545 INFO L445 BasicCegarLoop]: Path program histogram: [1, 1, 1, 1, 1, 1] [2023-08-26 12:33:49,545 WARN L233 ceAbstractionStarter]: 4 thread instances were not sufficient, I will increase this number and restart the analysis [2023-08-26 12:33:49,545 INFO L515 ceAbstractionStarter]: Constructing petrified ICFG for 5 thread instances. [2023-08-26 12:33:49,572 INFO L144 ThreadInstanceAdder]: Constructed 5 joinOtherThreadTransitions. [2023-08-26 12:33:49,574 INFO L73 FinitePrefix]: Start finitePrefix. Operand has 216 places, 249 transitions, 558 flow [2023-08-26 12:33:49,678 INFO L124 PetriNetUnfolderBase]: 164/1036 cut-off events. [2023-08-26 12:33:49,678 INFO L125 PetriNetUnfolderBase]: For 110/110 co-relation queries the response was YES. [2023-08-26 12:33:49,685 INFO L83 FinitePrefix]: Finished finitePrefix Result has 1147 conditions, 1036 events. 164/1036 cut-off events. For 110/110 co-relation queries the response was YES. Maximal size of possible extension queue 26. Compared 4957 event pairs, 23 based on Foata normal form. 0/806 useless extension candidates. Maximal degree in co-relation 703. Up to 80 conditions per place. [2023-08-26 12:33:49,685 INFO L82 GeneralOperation]: Start removeDead. Operand has 216 places, 249 transitions, 558 flow [2023-08-26 12:33:49,691 INFO L88 GeneralOperation]: Finished RemoveDead, result has has 216 places, 249 transitions, 558 flow [2023-08-26 12:33:49,691 INFO L124 etLargeBlockEncoding]: Petri net LBE is using variable-based independence relation. [2023-08-26 12:33:49,691 INFO L131 etLargeBlockEncoding]: Starting large block encoding on Petri net that has 216 places, 249 transitions, 558 flow [2023-08-26 12:33:49,691 INFO L113 LiptonReduction]: Starting Lipton reduction on Petri net that has 216 places, 249 transitions, 558 flow [2023-08-26 12:33:49,692 INFO L73 FinitePrefix]: Start finitePrefix. Operand has 216 places, 249 transitions, 558 flow [2023-08-26 12:33:49,798 INFO L124 PetriNetUnfolderBase]: 164/1036 cut-off events. [2023-08-26 12:33:49,799 INFO L125 PetriNetUnfolderBase]: For 110/110 co-relation queries the response was YES. [2023-08-26 12:33:49,809 INFO L83 FinitePrefix]: Finished finitePrefix Result has 1147 conditions, 1036 events. 164/1036 cut-off events. For 110/110 co-relation queries the response was YES. Maximal size of possible extension queue 26. Compared 4957 event pairs, 23 based on Foata normal form. 0/806 useless extension candidates. Maximal degree in co-relation 703. Up to 80 conditions per place. [2023-08-26 12:33:49,837 INFO L119 LiptonReduction]: Number of co-enabled transitions 34720 [2023-08-26 12:33:53,172 INFO L134 LiptonReduction]: Checked pairs total: 95830 [2023-08-26 12:33:53,172 INFO L136 LiptonReduction]: Total number of compositions: 176 [2023-08-26 12:33:53,174 INFO L356 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2023-08-26 12:33:53,174 INFO L357 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=false, mAutomataTypeConcurrency=PETRI_NET, mHoareTripleChecks=INCREMENTAL, mHoareAnnotationPositions=LoopsAndPotentialCycles, 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;@44a04137, mLbeIndependenceSettings=[IndependenceType=SYNTACTIC, AbstractionType=NONE, UseConditional=, UseSemiCommutativity=, Solver=, SolverTimeout=] [2023-08-26 12:33:53,174 INFO L358 AbstractCegarLoop]: Starting to check reachability of 6 error locations. [2023-08-26 12:33:53,175 INFO L185 PetriNetUnfolderBase]: Found word, exiting Unfolder. [2023-08-26 12:33:53,175 INFO L124 PetriNetUnfolderBase]: 0/2 cut-off events. [2023-08-26 12:33:53,175 INFO L125 PetriNetUnfolderBase]: For 0/0 co-relation queries the response was YES. [2023-08-26 12:33:53,175 INFO L200 CegarLoopForPetriNet]: Found error trace [2023-08-26 12:33:53,175 INFO L208 CegarLoopForPetriNet]: trace histogram [1, 1] [2023-08-26 12:33:53,176 INFO L420 AbstractCegarLoop]: === Iteration 1 === Targeting ULTIMATE.startErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE === [ULTIMATE.startErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr3REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 3 more)] === [2023-08-26 12:33:53,176 INFO L145 PredicateUnifier]: Initialized classic predicate unifier [2023-08-26 12:33:53,176 INFO L85 PathProgramCache]: Analyzing trace with hash 65937, now seen corresponding path program 1 times [2023-08-26 12:33:53,176 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-08-26 12:33:53,176 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [466651537] [2023-08-26 12:33:53,176 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-08-26 12:33:53,176 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-08-26 12:33:53,189 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-08-26 12:33:53,234 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-08-26 12:33:53,234 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-08-26 12:33:53,234 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [466651537] [2023-08-26 12:33:53,234 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [466651537] provided 1 perfect and 0 imperfect interpolant sequences [2023-08-26 12:33:53,234 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-08-26 12:33:53,234 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [1] imperfect sequences [] total 1 [2023-08-26 12:33:53,235 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [547617994] [2023-08-26 12:33:53,235 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-08-26 12:33:53,235 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2023-08-26 12:33:53,235 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-08-26 12:33:53,235 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2023-08-26 12:33:53,235 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2023-08-26 12:33:53,236 INFO L471 CegarLoopForPetriNet]: Number of universal loopers: 181 out of 425 [2023-08-26 12:33:53,243 INFO L103 encePairwiseOnDemand]: Start differencePairwiseOnDemand. First operand has 93 places, 122 transitions, 304 flow. Second operand has 3 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-08-26 12:33:53,243 INFO L112 encePairwiseOnDemand]: Universal subtrahend loopers provided by user. [2023-08-26 12:33:53,243 INFO L113 encePairwiseOnDemand]: Number of universal subtrahend loopers: 181 of 425 [2023-08-26 12:33:53,243 INFO L73 FinitePrefix]: Start finitePrefix. Operand will be constructed on-demand