/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 --traceabstraction.order.of.the.error.locations.to.be.checked PROGRAM_FIRST -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/weaver/chl-nzb-file-subst.wvr.c -------------------------------------------------------------------------------- This is Ultimate 0.2.3-dev-ac9dbd0-m [2023-08-26 19:33:39,676 INFO L188 SettingsManager]: Resetting all preferences to default values... [2023-08-26 19:33:39,735 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 19:33:39,739 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2023-08-26 19:33:39,739 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.Checked method. Library mode if empty. [2023-08-26 19:33:39,779 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2023-08-26 19:33:39,780 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2023-08-26 19:33:39,780 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2023-08-26 19:33:39,781 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2023-08-26 19:33:39,785 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2023-08-26 19:33:39,785 INFO L153 SettingsManager]: * Use SBE=true [2023-08-26 19:33:39,785 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2023-08-26 19:33:39,785 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2023-08-26 19:33:39,787 INFO L153 SettingsManager]: * sizeof long=4 [2023-08-26 19:33:39,787 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2023-08-26 19:33:39,787 INFO L153 SettingsManager]: * sizeof POINTER=4 [2023-08-26 19:33:39,787 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2023-08-26 19:33:39,788 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2023-08-26 19:33:39,788 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2023-08-26 19:33:39,788 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2023-08-26 19:33:39,788 INFO L153 SettingsManager]: * sizeof long double=12 [2023-08-26 19:33:39,789 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2023-08-26 19:33:39,789 INFO L153 SettingsManager]: * Use constant arrays=true [2023-08-26 19:33:39,789 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2023-08-26 19:33:39,790 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2023-08-26 19:33:39,790 INFO L153 SettingsManager]: * To the following directory=./dump/ [2023-08-26 19:33:39,790 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2023-08-26 19:33:39,791 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2023-08-26 19:33:39,791 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2023-08-26 19:33:39,791 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2023-08-26 19:33:39,792 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2023-08-26 19:33:39,792 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2023-08-26 19:33:39,792 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2023-08-26 19:33:39,793 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2023-08-26 19:33:39,793 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2023-08-26 19:33:39,793 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.traceabstraction: Order of the error locations to be checked -> PROGRAM_FIRST 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 19:33:40,149 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2023-08-26 19:33:40,171 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2023-08-26 19:33:40,173 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2023-08-26 19:33:40,174 INFO L270 PluginConnector]: Initializing CDTParser... [2023-08-26 19:33:40,174 INFO L274 PluginConnector]: CDTParser initialized [2023-08-26 19:33:40,175 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/svcomp/weaver/chl-nzb-file-subst.wvr.c [2023-08-26 19:33:41,342 INFO L533 CDTParser]: Created temporary CDT project at NULL [2023-08-26 19:33:41,547 INFO L384 CDTParser]: Found 1 translation units. [2023-08-26 19:33:41,548 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/trunk/examples/svcomp/weaver/chl-nzb-file-subst.wvr.c [2023-08-26 19:33:41,555 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/3e4e8db93/b5f72c0908fb4d098bb0060654a8addd/FLAGf15983bd4 [2023-08-26 19:33:41,571 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/3e4e8db93/b5f72c0908fb4d098bb0060654a8addd [2023-08-26 19:33:41,576 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2023-08-26 19:33:41,578 INFO L133 ToolchainWalker]: Walking toolchain with 5 elements. [2023-08-26 19:33:41,580 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2023-08-26 19:33:41,580 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2023-08-26 19:33:41,583 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2023-08-26 19:33:41,584 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 26.08 07:33:41" (1/1) ... [2023-08-26 19:33:41,584 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@5b478549 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 26.08 07:33:41, skipping insertion in model container [2023-08-26 19:33:41,585 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 26.08 07:33:41" (1/1) ... [2023-08-26 19:33:41,619 INFO L176 MainTranslator]: Built tables and reachable declarations [2023-08-26 19:33:41,770 INFO L209 PostProcessor]: Analyzing one entry point: main [2023-08-26 19:33:41,779 INFO L201 MainTranslator]: Completed pre-run [2023-08-26 19:33:41,822 INFO L209 PostProcessor]: Analyzing one entry point: main [2023-08-26 19:33:41,836 INFO L206 MainTranslator]: Completed translation [2023-08-26 19:33:41,837 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 26.08 07:33:41 WrapperNode [2023-08-26 19:33:41,837 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2023-08-26 19:33:41,838 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2023-08-26 19:33:41,838 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2023-08-26 19:33:41,838 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2023-08-26 19:33:41,843 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 26.08 07:33:41" (1/1) ... [2023-08-26 19:33:41,857 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 26.08 07:33:41" (1/1) ... [2023-08-26 19:33:41,894 INFO L138 Inliner]: procedures = 26, calls = 77, calls flagged for inlining = 29, calls inlined = 43, statements flattened = 606 [2023-08-26 19:33:41,894 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2023-08-26 19:33:41,895 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2023-08-26 19:33:41,895 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2023-08-26 19:33:41,895 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2023-08-26 19:33:41,902 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 26.08 07:33:41" (1/1) ... [2023-08-26 19:33:41,902 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 26.08 07:33:41" (1/1) ... [2023-08-26 19:33:41,907 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 26.08 07:33:41" (1/1) ... [2023-08-26 19:33:41,908 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 26.08 07:33:41" (1/1) ... [2023-08-26 19:33:41,922 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 26.08 07:33:41" (1/1) ... [2023-08-26 19:33:41,927 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 26.08 07:33:41" (1/1) ... [2023-08-26 19:33:41,930 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 26.08 07:33:41" (1/1) ... [2023-08-26 19:33:41,932 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 26.08 07:33:41" (1/1) ... [2023-08-26 19:33:41,937 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2023-08-26 19:33:41,938 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2023-08-26 19:33:41,938 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2023-08-26 19:33:41,938 INFO L274 PluginConnector]: RCFGBuilder initialized [2023-08-26 19:33:41,938 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 26.08 07:33:41" (1/1) ... [2023-08-26 19:33:41,954 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2023-08-26 19:33:41,966 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-08-26 19:33:41,977 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 19:33:41,984 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 19:33:42,006 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2023-08-26 19:33:42,007 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnStack [2023-08-26 19:33:42,007 INFO L130 BoogieDeclarations]: Found specification of procedure write~int [2023-08-26 19:33:42,007 INFO L130 BoogieDeclarations]: Found specification of procedure read~int [2023-08-26 19:33:42,007 INFO L130 BoogieDeclarations]: Found specification of procedure thread1 [2023-08-26 19:33:42,007 INFO L138 BoogieDeclarations]: Found implementation of procedure thread1 [2023-08-26 19:33:42,007 INFO L130 BoogieDeclarations]: Found specification of procedure thread2 [2023-08-26 19:33:42,008 INFO L138 BoogieDeclarations]: Found implementation of procedure thread2 [2023-08-26 19:33:42,008 INFO L130 BoogieDeclarations]: Found specification of procedure thread3 [2023-08-26 19:33:42,008 INFO L138 BoogieDeclarations]: Found implementation of procedure thread3 [2023-08-26 19:33:42,008 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2023-08-26 19:33:42,008 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnHeap [2023-08-26 19:33:42,008 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2023-08-26 19:33:42,008 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2023-08-26 19:33:42,009 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2023-08-26 19:33:42,010 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 19:33:42,117 INFO L236 CfgBuilder]: Building ICFG [2023-08-26 19:33:42,126 INFO L262 CfgBuilder]: Building CFG for each procedure with an implementation [2023-08-26 19:33:42,937 INFO L277 CfgBuilder]: Performing block encoding [2023-08-26 19:33:42,946 INFO L297 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2023-08-26 19:33:42,946 INFO L302 CfgBuilder]: Removed 6 assume(true) statements. [2023-08-26 19:33:42,949 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 26.08 07:33:42 BoogieIcfgContainer [2023-08-26 19:33:42,949 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2023-08-26 19:33:42,950 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2023-08-26 19:33:42,951 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2023-08-26 19:33:42,953 INFO L274 PluginConnector]: TraceAbstraction initialized [2023-08-26 19:33:42,953 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 26.08 07:33:41" (1/3) ... [2023-08-26 19:33:42,954 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@75764260 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 26.08 07:33:42, skipping insertion in model container [2023-08-26 19:33:42,954 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 26.08 07:33:41" (2/3) ... [2023-08-26 19:33:42,954 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@75764260 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 26.08 07:33:42, skipping insertion in model container [2023-08-26 19:33:42,954 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 26.08 07:33:42" (3/3) ... [2023-08-26 19:33:42,955 INFO L112 eAbstractionObserver]: Analyzing ICFG chl-nzb-file-subst.wvr.c [2023-08-26 19:33:42,969 INFO L203 ceAbstractionStarter]: Automizer settings: Hoare:false NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2023-08-26 19:33:42,969 INFO L162 ceAbstractionStarter]: Applying trace abstraction to program that has 67 error locations. [2023-08-26 19:33:42,969 INFO L515 ceAbstractionStarter]: Constructing petrified ICFG for 1 thread instances. [2023-08-26 19:33:43,156 INFO L144 ThreadInstanceAdder]: Constructed 3 joinOtherThreadTransitions. [2023-08-26 19:33:43,193 INFO L73 FinitePrefix]: Start finitePrefix. Operand has 724 places, 787 transitions, 1598 flow [2023-08-26 19:33:43,532 INFO L124 PetriNetUnfolderBase]: 73/784 cut-off events. [2023-08-26 19:33:43,532 INFO L125 PetriNetUnfolderBase]: For 3/3 co-relation queries the response was YES. [2023-08-26 19:33:43,554 INFO L83 FinitePrefix]: Finished finitePrefix Result has 797 conditions, 784 events. 73/784 cut-off events. For 3/3 co-relation queries the response was YES. Maximal size of possible extension queue 18. Compared 2894 event pairs, 0 based on Foata normal form. 0/644 useless extension candidates. Maximal degree in co-relation 579. Up to 2 conditions per place. [2023-08-26 19:33:43,556 INFO L82 GeneralOperation]: Start removeDead. Operand has 724 places, 787 transitions, 1598 flow [2023-08-26 19:33:43,575 INFO L88 GeneralOperation]: Finished RemoveDead, result has has 710 places, 773 transitions, 1564 flow [2023-08-26 19:33:43,578 INFO L124 etLargeBlockEncoding]: Petri net LBE is using variable-based independence relation. [2023-08-26 19:33:43,594 INFO L131 etLargeBlockEncoding]: Starting large block encoding on Petri net that has 710 places, 773 transitions, 1564 flow [2023-08-26 19:33:43,599 INFO L113 LiptonReduction]: Starting Lipton reduction on Petri net that has 710 places, 773 transitions, 1564 flow [2023-08-26 19:33:43,600 INFO L73 FinitePrefix]: Start finitePrefix. Operand has 710 places, 773 transitions, 1564 flow [2023-08-26 19:33:43,804 INFO L124 PetriNetUnfolderBase]: 73/773 cut-off events. [2023-08-26 19:33:43,804 INFO L125 PetriNetUnfolderBase]: For 3/3 co-relation queries the response was YES. [2023-08-26 19:33:43,819 INFO L83 FinitePrefix]: Finished finitePrefix Result has 786 conditions, 773 events. 73/773 cut-off events. For 3/3 co-relation queries the response was YES. Maximal size of possible extension queue 18. Compared 2896 event pairs, 0 based on Foata normal form. 0/634 useless extension candidates. Maximal degree in co-relation 579. Up to 2 conditions per place. [2023-08-26 19:33:43,870 INFO L119 LiptonReduction]: Number of co-enabled transitions 196080 [2023-08-26 19:34:19,009 INFO L134 LiptonReduction]: Checked pairs total: 223696 [2023-08-26 19:34:19,009 INFO L136 LiptonReduction]: Total number of compositions: 1062 [2023-08-26 19:34:19,020 INFO L356 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2023-08-26 19:34:19,025 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;@2d2c5fad, mLbeIndependenceSettings=[IndependenceType=SYNTACTIC, AbstractionType=NONE, UseConditional=, UseSemiCommutativity=, Solver=, SolverTimeout=] [2023-08-26 19:34:19,025 INFO L358 AbstractCegarLoop]: Starting to check reachability of 118 error locations. [2023-08-26 19:34:19,027 INFO L185 PetriNetUnfolderBase]: Found word, exiting Unfolder. [2023-08-26 19:34:19,027 INFO L124 PetriNetUnfolderBase]: 1/2 cut-off events. [2023-08-26 19:34:19,027 INFO L125 PetriNetUnfolderBase]: For 0/0 co-relation queries the response was YES. [2023-08-26 19:34:19,028 INFO L200 CegarLoopForPetriNet]: Found error trace [2023-08-26 19:34:19,028 INFO L208 CegarLoopForPetriNet]: trace histogram [1, 1] [2023-08-26 19:34:19,028 INFO L420 AbstractCegarLoop]: === Iteration 1 === Targeting ULTIMATE.startErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE === [thread1Err0REQUIRES_VIOLATIONMEMORY_DEREFERENCE, thread1Err1REQUIRES_VIOLATIONMEMORY_DEREFERENCE, thread1Err2REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 115 more)] === [2023-08-26 19:34:19,032 INFO L145 PredicateUnifier]: Initialized classic predicate unifier [2023-08-26 19:34:19,032 INFO L85 PathProgramCache]: Analyzing trace with hash 111277, now seen corresponding path program 1 times [2023-08-26 19:34:19,038 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-08-26 19:34:19,038 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [476827261] [2023-08-26 19:34:19,039 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-08-26 19:34:19,039 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-08-26 19:34:19,118 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-08-26 19:34:19,244 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 19:34:19,244 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-08-26 19:34:19,244 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [476827261] [2023-08-26 19:34:19,245 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [476827261] provided 1 perfect and 0 imperfect interpolant sequences [2023-08-26 19:34:19,245 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-08-26 19:34:19,246 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [1] imperfect sequences [] total 1 [2023-08-26 19:34:19,247 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [644855954] [2023-08-26 19:34:19,247 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-08-26 19:34:19,253 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2023-08-26 19:34:19,258 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-08-26 19:34:19,277 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2023-08-26 19:34:19,278 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2023-08-26 19:34:19,282 INFO L471 CegarLoopForPetriNet]: Number of universal loopers: 653 out of 1849 [2023-08-26 19:34:19,288 INFO L103 encePairwiseOnDemand]: Start differencePairwiseOnDemand. First operand has 112 places, 114 transitions, 246 flow. Second operand has 3 states, 3 states have (on average 653.6666666666666) internal successors, (1961), 3 states have internal predecessors, (1961), 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 19:34:19,288 INFO L112 encePairwiseOnDemand]: Universal subtrahend loopers provided by user. [2023-08-26 19:34:19,288 INFO L113 encePairwiseOnDemand]: Number of universal subtrahend loopers: 653 of 1849 [2023-08-26 19:34:19,289 INFO L73 FinitePrefix]: Start finitePrefix. Operand will be constructed on-demand [2023-08-26 19:34:27,123 INFO L124 PetriNetUnfolderBase]: 60044/80331 cut-off events. [2023-08-26 19:34:27,123 INFO L125 PetriNetUnfolderBase]: For 1046/1046 co-relation queries the response was YES. [2023-08-26 19:34:27,233 INFO L83 FinitePrefix]: Finished finitePrefix Result has 161889 conditions, 80331 events. 60044/80331 cut-off events. For 1046/1046 co-relation queries the response was YES. Maximal size of possible extension queue 3541. Compared 480075 event pairs, 49669 based on Foata normal form. 0/26045 useless extension candidates. Maximal degree in co-relation 156348. Up to 80331 conditions per place. [2023-08-26 19:34:27,553 INFO L140 encePairwiseOnDemand]: 1827/1849 looper letters, 92 selfloop transitions, 1 changer transitions 0/93 dead transitions. [2023-08-26 19:34:27,554 INFO L145 encePairwiseOnDemand]: Finished differencePairwiseOnDemand. Result has 93 places, 93 transitions, 390 flow [2023-08-26 19:34:27,557 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2023-08-26 19:34:27,559 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 3 states. [2023-08-26 19:34:27,575 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 3 states to 3 states and 2073 transitions. [2023-08-26 19:34:27,578 INFO L516 CegarLoopForPetriNet]: DFA transition density 0.37371552190373175 [2023-08-26 19:34:27,579 INFO L72 ComplementDD]: Start complementDD. Operand 3 states and 2073 transitions. [2023-08-26 19:34:27,579 INFO L73 IsDeterministic]: Start isDeterministic. Operand 3 states and 2073 transitions. [2023-08-26 19:34:27,583 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2023-08-26 19:34:27,585 INFO L117 ReachableStatesCopy]: Start reachableStatesCopy. Operand 3 states and 2073 transitions. [2023-08-26 19:34:27,592 INFO L343 DoubleDeckerVisitor]: Before removal of dead ends has 4 states, 3 states have (on average 691.0) internal successors, (2073), 3 states have internal predecessors, (2073), 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 19:34:27,606 INFO L131 ReachableStatesCopy]: Finished reachableStatesCopy Result has 4 states, 4 states have (on average 1849.0) internal successors, (7396), 4 states have internal predecessors, (7396), 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 19:34:27,609 INFO L81 ComplementDD]: Finished complementDD. Result has 4 states, 4 states have (on average 1849.0) internal successors, (7396), 4 states have internal predecessors, (7396), 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 19:34:27,611 INFO L175 Difference]: Start difference. First operand has 112 places, 114 transitions, 246 flow. Second operand 3 states and 2073 transitions. [2023-08-26 19:34:27,611 INFO L82 GeneralOperation]: Start removeRedundantFlow. Operand has 93 places, 93 transitions, 390 flow [2023-08-26 19:34:27,675 INFO L88 GeneralOperation]: Finished removeRedundantFlow, result has has 87 places, 93 transitions, 378 flow, removed 0 selfloop flow, removed 6 redundant places. [2023-08-26 19:34:27,677 INFO L231 Difference]: Finished difference. Result has 87 places, 93 transitions, 194 flow [2023-08-26 19:34:27,679 INFO L264 CegarLoopForPetriNet]: {PETRI_ALPHABET=1849, PETRI_DIFFERENCE_MINUEND_FLOW=192, PETRI_DIFFERENCE_MINUEND_PLACES=85, PETRI_DIFFERENCE_MINUEND_TRANSITIONS=93, PETRI_DIFFERENCE_SUBTRAHEND_LETTERS_WITH_MORE_CHANGERS_THAN_LOOPERS=1, PETRI_DIFFERENCE_SUBTRAHEND_LOOPER_ONLY_LETTERS=92, PETRI_DIFFERENCE_SUBTRAHEND_STATES=3, PETRI_FLOW=194, PETRI_PLACES=87, PETRI_TRANSITIONS=93} [2023-08-26 19:34:27,685 INFO L281 CegarLoopForPetriNet]: 112 programPoint places, -25 predicate places. [2023-08-26 19:34:27,685 INFO L495 AbstractCegarLoop]: Abstraction has has 87 places, 93 transitions, 194 flow [2023-08-26 19:34:27,687 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 653.6666666666666) internal successors, (1961), 3 states have internal predecessors, (1961), 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 19:34:27,687 INFO L200 CegarLoopForPetriNet]: Found error trace [2023-08-26 19:34:27,687 INFO L208 CegarLoopForPetriNet]: trace histogram [1, 1] [2023-08-26 19:34:27,687 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2023-08-26 19:34:27,688 INFO L420 AbstractCegarLoop]: === Iteration 2 === Targeting ULTIMATE.startErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE === [thread1Err0REQUIRES_VIOLATIONMEMORY_DEREFERENCE, thread1Err1REQUIRES_VIOLATIONMEMORY_DEREFERENCE, thread1Err2REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 115 more)] === [2023-08-26 19:34:27,694 INFO L145 PredicateUnifier]: Initialized classic predicate unifier [2023-08-26 19:34:27,695 INFO L85 PathProgramCache]: Analyzing trace with hash 111278, now seen corresponding path program 1 times [2023-08-26 19:34:27,695 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-08-26 19:34:27,695 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2110846059] [2023-08-26 19:34:27,695 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-08-26 19:34:27,695 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-08-26 19:34:27,736 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-08-26 19:34:27,919 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 19:34:27,919 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-08-26 19:34:27,920 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2110846059] [2023-08-26 19:34:27,920 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2110846059] provided 1 perfect and 0 imperfect interpolant sequences [2023-08-26 19:34:27,920 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-08-26 19:34:27,920 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [1] imperfect sequences [] total 1 [2023-08-26 19:34:27,921 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [335229525] [2023-08-26 19:34:27,921 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-08-26 19:34:27,921 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2023-08-26 19:34:27,922 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-08-26 19:34:27,923 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2023-08-26 19:34:27,923 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2023-08-26 19:34:27,925 INFO L471 CegarLoopForPetriNet]: Number of universal loopers: 633 out of 1849 [2023-08-26 19:34:27,927 INFO L103 encePairwiseOnDemand]: Start differencePairwiseOnDemand. First operand has 87 places, 93 transitions, 194 flow. Second operand has 3 states, 3 states have (on average 633.6666666666666) internal successors, (1901), 3 states have internal predecessors, (1901), 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 19:34:27,928 INFO L112 encePairwiseOnDemand]: Universal subtrahend loopers provided by user. [2023-08-26 19:34:27,928 INFO L113 encePairwiseOnDemand]: Number of universal subtrahend loopers: 633 of 1849 [2023-08-26 19:34:27,928 INFO L73 FinitePrefix]: Start finitePrefix. Operand will be constructed on-demand [2023-08-26 19:34:35,019 INFO L124 PetriNetUnfolderBase]: 60049/80339 cut-off events. [2023-08-26 19:34:35,020 INFO L125 PetriNetUnfolderBase]: For 171/171 co-relation queries the response was YES. [2023-08-26 19:34:35,083 INFO L83 FinitePrefix]: Finished finitePrefix Result has 161189 conditions, 80339 events. 60049/80339 cut-off events. For 171/171 co-relation queries the response was YES. Maximal size of possible extension queue 3541. Compared 480006 event pairs, 49669 based on Foata normal form. 0/26048 useless extension candidates. Maximal degree in co-relation 161183. Up to 80335 conditions per place. [2023-08-26 19:34:35,601 INFO L140 encePairwiseOnDemand]: 1837/1849 looper letters, 92 selfloop transitions, 9 changer transitions 0/101 dead transitions. [2023-08-26 19:34:35,601 INFO L145 encePairwiseOnDemand]: Finished differencePairwiseOnDemand. Result has 89 places, 101 transitions, 412 flow [2023-08-26 19:34:35,605 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2023-08-26 19:34:35,605 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 3 states. [2023-08-26 19:34:35,609 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 3 states to 3 states and 2003 transitions. [2023-08-26 19:34:35,610 INFO L516 CegarLoopForPetriNet]: DFA transition density 0.36109608797548226 [2023-08-26 19:34:35,610 INFO L72 ComplementDD]: Start complementDD. Operand 3 states and 2003 transitions. [2023-08-26 19:34:35,611 INFO L73 IsDeterministic]: Start isDeterministic. Operand 3 states and 2003 transitions. [2023-08-26 19:34:35,611 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2023-08-26 19:34:35,612 INFO L117 ReachableStatesCopy]: Start reachableStatesCopy. Operand 3 states and 2003 transitions. [2023-08-26 19:34:35,616 INFO L343 DoubleDeckerVisitor]: Before removal of dead ends has 4 states, 3 states have (on average 667.6666666666666) internal successors, (2003), 3 states have internal predecessors, (2003), 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 19:34:35,624 INFO L131 ReachableStatesCopy]: Finished reachableStatesCopy Result has 4 states, 4 states have (on average 1849.0) internal successors, (7396), 4 states have internal predecessors, (7396), 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 19:34:35,627 INFO L81 ComplementDD]: Finished complementDD. Result has 4 states, 4 states have (on average 1849.0) internal successors, (7396), 4 states have internal predecessors, (7396), 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 19:34:35,628 INFO L175 Difference]: Start difference. First operand has 87 places, 93 transitions, 194 flow. Second operand 3 states and 2003 transitions. [2023-08-26 19:34:35,628 INFO L82 GeneralOperation]: Start removeRedundantFlow. Operand has 89 places, 101 transitions, 412 flow [2023-08-26 19:34:35,629 INFO L88 GeneralOperation]: Finished removeRedundantFlow, result has has 88 places, 101 transitions, 411 flow, removed 0 selfloop flow, removed 1 redundant places. [2023-08-26 19:34:35,631 INFO L231 Difference]: Finished difference. Result has 90 places, 101 transitions, 267 flow [2023-08-26 19:34:35,632 INFO L264 CegarLoopForPetriNet]: {PETRI_ALPHABET=1849, PETRI_DIFFERENCE_MINUEND_FLOW=193, PETRI_DIFFERENCE_MINUEND_PLACES=86, PETRI_DIFFERENCE_MINUEND_TRANSITIONS=93, PETRI_DIFFERENCE_SUBTRAHEND_LETTERS_WITH_MORE_CHANGERS_THAN_LOOPERS=1, PETRI_DIFFERENCE_SUBTRAHEND_LOOPER_ONLY_LETTERS=84, PETRI_DIFFERENCE_SUBTRAHEND_STATES=3, PETRI_FLOW=267, PETRI_PLACES=90, PETRI_TRANSITIONS=101} [2023-08-26 19:34:35,633 INFO L281 CegarLoopForPetriNet]: 112 programPoint places, -22 predicate places. [2023-08-26 19:34:35,633 INFO L495 AbstractCegarLoop]: Abstraction has has 90 places, 101 transitions, 267 flow [2023-08-26 19:34:35,636 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 633.6666666666666) internal successors, (1901), 3 states have internal predecessors, (1901), 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 19:34:35,636 INFO L200 CegarLoopForPetriNet]: Found error trace [2023-08-26 19:34:35,636 INFO L208 CegarLoopForPetriNet]: trace histogram [1, 1, 1] [2023-08-26 19:34:35,636 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2023-08-26 19:34:35,636 INFO L420 AbstractCegarLoop]: === Iteration 3 === Targeting ULTIMATE.startErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE === [thread1Err0REQUIRES_VIOLATIONMEMORY_DEREFERENCE, thread1Err1REQUIRES_VIOLATIONMEMORY_DEREFERENCE, thread1Err2REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 115 more)] === [2023-08-26 19:34:35,639 INFO L145 PredicateUnifier]: Initialized classic predicate unifier [2023-08-26 19:34:35,639 INFO L85 PathProgramCache]: Analyzing trace with hash 3459154, now seen corresponding path program 1 times [2023-08-26 19:34:35,640 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-08-26 19:34:35,645 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1684203480] [2023-08-26 19:34:35,645 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-08-26 19:34:35,645 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-08-26 19:34:35,672 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-08-26 19:34:35,835 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 19:34:35,835 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-08-26 19:34:35,836 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1684203480] [2023-08-26 19:34:35,836 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1684203480] provided 0 perfect and 1 imperfect interpolant sequences [2023-08-26 19:34:35,836 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [692194505] [2023-08-26 19:34:35,837 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-08-26 19:34:35,838 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-08-26 19:34:35,838 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-08-26 19:34:35,845 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 19:34:35,846 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 19:34:35,957 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-08-26 19:34:35,959 INFO L262 TraceCheckSpWp]: Trace formula consists of 131 conjuncts, 13 conjunts are in the unsatisfiable core [2023-08-26 19:34:35,975 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-08-26 19:34:36,113 INFO L322 Elim1Store]: treesize reduction 72, result has 33.9 percent of original size [2023-08-26 19:34:36,118 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 3 case distinctions, treesize of input 15 treesize of output 42 [2023-08-26 19:34:36,169 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 19:34:36,169 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-08-26 19:34:36,200 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 19:34:36,200 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [692194505] provided 0 perfect and 2 imperfect interpolant sequences [2023-08-26 19:34:36,200 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2023-08-26 19:34:36,200 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [2, 2, 2] total 6 [2023-08-26 19:34:36,201 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [177945603] [2023-08-26 19:34:36,201 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2023-08-26 19:34:36,201 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2023-08-26 19:34:36,201 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-08-26 19:34:36,202 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2023-08-26 19:34:36,202 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=23, Invalid=33, Unknown=0, NotChecked=0, Total=56 [2023-08-26 19:34:36,205 INFO L471 CegarLoopForPetriNet]: Number of universal loopers: 633 out of 1849 [2023-08-26 19:34:36,210 INFO L103 encePairwiseOnDemand]: Start differencePairwiseOnDemand. First operand has 90 places, 101 transitions, 267 flow. Second operand has 8 states, 8 states have (on average 634.125) internal successors, (5073), 8 states have internal predecessors, (5073), 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 19:34:36,210 INFO L112 encePairwiseOnDemand]: Universal subtrahend loopers provided by user. [2023-08-26 19:34:36,210 INFO L113 encePairwiseOnDemand]: Number of universal subtrahend loopers: 633 of 1849 [2023-08-26 19:34:36,211 INFO L73 FinitePrefix]: Start finitePrefix. Operand will be constructed on-demand [2023-08-26 19:34:43,753 INFO L124 PetriNetUnfolderBase]: 60054/80353 cut-off events. [2023-08-26 19:34:43,753 INFO L125 PetriNetUnfolderBase]: For 171/171 co-relation queries the response was YES. [2023-08-26 19:34:43,849 INFO L83 FinitePrefix]: Finished finitePrefix Result has 161262 conditions, 80353 events. 60054/80353 cut-off events. For 171/171 co-relation queries the response was YES. Maximal size of possible extension queue 3534. Compared 480227 event pairs, 49669 based on Foata normal form. 4/26067 useless extension candidates. Maximal degree in co-relation 161253. Up to 80338 conditions per place. [2023-08-26 19:34:44,084 INFO L140 encePairwiseOnDemand]: 1837/1849 looper letters, 90 selfloop transitions, 25 changer transitions 0/115 dead transitions. [2023-08-26 19:34:44,084 INFO L145 encePairwiseOnDemand]: Finished differencePairwiseOnDemand. Result has 95 places, 115 transitions, 555 flow [2023-08-26 19:34:44,084 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2023-08-26 19:34:44,085 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 6 states. [2023-08-26 19:34:44,093 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 3932 transitions. [2023-08-26 19:34:44,095 INFO L516 CegarLoopForPetriNet]: DFA transition density 0.35442581575626464 [2023-08-26 19:34:44,095 INFO L72 ComplementDD]: Start complementDD. Operand 6 states and 3932 transitions. [2023-08-26 19:34:44,095 INFO L73 IsDeterministic]: Start isDeterministic. Operand 6 states and 3932 transitions. [2023-08-26 19:34:44,097 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2023-08-26 19:34:44,097 INFO L117 ReachableStatesCopy]: Start reachableStatesCopy. Operand 6 states and 3932 transitions. [2023-08-26 19:34:44,104 INFO L343 DoubleDeckerVisitor]: Before removal of dead ends has 7 states, 6 states have (on average 655.3333333333334) internal successors, (3932), 6 states have internal predecessors, (3932), 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 19:34:44,119 INFO L131 ReachableStatesCopy]: Finished reachableStatesCopy Result has 7 states, 7 states have (on average 1849.0) internal successors, (12943), 7 states have internal predecessors, (12943), 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 19:34:44,122 INFO L81 ComplementDD]: Finished complementDD. Result has 7 states, 7 states have (on average 1849.0) internal successors, (12943), 7 states have internal predecessors, (12943), 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 19:34:44,122 INFO L175 Difference]: Start difference. First operand has 90 places, 101 transitions, 267 flow. Second operand 6 states and 3932 transitions. [2023-08-26 19:34:44,122 INFO L82 GeneralOperation]: Start removeRedundantFlow. Operand has 95 places, 115 transitions, 555 flow [2023-08-26 19:34:44,124 INFO L88 GeneralOperation]: Finished removeRedundantFlow, result has has 93 places, 115 transitions, 535 flow, removed 0 selfloop flow, removed 2 redundant places. [2023-08-26 19:34:44,127 INFO L231 Difference]: Finished difference. Result has 96 places, 115 transitions, 413 flow [2023-08-26 19:34:44,128 INFO L264 CegarLoopForPetriNet]: {PETRI_ALPHABET=1849, PETRI_DIFFERENCE_MINUEND_FLOW=229, PETRI_DIFFERENCE_MINUEND_PLACES=88, PETRI_DIFFERENCE_MINUEND_TRANSITIONS=96, PETRI_DIFFERENCE_SUBTRAHEND_LETTERS_WITH_MORE_CHANGERS_THAN_LOOPERS=12, PETRI_DIFFERENCE_SUBTRAHEND_LOOPER_ONLY_LETTERS=84, PETRI_DIFFERENCE_SUBTRAHEND_STATES=6, PETRI_FLOW=413, PETRI_PLACES=96, PETRI_TRANSITIONS=115} [2023-08-26 19:34:44,129 INFO L281 CegarLoopForPetriNet]: 112 programPoint places, -16 predicate places. [2023-08-26 19:34:44,129 INFO L495 AbstractCegarLoop]: Abstraction has has 96 places, 115 transitions, 413 flow [2023-08-26 19:34:44,131 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 8 states have (on average 634.125) internal successors, (5073), 8 states have internal predecessors, (5073), 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 19:34:44,131 INFO L200 CegarLoopForPetriNet]: Found error trace [2023-08-26 19:34:44,131 INFO L208 CegarLoopForPetriNet]: trace histogram [4, 1, 1] [2023-08-26 19:34:44,139 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 19:34:44,336 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2,2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-08-26 19:34:44,336 INFO L420 AbstractCegarLoop]: === Iteration 4 === Targeting ULTIMATE.startErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE === [thread1Err0REQUIRES_VIOLATIONMEMORY_DEREFERENCE, thread1Err1REQUIRES_VIOLATIONMEMORY_DEREFERENCE, thread1Err2REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 115 more)] === [2023-08-26 19:34:44,337 INFO L145 PredicateUnifier]: Initialized classic predicate unifier [2023-08-26 19:34:44,337 INFO L85 PathProgramCache]: Analyzing trace with hash -18089042, now seen corresponding path program 2 times [2023-08-26 19:34:44,337 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-08-26 19:34:44,337 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1622956915] [2023-08-26 19:34:44,337 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-08-26 19:34:44,337 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-08-26 19:34:44,359 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-08-26 19:34:44,646 INFO L134 CoverageAnalysis]: Checked inductivity of 10 backedges. 0 proven. 10 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-08-26 19:34:44,646 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-08-26 19:34:44,647 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1622956915] [2023-08-26 19:34:44,647 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1622956915] provided 0 perfect and 1 imperfect interpolant sequences [2023-08-26 19:34:44,647 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [83463227] [2023-08-26 19:34:44,647 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2023-08-26 19:34:44,647 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-08-26 19:34:44,647 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-08-26 19:34:44,648 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 19:34:44,651 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 19:34:44,777 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2023-08-26 19:34:44,777 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-08-26 19:34:44,778 INFO L262 TraceCheckSpWp]: Trace formula consists of 164 conjuncts, 13 conjunts are in the unsatisfiable core [2023-08-26 19:34:44,780 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-08-26 19:34:44,838 INFO L322 Elim1Store]: treesize reduction 72, result has 33.9 percent of original size [2023-08-26 19:34:44,838 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 3 case distinctions, treesize of input 15 treesize of output 42 [2023-08-26 19:34:44,981 INFO L134 CoverageAnalysis]: Checked inductivity of 10 backedges. 10 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-08-26 19:34:44,981 INFO L323 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2023-08-26 19:34:44,982 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [83463227] provided 1 perfect and 0 imperfect interpolant sequences [2023-08-26 19:34:44,982 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2023-08-26 19:34:44,982 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [5] total 10 [2023-08-26 19:34:44,982 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1522205267] [2023-08-26 19:34:44,982 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-08-26 19:34:44,982 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2023-08-26 19:34:44,982 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-08-26 19:34:44,983 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2023-08-26 19:34:44,983 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=31, Invalid=101, Unknown=0, NotChecked=0, Total=132 [2023-08-26 19:34:44,986 INFO L471 CegarLoopForPetriNet]: Number of universal loopers: 633 out of 1849 [2023-08-26 19:34:44,990 INFO L103 encePairwiseOnDemand]: Start differencePairwiseOnDemand. First operand has 96 places, 115 transitions, 413 flow. Second operand has 7 states, 7 states have (on average 633.8571428571429) internal successors, (4437), 7 states have internal predecessors, (4437), 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 19:34:44,990 INFO L112 encePairwiseOnDemand]: Universal subtrahend loopers provided by user. [2023-08-26 19:34:44,990 INFO L113 encePairwiseOnDemand]: Number of universal subtrahend loopers: 633 of 1849 [2023-08-26 19:34:44,991 INFO L73 FinitePrefix]: Start finitePrefix. Operand will be constructed on-demand [2023-08-26 19:34:52,448 INFO L124 PetriNetUnfolderBase]: 60054/80350 cut-off events. [2023-08-26 19:34:52,448 INFO L125 PetriNetUnfolderBase]: For 174/174 co-relation queries the response was YES. [2023-08-26 19:34:52,589 INFO L83 FinitePrefix]: Finished finitePrefix Result has 161296 conditions, 80350 events. 60054/80350 cut-off events. For 174/174 co-relation queries the response was YES. Maximal size of possible extension queue 3503. Compared 479411 event pairs, 49669 based on Foata normal form. 3/26063 useless extension candidates. Maximal degree in co-relation 161284. Up to 80329 conditions per place. [2023-08-26 19:34:52,826 INFO L140 encePairwiseOnDemand]: 1837/1849 looper letters, 84 selfloop transitions, 28 changer transitions 0/112 dead transitions. [2023-08-26 19:34:52,826 INFO L145 encePairwiseOnDemand]: Finished differencePairwiseOnDemand. Result has 99 places, 112 transitions, 607 flow [2023-08-26 19:34:52,826 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2023-08-26 19:34:52,827 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 7 states. [2023-08-26 19:34:52,836 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 7 states to 7 states and 4546 transitions. [2023-08-26 19:34:52,838 INFO L516 CegarLoopForPetriNet]: DFA transition density 0.35123232635401375 [2023-08-26 19:34:52,838 INFO L72 ComplementDD]: Start complementDD. Operand 7 states and 4546 transitions. [2023-08-26 19:34:52,838 INFO L73 IsDeterministic]: Start isDeterministic. Operand 7 states and 4546 transitions. [2023-08-26 19:34:52,840 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2023-08-26 19:34:52,840 INFO L117 ReachableStatesCopy]: Start reachableStatesCopy. Operand 7 states and 4546 transitions. [2023-08-26 19:34:52,849 INFO L343 DoubleDeckerVisitor]: Before removal of dead ends has 8 states, 7 states have (on average 649.4285714285714) internal successors, (4546), 7 states have internal predecessors, (4546), 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 19:34:52,867 INFO L131 ReachableStatesCopy]: Finished reachableStatesCopy Result has 8 states, 8 states have (on average 1849.0) internal successors, (14792), 8 states have internal predecessors, (14792), 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 19:34:52,870 INFO L81 ComplementDD]: Finished complementDD. Result has 8 states, 8 states have (on average 1849.0) internal successors, (14792), 8 states have internal predecessors, (14792), 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 19:34:52,870 INFO L175 Difference]: Start difference. First operand has 96 places, 115 transitions, 413 flow. Second operand 7 states and 4546 transitions. [2023-08-26 19:34:52,870 INFO L82 GeneralOperation]: Start removeRedundantFlow. Operand has 99 places, 112 transitions, 607 flow [2023-08-26 19:34:52,872 INFO L88 GeneralOperation]: Finished removeRedundantFlow, result has has 94 places, 112 transitions, 517 flow, removed 21 selfloop flow, removed 5 redundant places. [2023-08-26 19:34:52,874 INFO L231 Difference]: Finished difference. Result has 94 places, 112 transitions, 349 flow [2023-08-26 19:34:52,874 INFO L264 CegarLoopForPetriNet]: {PETRI_ALPHABET=1849, PETRI_DIFFERENCE_MINUEND_FLOW=293, PETRI_DIFFERENCE_MINUEND_PLACES=88, PETRI_DIFFERENCE_MINUEND_TRANSITIONS=112, PETRI_DIFFERENCE_SUBTRAHEND_LETTERS_WITH_MORE_CHANGERS_THAN_LOOPERS=28, PETRI_DIFFERENCE_SUBTRAHEND_LOOPER_ONLY_LETTERS=84, PETRI_DIFFERENCE_SUBTRAHEND_STATES=7, PETRI_FLOW=349, PETRI_PLACES=94, PETRI_TRANSITIONS=112} [2023-08-26 19:34:52,874 INFO L281 CegarLoopForPetriNet]: 112 programPoint places, -18 predicate places. [2023-08-26 19:34:52,875 INFO L495 AbstractCegarLoop]: Abstraction has has 94 places, 112 transitions, 349 flow [2023-08-26 19:34:52,876 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 7 states have (on average 633.8571428571429) internal successors, (4437), 7 states have internal predecessors, (4437), 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 19:34:52,877 INFO L200 CegarLoopForPetriNet]: Found error trace [2023-08-26 19:34:52,877 INFO L208 CegarLoopForPetriNet]: trace histogram [2, 2, 2, 1, 1, 1, 1] [2023-08-26 19:34:52,885 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 19:34:53,077 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,SelfDestructingSolverStorable3 [2023-08-26 19:34:53,077 INFO L420 AbstractCegarLoop]: === Iteration 5 === Targeting ULTIMATE.startErr7REQUIRES_VIOLATIONMEMORY_DEREFERENCE === [thread1Err0REQUIRES_VIOLATIONMEMORY_DEREFERENCE, thread1Err1REQUIRES_VIOLATIONMEMORY_DEREFERENCE, thread1Err2REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 115 more)] === [2023-08-26 19:34:53,078 INFO L145 PredicateUnifier]: Initialized classic predicate unifier [2023-08-26 19:34:53,078 INFO L85 PathProgramCache]: Analyzing trace with hash -329522673, now seen corresponding path program 1 times [2023-08-26 19:34:53,078 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-08-26 19:34:53,078 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1829115007] [2023-08-26 19:34:53,079 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-08-26 19:34:53,079 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-08-26 19:34:53,106 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-08-26 19:34:53,201 INFO L134 CoverageAnalysis]: Checked inductivity of 9 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2023-08-26 19:34:53,201 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-08-26 19:34:53,201 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1829115007] [2023-08-26 19:34:53,201 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1829115007] provided 0 perfect and 1 imperfect interpolant sequences [2023-08-26 19:34:53,203 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [655934501] [2023-08-26 19:34:53,204 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-08-26 19:34:53,204 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-08-26 19:34:53,204 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-08-26 19:34:53,205 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 19:34:53,210 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 19:34:53,357 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-08-26 19:34:53,359 INFO L262 TraceCheckSpWp]: Trace formula consists of 252 conjuncts, 6 conjunts are in the unsatisfiable core [2023-08-26 19:34:53,360 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-08-26 19:34:53,405 INFO L134 CoverageAnalysis]: Checked inductivity of 9 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2023-08-26 19:34:53,405 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-08-26 19:34:53,436 INFO L134 CoverageAnalysis]: Checked inductivity of 9 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2023-08-26 19:34:53,436 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [655934501] provided 0 perfect and 2 imperfect interpolant sequences [2023-08-26 19:34:53,437 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2023-08-26 19:34:53,437 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 4, 4] total 11 [2023-08-26 19:34:53,437 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [393930109] [2023-08-26 19:34:53,437 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2023-08-26 19:34:53,438 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 11 states [2023-08-26 19:34:53,438 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-08-26 19:34:53,439 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2023-08-26 19:34:53,439 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=52, Invalid=58, Unknown=0, NotChecked=0, Total=110 [2023-08-26 19:34:53,446 INFO L471 CegarLoopForPetriNet]: Number of universal loopers: 707 out of 1849 [2023-08-26 19:34:53,450 INFO L103 encePairwiseOnDemand]: Start differencePairwiseOnDemand. First operand has 94 places, 112 transitions, 349 flow. Second operand has 11 states, 11 states have (on average 708.6363636363636) internal successors, (7795), 11 states have internal predecessors, (7795), 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 19:34:53,451 INFO L112 encePairwiseOnDemand]: Universal subtrahend loopers provided by user. [2023-08-26 19:34:53,451 INFO L113 encePairwiseOnDemand]: Number of universal subtrahend loopers: 707 of 1849 [2023-08-26 19:34:53,451 INFO L73 FinitePrefix]: Start finitePrefix. Operand will be constructed on-demand [2023-08-26 19:35:00,674 INFO L124 PetriNetUnfolderBase]: 60044/80343 cut-off events. [2023-08-26 19:35:00,674 INFO L125 PetriNetUnfolderBase]: For 171/171 co-relation queries the response was YES. [2023-08-26 19:35:00,757 INFO L83 FinitePrefix]: Finished finitePrefix Result has 161240 conditions, 80343 events. 60044/80343 cut-off events. For 171/171 co-relation queries the response was YES. Maximal size of possible extension queue 3502. Compared 478714 event pairs, 49669 based on Foata normal form. 3/26066 useless extension candidates. Maximal degree in co-relation 161231. Up to 80329 conditions per place. [2023-08-26 19:35:00,954 INFO L140 encePairwiseOnDemand]: 1840/1849 looper letters, 87 selfloop transitions, 18 changer transitions 0/105 dead transitions. [2023-08-26 19:35:00,954 INFO L145 encePairwiseOnDemand]: Finished differencePairwiseOnDemand. Result has 100 places, 105 transitions, 511 flow [2023-08-26 19:35:00,954 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2023-08-26 19:35:00,954 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 7 states. [2023-08-26 19:35:00,962 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 7 states to 7 states and 5069 transitions. [2023-08-26 19:35:00,964 INFO L516 CegarLoopForPetriNet]: DFA transition density 0.3916402688712045 [2023-08-26 19:35:00,965 INFO L72 ComplementDD]: Start complementDD. Operand 7 states and 5069 transitions. [2023-08-26 19:35:00,965 INFO L73 IsDeterministic]: Start isDeterministic. Operand 7 states and 5069 transitions. [2023-08-26 19:35:00,967 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2023-08-26 19:35:00,967 INFO L117 ReachableStatesCopy]: Start reachableStatesCopy. Operand 7 states and 5069 transitions. [2023-08-26 19:35:00,976 INFO L343 DoubleDeckerVisitor]: Before removal of dead ends has 8 states, 7 states have (on average 724.1428571428571) internal successors, (5069), 7 states have internal predecessors, (5069), 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 19:35:00,989 INFO L131 ReachableStatesCopy]: Finished reachableStatesCopy Result has 8 states, 8 states have (on average 1849.0) internal successors, (14792), 8 states have internal predecessors, (14792), 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 19:35:00,991 INFO L81 ComplementDD]: Finished complementDD. Result has 8 states, 8 states have (on average 1849.0) internal successors, (14792), 8 states have internal predecessors, (14792), 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 19:35:00,991 INFO L175 Difference]: Start difference. First operand has 94 places, 112 transitions, 349 flow. Second operand 7 states and 5069 transitions. [2023-08-26 19:35:00,991 INFO L82 GeneralOperation]: Start removeRedundantFlow. Operand has 100 places, 105 transitions, 511 flow [2023-08-26 19:35:00,993 INFO L88 GeneralOperation]: Finished removeRedundantFlow, result has has 95 places, 105 transitions, 483 flow, removed 0 selfloop flow, removed 5 redundant places. [2023-08-26 19:35:00,994 INFO L231 Difference]: Finished difference. Result has 96 places, 105 transitions, 327 flow [2023-08-26 19:35:00,994 INFO L264 CegarLoopForPetriNet]: {PETRI_ALPHABET=1849, PETRI_DIFFERENCE_MINUEND_FLOW=261, PETRI_DIFFERENCE_MINUEND_PLACES=89, PETRI_DIFFERENCE_MINUEND_TRANSITIONS=102, PETRI_DIFFERENCE_SUBTRAHEND_LETTERS_WITH_MORE_CHANGERS_THAN_LOOPERS=15, PETRI_DIFFERENCE_SUBTRAHEND_LOOPER_ONLY_LETTERS=84, PETRI_DIFFERENCE_SUBTRAHEND_STATES=7, PETRI_FLOW=327, PETRI_PLACES=96, PETRI_TRANSITIONS=105} [2023-08-26 19:35:00,995 INFO L281 CegarLoopForPetriNet]: 112 programPoint places, -16 predicate places. [2023-08-26 19:35:00,995 INFO L495 AbstractCegarLoop]: Abstraction has has 96 places, 105 transitions, 327 flow [2023-08-26 19:35:00,997 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 11 states, 11 states have (on average 708.6363636363636) internal successors, (7795), 11 states have internal predecessors, (7795), 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 19:35:00,997 INFO L200 CegarLoopForPetriNet]: Found error trace [2023-08-26 19:35:00,997 INFO L208 CegarLoopForPetriNet]: trace histogram [5, 5, 5, 1, 1, 1, 1] [2023-08-26 19:35:01,005 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Forceful destruction successful, exit code 0 [2023-08-26 19:35:01,201 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-08-26 19:35:01,202 INFO L420 AbstractCegarLoop]: === Iteration 6 === Targeting ULTIMATE.startErr6REQUIRES_VIOLATIONMEMORY_DEREFERENCE === [thread1Err0REQUIRES_VIOLATIONMEMORY_DEREFERENCE, thread1Err1REQUIRES_VIOLATIONMEMORY_DEREFERENCE, thread1Err2REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 115 more)] === [2023-08-26 19:35:01,202 INFO L145 PredicateUnifier]: Initialized classic predicate unifier [2023-08-26 19:35:01,202 INFO L85 PathProgramCache]: Analyzing trace with hash -2032926300, now seen corresponding path program 1 times [2023-08-26 19:35:01,202 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-08-26 19:35:01,203 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1146594525] [2023-08-26 19:35:01,203 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-08-26 19:35:01,203 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-08-26 19:35:01,251 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-08-26 19:35:01,746 INFO L134 CoverageAnalysis]: Checked inductivity of 45 backedges. 5 proven. 0 refuted. 0 times theorem prover too weak. 40 trivial. 0 not checked. [2023-08-26 19:35:01,747 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-08-26 19:35:01,747 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1146594525] [2023-08-26 19:35:01,747 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1146594525] provided 1 perfect and 0 imperfect interpolant sequences [2023-08-26 19:35:01,747 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-08-26 19:35:01,747 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2023-08-26 19:35:01,747 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [989810833] [2023-08-26 19:35:01,747 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-08-26 19:35:01,748 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2023-08-26 19:35:01,748 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-08-26 19:35:01,749 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2023-08-26 19:35:01,749 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=15, Invalid=15, Unknown=0, NotChecked=0, Total=30 [2023-08-26 19:35:01,752 INFO L471 CegarLoopForPetriNet]: Number of universal loopers: 648 out of 1849 [2023-08-26 19:35:01,754 INFO L103 encePairwiseOnDemand]: Start differencePairwiseOnDemand. First operand has 96 places, 105 transitions, 327 flow. Second operand has 6 states, 6 states have (on average 649.3333333333334) internal successors, (3896), 6 states have internal predecessors, (3896), 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 19:35:01,754 INFO L112 encePairwiseOnDemand]: Universal subtrahend loopers provided by user. [2023-08-26 19:35:01,754 INFO L113 encePairwiseOnDemand]: Number of universal subtrahend loopers: 648 of 1849 [2023-08-26 19:35:01,754 INFO L73 FinitePrefix]: Start finitePrefix. Operand will be constructed on-demand [2023-08-26 19:35:07,432 INFO L124 PetriNetUnfolderBase]: 45502/61444 cut-off events. [2023-08-26 19:35:07,433 INFO L125 PetriNetUnfolderBase]: For 171/171 co-relation queries the response was YES. [2023-08-26 19:35:07,511 INFO L83 FinitePrefix]: Finished finitePrefix Result has 123453 conditions, 61444 events. 45502/61444 cut-off events. For 171/171 co-relation queries the response was YES. Maximal size of possible extension queue 2751. Compared 362540 event pairs, 37481 based on Foata normal form. 0/21531 useless extension candidates. Maximal degree in co-relation 123443. Up to 61444 conditions per place. [2023-08-26 19:35:07,665 INFO L140 encePairwiseOnDemand]: 1846/1849 looper letters, 102 selfloop transitions, 1 changer transitions 0/103 dead transitions. [2023-08-26 19:35:07,665 INFO L145 encePairwiseOnDemand]: Finished differencePairwiseOnDemand. Result has 96 places, 103 transitions, 524 flow [2023-08-26 19:35:07,666 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2023-08-26 19:35:07,666 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 3 states. [2023-08-26 19:35:07,668 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 3 states to 3 states and 2034 transitions. [2023-08-26 19:35:07,669 INFO L516 CegarLoopForPetriNet]: DFA transition density 0.3666846944294213 [2023-08-26 19:35:07,669 INFO L72 ComplementDD]: Start complementDD. Operand 3 states and 2034 transitions. [2023-08-26 19:35:07,669 INFO L73 IsDeterministic]: Start isDeterministic. Operand 3 states and 2034 transitions. [2023-08-26 19:35:07,670 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2023-08-26 19:35:07,671 INFO L117 ReachableStatesCopy]: Start reachableStatesCopy. Operand 3 states and 2034 transitions. [2023-08-26 19:35:07,674 INFO L343 DoubleDeckerVisitor]: Before removal of dead ends has 4 states, 3 states have (on average 678.0) internal successors, (2034), 3 states have internal predecessors, (2034), 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 19:35:07,681 INFO L131 ReachableStatesCopy]: Finished reachableStatesCopy Result has 4 states, 4 states have (on average 1849.0) internal successors, (7396), 4 states have internal predecessors, (7396), 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 19:35:07,682 INFO L81 ComplementDD]: Finished complementDD. Result has 4 states, 4 states have (on average 1849.0) internal successors, (7396), 4 states have internal predecessors, (7396), 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 19:35:07,682 INFO L175 Difference]: Start difference. First operand has 96 places, 105 transitions, 327 flow. Second operand 3 states and 2034 transitions. [2023-08-26 19:35:07,682 INFO L82 GeneralOperation]: Start removeRedundantFlow. Operand has 96 places, 103 transitions, 524 flow [2023-08-26 19:35:07,683 INFO L88 GeneralOperation]: Finished removeRedundantFlow, result has has 92 places, 103 transitions, 494 flow, removed 3 selfloop flow, removed 4 redundant places. [2023-08-26 19:35:07,684 INFO L231 Difference]: Finished difference. Result has 92 places, 103 transitions, 290 flow [2023-08-26 19:35:07,685 INFO L264 CegarLoopForPetriNet]: {PETRI_ALPHABET=1849, PETRI_DIFFERENCE_MINUEND_FLOW=288, PETRI_DIFFERENCE_MINUEND_PLACES=90, PETRI_DIFFERENCE_MINUEND_TRANSITIONS=103, PETRI_DIFFERENCE_SUBTRAHEND_LETTERS_WITH_MORE_CHANGERS_THAN_LOOPERS=1, PETRI_DIFFERENCE_SUBTRAHEND_LOOPER_ONLY_LETTERS=102, PETRI_DIFFERENCE_SUBTRAHEND_STATES=3, PETRI_FLOW=290, PETRI_PLACES=92, PETRI_TRANSITIONS=103} [2023-08-26 19:35:07,685 INFO L281 CegarLoopForPetriNet]: 112 programPoint places, -20 predicate places. [2023-08-26 19:35:07,685 INFO L495 AbstractCegarLoop]: Abstraction has has 92 places, 103 transitions, 290 flow [2023-08-26 19:35:07,686 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 649.3333333333334) internal successors, (3896), 6 states have internal predecessors, (3896), 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 19:35:07,686 INFO L200 CegarLoopForPetriNet]: Found error trace [2023-08-26 19:35:07,686 INFO L208 CegarLoopForPetriNet]: trace histogram [5, 5, 5, 1, 1, 1, 1] [2023-08-26 19:35:07,686 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5 [2023-08-26 19:35:07,687 INFO L420 AbstractCegarLoop]: === Iteration 7 === Targeting ULTIMATE.startErr7REQUIRES_VIOLATIONMEMORY_DEREFERENCE === [thread1Err0REQUIRES_VIOLATIONMEMORY_DEREFERENCE, thread1Err1REQUIRES_VIOLATIONMEMORY_DEREFERENCE, thread1Err2REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 115 more)] === [2023-08-26 19:35:07,687 INFO L145 PredicateUnifier]: Initialized classic predicate unifier [2023-08-26 19:35:07,687 INFO L85 PathProgramCache]: Analyzing trace with hash -2032926299, now seen corresponding path program 2 times [2023-08-26 19:35:07,687 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-08-26 19:35:07,687 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1424062188] [2023-08-26 19:35:07,687 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-08-26 19:35:07,687 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-08-26 19:35:07,727 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-08-26 19:35:08,167 INFO L134 CoverageAnalysis]: Checked inductivity of 45 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2023-08-26 19:35:08,167 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-08-26 19:35:08,167 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1424062188] [2023-08-26 19:35:08,167 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1424062188] provided 1 perfect and 0 imperfect interpolant sequences [2023-08-26 19:35:08,167 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-08-26 19:35:08,167 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2023-08-26 19:35:08,167 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [487717133] [2023-08-26 19:35:08,167 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-08-26 19:35:08,168 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2023-08-26 19:35:08,168 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-08-26 19:35:08,168 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2023-08-26 19:35:08,168 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=6, Invalid=6, Unknown=0, NotChecked=0, Total=12 [2023-08-26 19:35:08,170 INFO L471 CegarLoopForPetriNet]: Number of universal loopers: 651 out of 1849 [2023-08-26 19:35:08,172 INFO L103 encePairwiseOnDemand]: Start differencePairwiseOnDemand. First operand has 92 places, 103 transitions, 290 flow. Second operand has 4 states, 4 states have (on average 652.75) internal successors, (2611), 4 states have internal predecessors, (2611), 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 19:35:08,172 INFO L112 encePairwiseOnDemand]: Universal subtrahend loopers provided by user. [2023-08-26 19:35:08,172 INFO L113 encePairwiseOnDemand]: Number of universal subtrahend loopers: 651 of 1849 [2023-08-26 19:35:08,172 INFO L73 FinitePrefix]: Start finitePrefix. Operand will be constructed on-demand [2023-08-26 19:35:12,199 INFO L124 PetriNetUnfolderBase]: 30960/42545 cut-off events. [2023-08-26 19:35:12,199 INFO L125 PetriNetUnfolderBase]: For 174/174 co-relation queries the response was YES. [2023-08-26 19:35:12,252 INFO L83 FinitePrefix]: Finished finitePrefix Result has 85640 conditions, 42545 events. 30960/42545 cut-off events. For 174/174 co-relation queries the response was YES. Maximal size of possible extension queue 1988. Compared 250475 event pairs, 25293 based on Foata normal form. 0/16999 useless extension candidates. Maximal degree in co-relation 85629. Up to 42545 conditions per place. [2023-08-26 19:35:12,353 INFO L140 encePairwiseOnDemand]: 1846/1849 looper letters, 100 selfloop transitions, 1 changer transitions 0/101 dead transitions. [2023-08-26 19:35:12,353 INFO L145 encePairwiseOnDemand]: Finished differencePairwiseOnDemand. Result has 92 places, 101 transitions, 483 flow [2023-08-26 19:35:12,354 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2023-08-26 19:35:12,354 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 3 states. [2023-08-26 19:35:12,356 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 3 states to 3 states and 2041 transitions. [2023-08-26 19:35:12,357 INFO L516 CegarLoopForPetriNet]: DFA transition density 0.36794663782224624 [2023-08-26 19:35:12,357 INFO L72 ComplementDD]: Start complementDD. Operand 3 states and 2041 transitions. [2023-08-26 19:35:12,357 INFO L73 IsDeterministic]: Start isDeterministic. Operand 3 states and 2041 transitions. [2023-08-26 19:35:12,358 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2023-08-26 19:35:12,358 INFO L117 ReachableStatesCopy]: Start reachableStatesCopy. Operand 3 states and 2041 transitions. [2023-08-26 19:35:12,361 INFO L343 DoubleDeckerVisitor]: Before removal of dead ends has 4 states, 3 states have (on average 680.3333333333334) internal successors, (2041), 3 states have internal predecessors, (2041), 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 19:35:12,366 INFO L131 ReachableStatesCopy]: Finished reachableStatesCopy Result has 4 states, 4 states have (on average 1849.0) internal successors, (7396), 4 states have internal predecessors, (7396), 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 19:35:12,367 INFO L81 ComplementDD]: Finished complementDD. Result has 4 states, 4 states have (on average 1849.0) internal successors, (7396), 4 states have internal predecessors, (7396), 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 19:35:12,367 INFO L175 Difference]: Start difference. First operand has 92 places, 103 transitions, 290 flow. Second operand 3 states and 2041 transitions. [2023-08-26 19:35:12,367 INFO L82 GeneralOperation]: Start removeRedundantFlow. Operand has 92 places, 101 transitions, 483 flow [2023-08-26 19:35:12,368 INFO L88 GeneralOperation]: Finished removeRedundantFlow, result has has 91 places, 101 transitions, 482 flow, removed 0 selfloop flow, removed 1 redundant places. [2023-08-26 19:35:12,369 INFO L231 Difference]: Finished difference. Result has 91 places, 101 transitions, 282 flow [2023-08-26 19:35:12,369 INFO L264 CegarLoopForPetriNet]: {PETRI_ALPHABET=1849, PETRI_DIFFERENCE_MINUEND_FLOW=280, PETRI_DIFFERENCE_MINUEND_PLACES=89, PETRI_DIFFERENCE_MINUEND_TRANSITIONS=101, PETRI_DIFFERENCE_SUBTRAHEND_LETTERS_WITH_MORE_CHANGERS_THAN_LOOPERS=1, PETRI_DIFFERENCE_SUBTRAHEND_LOOPER_ONLY_LETTERS=100, PETRI_DIFFERENCE_SUBTRAHEND_STATES=3, PETRI_FLOW=282, PETRI_PLACES=91, PETRI_TRANSITIONS=101} [2023-08-26 19:35:12,370 INFO L281 CegarLoopForPetriNet]: 112 programPoint places, -21 predicate places. [2023-08-26 19:35:12,370 INFO L495 AbstractCegarLoop]: Abstraction has has 91 places, 101 transitions, 282 flow [2023-08-26 19:35:12,370 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 652.75) internal successors, (2611), 4 states have internal predecessors, (2611), 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 19:35:12,370 INFO L200 CegarLoopForPetriNet]: Found error trace [2023-08-26 19:35:12,371 INFO L208 CegarLoopForPetriNet]: trace histogram [5, 5, 5, 1, 1, 1, 1, 1, 1] [2023-08-26 19:35:12,371 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6 [2023-08-26 19:35:12,371 INFO L420 AbstractCegarLoop]: === Iteration 8 === Targeting ULTIMATE.startErr9REQUIRES_VIOLATIONMEMORY_DEREFERENCE === [thread1Err0REQUIRES_VIOLATIONMEMORY_DEREFERENCE, thread1Err1REQUIRES_VIOLATIONMEMORY_DEREFERENCE, thread1Err2REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 115 more)] === [2023-08-26 19:35:12,371 INFO L145 PredicateUnifier]: Initialized classic predicate unifier [2023-08-26 19:35:12,371 INFO L85 PathProgramCache]: Analyzing trace with hash 568021899, now seen corresponding path program 1 times [2023-08-26 19:35:12,371 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-08-26 19:35:12,371 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [519652862] [2023-08-26 19:35:12,371 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-08-26 19:35:12,372 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-08-26 19:35:12,399 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-08-26 19:35:12,971 INFO L134 CoverageAnalysis]: Checked inductivity of 45 backedges. 6 proven. 9 refuted. 0 times theorem prover too weak. 30 trivial. 0 not checked. [2023-08-26 19:35:12,973 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-08-26 19:35:12,974 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [519652862] [2023-08-26 19:35:12,974 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [519652862] provided 0 perfect and 1 imperfect interpolant sequences [2023-08-26 19:35:12,974 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [843896099] [2023-08-26 19:35:12,974 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-08-26 19:35:12,974 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-08-26 19:35:12,974 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-08-26 19:35:12,976 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 19:35:12,978 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 19:35:13,170 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-08-26 19:35:13,172 INFO L262 TraceCheckSpWp]: Trace formula consists of 367 conjuncts, 13 conjunts are in the unsatisfiable core [2023-08-26 19:35:13,175 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-08-26 19:35:13,198 INFO L190 IndexEqualityManager]: detected not equals via solver [2023-08-26 19:35:13,199 INFO L190 IndexEqualityManager]: detected not equals via solver [2023-08-26 19:35:13,228 INFO L322 Elim1Store]: treesize reduction 49, result has 33.8 percent of original size [2023-08-26 19:35:13,228 INFO L351 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 2 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 2 case distinctions, treesize of input 15 treesize of output 35 [2023-08-26 19:35:13,242 INFO L351 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 98 treesize of output 94 [2023-08-26 19:35:13,305 INFO L190 IndexEqualityManager]: detected not equals via solver [2023-08-26 19:35:13,306 INFO L351 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 12 treesize of output 14 [2023-08-26 19:35:13,348 INFO L190 IndexEqualityManager]: detected not equals via solver [2023-08-26 19:35:13,349 INFO L351 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 12 treesize of output 14 [2023-08-26 19:35:13,373 INFO L134 CoverageAnalysis]: Checked inductivity of 45 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2023-08-26 19:35:13,374 INFO L323 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2023-08-26 19:35:13,374 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [843896099] provided 1 perfect and 0 imperfect interpolant sequences [2023-08-26 19:35:13,374 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2023-08-26 19:35:13,374 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [9] total 10 [2023-08-26 19:35:13,374 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1416187199] [2023-08-26 19:35:13,374 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-08-26 19:35:13,375 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2023-08-26 19:35:13,375 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-08-26 19:35:13,375 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2023-08-26 19:35:13,375 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=45, Invalid=87, Unknown=0, NotChecked=0, Total=132 [2023-08-26 19:35:13,377 INFO L471 CegarLoopForPetriNet]: Number of universal loopers: 663 out of 1849 [2023-08-26 19:35:13,379 INFO L103 encePairwiseOnDemand]: Start differencePairwiseOnDemand. First operand has 91 places, 101 transitions, 282 flow. Second operand has 4 states, 4 states have (on average 665.25) internal successors, (2661), 4 states have internal predecessors, (2661), 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 19:35:13,379 INFO L112 encePairwiseOnDemand]: Universal subtrahend loopers provided by user. [2023-08-26 19:35:13,379 INFO L113 encePairwiseOnDemand]: Number of universal subtrahend loopers: 663 of 1849 [2023-08-26 19:35:13,379 INFO L73 FinitePrefix]: Start finitePrefix. Operand will be constructed on-demand [2023-08-26 19:35:17,333 INFO L124 PetriNetUnfolderBase]: 30491/41856 cut-off events. [2023-08-26 19:35:17,333 INFO L125 PetriNetUnfolderBase]: For 174/174 co-relation queries the response was YES. [2023-08-26 19:35:17,386 INFO L83 FinitePrefix]: Finished finitePrefix Result has 84263 conditions, 41856 events. 30491/41856 cut-off events. For 174/174 co-relation queries the response was YES. Maximal size of possible extension queue 1850. Compared 244532 event pairs, 24907 based on Foata normal form. 0/16865 useless extension candidates. Maximal degree in co-relation 84251. Up to 41856 conditions per place. [2023-08-26 19:35:17,480 INFO L140 encePairwiseOnDemand]: 1846/1849 looper letters, 98 selfloop transitions, 1 changer transitions 0/99 dead transitions. [2023-08-26 19:35:17,480 INFO L145 encePairwiseOnDemand]: Finished differencePairwiseOnDemand. Result has 91 places, 99 transitions, 476 flow [2023-08-26 19:35:17,480 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2023-08-26 19:35:17,480 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 3 states. [2023-08-26 19:35:17,483 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 3 states to 3 states and 2075 transitions. [2023-08-26 19:35:17,484 INFO L516 CegarLoopForPetriNet]: DFA transition density 0.37407607715882457 [2023-08-26 19:35:17,484 INFO L72 ComplementDD]: Start complementDD. Operand 3 states and 2075 transitions. [2023-08-26 19:35:17,484 INFO L73 IsDeterministic]: Start isDeterministic. Operand 3 states and 2075 transitions. [2023-08-26 19:35:17,485 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2023-08-26 19:35:17,485 INFO L117 ReachableStatesCopy]: Start reachableStatesCopy. Operand 3 states and 2075 transitions. [2023-08-26 19:35:17,488 INFO L343 DoubleDeckerVisitor]: Before removal of dead ends has 4 states, 3 states have (on average 691.6666666666666) internal successors, (2075), 3 states have internal predecessors, (2075), 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 19:35:17,493 INFO L131 ReachableStatesCopy]: Finished reachableStatesCopy Result has 4 states, 4 states have (on average 1849.0) internal successors, (7396), 4 states have internal predecessors, (7396), 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 19:35:17,494 INFO L81 ComplementDD]: Finished complementDD. Result has 4 states, 4 states have (on average 1849.0) internal successors, (7396), 4 states have internal predecessors, (7396), 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 19:35:17,494 INFO L175 Difference]: Start difference. First operand has 91 places, 101 transitions, 282 flow. Second operand 3 states and 2075 transitions. [2023-08-26 19:35:17,494 INFO L82 GeneralOperation]: Start removeRedundantFlow. Operand has 91 places, 99 transitions, 476 flow [2023-08-26 19:35:17,495 INFO L88 GeneralOperation]: Finished removeRedundantFlow, result has has 90 places, 99 transitions, 475 flow, removed 0 selfloop flow, removed 1 redundant places. [2023-08-26 19:35:17,497 INFO L231 Difference]: Finished difference. Result has 90 places, 99 transitions, 279 flow [2023-08-26 19:35:17,497 INFO L264 CegarLoopForPetriNet]: {PETRI_ALPHABET=1849, PETRI_DIFFERENCE_MINUEND_FLOW=277, PETRI_DIFFERENCE_MINUEND_PLACES=88, PETRI_DIFFERENCE_MINUEND_TRANSITIONS=99, PETRI_DIFFERENCE_SUBTRAHEND_LETTERS_WITH_MORE_CHANGERS_THAN_LOOPERS=1, PETRI_DIFFERENCE_SUBTRAHEND_LOOPER_ONLY_LETTERS=98, PETRI_DIFFERENCE_SUBTRAHEND_STATES=3, PETRI_FLOW=279, PETRI_PLACES=90, PETRI_TRANSITIONS=99} [2023-08-26 19:35:17,497 INFO L281 CegarLoopForPetriNet]: 112 programPoint places, -22 predicate places. [2023-08-26 19:35:17,497 INFO L495 AbstractCegarLoop]: Abstraction has has 90 places, 99 transitions, 279 flow [2023-08-26 19:35:17,498 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 665.25) internal successors, (2661), 4 states have internal predecessors, (2661), 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 19:35:17,498 INFO L200 CegarLoopForPetriNet]: Found error trace [2023-08-26 19:35:17,498 INFO L208 CegarLoopForPetriNet]: trace histogram [5, 5, 5, 1, 1, 1, 1, 1, 1] [2023-08-26 19:35:17,504 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Ended with exit code 0 [2023-08-26 19:35:17,704 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-08-26 19:35:17,704 INFO L420 AbstractCegarLoop]: === Iteration 9 === Targeting ULTIMATE.startErr8REQUIRES_VIOLATIONMEMORY_DEREFERENCE === [thread1Err0REQUIRES_VIOLATIONMEMORY_DEREFERENCE, thread1Err1REQUIRES_VIOLATIONMEMORY_DEREFERENCE, thread1Err2REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 115 more)] === [2023-08-26 19:35:17,705 INFO L145 PredicateUnifier]: Initialized classic predicate unifier [2023-08-26 19:35:17,705 INFO L85 PathProgramCache]: Analyzing trace with hash 568021898, now seen corresponding path program 1 times [2023-08-26 19:35:17,705 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-08-26 19:35:17,705 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1163466348] [2023-08-26 19:35:17,705 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-08-26 19:35:17,705 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-08-26 19:35:17,734 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-08-26 19:35:17,983 INFO L134 CoverageAnalysis]: Checked inductivity of 45 backedges. 5 proven. 0 refuted. 0 times theorem prover too weak. 40 trivial. 0 not checked. [2023-08-26 19:35:17,983 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-08-26 19:35:17,983 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1163466348] [2023-08-26 19:35:17,983 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1163466348] provided 1 perfect and 0 imperfect interpolant sequences [2023-08-26 19:35:17,983 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-08-26 19:35:17,983 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2023-08-26 19:35:17,984 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1013102774] [2023-08-26 19:35:17,984 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-08-26 19:35:17,984 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2023-08-26 19:35:17,984 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-08-26 19:35:17,984 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2023-08-26 19:35:17,984 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=15, Invalid=15, Unknown=0, NotChecked=0, Total=30 [2023-08-26 19:35:17,987 INFO L471 CegarLoopForPetriNet]: Number of universal loopers: 648 out of 1849 [2023-08-26 19:35:17,989 INFO L103 encePairwiseOnDemand]: Start differencePairwiseOnDemand. First operand has 90 places, 99 transitions, 279 flow. Second operand has 6 states, 6 states have (on average 649.6666666666666) internal successors, (3898), 6 states have internal predecessors, (3898), 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 19:35:17,989 INFO L112 encePairwiseOnDemand]: Universal subtrahend loopers provided by user. [2023-08-26 19:35:17,989 INFO L113 encePairwiseOnDemand]: Number of universal subtrahend loopers: 648 of 1849 [2023-08-26 19:35:17,989 INFO L73 FinitePrefix]: Start finitePrefix. Operand will be constructed on-demand [2023-08-26 19:35:21,857 INFO L124 PetriNetUnfolderBase]: 30022/41167 cut-off events. [2023-08-26 19:35:21,857 INFO L125 PetriNetUnfolderBase]: For 174/174 co-relation queries the response was YES. [2023-08-26 19:35:21,922 INFO L83 FinitePrefix]: Finished finitePrefix Result has 82886 conditions, 41167 events. 30022/41167 cut-off events. For 174/174 co-relation queries the response was YES. Maximal size of possible extension queue 1888. Compared 240297 event pairs, 24521 based on Foata normal form. 0/16731 useless extension candidates. Maximal degree in co-relation 82873. Up to 41167 conditions per place. [2023-08-26 19:35:22,031 INFO L140 encePairwiseOnDemand]: 1846/1849 looper letters, 96 selfloop transitions, 1 changer transitions 0/97 dead transitions. [2023-08-26 19:35:22,031 INFO L145 encePairwiseOnDemand]: Finished differencePairwiseOnDemand. Result has 90 places, 97 transitions, 469 flow [2023-08-26 19:35:22,031 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2023-08-26 19:35:22,031 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 3 states. [2023-08-26 19:35:22,034 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 3 states to 3 states and 2028 transitions. [2023-08-26 19:35:22,034 INFO L516 CegarLoopForPetriNet]: DFA transition density 0.3656030286641428 [2023-08-26 19:35:22,034 INFO L72 ComplementDD]: Start complementDD. Operand 3 states and 2028 transitions. [2023-08-26 19:35:22,034 INFO L73 IsDeterministic]: Start isDeterministic. Operand 3 states and 2028 transitions. [2023-08-26 19:35:22,035 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2023-08-26 19:35:22,035 INFO L117 ReachableStatesCopy]: Start reachableStatesCopy. Operand 3 states and 2028 transitions. [2023-08-26 19:35:22,038 INFO L343 DoubleDeckerVisitor]: Before removal of dead ends has 4 states, 3 states have (on average 676.0) internal successors, (2028), 3 states have internal predecessors, (2028), 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 19:35:22,043 INFO L131 ReachableStatesCopy]: Finished reachableStatesCopy Result has 4 states, 4 states have (on average 1849.0) internal successors, (7396), 4 states have internal predecessors, (7396), 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 19:35:22,044 INFO L81 ComplementDD]: Finished complementDD. Result has 4 states, 4 states have (on average 1849.0) internal successors, (7396), 4 states have internal predecessors, (7396), 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 19:35:22,044 INFO L175 Difference]: Start difference. First operand has 90 places, 99 transitions, 279 flow. Second operand 3 states and 2028 transitions. [2023-08-26 19:35:22,044 INFO L82 GeneralOperation]: Start removeRedundantFlow. Operand has 90 places, 97 transitions, 469 flow [2023-08-26 19:35:22,045 INFO L88 GeneralOperation]: Finished removeRedundantFlow, result has has 89 places, 97 transitions, 468 flow, removed 0 selfloop flow, removed 1 redundant places. [2023-08-26 19:35:22,046 INFO L231 Difference]: Finished difference. Result has 89 places, 97 transitions, 276 flow [2023-08-26 19:35:22,046 INFO L264 CegarLoopForPetriNet]: {PETRI_ALPHABET=1849, PETRI_DIFFERENCE_MINUEND_FLOW=274, PETRI_DIFFERENCE_MINUEND_PLACES=87, PETRI_DIFFERENCE_MINUEND_TRANSITIONS=97, PETRI_DIFFERENCE_SUBTRAHEND_LETTERS_WITH_MORE_CHANGERS_THAN_LOOPERS=1, PETRI_DIFFERENCE_SUBTRAHEND_LOOPER_ONLY_LETTERS=96, PETRI_DIFFERENCE_SUBTRAHEND_STATES=3, PETRI_FLOW=276, PETRI_PLACES=89, PETRI_TRANSITIONS=97} [2023-08-26 19:35:22,047 INFO L281 CegarLoopForPetriNet]: 112 programPoint places, -23 predicate places. [2023-08-26 19:35:22,047 INFO L495 AbstractCegarLoop]: Abstraction has has 89 places, 97 transitions, 276 flow [2023-08-26 19:35:22,048 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 649.6666666666666) internal successors, (3898), 6 states have internal predecessors, (3898), 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 19:35:22,048 INFO L200 CegarLoopForPetriNet]: Found error trace [2023-08-26 19:35:22,048 INFO L208 CegarLoopForPetriNet]: trace histogram [5, 5, 5, 1, 1, 1, 1, 1, 1, 1] [2023-08-26 19:35:22,048 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8 [2023-08-26 19:35:22,049 INFO L420 AbstractCegarLoop]: === Iteration 10 === Targeting thread1Err1REQUIRES_VIOLATIONMEMORY_DEREFERENCE === [thread1Err0REQUIRES_VIOLATIONMEMORY_DEREFERENCE, thread1Err1REQUIRES_VIOLATIONMEMORY_DEREFERENCE, thread1Err2REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 115 more)] === [2023-08-26 19:35:22,049 INFO L145 PredicateUnifier]: Initialized classic predicate unifier [2023-08-26 19:35:22,049 INFO L85 PathProgramCache]: Analyzing trace with hash 428819723, now seen corresponding path program 1 times [2023-08-26 19:35:22,049 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-08-26 19:35:22,049 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [628065229] [2023-08-26 19:35:22,049 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-08-26 19:35:22,050 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-08-26 19:35:22,082 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-08-26 19:35:22,606 INFO L134 CoverageAnalysis]: Checked inductivity of 45 backedges. 6 proven. 9 refuted. 0 times theorem prover too weak. 30 trivial. 0 not checked. [2023-08-26 19:35:22,607 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-08-26 19:35:22,607 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [628065229] [2023-08-26 19:35:22,607 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [628065229] provided 0 perfect and 1 imperfect interpolant sequences [2023-08-26 19:35:22,607 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1180491680] [2023-08-26 19:35:22,607 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-08-26 19:35:22,607 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-08-26 19:35:22,608 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-08-26 19:35:22,608 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 19:35:22,611 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 19:35:22,795 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-08-26 19:35:22,797 INFO L262 TraceCheckSpWp]: Trace formula consists of 379 conjuncts, 24 conjunts are in the unsatisfiable core [2023-08-26 19:35:22,799 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-08-26 19:35:22,843 INFO L322 Elim1Store]: treesize reduction 72, result has 33.9 percent of original size [2023-08-26 19:35:22,844 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 3 case distinctions, treesize of input 15 treesize of output 42 [2023-08-26 19:35:23,003 INFO L322 Elim1Store]: treesize reduction 18, result has 35.7 percent of original size [2023-08-26 19:35:23,004 INFO L351 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 2 case distinctions, treesize of input 17 treesize of output 21 [2023-08-26 19:35:23,008 INFO L351 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 14 treesize of output 16 [2023-08-26 19:35:23,079 INFO L190 IndexEqualityManager]: detected not equals via solver [2023-08-26 19:35:23,080 INFO L351 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 14 treesize of output 16 [2023-08-26 19:35:23,089 INFO L322 Elim1Store]: treesize reduction 4, result has 50.0 percent of original size [2023-08-26 19:35:23,089 INFO L351 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 11 treesize of output 11 [2023-08-26 19:35:23,152 INFO L134 CoverageAnalysis]: Checked inductivity of 45 backedges. 10 proven. 5 refuted. 0 times theorem prover too weak. 30 trivial. 0 not checked. [2023-08-26 19:35:23,152 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-08-26 19:35:29,285 WARN L234 SmtUtils]: Spent 6.01s on a formula simplification that was a NOOP. DAG size: 22 (called from [L 376] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2023-08-26 19:35:31,346 INFO L351 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 96 treesize of output 92 [2023-08-26 19:35:31,787 INFO L134 CoverageAnalysis]: Checked inductivity of 45 backedges. 10 proven. 5 refuted. 0 times theorem prover too weak. 30 trivial. 0 not checked. [2023-08-26 19:35:31,787 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1180491680] provided 0 perfect and 2 imperfect interpolant sequences [2023-08-26 19:35:31,787 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2023-08-26 19:35:31,787 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9, 9] total 27 [2023-08-26 19:35:31,788 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [700078333] [2023-08-26 19:35:31,788 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2023-08-26 19:35:31,788 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 29 states [2023-08-26 19:35:31,788 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-08-26 19:35:31,789 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 29 interpolants. [2023-08-26 19:35:31,789 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=146, Invalid=666, Unknown=0, NotChecked=0, Total=812 [2023-08-26 19:35:31,798 INFO L471 CegarLoopForPetriNet]: Number of universal loopers: 588 out of 1849 [2023-08-26 19:35:31,807 INFO L103 encePairwiseOnDemand]: Start differencePairwiseOnDemand. First operand has 89 places, 97 transitions, 276 flow. Second operand has 29 states, 29 states have (on average 589.448275862069) internal successors, (17094), 29 states have internal predecessors, (17094), 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 19:35:31,807 INFO L112 encePairwiseOnDemand]: Universal subtrahend loopers provided by user. [2023-08-26 19:35:31,807 INFO L113 encePairwiseOnDemand]: Number of universal subtrahend loopers: 588 of 1849 [2023-08-26 19:35:31,807 INFO L73 FinitePrefix]: Start finitePrefix. Operand will be constructed on-demand [2023-08-26 19:35:38,047 INFO L124 PetriNetUnfolderBase]: 42814/58253 cut-off events. [2023-08-26 19:35:38,048 INFO L125 PetriNetUnfolderBase]: For 150/150 co-relation queries the response was YES. [2023-08-26 19:35:38,221 INFO L83 FinitePrefix]: Finished finitePrefix Result has 117233 conditions, 58253 events. 42814/58253 cut-off events. For 150/150 co-relation queries the response was YES. Maximal size of possible extension queue 1226. Compared 337534 event pairs, 4037 based on Foata normal form. 0/25897 useless extension candidates. Maximal degree in co-relation 117219. Up to 26291 conditions per place. [2023-08-26 19:35:38,402 INFO L140 encePairwiseOnDemand]: 1827/1849 looper letters, 181 selfloop transitions, 23 changer transitions 0/204 dead transitions. [2023-08-26 19:35:38,402 INFO L145 encePairwiseOnDemand]: Finished differencePairwiseOnDemand. Result has 95 places, 204 transitions, 908 flow [2023-08-26 19:35:38,403 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2023-08-26 19:35:38,403 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 15 states. [2023-08-26 19:35:38,411 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 15 states to 15 states and 9043 transitions. [2023-08-26 19:35:38,413 INFO L516 CegarLoopForPetriNet]: DFA transition density 0.3260501171804579 [2023-08-26 19:35:38,413 INFO L72 ComplementDD]: Start complementDD. Operand 15 states and 9043 transitions. [2023-08-26 19:35:38,413 INFO L73 IsDeterministic]: Start isDeterministic. Operand 15 states and 9043 transitions. [2023-08-26 19:35:38,415 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2023-08-26 19:35:38,415 INFO L117 ReachableStatesCopy]: Start reachableStatesCopy. Operand 15 states and 9043 transitions. [2023-08-26 19:35:38,425 INFO L343 DoubleDeckerVisitor]: Before removal of dead ends has 16 states, 15 states have (on average 602.8666666666667) internal successors, (9043), 15 states have internal predecessors, (9043), 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 19:35:38,446 INFO L131 ReachableStatesCopy]: Finished reachableStatesCopy Result has 16 states, 16 states have (on average 1849.0) internal successors, (29584), 16 states have internal predecessors, (29584), 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 19:35:38,449 INFO L81 ComplementDD]: Finished complementDD. Result has 16 states, 16 states have (on average 1849.0) internal successors, (29584), 16 states have internal predecessors, (29584), 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 19:35:38,450 INFO L175 Difference]: Start difference. First operand has 89 places, 97 transitions, 276 flow. Second operand 15 states and 9043 transitions. [2023-08-26 19:35:38,450 INFO L82 GeneralOperation]: Start removeRedundantFlow. Operand has 95 places, 204 transitions, 908 flow [2023-08-26 19:35:38,451 INFO L88 GeneralOperation]: Finished removeRedundantFlow, result has has 94 places, 204 transitions, 907 flow, removed 0 selfloop flow, removed 1 redundant places. [2023-08-26 19:35:38,453 INFO L231 Difference]: Finished difference. Result has 97 places, 94 transitions, 342 flow [2023-08-26 19:35:38,453 INFO L264 CegarLoopForPetriNet]: {PETRI_ALPHABET=1849, PETRI_DIFFERENCE_MINUEND_FLOW=259, PETRI_DIFFERENCE_MINUEND_PLACES=80, PETRI_DIFFERENCE_MINUEND_TRANSITIONS=89, PETRI_DIFFERENCE_SUBTRAHEND_LETTERS_WITH_MORE_CHANGERS_THAN_LOOPERS=18, PETRI_DIFFERENCE_SUBTRAHEND_LOOPER_ONLY_LETTERS=67, PETRI_DIFFERENCE_SUBTRAHEND_STATES=15, PETRI_FLOW=342, PETRI_PLACES=97, PETRI_TRANSITIONS=94} [2023-08-26 19:35:38,454 INFO L281 CegarLoopForPetriNet]: 112 programPoint places, -15 predicate places. [2023-08-26 19:35:38,454 INFO L495 AbstractCegarLoop]: Abstraction has has 97 places, 94 transitions, 342 flow [2023-08-26 19:35:38,457 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 29 states, 29 states have (on average 589.448275862069) internal successors, (17094), 29 states have internal predecessors, (17094), 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 19:35:38,457 INFO L200 CegarLoopForPetriNet]: Found error trace [2023-08-26 19:35:38,457 INFO L208 CegarLoopForPetriNet]: trace histogram [5, 5, 5, 1, 1, 1, 1, 1, 1, 1] [2023-08-26 19:35:38,465 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 19:35:38,662 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable9 [2023-08-26 19:35:38,663 INFO L420 AbstractCegarLoop]: === Iteration 11 === Targeting thread1Err3REQUIRES_VIOLATIONMEMORY_DEREFERENCE === [thread1Err0REQUIRES_VIOLATIONMEMORY_DEREFERENCE, thread1Err1REQUIRES_VIOLATIONMEMORY_DEREFERENCE, thread1Err2REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 115 more)] === [2023-08-26 19:35:38,663 INFO L145 PredicateUnifier]: Initialized classic predicate unifier [2023-08-26 19:35:38,663 INFO L85 PathProgramCache]: Analyzing trace with hash 428819725, now seen corresponding path program 1 times [2023-08-26 19:35:38,663 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-08-26 19:35:38,663 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [69457576] [2023-08-26 19:35:38,663 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-08-26 19:35:38,664 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-08-26 19:35:38,696 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-08-26 19:35:39,015 INFO L134 CoverageAnalysis]: Checked inductivity of 45 backedges. 6 proven. 9 refuted. 0 times theorem prover too weak. 30 trivial. 0 not checked. [2023-08-26 19:35:39,015 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-08-26 19:35:39,017 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [69457576] [2023-08-26 19:35:39,017 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [69457576] provided 0 perfect and 1 imperfect interpolant sequences [2023-08-26 19:35:39,017 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [505217304] [2023-08-26 19:35:39,017 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-08-26 19:35:39,017 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-08-26 19:35:39,017 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-08-26 19:35:39,018 INFO L229 MonitoredProcess]: Starting monitored process 7 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-08-26 19:35:39,020 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2023-08-26 19:35:39,217 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-08-26 19:35:39,219 INFO L262 TraceCheckSpWp]: Trace formula consists of 387 conjuncts, 20 conjunts are in the unsatisfiable core [2023-08-26 19:35:39,221 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-08-26 19:35:39,233 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 19:35:39,337 INFO L190 IndexEqualityManager]: detected not equals via solver [2023-08-26 19:35:39,338 INFO L351 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 14 treesize of output 16 [2023-08-26 19:35:39,346 INFO L322 Elim1Store]: treesize reduction 4, result has 50.0 percent of original size [2023-08-26 19:35:39,346 INFO L351 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 11 treesize of output 11 [2023-08-26 19:35:39,403 INFO L134 CoverageAnalysis]: Checked inductivity of 45 backedges. 10 proven. 5 refuted. 0 times theorem prover too weak. 30 trivial. 0 not checked. [2023-08-26 19:35:39,403 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-08-26 19:35:45,498 WARN L234 SmtUtils]: Spent 6.01s on a formula simplification that was a NOOP. DAG size: 22 (called from [L 376] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2023-08-26 19:35:45,507 INFO L351 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 48 treesize of output 44 [2023-08-26 19:35:45,718 INFO L134 CoverageAnalysis]: Checked inductivity of 45 backedges. 10 proven. 5 refuted. 0 times theorem prover too weak. 30 trivial. 0 not checked. [2023-08-26 19:35:45,718 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [505217304] provided 0 perfect and 2 imperfect interpolant sequences [2023-08-26 19:35:45,718 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2023-08-26 19:35:45,718 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9, 9] total 25 [2023-08-26 19:35:45,719 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1296369354] [2023-08-26 19:35:45,719 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2023-08-26 19:35:45,719 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 26 states [2023-08-26 19:35:45,720 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-08-26 19:35:45,720 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 26 interpolants. [2023-08-26 19:35:45,720 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=148, Invalid=502, Unknown=0, NotChecked=0, Total=650 [2023-08-26 19:35:45,728 INFO L471 CegarLoopForPetriNet]: Number of universal loopers: 594 out of 1849 [2023-08-26 19:35:45,736 INFO L103 encePairwiseOnDemand]: Start differencePairwiseOnDemand. First operand has 97 places, 94 transitions, 342 flow. Second operand has 26 states, 26 states have (on average 595.4615384615385) internal successors, (15482), 26 states have internal predecessors, (15482), 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 19:35:45,736 INFO L112 encePairwiseOnDemand]: Universal subtrahend loopers provided by user. [2023-08-26 19:35:45,736 INFO L113 encePairwiseOnDemand]: Number of universal subtrahend loopers: 594 of 1849 [2023-08-26 19:35:45,736 INFO L73 FinitePrefix]: Start finitePrefix. Operand will be constructed on-demand [2023-08-26 19:35:53,203 INFO L124 PetriNetUnfolderBase]: 49765/68144 cut-off events. [2023-08-26 19:35:53,203 INFO L125 PetriNetUnfolderBase]: For 5191/5191 co-relation queries the response was YES. [2023-08-26 19:35:53,370 INFO L83 FinitePrefix]: Finished finitePrefix Result has 147254 conditions, 68144 events. 49765/68144 cut-off events. For 5191/5191 co-relation queries the response was YES. Maximal size of possible extension queue 1069. Compared 394435 event pairs, 16374 based on Foata normal form. 0/34332 useless extension candidates. Maximal degree in co-relation 147236. Up to 27679 conditions per place. [2023-08-26 19:35:53,543 INFO L140 encePairwiseOnDemand]: 1836/1849 looper letters, 189 selfloop transitions, 20 changer transitions 0/209 dead transitions. [2023-08-26 19:35:53,543 INFO L145 encePairwiseOnDemand]: Finished differencePairwiseOnDemand. Result has 111 places, 209 transitions, 1008 flow [2023-08-26 19:35:53,544 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2023-08-26 19:35:53,544 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 15 states. [2023-08-26 19:35:53,555 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 15 states to 15 states and 9122 transitions. [2023-08-26 19:35:53,558 INFO L516 CegarLoopForPetriNet]: DFA transition density 0.32889850369569135 [2023-08-26 19:35:53,558 INFO L72 ComplementDD]: Start complementDD. Operand 15 states and 9122 transitions. [2023-08-26 19:35:53,558 INFO L73 IsDeterministic]: Start isDeterministic. Operand 15 states and 9122 transitions. [2023-08-26 19:35:53,560 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2023-08-26 19:35:53,560 INFO L117 ReachableStatesCopy]: Start reachableStatesCopy. Operand 15 states and 9122 transitions. [2023-08-26 19:35:53,757 INFO L343 DoubleDeckerVisitor]: Before removal of dead ends has 16 states, 15 states have (on average 608.1333333333333) internal successors, (9122), 15 states have internal predecessors, (9122), 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 19:35:53,773 INFO L131 ReachableStatesCopy]: Finished reachableStatesCopy Result has 16 states, 16 states have (on average 1849.0) internal successors, (29584), 16 states have internal predecessors, (29584), 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 19:35:53,776 INFO L81 ComplementDD]: Finished complementDD. Result has 16 states, 16 states have (on average 1849.0) internal successors, (29584), 16 states have internal predecessors, (29584), 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 19:35:53,776 INFO L175 Difference]: Start difference. First operand has 97 places, 94 transitions, 342 flow. Second operand 15 states and 9122 transitions. [2023-08-26 19:35:53,776 INFO L82 GeneralOperation]: Start removeRedundantFlow. Operand has 111 places, 209 transitions, 1008 flow [2023-08-26 19:35:53,829 INFO L88 GeneralOperation]: Finished removeRedundantFlow, result has has 105 places, 209 transitions, 969 flow, removed 4 selfloop flow, removed 6 redundant places. [2023-08-26 19:35:53,831 INFO L231 Difference]: Finished difference. Result has 108 places, 95 transitions, 368 flow [2023-08-26 19:35:53,831 INFO L264 CegarLoopForPetriNet]: {PETRI_ALPHABET=1849, PETRI_DIFFERENCE_MINUEND_FLOW=299, PETRI_DIFFERENCE_MINUEND_PLACES=91, PETRI_DIFFERENCE_MINUEND_TRANSITIONS=93, PETRI_DIFFERENCE_SUBTRAHEND_LETTERS_WITH_MORE_CHANGERS_THAN_LOOPERS=18, PETRI_DIFFERENCE_SUBTRAHEND_LOOPER_ONLY_LETTERS=73, PETRI_DIFFERENCE_SUBTRAHEND_STATES=15, PETRI_FLOW=368, PETRI_PLACES=108, PETRI_TRANSITIONS=95} [2023-08-26 19:35:53,832 INFO L281 CegarLoopForPetriNet]: 112 programPoint places, -4 predicate places. [2023-08-26 19:35:53,832 INFO L495 AbstractCegarLoop]: Abstraction has has 108 places, 95 transitions, 368 flow [2023-08-26 19:35:53,834 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 26 states, 26 states have (on average 595.4615384615385) internal successors, (15482), 26 states have internal predecessors, (15482), 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 19:35:53,834 INFO L200 CegarLoopForPetriNet]: Found error trace [2023-08-26 19:35:53,834 INFO L208 CegarLoopForPetriNet]: trace histogram [5, 5, 5, 1, 1, 1, 1, 1, 1, 1] [2023-08-26 19:35:53,839 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Ended with exit code 0 [2023-08-26 19:35:54,034 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable10,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-08-26 19:35:54,035 INFO L420 AbstractCegarLoop]: === Iteration 12 === Targeting thread1Err2REQUIRES_VIOLATIONMEMORY_DEREFERENCE === [thread1Err0REQUIRES_VIOLATIONMEMORY_DEREFERENCE, thread1Err1REQUIRES_VIOLATIONMEMORY_DEREFERENCE, thread1Err2REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 115 more)] === [2023-08-26 19:35:54,035 INFO L145 PredicateUnifier]: Initialized classic predicate unifier [2023-08-26 19:35:54,035 INFO L85 PathProgramCache]: Analyzing trace with hash 428819724, now seen corresponding path program 1 times [2023-08-26 19:35:54,035 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-08-26 19:35:54,035 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1011551473] [2023-08-26 19:35:54,035 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-08-26 19:35:54,036 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-08-26 19:35:54,060 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-08-26 19:35:54,158 INFO L134 CoverageAnalysis]: Checked inductivity of 45 backedges. 10 proven. 0 refuted. 0 times theorem prover too weak. 35 trivial. 0 not checked. [2023-08-26 19:35:54,158 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-08-26 19:35:54,158 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1011551473] [2023-08-26 19:35:54,158 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1011551473] provided 1 perfect and 0 imperfect interpolant sequences [2023-08-26 19:35:54,158 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-08-26 19:35:54,158 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2023-08-26 19:35:54,159 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [524512397] [2023-08-26 19:35:54,159 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-08-26 19:35:54,159 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2023-08-26 19:35:54,159 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-08-26 19:35:54,159 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2023-08-26 19:35:54,159 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2023-08-26 19:35:54,162 INFO L471 CegarLoopForPetriNet]: Number of universal loopers: 643 out of 1849 [2023-08-26 19:35:54,170 INFO L103 encePairwiseOnDemand]: Start differencePairwiseOnDemand. First operand has 108 places, 95 transitions, 368 flow. Second operand has 5 states, 5 states have (on average 645.4) internal successors, (3227), 5 states have internal predecessors, (3227), 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 19:35:54,170 INFO L112 encePairwiseOnDemand]: Universal subtrahend loopers provided by user. [2023-08-26 19:35:54,170 INFO L113 encePairwiseOnDemand]: Number of universal subtrahend loopers: 643 of 1849 [2023-08-26 19:35:54,170 INFO L73 FinitePrefix]: Start finitePrefix. Operand will be constructed on-demand [2023-08-26 19:35:59,438 INFO L124 PetriNetUnfolderBase]: 36106/49363 cut-off events. [2023-08-26 19:35:59,438 INFO L125 PetriNetUnfolderBase]: For 12173/12173 co-relation queries the response was YES. [2023-08-26 19:35:59,552 INFO L83 FinitePrefix]: Finished finitePrefix Result has 112802 conditions, 49363 events. 36106/49363 cut-off events. For 12173/12173 co-relation queries the response was YES. Maximal size of possible extension queue 799. Compared 274150 event pairs, 28757 based on Foata normal form. 0/28233 useless extension candidates. Maximal degree in co-relation 112781. Up to 49349 conditions per place. [2023-08-26 19:35:59,672 INFO L140 encePairwiseOnDemand]: 1843/1849 looper letters, 88 selfloop transitions, 2 changer transitions 0/90 dead transitions. [2023-08-26 19:35:59,672 INFO L145 encePairwiseOnDemand]: Finished differencePairwiseOnDemand. Result has 107 places, 90 transitions, 532 flow [2023-08-26 19:35:59,672 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2023-08-26 19:35:59,673 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 4 states. [2023-08-26 19:35:59,676 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 4 states to 4 states and 2646 transitions. [2023-08-26 19:35:59,677 INFO L516 CegarLoopForPetriNet]: DFA transition density 0.3577609518658734 [2023-08-26 19:35:59,677 INFO L72 ComplementDD]: Start complementDD. Operand 4 states and 2646 transitions. [2023-08-26 19:35:59,677 INFO L73 IsDeterministic]: Start isDeterministic. Operand 4 states and 2646 transitions. [2023-08-26 19:35:59,678 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2023-08-26 19:35:59,678 INFO L117 ReachableStatesCopy]: Start reachableStatesCopy. Operand 4 states and 2646 transitions. [2023-08-26 19:35:59,681 INFO L343 DoubleDeckerVisitor]: Before removal of dead ends has 5 states, 4 states have (on average 661.5) internal successors, (2646), 4 states have internal predecessors, (2646), 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 19:35:59,685 INFO L131 ReachableStatesCopy]: Finished reachableStatesCopy Result has 5 states, 5 states have (on average 1849.0) internal successors, (9245), 5 states have internal predecessors, (9245), 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 19:35:59,685 INFO L81 ComplementDD]: Finished complementDD. Result has 5 states, 5 states have (on average 1849.0) internal successors, (9245), 5 states have internal predecessors, (9245), 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 19:35:59,686 INFO L175 Difference]: Start difference. First operand has 108 places, 95 transitions, 368 flow. Second operand 4 states and 2646 transitions. [2023-08-26 19:35:59,686 INFO L82 GeneralOperation]: Start removeRedundantFlow. Operand has 107 places, 90 transitions, 532 flow [2023-08-26 19:35:59,729 INFO L88 GeneralOperation]: Finished removeRedundantFlow, result has has 105 places, 90 transitions, 521 flow, removed 4 selfloop flow, removed 2 redundant places. [2023-08-26 19:35:59,731 INFO L231 Difference]: Finished difference. Result has 105 places, 90 transitions, 345 flow [2023-08-26 19:35:59,731 INFO L264 CegarLoopForPetriNet]: {PETRI_ALPHABET=1849, PETRI_DIFFERENCE_MINUEND_FLOW=341, PETRI_DIFFERENCE_MINUEND_PLACES=102, PETRI_DIFFERENCE_MINUEND_TRANSITIONS=90, PETRI_DIFFERENCE_SUBTRAHEND_LETTERS_WITH_MORE_CHANGERS_THAN_LOOPERS=2, PETRI_DIFFERENCE_SUBTRAHEND_LOOPER_ONLY_LETTERS=88, PETRI_DIFFERENCE_SUBTRAHEND_STATES=4, PETRI_FLOW=345, PETRI_PLACES=105, PETRI_TRANSITIONS=90} [2023-08-26 19:35:59,732 INFO L281 CegarLoopForPetriNet]: 112 programPoint places, -7 predicate places. [2023-08-26 19:35:59,732 INFO L495 AbstractCegarLoop]: Abstraction has has 105 places, 90 transitions, 345 flow [2023-08-26 19:35:59,732 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 645.4) internal successors, (3227), 5 states have internal predecessors, (3227), 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 19:35:59,732 INFO L200 CegarLoopForPetriNet]: Found error trace [2023-08-26 19:35:59,732 INFO L208 CegarLoopForPetriNet]: trace histogram [5, 5, 5, 1, 1, 1, 1, 1, 1, 1, 1] [2023-08-26 19:35:59,732 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable11 [2023-08-26 19:35:59,733 INFO L420 AbstractCegarLoop]: === Iteration 13 === Targeting ULTIMATE.startErr11REQUIRES_VIOLATIONMEMORY_DEREFERENCE === [thread1Err0REQUIRES_VIOLATIONMEMORY_DEREFERENCE, thread1Err1REQUIRES_VIOLATIONMEMORY_DEREFERENCE, thread1Err2REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 115 more)] === [2023-08-26 19:35:59,733 INFO L145 PredicateUnifier]: Initialized classic predicate unifier [2023-08-26 19:35:59,733 INFO L85 PathProgramCache]: Analyzing trace with hash 408273755, now seen corresponding path program 1 times [2023-08-26 19:35:59,733 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-08-26 19:35:59,733 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2034211419] [2023-08-26 19:35:59,733 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-08-26 19:35:59,733 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-08-26 19:35:59,769 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-08-26 19:36:00,276 INFO L134 CoverageAnalysis]: Checked inductivity of 45 backedges. 11 proven. 4 refuted. 0 times theorem prover too weak. 30 trivial. 0 not checked. [2023-08-26 19:36:00,276 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-08-26 19:36:00,276 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2034211419] [2023-08-26 19:36:00,276 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2034211419] provided 0 perfect and 1 imperfect interpolant sequences [2023-08-26 19:36:00,276 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [759186693] [2023-08-26 19:36:00,276 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-08-26 19:36:00,277 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-08-26 19:36:00,277 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-08-26 19:36:00,278 INFO L229 MonitoredProcess]: Starting monitored process 8 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-08-26 19:36:00,280 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2023-08-26 19:36:00,478 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-08-26 19:36:00,480 INFO L262 TraceCheckSpWp]: Trace formula consists of 385 conjuncts, 11 conjunts are in the unsatisfiable core [2023-08-26 19:36:00,482 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-08-26 19:36:00,490 INFO L190 IndexEqualityManager]: detected not equals via solver [2023-08-26 19:36:00,515 INFO L322 Elim1Store]: treesize reduction 62, result has 31.1 percent of original size [2023-08-26 19:36:00,515 INFO L351 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 2 case distinctions, treesize of input 15 treesize of output 38 [2023-08-26 19:36:00,556 INFO L190 IndexEqualityManager]: detected not equals via solver [2023-08-26 19:36:00,556 INFO L351 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 12 treesize of output 14 [2023-08-26 19:36:00,588 INFO L190 IndexEqualityManager]: detected not equals via solver [2023-08-26 19:36:00,589 INFO L351 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 12 treesize of output 14 [2023-08-26 19:36:00,616 INFO L134 CoverageAnalysis]: Checked inductivity of 45 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2023-08-26 19:36:00,616 INFO L323 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2023-08-26 19:36:00,616 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [759186693] provided 1 perfect and 0 imperfect interpolant sequences [2023-08-26 19:36:00,616 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2023-08-26 19:36:00,616 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [8] total 9 [2023-08-26 19:36:00,616 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [878017132] [2023-08-26 19:36:00,616 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-08-26 19:36:00,617 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2023-08-26 19:36:00,617 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-08-26 19:36:00,617 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2023-08-26 19:36:00,617 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=50, Invalid=60, Unknown=0, NotChecked=0, Total=110 [2023-08-26 19:36:00,619 INFO L471 CegarLoopForPetriNet]: Number of universal loopers: 663 out of 1849 [2023-08-26 19:36:00,620 INFO L103 encePairwiseOnDemand]: Start differencePairwiseOnDemand. First operand has 105 places, 90 transitions, 345 flow. Second operand has 4 states, 4 states have (on average 665.75) internal successors, (2663), 4 states have internal predecessors, (2663), 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 19:36:00,620 INFO L112 encePairwiseOnDemand]: Universal subtrahend loopers provided by user. [2023-08-26 19:36:00,621 INFO L113 encePairwiseOnDemand]: Number of universal subtrahend loopers: 663 of 1849 [2023-08-26 19:36:00,621 INFO L73 FinitePrefix]: Start finitePrefix. Operand will be constructed on-demand [2023-08-26 19:36:05,882 INFO L124 PetriNetUnfolderBase]: 34691/47316 cut-off events. [2023-08-26 19:36:05,882 INFO L125 PetriNetUnfolderBase]: For 10419/10419 co-relation queries the response was YES. [2023-08-26 19:36:06,033 INFO L83 FinitePrefix]: Finished finitePrefix Result has 107678 conditions, 47316 events. 34691/47316 cut-off events. For 10419/10419 co-relation queries the response was YES. Maximal size of possible extension queue 770. Compared 259919 event pairs, 27571 based on Foata normal form. 0/27331 useless extension candidates. Maximal degree in co-relation 107656. Up to 47316 conditions per place. [2023-08-26 19:36:06,156 INFO L140 encePairwiseOnDemand]: 1846/1849 looper letters, 87 selfloop transitions, 1 changer transitions 0/88 dead transitions. [2023-08-26 19:36:06,157 INFO L145 encePairwiseOnDemand]: Finished differencePairwiseOnDemand. Result has 105 places, 88 transitions, 517 flow [2023-08-26 19:36:06,157 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2023-08-26 19:36:06,157 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 3 states. [2023-08-26 19:36:06,159 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 3 states to 3 states and 2059 transitions. [2023-08-26 19:36:06,160 INFO L516 CegarLoopForPetriNet]: DFA transition density 0.37119163511808184 [2023-08-26 19:36:06,160 INFO L72 ComplementDD]: Start complementDD. Operand 3 states and 2059 transitions. [2023-08-26 19:36:06,160 INFO L73 IsDeterministic]: Start isDeterministic. Operand 3 states and 2059 transitions. [2023-08-26 19:36:06,160 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2023-08-26 19:36:06,160 INFO L117 ReachableStatesCopy]: Start reachableStatesCopy. Operand 3 states and 2059 transitions. [2023-08-26 19:36:06,162 INFO L343 DoubleDeckerVisitor]: Before removal of dead ends has 4 states, 3 states have (on average 686.3333333333334) internal successors, (2059), 3 states have internal predecessors, (2059), 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 19:36:06,164 INFO L131 ReachableStatesCopy]: Finished reachableStatesCopy Result has 4 states, 4 states have (on average 1849.0) internal successors, (7396), 4 states have internal predecessors, (7396), 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 19:36:06,164 INFO L81 ComplementDD]: Finished complementDD. Result has 4 states, 4 states have (on average 1849.0) internal successors, (7396), 4 states have internal predecessors, (7396), 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 19:36:06,165 INFO L175 Difference]: Start difference. First operand has 105 places, 90 transitions, 345 flow. Second operand 3 states and 2059 transitions. [2023-08-26 19:36:06,165 INFO L82 GeneralOperation]: Start removeRedundantFlow. Operand has 105 places, 88 transitions, 517 flow [2023-08-26 19:36:06,209 INFO L88 GeneralOperation]: Finished removeRedundantFlow, result has has 103 places, 88 transitions, 514 flow, removed 0 selfloop flow, removed 2 redundant places. [2023-08-26 19:36:06,211 INFO L231 Difference]: Finished difference. Result has 103 places, 88 transitions, 340 flow [2023-08-26 19:36:06,211 INFO L264 CegarLoopForPetriNet]: {PETRI_ALPHABET=1849, PETRI_DIFFERENCE_MINUEND_FLOW=338, PETRI_DIFFERENCE_MINUEND_PLACES=101, PETRI_DIFFERENCE_MINUEND_TRANSITIONS=88, PETRI_DIFFERENCE_SUBTRAHEND_LETTERS_WITH_MORE_CHANGERS_THAN_LOOPERS=1, PETRI_DIFFERENCE_SUBTRAHEND_LOOPER_ONLY_LETTERS=87, PETRI_DIFFERENCE_SUBTRAHEND_STATES=3, PETRI_FLOW=340, PETRI_PLACES=103, PETRI_TRANSITIONS=88} [2023-08-26 19:36:06,211 INFO L281 CegarLoopForPetriNet]: 112 programPoint places, -9 predicate places. [2023-08-26 19:36:06,212 INFO L495 AbstractCegarLoop]: Abstraction has has 103 places, 88 transitions, 340 flow [2023-08-26 19:36:06,212 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 665.75) internal successors, (2663), 4 states have internal predecessors, (2663), 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 19:36:06,212 INFO L200 CegarLoopForPetriNet]: Found error trace [2023-08-26 19:36:06,212 INFO L208 CegarLoopForPetriNet]: trace histogram [5, 5, 5, 1, 1, 1, 1, 1, 1, 1, 1] [2023-08-26 19:36:06,218 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Ended with exit code 0 [2023-08-26 19:36:06,417 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable12,8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-08-26 19:36:06,418 INFO L420 AbstractCegarLoop]: === Iteration 14 === Targeting ULTIMATE.startErr10REQUIRES_VIOLATIONMEMORY_DEREFERENCE === [thread1Err0REQUIRES_VIOLATIONMEMORY_DEREFERENCE, thread1Err1REQUIRES_VIOLATIONMEMORY_DEREFERENCE, thread1Err2REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 115 more)] === [2023-08-26 19:36:06,418 INFO L145 PredicateUnifier]: Initialized classic predicate unifier [2023-08-26 19:36:06,418 INFO L85 PathProgramCache]: Analyzing trace with hash 408273756, now seen corresponding path program 1 times [2023-08-26 19:36:06,418 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-08-26 19:36:06,418 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1197646365] [2023-08-26 19:36:06,419 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-08-26 19:36:06,419 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-08-26 19:36:06,463 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-08-26 19:36:06,682 INFO L134 CoverageAnalysis]: Checked inductivity of 45 backedges. 5 proven. 0 refuted. 0 times theorem prover too weak. 40 trivial. 0 not checked. [2023-08-26 19:36:06,682 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-08-26 19:36:06,682 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1197646365] [2023-08-26 19:36:06,682 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1197646365] provided 1 perfect and 0 imperfect interpolant sequences [2023-08-26 19:36:06,682 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-08-26 19:36:06,683 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2023-08-26 19:36:06,683 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1163297499] [2023-08-26 19:36:06,683 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-08-26 19:36:06,683 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2023-08-26 19:36:06,683 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-08-26 19:36:06,683 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2023-08-26 19:36:06,684 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=15, Invalid=15, Unknown=0, NotChecked=0, Total=30 [2023-08-26 19:36:06,686 INFO L471 CegarLoopForPetriNet]: Number of universal loopers: 648 out of 1849 [2023-08-26 19:36:06,688 INFO L103 encePairwiseOnDemand]: Start differencePairwiseOnDemand. First operand has 103 places, 88 transitions, 340 flow. Second operand has 6 states, 6 states have (on average 650.0) internal successors, (3900), 6 states have internal predecessors, (3900), 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 19:36:06,688 INFO L112 encePairwiseOnDemand]: Universal subtrahend loopers provided by user. [2023-08-26 19:36:06,688 INFO L113 encePairwiseOnDemand]: Number of universal subtrahend loopers: 648 of 1849 [2023-08-26 19:36:06,688 INFO L73 FinitePrefix]: Start finitePrefix. Operand will be constructed on-demand [2023-08-26 19:36:12,330 INFO L124 PetriNetUnfolderBase]: 33276/45269 cut-off events. [2023-08-26 19:36:12,330 INFO L125 PetriNetUnfolderBase]: For 9885/9885 co-relation queries the response was YES. [2023-08-26 19:36:12,467 INFO L83 FinitePrefix]: Finished finitePrefix Result has 102938 conditions, 45269 events. 33276/45269 cut-off events. For 9885/9885 co-relation queries the response was YES. Maximal size of possible extension queue 733. Compared 245354 event pairs, 26385 based on Foata normal form. 0/26429 useless extension candidates. Maximal degree in co-relation 102916. Up to 45269 conditions per place. [2023-08-26 19:36:12,578 INFO L140 encePairwiseOnDemand]: 1846/1849 looper letters, 85 selfloop transitions, 1 changer transitions 0/86 dead transitions. [2023-08-26 19:36:12,579 INFO L145 encePairwiseOnDemand]: Finished differencePairwiseOnDemand. Result has 103 places, 86 transitions, 508 flow [2023-08-26 19:36:12,579 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2023-08-26 19:36:12,579 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 3 states. [2023-08-26 19:36:12,581 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 3 states to 3 states and 2012 transitions. [2023-08-26 19:36:12,582 INFO L516 CegarLoopForPetriNet]: DFA transition density 0.36271858662340006 [2023-08-26 19:36:12,582 INFO L72 ComplementDD]: Start complementDD. Operand 3 states and 2012 transitions. [2023-08-26 19:36:12,582 INFO L73 IsDeterministic]: Start isDeterministic. Operand 3 states and 2012 transitions. [2023-08-26 19:36:12,582 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2023-08-26 19:36:12,582 INFO L117 ReachableStatesCopy]: Start reachableStatesCopy. Operand 3 states and 2012 transitions. [2023-08-26 19:36:12,584 INFO L343 DoubleDeckerVisitor]: Before removal of dead ends has 4 states, 3 states have (on average 670.6666666666666) internal successors, (2012), 3 states have internal predecessors, (2012), 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 19:36:12,586 INFO L131 ReachableStatesCopy]: Finished reachableStatesCopy Result has 4 states, 4 states have (on average 1849.0) internal successors, (7396), 4 states have internal predecessors, (7396), 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 19:36:12,587 INFO L81 ComplementDD]: Finished complementDD. Result has 4 states, 4 states have (on average 1849.0) internal successors, (7396), 4 states have internal predecessors, (7396), 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 19:36:12,587 INFO L175 Difference]: Start difference. First operand has 103 places, 88 transitions, 340 flow. Second operand 3 states and 2012 transitions. [2023-08-26 19:36:12,587 INFO L82 GeneralOperation]: Start removeRedundantFlow. Operand has 103 places, 86 transitions, 508 flow [2023-08-26 19:36:12,623 INFO L88 GeneralOperation]: Finished removeRedundantFlow, result has has 102 places, 86 transitions, 507 flow, removed 0 selfloop flow, removed 1 redundant places. [2023-08-26 19:36:12,624 INFO L231 Difference]: Finished difference. Result has 102 places, 86 transitions, 337 flow [2023-08-26 19:36:12,624 INFO L264 CegarLoopForPetriNet]: {PETRI_ALPHABET=1849, PETRI_DIFFERENCE_MINUEND_FLOW=335, PETRI_DIFFERENCE_MINUEND_PLACES=100, PETRI_DIFFERENCE_MINUEND_TRANSITIONS=86, PETRI_DIFFERENCE_SUBTRAHEND_LETTERS_WITH_MORE_CHANGERS_THAN_LOOPERS=1, PETRI_DIFFERENCE_SUBTRAHEND_LOOPER_ONLY_LETTERS=85, PETRI_DIFFERENCE_SUBTRAHEND_STATES=3, PETRI_FLOW=337, PETRI_PLACES=102, PETRI_TRANSITIONS=86} [2023-08-26 19:36:12,625 INFO L281 CegarLoopForPetriNet]: 112 programPoint places, -10 predicate places. [2023-08-26 19:36:12,625 INFO L495 AbstractCegarLoop]: Abstraction has has 102 places, 86 transitions, 337 flow [2023-08-26 19:36:12,625 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 650.0) internal successors, (3900), 6 states have internal predecessors, (3900), 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 19:36:12,625 INFO L200 CegarLoopForPetriNet]: Found error trace [2023-08-26 19:36:12,625 INFO L208 CegarLoopForPetriNet]: trace histogram [5, 5, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-08-26 19:36:12,626 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable13 [2023-08-26 19:36:12,626 INFO L420 AbstractCegarLoop]: === Iteration 15 === Targeting thread2Err3REQUIRES_VIOLATIONMEMORY_DEREFERENCE === [thread1Err0REQUIRES_VIOLATIONMEMORY_DEREFERENCE, thread1Err1REQUIRES_VIOLATIONMEMORY_DEREFERENCE, thread1Err2REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 115 more)] === [2023-08-26 19:36:12,626 INFO L145 PredicateUnifier]: Initialized classic predicate unifier [2023-08-26 19:36:12,626 INFO L85 PathProgramCache]: Analyzing trace with hash -228406535, now seen corresponding path program 1 times [2023-08-26 19:36:12,626 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-08-26 19:36:12,626 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [634862437] [2023-08-26 19:36:12,626 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-08-26 19:36:12,626 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-08-26 19:36:12,652 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-08-26 19:36:12,942 INFO L134 CoverageAnalysis]: Checked inductivity of 45 backedges. 6 proven. 9 refuted. 0 times theorem prover too weak. 30 trivial. 0 not checked. [2023-08-26 19:36:12,942 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-08-26 19:36:12,942 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [634862437] [2023-08-26 19:36:12,942 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [634862437] provided 0 perfect and 1 imperfect interpolant sequences [2023-08-26 19:36:12,942 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1097989400] [2023-08-26 19:36:12,942 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-08-26 19:36:12,942 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-08-26 19:36:12,942 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-08-26 19:36:12,943 INFO L229 MonitoredProcess]: Starting monitored process 9 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-08-26 19:36:12,947 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2023-08-26 19:36:13,155 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-08-26 19:36:13,158 INFO L262 TraceCheckSpWp]: Trace formula consists of 405 conjuncts, 19 conjunts are in the unsatisfiable core [2023-08-26 19:36:13,166 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-08-26 19:36:13,169 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 19:36:13,295 INFO L134 CoverageAnalysis]: Checked inductivity of 45 backedges. 10 proven. 5 refuted. 0 times theorem prover too weak. 30 trivial. 0 not checked. [2023-08-26 19:36:13,295 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-08-26 19:36:13,478 INFO L134 CoverageAnalysis]: Checked inductivity of 45 backedges. 15 proven. 0 refuted. 0 times theorem prover too weak. 30 trivial. 0 not checked. [2023-08-26 19:36:13,479 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1097989400] provided 1 perfect and 1 imperfect interpolant sequences [2023-08-26 19:36:13,479 INFO L185 FreeRefinementEngine]: Found 1 perfect and 2 imperfect interpolant sequences. [2023-08-26 19:36:13,479 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [9] imperfect sequences [9, 9] total 25 [2023-08-26 19:36:13,479 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [221439071] [2023-08-26 19:36:13,479 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-08-26 19:36:13,479 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2023-08-26 19:36:13,480 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-08-26 19:36:13,480 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2023-08-26 19:36:13,480 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=169, Invalid=481, Unknown=0, NotChecked=0, Total=650 [2023-08-26 19:36:13,484 INFO L471 CegarLoopForPetriNet]: Number of universal loopers: 620 out of 1849 [2023-08-26 19:36:13,486 INFO L103 encePairwiseOnDemand]: Start differencePairwiseOnDemand. First operand has 102 places, 86 transitions, 337 flow. Second operand has 10 states, 10 states have (on average 621.6) internal successors, (6216), 10 states have internal predecessors, (6216), 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 19:36:13,486 INFO L112 encePairwiseOnDemand]: Universal subtrahend loopers provided by user. [2023-08-26 19:36:13,486 INFO L113 encePairwiseOnDemand]: Number of universal subtrahend loopers: 620 of 1849 [2023-08-26 19:36:13,486 INFO L73 FinitePrefix]: Start finitePrefix. Operand will be constructed on-demand [2023-08-26 19:36:22,767 INFO L124 PetriNetUnfolderBase]: 59268/80675 cut-off events. [2023-08-26 19:36:22,767 INFO L125 PetriNetUnfolderBase]: For 26433/26433 co-relation queries the response was YES. [2023-08-26 19:36:23,067 INFO L83 FinitePrefix]: Finished finitePrefix Result has 183411 conditions, 80675 events. 59268/80675 cut-off events. For 26433/26433 co-relation queries the response was YES. Maximal size of possible extension queue 1140. Compared 465866 event pairs, 26385 based on Foata normal form. 0/47747 useless extension candidates. Maximal degree in co-relation 183388. Up to 44000 conditions per place. [2023-08-26 19:36:23,282 INFO L140 encePairwiseOnDemand]: 1840/1849 looper letters, 136 selfloop transitions, 6 changer transitions 0/142 dead transitions. [2023-08-26 19:36:23,282 INFO L145 encePairwiseOnDemand]: Finished differencePairwiseOnDemand. Result has 106 places, 142 transitions, 799 flow [2023-08-26 19:36:23,282 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2023-08-26 19:36:23,283 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 5 states. [2023-08-26 19:36:23,286 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 3220 transitions. [2023-08-26 19:36:23,286 INFO L516 CegarLoopForPetriNet]: DFA transition density 0.3482963764196863 [2023-08-26 19:36:23,286 INFO L72 ComplementDD]: Start complementDD. Operand 5 states and 3220 transitions. [2023-08-26 19:36:23,286 INFO L73 IsDeterministic]: Start isDeterministic. Operand 5 states and 3220 transitions. [2023-08-26 19:36:23,287 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2023-08-26 19:36:23,287 INFO L117 ReachableStatesCopy]: Start reachableStatesCopy. Operand 5 states and 3220 transitions. [2023-08-26 19:36:23,290 INFO L343 DoubleDeckerVisitor]: Before removal of dead ends has 6 states, 5 states have (on average 644.0) internal successors, (3220), 5 states have internal predecessors, (3220), 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 19:36:23,296 INFO L131 ReachableStatesCopy]: Finished reachableStatesCopy Result has 6 states, 6 states have (on average 1849.0) internal successors, (11094), 6 states have internal predecessors, (11094), 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 19:36:23,297 INFO L81 ComplementDD]: Finished complementDD. Result has 6 states, 6 states have (on average 1849.0) internal successors, (11094), 6 states have internal predecessors, (11094), 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 19:36:23,297 INFO L175 Difference]: Start difference. First operand has 102 places, 86 transitions, 337 flow. Second operand 5 states and 3220 transitions. [2023-08-26 19:36:23,297 INFO L82 GeneralOperation]: Start removeRedundantFlow. Operand has 106 places, 142 transitions, 799 flow [2023-08-26 19:36:23,321 INFO L88 GeneralOperation]: Finished removeRedundantFlow, result has has 105 places, 142 transitions, 798 flow, removed 0 selfloop flow, removed 1 redundant places. [2023-08-26 19:36:23,322 INFO L231 Difference]: Finished difference. Result has 107 places, 89 transitions, 375 flow [2023-08-26 19:36:23,322 INFO L264 CegarLoopForPetriNet]: {PETRI_ALPHABET=1849, PETRI_DIFFERENCE_MINUEND_FLOW=336, PETRI_DIFFERENCE_MINUEND_PLACES=101, PETRI_DIFFERENCE_MINUEND_TRANSITIONS=86, PETRI_DIFFERENCE_SUBTRAHEND_LETTERS_WITH_MORE_CHANGERS_THAN_LOOPERS=3, PETRI_DIFFERENCE_SUBTRAHEND_LOOPER_ONLY_LETTERS=80, PETRI_DIFFERENCE_SUBTRAHEND_STATES=5, PETRI_FLOW=375, PETRI_PLACES=107, PETRI_TRANSITIONS=89} [2023-08-26 19:36:23,323 INFO L281 CegarLoopForPetriNet]: 112 programPoint places, -5 predicate places. [2023-08-26 19:36:23,323 INFO L495 AbstractCegarLoop]: Abstraction has has 107 places, 89 transitions, 375 flow [2023-08-26 19:36:23,324 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 10 states have (on average 621.6) internal successors, (6216), 10 states have internal predecessors, (6216), 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 19:36:23,324 INFO L200 CegarLoopForPetriNet]: Found error trace [2023-08-26 19:36:23,324 INFO L208 CegarLoopForPetriNet]: trace histogram [5, 5, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-08-26 19:36:23,337 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Forceful destruction successful, exit code 0 [2023-08-26 19:36:23,530 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 9 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable14 [2023-08-26 19:36:23,530 INFO L420 AbstractCegarLoop]: === Iteration 16 === Targeting thread2Err2REQUIRES_VIOLATIONMEMORY_DEREFERENCE === [thread1Err0REQUIRES_VIOLATIONMEMORY_DEREFERENCE, thread1Err1REQUIRES_VIOLATIONMEMORY_DEREFERENCE, thread1Err2REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 115 more)] === [2023-08-26 19:36:23,531 INFO L145 PredicateUnifier]: Initialized classic predicate unifier [2023-08-26 19:36:23,531 INFO L85 PathProgramCache]: Analyzing trace with hash -228406536, now seen corresponding path program 1 times [2023-08-26 19:36:23,531 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-08-26 19:36:23,531 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2036693617] [2023-08-26 19:36:23,531 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-08-26 19:36:23,531 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-08-26 19:36:23,553 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-08-26 19:36:23,611 INFO L134 CoverageAnalysis]: Checked inductivity of 45 backedges. 5 proven. 0 refuted. 0 times theorem prover too weak. 40 trivial. 0 not checked. [2023-08-26 19:36:23,611 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-08-26 19:36:23,611 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2036693617] [2023-08-26 19:36:23,611 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2036693617] provided 1 perfect and 0 imperfect interpolant sequences [2023-08-26 19:36:23,612 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-08-26 19:36:23,612 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2023-08-26 19:36:23,613 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [981382993] [2023-08-26 19:36:23,613 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-08-26 19:36:23,614 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2023-08-26 19:36:23,615 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-08-26 19:36:23,615 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2023-08-26 19:36:23,615 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2023-08-26 19:36:23,617 INFO L471 CegarLoopForPetriNet]: Number of universal loopers: 643 out of 1849 [2023-08-26 19:36:23,618 INFO L103 encePairwiseOnDemand]: Start differencePairwiseOnDemand. First operand has 107 places, 89 transitions, 375 flow. Second operand has 4 states, 4 states have (on average 646.25) internal successors, (2585), 4 states have internal predecessors, (2585), 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 19:36:23,618 INFO L112 encePairwiseOnDemand]: Universal subtrahend loopers provided by user. [2023-08-26 19:36:23,618 INFO L113 encePairwiseOnDemand]: Number of universal subtrahend loopers: 643 of 1849 [2023-08-26 19:36:23,618 INFO L73 FinitePrefix]: Start finitePrefix. Operand will be constructed on-demand [2023-08-26 19:36:30,058 INFO L124 PetriNetUnfolderBase]: 38588/52307 cut-off events. [2023-08-26 19:36:30,058 INFO L125 PetriNetUnfolderBase]: For 18453/18453 co-relation queries the response was YES. [2023-08-26 19:36:30,252 INFO L83 FinitePrefix]: Finished finitePrefix Result has 125783 conditions, 52307 events. 38588/52307 cut-off events. For 18453/18453 co-relation queries the response was YES. Maximal size of possible extension queue 733. Compared 280754 event pairs, 29767 based on Foata normal form. 0/35063 useless extension candidates. Maximal degree in co-relation 125757. Up to 52286 conditions per place. [2023-08-26 19:36:30,389 INFO L140 encePairwiseOnDemand]: 1842/1849 looper letters, 82 selfloop transitions, 2 changer transitions 0/84 dead transitions. [2023-08-26 19:36:30,389 INFO L145 encePairwiseOnDemand]: Finished differencePairwiseOnDemand. Result has 105 places, 84 transitions, 533 flow [2023-08-26 19:36:30,390 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2023-08-26 19:36:30,390 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 4 states. [2023-08-26 19:36:30,392 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 4 states to 4 states and 2638 transitions. [2023-08-26 19:36:30,393 INFO L516 CegarLoopForPetriNet]: DFA transition density 0.3566792861005949 [2023-08-26 19:36:30,393 INFO L72 ComplementDD]: Start complementDD. Operand 4 states and 2638 transitions. [2023-08-26 19:36:30,393 INFO L73 IsDeterministic]: Start isDeterministic. Operand 4 states and 2638 transitions. [2023-08-26 19:36:30,394 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2023-08-26 19:36:30,394 INFO L117 ReachableStatesCopy]: Start reachableStatesCopy. Operand 4 states and 2638 transitions. [2023-08-26 19:36:30,396 INFO L343 DoubleDeckerVisitor]: Before removal of dead ends has 5 states, 4 states have (on average 659.5) internal successors, (2638), 4 states have internal predecessors, (2638), 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 19:36:30,401 INFO L131 ReachableStatesCopy]: Finished reachableStatesCopy Result has 5 states, 5 states have (on average 1849.0) internal successors, (9245), 5 states have internal predecessors, (9245), 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 19:36:30,402 INFO L81 ComplementDD]: Finished complementDD. Result has 5 states, 5 states have (on average 1849.0) internal successors, (9245), 5 states have internal predecessors, (9245), 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 19:36:30,402 INFO L175 Difference]: Start difference. First operand has 107 places, 89 transitions, 375 flow. Second operand 4 states and 2638 transitions. [2023-08-26 19:36:30,402 INFO L82 GeneralOperation]: Start removeRedundantFlow. Operand has 105 places, 84 transitions, 533 flow [2023-08-26 19:36:30,437 INFO L88 GeneralOperation]: Finished removeRedundantFlow, result has has 103 places, 84 transitions, 530 flow, removed 0 selfloop flow, removed 2 redundant places. [2023-08-26 19:36:30,438 INFO L231 Difference]: Finished difference. Result has 103 places, 84 transitions, 366 flow [2023-08-26 19:36:30,438 INFO L264 CegarLoopForPetriNet]: {PETRI_ALPHABET=1849, PETRI_DIFFERENCE_MINUEND_FLOW=362, PETRI_DIFFERENCE_MINUEND_PLACES=100, PETRI_DIFFERENCE_MINUEND_TRANSITIONS=84, PETRI_DIFFERENCE_SUBTRAHEND_LETTERS_WITH_MORE_CHANGERS_THAN_LOOPERS=2, PETRI_DIFFERENCE_SUBTRAHEND_LOOPER_ONLY_LETTERS=82, PETRI_DIFFERENCE_SUBTRAHEND_STATES=4, PETRI_FLOW=366, PETRI_PLACES=103, PETRI_TRANSITIONS=84} [2023-08-26 19:36:30,438 INFO L281 CegarLoopForPetriNet]: 112 programPoint places, -9 predicate places. [2023-08-26 19:36:30,439 INFO L495 AbstractCegarLoop]: Abstraction has has 103 places, 84 transitions, 366 flow [2023-08-26 19:36:30,439 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 646.25) internal successors, (2585), 4 states have internal predecessors, (2585), 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 19:36:30,439 INFO L200 CegarLoopForPetriNet]: Found error trace [2023-08-26 19:36:30,439 INFO L208 CegarLoopForPetriNet]: trace histogram [5, 5, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-08-26 19:36:30,439 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable15 [2023-08-26 19:36:30,439 INFO L420 AbstractCegarLoop]: === Iteration 17 === Targeting thread2Err1REQUIRES_VIOLATIONMEMORY_DEREFERENCE === [thread1Err0REQUIRES_VIOLATIONMEMORY_DEREFERENCE, thread1Err1REQUIRES_VIOLATIONMEMORY_DEREFERENCE, thread1Err2REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 115 more)] === [2023-08-26 19:36:30,440 INFO L145 PredicateUnifier]: Initialized classic predicate unifier [2023-08-26 19:36:30,440 INFO L85 PathProgramCache]: Analyzing trace with hash -228406538, now seen corresponding path program 1 times [2023-08-26 19:36:30,440 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-08-26 19:36:30,440 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1414658228] [2023-08-26 19:36:30,440 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-08-26 19:36:30,440 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-08-26 19:36:30,468 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-08-26 19:36:31,065 INFO L134 CoverageAnalysis]: Checked inductivity of 45 backedges. 17 proven. 13 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2023-08-26 19:36:31,066 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-08-26 19:36:31,066 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1414658228] [2023-08-26 19:36:31,066 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1414658228] provided 0 perfect and 1 imperfect interpolant sequences [2023-08-26 19:36:31,066 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2135387598] [2023-08-26 19:36:31,066 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-08-26 19:36:31,066 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-08-26 19:36:31,066 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-08-26 19:36:31,067 INFO L229 MonitoredProcess]: Starting monitored process 10 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-08-26 19:36:31,069 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Waiting until timeout for monitored process [2023-08-26 19:36:31,275 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-08-26 19:36:31,278 INFO L262 TraceCheckSpWp]: Trace formula consists of 397 conjuncts, 35 conjunts are in the unsatisfiable core [2023-08-26 19:36:31,281 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-08-26 19:36:31,339 INFO L322 Elim1Store]: treesize reduction 72, result has 33.9 percent of original size [2023-08-26 19:36:31,340 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 3 case distinctions, treesize of input 15 treesize of output 42 [2023-08-26 19:36:31,384 INFO L322 Elim1Store]: treesize reduction 72, result has 33.9 percent of original size [2023-08-26 19:36:31,384 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 3 case distinctions, treesize of input 15 treesize of output 42 [2023-08-26 19:36:31,550 INFO L190 IndexEqualityManager]: detected not equals via solver [2023-08-26 19:36:31,550 INFO L351 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 12 treesize of output 14 [2023-08-26 19:36:31,557 INFO L322 Elim1Store]: treesize reduction 4, result has 50.0 percent of original size [2023-08-26 19:36:31,557 INFO L351 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 11 treesize of output 11 [2023-08-26 19:36:31,603 INFO L322 Elim1Store]: treesize reduction 15, result has 25.0 percent of original size [2023-08-26 19:36:31,604 INFO L351 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 1 case distinctions, treesize of input 12 treesize of output 14 [2023-08-26 19:36:31,688 INFO L134 CoverageAnalysis]: Checked inductivity of 45 backedges. 6 proven. 9 refuted. 0 times theorem prover too weak. 30 trivial. 0 not checked. [2023-08-26 19:36:31,689 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-08-26 19:36:37,868 WARN L234 SmtUtils]: Spent 6.01s on a formula simplification that was a NOOP. DAG size: 25 (called from [L 376] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2023-08-26 19:36:38,139 INFO L134 CoverageAnalysis]: Checked inductivity of 45 backedges. 15 proven. 0 refuted. 0 times theorem prover too weak. 30 trivial. 0 not checked. [2023-08-26 19:36:38,139 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2135387598] provided 1 perfect and 1 imperfect interpolant sequences [2023-08-26 19:36:38,139 INFO L185 FreeRefinementEngine]: Found 1 perfect and 2 imperfect interpolant sequences. [2023-08-26 19:36:38,139 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [9] imperfect sequences [14, 8] total 31 [2023-08-26 19:36:38,139 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1391124071] [2023-08-26 19:36:38,139 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-08-26 19:36:38,139 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 11 states [2023-08-26 19:36:38,140 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-08-26 19:36:38,140 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2023-08-26 19:36:38,140 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=190, Invalid=866, Unknown=0, NotChecked=0, Total=1056 [2023-08-26 19:36:38,144 INFO L471 CegarLoopForPetriNet]: Number of universal loopers: 594 out of 1849 [2023-08-26 19:36:38,145 INFO L103 encePairwiseOnDemand]: Start differencePairwiseOnDemand. First operand has 103 places, 84 transitions, 366 flow. Second operand has 11 states, 11 states have (on average 595.4545454545455) internal successors, (6550), 11 states have internal predecessors, (6550), 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 19:36:38,145 INFO L112 encePairwiseOnDemand]: Universal subtrahend loopers provided by user. [2023-08-26 19:36:38,146 INFO L113 encePairwiseOnDemand]: Number of universal subtrahend loopers: 594 of 1849 [2023-08-26 19:36:38,146 INFO L73 FinitePrefix]: Start finitePrefix. Operand will be constructed on-demand [2023-08-26 19:36:43,504 INFO L124 PetriNetUnfolderBase]: 32158/43457 cut-off events. [2023-08-26 19:36:43,504 INFO L125 PetriNetUnfolderBase]: For 19025/19025 co-relation queries the response was YES. [2023-08-26 19:36:43,653 INFO L83 FinitePrefix]: Finished finitePrefix Result has 105544 conditions, 43457 events. 32158/43457 cut-off events. For 19025/19025 co-relation queries the response was YES. Maximal size of possible extension queue 598. Compared 228004 event pairs, 3913 based on Foata normal form. 0/30663 useless extension candidates. Maximal degree in co-relation 105518. Up to 35650 conditions per place. [2023-08-26 19:36:43,758 INFO L140 encePairwiseOnDemand]: 1839/1849 looper letters, 114 selfloop transitions, 8 changer transitions 0/122 dead transitions. [2023-08-26 19:36:43,758 INFO L145 encePairwiseOnDemand]: Finished differencePairwiseOnDemand. Result has 105 places, 122 transitions, 752 flow [2023-08-26 19:36:43,759 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2023-08-26 19:36:43,759 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 5 states. [2023-08-26 19:36:43,763 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 3067 transitions. [2023-08-26 19:36:43,764 INFO L516 CegarLoopForPetriNet]: DFA transition density 0.33174689021092485 [2023-08-26 19:36:43,764 INFO L72 ComplementDD]: Start complementDD. Operand 5 states and 3067 transitions. [2023-08-26 19:36:43,764 INFO L73 IsDeterministic]: Start isDeterministic. Operand 5 states and 3067 transitions. [2023-08-26 19:36:43,765 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2023-08-26 19:36:43,765 INFO L117 ReachableStatesCopy]: Start reachableStatesCopy. Operand 5 states and 3067 transitions. [2023-08-26 19:36:43,767 INFO L343 DoubleDeckerVisitor]: Before removal of dead ends has 6 states, 5 states have (on average 613.4) internal successors, (3067), 5 states have internal predecessors, (3067), 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 19:36:43,771 INFO L131 ReachableStatesCopy]: Finished reachableStatesCopy Result has 6 states, 6 states have (on average 1849.0) internal successors, (11094), 6 states have internal predecessors, (11094), 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 19:36:43,772 INFO L81 ComplementDD]: Finished complementDD. Result has 6 states, 6 states have (on average 1849.0) internal successors, (11094), 6 states have internal predecessors, (11094), 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 19:36:43,772 INFO L175 Difference]: Start difference. First operand has 103 places, 84 transitions, 366 flow. Second operand 5 states and 3067 transitions. [2023-08-26 19:36:43,772 INFO L82 GeneralOperation]: Start removeRedundantFlow. Operand has 105 places, 122 transitions, 752 flow [2023-08-26 19:36:43,787 INFO L88 GeneralOperation]: Finished removeRedundantFlow, result has has 103 places, 122 transitions, 749 flow, removed 0 selfloop flow, removed 2 redundant places. [2023-08-26 19:36:43,788 INFO L231 Difference]: Finished difference. Result has 105 places, 84 transitions, 398 flow [2023-08-26 19:36:43,788 INFO L264 CegarLoopForPetriNet]: {PETRI_ALPHABET=1849, PETRI_DIFFERENCE_MINUEND_FLOW=359, PETRI_DIFFERENCE_MINUEND_PLACES=99, PETRI_DIFFERENCE_MINUEND_TRANSITIONS=82, PETRI_DIFFERENCE_SUBTRAHEND_LETTERS_WITH_MORE_CHANGERS_THAN_LOOPERS=6, PETRI_DIFFERENCE_SUBTRAHEND_LOOPER_ONLY_LETTERS=74, PETRI_DIFFERENCE_SUBTRAHEND_STATES=5, PETRI_FLOW=398, PETRI_PLACES=105, PETRI_TRANSITIONS=84} [2023-08-26 19:36:43,788 INFO L281 CegarLoopForPetriNet]: 112 programPoint places, -7 predicate places. [2023-08-26 19:36:43,788 INFO L495 AbstractCegarLoop]: Abstraction has has 105 places, 84 transitions, 398 flow [2023-08-26 19:36:43,789 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 11 states, 11 states have (on average 595.4545454545455) internal successors, (6550), 11 states have internal predecessors, (6550), 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 19:36:43,789 INFO L200 CegarLoopForPetriNet]: Found error trace [2023-08-26 19:36:43,790 INFO L208 CegarLoopForPetriNet]: trace histogram [5, 5, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-08-26 19:36:43,797 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Forceful destruction successful, exit code 0 [2023-08-26 19:36:43,994 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 10 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable16 [2023-08-26 19:36:43,995 INFO L420 AbstractCegarLoop]: === Iteration 18 === Targeting thread3Err3REQUIRES_VIOLATIONMEMORY_DEREFERENCE === [thread1Err0REQUIRES_VIOLATIONMEMORY_DEREFERENCE, thread1Err1REQUIRES_VIOLATIONMEMORY_DEREFERENCE, thread1Err2REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 115 more)] === [2023-08-26 19:36:43,995 INFO L145 PredicateUnifier]: Initialized classic predicate unifier [2023-08-26 19:36:43,995 INFO L85 PathProgramCache]: Analyzing trace with hash -461568164, now seen corresponding path program 1 times [2023-08-26 19:36:43,995 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-08-26 19:36:43,995 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1390875745] [2023-08-26 19:36:43,995 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-08-26 19:36:43,995 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-08-26 19:36:44,166 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-08-26 19:36:44,397 INFO L134 CoverageAnalysis]: Checked inductivity of 45 backedges. 6 proven. 9 refuted. 0 times theorem prover too weak. 30 trivial. 0 not checked. [2023-08-26 19:36:44,397 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-08-26 19:36:44,397 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1390875745] [2023-08-26 19:36:44,397 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1390875745] provided 0 perfect and 1 imperfect interpolant sequences [2023-08-26 19:36:44,397 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1601289183] [2023-08-26 19:36:44,397 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-08-26 19:36:44,397 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-08-26 19:36:44,398 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-08-26 19:36:44,401 INFO L229 MonitoredProcess]: Starting monitored process 11 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-08-26 19:36:44,425 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Waiting until timeout for monitored process [2023-08-26 19:36:44,640 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-08-26 19:36:44,642 INFO L262 TraceCheckSpWp]: Trace formula consists of 425 conjuncts, 19 conjunts are in the unsatisfiable core [2023-08-26 19:36:44,645 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-08-26 19:36:44,652 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 19:36:44,771 INFO L134 CoverageAnalysis]: Checked inductivity of 45 backedges. 10 proven. 5 refuted. 0 times theorem prover too weak. 30 trivial. 0 not checked. [2023-08-26 19:36:44,771 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-08-26 19:36:44,949 INFO L134 CoverageAnalysis]: Checked inductivity of 45 backedges. 15 proven. 0 refuted. 0 times theorem prover too weak. 30 trivial. 0 not checked. [2023-08-26 19:36:44,950 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1601289183] provided 1 perfect and 1 imperfect interpolant sequences [2023-08-26 19:36:44,950 INFO L185 FreeRefinementEngine]: Found 1 perfect and 2 imperfect interpolant sequences. [2023-08-26 19:36:44,950 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [9] imperfect sequences [9, 9] total 25 [2023-08-26 19:36:44,950 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1175270465] [2023-08-26 19:36:44,950 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-08-26 19:36:44,950 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2023-08-26 19:36:44,950 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-08-26 19:36:44,951 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2023-08-26 19:36:44,951 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=169, Invalid=481, Unknown=0, NotChecked=0, Total=650 [2023-08-26 19:36:44,954 INFO L471 CegarLoopForPetriNet]: Number of universal loopers: 620 out of 1849 [2023-08-26 19:36:44,958 INFO L103 encePairwiseOnDemand]: Start differencePairwiseOnDemand. First operand has 105 places, 84 transitions, 398 flow. Second operand has 10 states, 10 states have (on average 621.8) internal successors, (6218), 10 states have internal predecessors, (6218), 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 19:36:44,958 INFO L112 encePairwiseOnDemand]: Universal subtrahend loopers provided by user. [2023-08-26 19:36:44,958 INFO L113 encePairwiseOnDemand]: Number of universal subtrahend loopers: 620 of 1849 [2023-08-26 19:36:44,958 INFO L73 FinitePrefix]: Start finitePrefix. Operand will be constructed on-demand [2023-08-26 19:36:52,789 INFO L124 PetriNetUnfolderBase]: 45664/61841 cut-off events. [2023-08-26 19:36:52,789 INFO L125 PetriNetUnfolderBase]: For 43408/43408 co-relation queries the response was YES. [2023-08-26 19:36:53,024 INFO L83 FinitePrefix]: Finished finitePrefix Result has 160357 conditions, 61841 events. 45664/61841 cut-off events. For 43408/43408 co-relation queries the response was YES. Maximal size of possible extension queue 822. Compared 340725 event pairs, 24387 based on Foata normal form. 0/45863 useless extension candidates. Maximal degree in co-relation 160329. Up to 43436 conditions per place. [2023-08-26 19:36:53,182 INFO L140 encePairwiseOnDemand]: 1843/1849 looper letters, 133 selfloop transitions, 4 changer transitions 0/137 dead transitions. [2023-08-26 19:36:53,183 INFO L145 encePairwiseOnDemand]: Finished differencePairwiseOnDemand. Result has 109 places, 137 transitions, 901 flow [2023-08-26 19:36:53,183 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2023-08-26 19:36:53,183 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 5 states. [2023-08-26 19:36:53,187 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 3204 transitions. [2023-08-26 19:36:53,188 INFO L516 CegarLoopForPetriNet]: DFA transition density 0.34656571119524066 [2023-08-26 19:36:53,188 INFO L72 ComplementDD]: Start complementDD. Operand 5 states and 3204 transitions. [2023-08-26 19:36:53,188 INFO L73 IsDeterministic]: Start isDeterministic. Operand 5 states and 3204 transitions. [2023-08-26 19:36:53,188 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2023-08-26 19:36:53,188 INFO L117 ReachableStatesCopy]: Start reachableStatesCopy. Operand 5 states and 3204 transitions. [2023-08-26 19:36:53,191 INFO L343 DoubleDeckerVisitor]: Before removal of dead ends has 6 states, 5 states have (on average 640.8) internal successors, (3204), 5 states have internal predecessors, (3204), 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 19:36:53,196 INFO L131 ReachableStatesCopy]: Finished reachableStatesCopy Result has 6 states, 6 states have (on average 1849.0) internal successors, (11094), 6 states have internal predecessors, (11094), 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 19:36:53,197 INFO L81 ComplementDD]: Finished complementDD. Result has 6 states, 6 states have (on average 1849.0) internal successors, (11094), 6 states have internal predecessors, (11094), 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 19:36:53,197 INFO L175 Difference]: Start difference. First operand has 105 places, 84 transitions, 398 flow. Second operand 5 states and 3204 transitions. [2023-08-26 19:36:53,197 INFO L82 GeneralOperation]: Start removeRedundantFlow. Operand has 109 places, 137 transitions, 901 flow [2023-08-26 19:36:53,255 INFO L88 GeneralOperation]: Finished removeRedundantFlow, result has has 106 places, 137 transitions, 882 flow, removed 2 selfloop flow, removed 3 redundant places. [2023-08-26 19:36:53,257 INFO L231 Difference]: Finished difference. Result has 107 places, 85 transitions, 405 flow [2023-08-26 19:36:53,257 INFO L264 CegarLoopForPetriNet]: {PETRI_ALPHABET=1849, PETRI_DIFFERENCE_MINUEND_FLOW=387, PETRI_DIFFERENCE_MINUEND_PLACES=102, PETRI_DIFFERENCE_MINUEND_TRANSITIONS=84, PETRI_DIFFERENCE_SUBTRAHEND_LETTERS_WITH_MORE_CHANGERS_THAN_LOOPERS=3, PETRI_DIFFERENCE_SUBTRAHEND_LOOPER_ONLY_LETTERS=80, PETRI_DIFFERENCE_SUBTRAHEND_STATES=5, PETRI_FLOW=405, PETRI_PLACES=107, PETRI_TRANSITIONS=85} [2023-08-26 19:36:53,257 INFO L281 CegarLoopForPetriNet]: 112 programPoint places, -5 predicate places. [2023-08-26 19:36:53,257 INFO L495 AbstractCegarLoop]: Abstraction has has 107 places, 85 transitions, 405 flow [2023-08-26 19:36:53,258 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 10 states have (on average 621.8) internal successors, (6218), 10 states have internal predecessors, (6218), 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 19:36:53,258 INFO L200 CegarLoopForPetriNet]: Found error trace [2023-08-26 19:36:53,258 INFO L208 CegarLoopForPetriNet]: trace histogram [5, 5, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-08-26 19:36:53,264 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Forceful destruction successful, exit code 0 [2023-08-26 19:36:53,458 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 11 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable17 [2023-08-26 19:36:53,459 INFO L420 AbstractCegarLoop]: === Iteration 19 === Targeting thread3Err1REQUIRES_VIOLATIONMEMORY_DEREFERENCE === [thread1Err0REQUIRES_VIOLATIONMEMORY_DEREFERENCE, thread1Err1REQUIRES_VIOLATIONMEMORY_DEREFERENCE, thread1Err2REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 115 more)] === [2023-08-26 19:36:53,459 INFO L145 PredicateUnifier]: Initialized classic predicate unifier [2023-08-26 19:36:53,459 INFO L85 PathProgramCache]: Analyzing trace with hash -461568165, now seen corresponding path program 1 times [2023-08-26 19:36:53,459 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-08-26 19:36:53,459 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1073922629] [2023-08-26 19:36:53,459 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-08-26 19:36:53,459 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-08-26 19:36:53,483 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-08-26 19:36:53,790 INFO L134 CoverageAnalysis]: Checked inductivity of 45 backedges. 6 proven. 9 refuted. 0 times theorem prover too weak. 30 trivial. 0 not checked. [2023-08-26 19:36:53,790 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-08-26 19:36:53,791 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1073922629] [2023-08-26 19:36:53,791 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1073922629] provided 0 perfect and 1 imperfect interpolant sequences [2023-08-26 19:36:53,791 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1076404683] [2023-08-26 19:36:53,791 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-08-26 19:36:53,791 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-08-26 19:36:53,791 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-08-26 19:36:53,793 INFO L229 MonitoredProcess]: Starting monitored process 12 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-08-26 19:36:53,824 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Waiting until timeout for monitored process [2023-08-26 19:36:54,041 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-08-26 19:36:54,044 INFO L262 TraceCheckSpWp]: Trace formula consists of 417 conjuncts, 20 conjunts are in the unsatisfiable core [2023-08-26 19:36:54,045 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-08-26 19:36:54,050 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 19:36:54,156 INFO L190 IndexEqualityManager]: detected not equals via solver [2023-08-26 19:36:54,157 INFO L351 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 14 treesize of output 16 [2023-08-26 19:36:54,162 INFO L322 Elim1Store]: treesize reduction 4, result has 50.0 percent of original size [2023-08-26 19:36:54,162 INFO L351 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 11 treesize of output 11 [2023-08-26 19:36:54,225 INFO L134 CoverageAnalysis]: Checked inductivity of 45 backedges. 10 proven. 5 refuted. 0 times theorem prover too weak. 30 trivial. 0 not checked. [2023-08-26 19:36:54,226 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-08-26 19:37:00,332 WARN L234 SmtUtils]: Spent 6.01s on a formula simplification that was a NOOP. DAG size: 22 (called from [L 376] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2023-08-26 19:37:00,339 INFO L351 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 48 treesize of output 44 [2023-08-26 19:37:00,535 INFO L134 CoverageAnalysis]: Checked inductivity of 45 backedges. 10 proven. 5 refuted. 0 times theorem prover too weak. 30 trivial. 0 not checked. [2023-08-26 19:37:00,536 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1076404683] provided 0 perfect and 2 imperfect interpolant sequences [2023-08-26 19:37:00,536 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2023-08-26 19:37:00,536 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9, 9] total 25 [2023-08-26 19:37:00,536 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1279574708] [2023-08-26 19:37:00,536 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2023-08-26 19:37:00,536 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 26 states [2023-08-26 19:37:00,538 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-08-26 19:37:00,539 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 26 interpolants. [2023-08-26 19:37:00,539 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=148, Invalid=502, Unknown=0, NotChecked=0, Total=650 [2023-08-26 19:37:00,546 INFO L471 CegarLoopForPetriNet]: Number of universal loopers: 588 out of 1849 [2023-08-26 19:37:00,552 INFO L103 encePairwiseOnDemand]: Start differencePairwiseOnDemand. First operand has 107 places, 85 transitions, 405 flow. Second operand has 26 states, 26 states have (on average 589.9230769230769) internal successors, (15338), 26 states have internal predecessors, (15338), 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 19:37:00,552 INFO L112 encePairwiseOnDemand]: Universal subtrahend loopers provided by user. [2023-08-26 19:37:00,552 INFO L113 encePairwiseOnDemand]: Number of universal subtrahend loopers: 588 of 1849 [2023-08-26 19:37:00,552 INFO L73 FinitePrefix]: Start finitePrefix. Operand will be constructed on-demand [2023-08-26 19:37:10,503 INFO L124 PetriNetUnfolderBase]: 53410/71221 cut-off events. [2023-08-26 19:37:10,503 INFO L125 PetriNetUnfolderBase]: For 51271/51271 co-relation queries the response was YES. [2023-08-26 19:37:10,813 INFO L83 FinitePrefix]: Finished finitePrefix Result has 193491 conditions, 71221 events. 53410/71221 cut-off events. For 51271/51271 co-relation queries the response was YES. Maximal size of possible extension queue 896. Compared 384931 event pairs, 16683 based on Foata normal form. 0/57259 useless extension candidates. Maximal degree in co-relation 193462. Up to 31188 conditions per place. [2023-08-26 19:37:11,003 INFO L140 encePairwiseOnDemand]: 1837/1849 looper letters, 169 selfloop transitions, 21 changer transitions 0/190 dead transitions. [2023-08-26 19:37:11,003 INFO L145 encePairwiseOnDemand]: Finished differencePairwiseOnDemand. Result has 121 places, 190 transitions, 1231 flow [2023-08-26 19:37:11,004 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2023-08-26 19:37:11,004 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 15 states. [2023-08-26 19:37:11,009 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 15 states to 15 states and 8979 transitions. [2023-08-26 19:37:11,010 INFO L516 CegarLoopForPetriNet]: DFA transition density 0.32374256354786374 [2023-08-26 19:37:11,010 INFO L72 ComplementDD]: Start complementDD. Operand 15 states and 8979 transitions. [2023-08-26 19:37:11,010 INFO L73 IsDeterministic]: Start isDeterministic. Operand 15 states and 8979 transitions. [2023-08-26 19:37:11,011 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2023-08-26 19:37:11,011 INFO L117 ReachableStatesCopy]: Start reachableStatesCopy. Operand 15 states and 8979 transitions. [2023-08-26 19:37:11,020 INFO L343 DoubleDeckerVisitor]: Before removal of dead ends has 16 states, 15 states have (on average 598.6) internal successors, (8979), 15 states have internal predecessors, (8979), 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 19:37:11,036 INFO L131 ReachableStatesCopy]: Finished reachableStatesCopy Result has 16 states, 16 states have (on average 1849.0) internal successors, (29584), 16 states have internal predecessors, (29584), 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 19:37:11,038 INFO L81 ComplementDD]: Finished complementDD. Result has 16 states, 16 states have (on average 1849.0) internal successors, (29584), 16 states have internal predecessors, (29584), 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 19:37:11,038 INFO L175 Difference]: Start difference. First operand has 107 places, 85 transitions, 405 flow. Second operand 15 states and 8979 transitions. [2023-08-26 19:37:11,039 INFO L82 GeneralOperation]: Start removeRedundantFlow. Operand has 121 places, 190 transitions, 1231 flow [2023-08-26 19:37:11,091 INFO L88 GeneralOperation]: Finished removeRedundantFlow, result has has 118 places, 190 transitions, 1225 flow, removed 0 selfloop flow, removed 3 redundant places. [2023-08-26 19:37:11,092 INFO L231 Difference]: Finished difference. Result has 121 places, 88 transitions, 474 flow [2023-08-26 19:37:11,092 INFO L264 CegarLoopForPetriNet]: {PETRI_ALPHABET=1849, PETRI_DIFFERENCE_MINUEND_FLOW=399, PETRI_DIFFERENCE_MINUEND_PLACES=104, PETRI_DIFFERENCE_MINUEND_TRANSITIONS=85, PETRI_DIFFERENCE_SUBTRAHEND_LETTERS_WITH_MORE_CHANGERS_THAN_LOOPERS=18, PETRI_DIFFERENCE_SUBTRAHEND_LOOPER_ONLY_LETTERS=64, PETRI_DIFFERENCE_SUBTRAHEND_STATES=15, PETRI_FLOW=474, PETRI_PLACES=121, PETRI_TRANSITIONS=88} [2023-08-26 19:37:11,093 INFO L281 CegarLoopForPetriNet]: 112 programPoint places, 9 predicate places. [2023-08-26 19:37:11,093 INFO L495 AbstractCegarLoop]: Abstraction has has 121 places, 88 transitions, 474 flow [2023-08-26 19:37:11,094 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 26 states, 26 states have (on average 589.9230769230769) internal successors, (15338), 26 states have internal predecessors, (15338), 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 19:37:11,094 INFO L200 CegarLoopForPetriNet]: Found error trace [2023-08-26 19:37:11,094 INFO L208 CegarLoopForPetriNet]: trace histogram [5, 5, 5, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-08-26 19:37:11,100 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Forceful destruction successful, exit code 0 [2023-08-26 19:37:11,295 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable18,12 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-08-26 19:37:11,295 INFO L420 AbstractCegarLoop]: === Iteration 20 === Targeting thread3Err3REQUIRES_VIOLATIONMEMORY_DEREFERENCE === [thread1Err0REQUIRES_VIOLATIONMEMORY_DEREFERENCE, thread1Err1REQUIRES_VIOLATIONMEMORY_DEREFERENCE, thread1Err2REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 115 more)] === [2023-08-26 19:37:11,295 INFO L145 PredicateUnifier]: Initialized classic predicate unifier [2023-08-26 19:37:11,295 INFO L85 PathProgramCache]: Analyzing trace with hash -1185180868, now seen corresponding path program 1 times [2023-08-26 19:37:11,295 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-08-26 19:37:11,296 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [953585737] [2023-08-26 19:37:11,296 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-08-26 19:37:11,296 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-08-26 19:37:11,331 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-08-26 19:37:11,943 INFO L134 CoverageAnalysis]: Checked inductivity of 48 backedges. 0 proven. 8 refuted. 0 times theorem prover too weak. 40 trivial. 0 not checked. [2023-08-26 19:37:11,943 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-08-26 19:37:11,944 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [953585737] [2023-08-26 19:37:11,944 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [953585737] provided 0 perfect and 1 imperfect interpolant sequences [2023-08-26 19:37:11,944 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [211519375] [2023-08-26 19:37:11,944 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-08-26 19:37:11,944 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-08-26 19:37:11,944 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-08-26 19:37:11,949 INFO L229 MonitoredProcess]: Starting monitored process 13 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-08-26 19:37:11,951 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Waiting until timeout for monitored process [2023-08-26 19:37:12,209 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-08-26 19:37:12,212 INFO L262 TraceCheckSpWp]: Trace formula consists of 445 conjuncts, 21 conjunts are in the unsatisfiable core [2023-08-26 19:37:12,214 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-08-26 19:37:12,219 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 19:37:12,429 INFO L134 CoverageAnalysis]: Checked inductivity of 48 backedges. 10 proven. 8 refuted. 0 times theorem prover too weak. 30 trivial. 0 not checked. [2023-08-26 19:37:12,429 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-08-26 19:37:12,539 INFO L351 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 95 treesize of output 83 [2023-08-26 19:37:12,544 INFO L351 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 83 treesize of output 81 [2023-08-26 19:37:12,752 INFO L134 CoverageAnalysis]: Checked inductivity of 48 backedges. 15 proven. 3 refuted. 0 times theorem prover too weak. 30 trivial. 0 not checked. [2023-08-26 19:37:12,752 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [211519375] provided 0 perfect and 2 imperfect interpolant sequences [2023-08-26 19:37:12,752 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2023-08-26 19:37:12,752 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 11, 11] total 27 [2023-08-26 19:37:12,752 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [397349219] [2023-08-26 19:37:12,753 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2023-08-26 19:37:12,753 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 28 states [2023-08-26 19:37:12,753 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-08-26 19:37:12,754 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 28 interpolants. [2023-08-26 19:37:12,754 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=143, Invalid=613, Unknown=0, NotChecked=0, Total=756 [2023-08-26 19:37:12,761 INFO L471 CegarLoopForPetriNet]: Number of universal loopers: 614 out of 1849 [2023-08-26 19:37:12,769 INFO L103 encePairwiseOnDemand]: Start differencePairwiseOnDemand. First operand has 121 places, 88 transitions, 474 flow. Second operand has 28 states, 28 states have (on average 615.75) internal successors, (17241), 28 states have internal predecessors, (17241), 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 19:37:12,769 INFO L112 encePairwiseOnDemand]: Universal subtrahend loopers provided by user. [2023-08-26 19:37:12,769 INFO L113 encePairwiseOnDemand]: Number of universal subtrahend loopers: 614 of 1849 [2023-08-26 19:37:12,769 INFO L73 FinitePrefix]: Start finitePrefix. Operand will be constructed on-demand