./Ultimate.py --spec ../../../trunk/examples/svcomp/properties/unreach-call.prp --file ../../../trunk/examples/svcomp/pthread/stack_longest-1.i --full-output --witness-type correctness_witness --witnessparser.only.consider.loop.invariants false --validate ./goblint.2024-05-07_14-17-48.files/mutex-meet/stack_longest-1.yml/witness.yml --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version b44c8288 Calling Ultimate with: /root/.sdkman/candidates/java/current/bin/java -Dosgi.configuration.area=/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/config -Xmx15G -Xms4m -jar /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data -tc /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/AutomizerReachWitnessValidation.xml -i ../../../trunk/examples/svcomp/pthread/stack_longest-1.i ./goblint.2024-05-07_14-17-48.files/mutex-meet/stack_longest-1.yml/witness.yml -s /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf --cacsl2boogietranslator.entry.function main --traceabstraction.compute.hoare.annotation.of.negated.interpolant.automaton,.abstraction.and.cfg false --witnessparser.only.consider.loop.invariants false --- Real Ultimate output --- This is Ultimate 0.2.4-wip.fs.witness-ghost-b44c828-m [2024-05-12 11:10:27,207 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-05-12 11:10:27,307 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf [2024-05-12 11:10:27,315 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-05-12 11:10:27,315 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-05-12 11:10:27,350 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-05-12 11:10:27,351 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-05-12 11:10:27,351 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-05-12 11:10:27,352 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2024-05-12 11:10:27,356 INFO L153 SettingsManager]: * Use memory slicer=true [2024-05-12 11:10:27,356 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2024-05-12 11:10:27,356 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2024-05-12 11:10:27,357 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2024-05-12 11:10:27,359 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2024-05-12 11:10:27,359 INFO L153 SettingsManager]: * Use SBE=true [2024-05-12 11:10:27,359 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-05-12 11:10:27,359 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2024-05-12 11:10:27,360 INFO L153 SettingsManager]: * sizeof long=4 [2024-05-12 11:10:27,360 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2024-05-12 11:10:27,360 INFO L153 SettingsManager]: * sizeof POINTER=4 [2024-05-12 11:10:27,360 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-05-12 11:10:27,361 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2024-05-12 11:10:27,361 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2024-05-12 11:10:27,361 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2024-05-12 11:10:27,362 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-05-12 11:10:27,362 INFO L153 SettingsManager]: * sizeof long double=12 [2024-05-12 11:10:27,362 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-05-12 11:10:27,362 INFO L153 SettingsManager]: * Use constant arrays=true [2024-05-12 11:10:27,363 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2024-05-12 11:10:27,363 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2024-05-12 11:10:27,364 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2024-05-12 11:10:27,364 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2024-05-12 11:10:27,364 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-05-12 11:10:27,365 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-05-12 11:10:27,365 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2024-05-12 11:10:27,365 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2024-05-12 11:10:27,365 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2024-05-12 11:10:27,365 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2024-05-12 11:10:27,366 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2024-05-12 11:10:27,366 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2024-05-12 11:10:27,366 INFO L153 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2024-05-12 11:10:27,366 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2024-05-12 11:10:27,367 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2024-05-12 11:10:27,367 INFO L153 SettingsManager]: * Looper check in Petri net analysis=SEMANTIC WARNING: An illegal reflective access operation has occurred WARNING: Illegal reflective access by com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 (file:/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/com.sun.xml.bind_2.2.0.v201505121915.jar) to method java.lang.ClassLoader.defineClass(java.lang.String,byte[],int,int) WARNING: Please consider reporting this to the maintainers of com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 WARNING: Use --illegal-access=warn to enable warnings of further illegal reflective access operations WARNING: All illegal access operations will be denied in a future release Applying setting for plugin de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator: Entry function -> main Applying setting for plugin de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG -> false Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessparser: Only consider loop invariants -> false [2024-05-12 11:10:27,623 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-05-12 11:10:27,640 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-05-12 11:10:27,643 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-05-12 11:10:27,644 INFO L270 PluginConnector]: Initializing Witness Parser... [2024-05-12 11:10:27,644 INFO L274 PluginConnector]: Witness Parser initialized [2024-05-12 11:10:27,645 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/./goblint.2024-05-07_14-17-48.files/mutex-meet/stack_longest-1.yml/witness.yml [2024-05-12 11:10:27,742 INFO L270 PluginConnector]: Initializing CDTParser... [2024-05-12 11:10:27,743 INFO L274 PluginConnector]: CDTParser initialized [2024-05-12 11:10:27,744 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/svcomp/pthread/stack_longest-1.i [2024-05-12 11:10:28,897 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-05-12 11:10:29,172 INFO L384 CDTParser]: Found 1 translation units. [2024-05-12 11:10:29,173 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/trunk/examples/svcomp/pthread/stack_longest-1.i [2024-05-12 11:10:29,201 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/c2f8b47ec/f8fbf212dca94d2a82dd53ffc4de2bb6/FLAG1361ae369 [2024-05-12 11:10:29,218 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/c2f8b47ec/f8fbf212dca94d2a82dd53ffc4de2bb6 [2024-05-12 11:10:29,219 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-05-12 11:10:29,220 INFO L133 ToolchainWalker]: Walking toolchain with 5 elements. [2024-05-12 11:10:29,223 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-05-12 11:10:29,224 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-05-12 11:10:29,228 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-05-12 11:10:29,229 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "witness.yml de.uni_freiburg.informatik.ultimate.witnessparser CORRECTNESS_WITNESS 12.05 11:10:27" (1/2) ... [2024-05-12 11:10:29,231 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@2c8accba and model type witness.yml de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator CORRECTNESS_WITNESS 12.05 11:10:29, skipping insertion in model container [2024-05-12 11:10:29,231 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "witness.yml de.uni_freiburg.informatik.ultimate.witnessparser CORRECTNESS_WITNESS 12.05 11:10:27" (1/2) ... [2024-05-12 11:10:29,232 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.CACSL2BoogieTranslatorObserver@77d98f34 and model type witness.yml de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator CORRECTNESS_WITNESS 12.05 11:10:29, skipping insertion in model container [2024-05-12 11:10:29,233 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 12.05 11:10:29" (2/2) ... [2024-05-12 11:10:29,233 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@2c8accba and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.05 11:10:29, skipping insertion in model container [2024-05-12 11:10:29,233 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 12.05 11:10:29" (2/2) ... [2024-05-12 11:10:29,234 INFO L83 nessWitnessExtractor]: Extracting all invariants from correctness witness [2024-05-12 11:10:29,299 INFO L95 edCorrectnessWitness]: Found the following entries in the witness: [2024-05-12 11:10:29,300 INFO L97 edCorrectnessWitness]: Location invariant before [L1023-L1023] ! multithreaded || (m_locked || (long long )flag + (long long )top >= 0LL) [2024-05-12 11:10:29,300 INFO L97 edCorrectnessWitness]: Location invariant before [L1024-L1024] ! multithreaded || (m_locked || (long long )flag + (long long )top >= 0LL) [2024-05-12 11:10:29,301 INFO L103 edCorrectnessWitness]: ghost_variable multithreaded = 0 [2024-05-12 11:10:29,301 INFO L103 edCorrectnessWitness]: ghost_variable m_locked = 0 [2024-05-12 11:10:29,301 INFO L106 edCorrectnessWitness]: ghost_update [L993-L993] m_locked = 1; [2024-05-12 11:10:29,301 INFO L106 edCorrectnessWitness]: ghost_update [L1008-L1008] m_locked = 1; [2024-05-12 11:10:29,301 INFO L106 edCorrectnessWitness]: ghost_update [L1022-L1022] multithreaded = 1; [2024-05-12 11:10:29,301 INFO L106 edCorrectnessWitness]: ghost_update [L999-L999] m_locked = 0; [2024-05-12 11:10:29,302 INFO L106 edCorrectnessWitness]: ghost_update [L1014-L1014] m_locked = 0; [2024-05-12 11:10:29,356 INFO L177 MainTranslator]: Built tables and reachable declarations [2024-05-12 11:10:29,787 WARN L246 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/trunk/examples/svcomp/pthread/stack_longest-1.i[41530,41543] [2024-05-12 11:10:29,827 INFO L207 PostProcessor]: Analyzing one entry point: main [2024-05-12 11:10:29,837 INFO L202 MainTranslator]: Completed pre-run Start Parsing Local Start Parsing Local [2024-05-12 11:10:29,908 WARN L246 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/trunk/examples/svcomp/pthread/stack_longest-1.i[41530,41543] Start Parsing Local Start Parsing Local Start Parsing Local Start Parsing Local Start Parsing Local Start Parsing Local Start Parsing Local [2024-05-12 11:10:29,922 INFO L207 PostProcessor]: Analyzing one entry point: main [2024-05-12 11:10:29,976 INFO L206 MainTranslator]: Completed translation [2024-05-12 11:10:29,977 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.05 11:10:29 WrapperNode [2024-05-12 11:10:29,977 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-05-12 11:10:29,978 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-05-12 11:10:29,979 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-05-12 11:10:29,979 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-05-12 11:10:29,985 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.05 11:10:29" (1/1) ... [2024-05-12 11:10:30,011 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.05 11:10:29" (1/1) ... [2024-05-12 11:10:30,037 INFO L138 Inliner]: procedures = 278, calls = 41, calls flagged for inlining = 12, calls inlined = 12, statements flattened = 175 [2024-05-12 11:10:30,040 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-05-12 11:10:30,041 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-05-12 11:10:30,042 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-05-12 11:10:30,042 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-05-12 11:10:30,056 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.05 11:10:29" (1/1) ... [2024-05-12 11:10:30,056 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.05 11:10:29" (1/1) ... [2024-05-12 11:10:30,076 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.05 11:10:29" (1/1) ... [2024-05-12 11:10:30,090 INFO L175 MemorySlicer]: Split 14 memory accesses to 5 slices as follows [2, 5, 2, 3, 2]. 36 percent of accesses are in the largest equivalence class. The 7 initializations are split as follows [2, 5, 0, 0, 0]. The 4 writes are split as follows [0, 0, 1, 2, 1]. [2024-05-12 11:10:30,091 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.05 11:10:29" (1/1) ... [2024-05-12 11:10:30,091 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.05 11:10:29" (1/1) ... [2024-05-12 11:10:30,099 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.05 11:10:29" (1/1) ... [2024-05-12 11:10:30,102 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.05 11:10:29" (1/1) ... [2024-05-12 11:10:30,104 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.05 11:10:29" (1/1) ... [2024-05-12 11:10:30,105 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.05 11:10:29" (1/1) ... [2024-05-12 11:10:30,108 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-05-12 11:10:30,109 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2024-05-12 11:10:30,109 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2024-05-12 11:10:30,109 INFO L274 PluginConnector]: RCFGBuilder initialized [2024-05-12 11:10:30,109 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.05 11:10:29" (1/1) ... [2024-05-12 11:10:30,121 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-05-12 11:10:30,129 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-05-12 11:10:30,145 INFO L229 MonitoredProcess]: Starting monitored process 1 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (exit command is (exit), workingDir is null) [2024-05-12 11:10:30,169 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (1)] Waiting until timeout for monitored process [2024-05-12 11:10:30,184 INFO L130 BoogieDeclarations]: Found specification of procedure t1 [2024-05-12 11:10:30,184 INFO L138 BoogieDeclarations]: Found implementation of procedure t1 [2024-05-12 11:10:30,184 INFO L130 BoogieDeclarations]: Found specification of procedure t2 [2024-05-12 11:10:30,184 INFO L138 BoogieDeclarations]: Found implementation of procedure t2 [2024-05-12 11:10:30,184 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnStack [2024-05-12 11:10:30,185 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2024-05-12 11:10:30,185 INFO L130 BoogieDeclarations]: Found specification of procedure #PthreadsMutexUnlock [2024-05-12 11:10:30,185 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#0 [2024-05-12 11:10:30,186 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#1 [2024-05-12 11:10:30,186 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#2 [2024-05-12 11:10:30,187 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#3 [2024-05-12 11:10:30,188 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#4 [2024-05-12 11:10:30,188 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#0 [2024-05-12 11:10:30,188 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#1 [2024-05-12 11:10:30,188 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#2 [2024-05-12 11:10:30,188 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#3 [2024-05-12 11:10:30,188 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#4 [2024-05-12 11:10:30,188 INFO L130 BoogieDeclarations]: Found specification of procedure #PthreadsMutexLock [2024-05-12 11:10:30,189 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2024-05-12 11:10:30,189 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2024-05-12 11:10:30,189 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#1 [2024-05-12 11:10:30,189 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#2 [2024-05-12 11:10:30,189 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#3 [2024-05-12 11:10:30,189 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#4 [2024-05-12 11:10:30,189 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-05-12 11:10:30,189 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-05-12 11:10:30,191 WARN L214 CfgBuilder]: User set CodeBlockSize to SequenceOfStatements but program contains fork statements. Overwriting the user preferences and setting CodeBlockSize to OneNontrivialStatement [2024-05-12 11:10:30,373 INFO L244 CfgBuilder]: Building ICFG [2024-05-12 11:10:30,376 INFO L270 CfgBuilder]: Building CFG for each procedure with an implementation [2024-05-12 11:10:30,700 INFO L289 CfgBuilder]: Ommited future-live optimization because the input is a concurrent program. [2024-05-12 11:10:30,700 INFO L293 CfgBuilder]: Performing block encoding [2024-05-12 11:10:30,912 INFO L315 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-05-12 11:10:30,912 INFO L320 CfgBuilder]: Removed 2 assume(true) statements. [2024-05-12 11:10:30,913 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 12.05 11:10:30 BoogieIcfgContainer [2024-05-12 11:10:30,913 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2024-05-12 11:10:30,915 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2024-05-12 11:10:30,915 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2024-05-12 11:10:30,918 INFO L274 PluginConnector]: TraceAbstraction initialized [2024-05-12 11:10:30,918 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "witness.yml de.uni_freiburg.informatik.ultimate.witnessparser CORRECTNESS_WITNESS 12.05 11:10:27" (1/4) ... [2024-05-12 11:10:30,919 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@4244b14 and model type witness.yml de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CORRECTNESS_WITNESS 12.05 11:10:30, skipping insertion in model container [2024-05-12 11:10:30,919 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 12.05 11:10:29" (2/4) ... [2024-05-12 11:10:30,919 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@4244b14 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 12.05 11:10:30, skipping insertion in model container [2024-05-12 11:10:30,919 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.05 11:10:29" (3/4) ... [2024-05-12 11:10:30,920 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@4244b14 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 12.05 11:10:30, skipping insertion in model container [2024-05-12 11:10:30,920 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 12.05 11:10:30" (4/4) ... [2024-05-12 11:10:30,921 INFO L112 eAbstractionObserver]: Analyzing ICFG stack_longest-1.i [2024-05-12 11:10:30,940 INFO L204 ceAbstractionStarter]: Automizer settings: Hoare:false NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2024-05-12 11:10:30,940 INFO L163 ceAbstractionStarter]: Applying trace abstraction to program that has 4 error locations. [2024-05-12 11:10:30,940 INFO L522 ceAbstractionStarter]: Constructing petrified ICFG for 1 thread instances. [2024-05-12 11:10:30,991 INFO L144 ThreadInstanceAdder]: Constructed 2 joinOtherThreadTransitions. [2024-05-12 11:10:31,022 INFO L73 FinitePrefix]: Start finitePrefix. Operand has 44 places, 42 transitions, 98 flow [2024-05-12 11:10:31,045 INFO L124 PetriNetUnfolderBase]: 5/40 cut-off events. [2024-05-12 11:10:31,045 INFO L125 PetriNetUnfolderBase]: For 2/2 co-relation queries the response was YES. [2024-05-12 11:10:31,049 INFO L83 FinitePrefix]: Finished finitePrefix Result has 49 conditions, 40 events. 5/40 cut-off events. For 2/2 co-relation queries the response was YES. Maximal size of possible extension queue 6. Compared 76 event pairs, 0 based on Foata normal form. 0/31 useless extension candidates. Maximal degree in co-relation 34. Up to 3 conditions per place. [2024-05-12 11:10:31,050 INFO L82 GeneralOperation]: Start removeDead. Operand has 44 places, 42 transitions, 98 flow [2024-05-12 11:10:31,052 INFO L88 GeneralOperation]: Finished RemoveDead, result has has 40 places, 38 transitions, 85 flow [2024-05-12 11:10:31,060 INFO L356 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2024-05-12 11:10:31,066 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=LoopHeads, mDumpOnlyReuseAutomata=false, mLimitTraceHistogram=0, mErrorLocTimeLimit=0, mLimitPathProgramCount=0, mCollectInterpolantStatistics=true, mHeuristicEmptinessCheck=false, mHeuristicEmptinessCheckAStarHeuristic=ZERO, mHeuristicEmptinessCheckAStarHeuristicRandomSeed=1337, mHeuristicEmptinessCheckSmtFeatureScoringMethod=DAGSIZE, mSMTFeatureExtraction=false, mSMTFeatureExtractionDumpPath=., mOverrideInterpolantAutomaton=false, mMcrInterpolantMethod=WP, mPorIndependenceSettings=[Lde.uni_freiburg.informatik.ultimate.lib.tracecheckerutils.partialorder.independence.IndependenceSettings;@10952647, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2024-05-12 11:10:31,066 INFO L358 AbstractCegarLoop]: Starting to check reachability of 8 error locations. [2024-05-12 11:10:31,070 INFO L185 PetriNetUnfolderBase]: Found word, exiting Unfolder. [2024-05-12 11:10:31,070 INFO L124 PetriNetUnfolderBase]: 0/6 cut-off events. [2024-05-12 11:10:31,070 INFO L125 PetriNetUnfolderBase]: For 0/0 co-relation queries the response was YES. [2024-05-12 11:10:31,072 INFO L200 CegarLoopForPetriNet]: Found error trace [2024-05-12 11:10:31,072 INFO L208 CegarLoopForPetriNet]: trace histogram [1, 1, 1, 1, 1, 1] [2024-05-12 11:10:31,073 INFO L420 AbstractCegarLoop]: === Iteration 1 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONWITNESS_INVARIANT === [ULTIMATE.startErr0ASSERT_VIOLATIONWITNESS_INVARIANT, ULTIMATE.startErr1ASSERT_VIOLATIONWITNESS_INVARIANT, ULTIMATE.startErr0INUSE_VIOLATIONSUFFICIENT_THREAD_INSTANCES (and 5 more)] === [2024-05-12 11:10:31,079 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2024-05-12 11:10:31,080 INFO L85 PathProgramCache]: Analyzing trace with hash 333389562, now seen corresponding path program 1 times [2024-05-12 11:10:31,088 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-05-12 11:10:31,089 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2058763783] [2024-05-12 11:10:31,090 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-05-12 11:10:31,090 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-05-12 11:10:31,187 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-05-12 11:10:31,348 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-05-12 11:10:31,348 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-05-12 11:10:31,348 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2058763783] [2024-05-12 11:10:31,349 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2058763783] provided 1 perfect and 0 imperfect interpolant sequences [2024-05-12 11:10:31,349 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-05-12 11:10:31,349 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [1] imperfect sequences [] total 1 [2024-05-12 11:10:31,350 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1930877269] [2024-05-12 11:10:31,351 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-05-12 11:10:31,358 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2024-05-12 11:10:31,364 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-05-12 11:10:31,386 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2024-05-12 11:10:31,387 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2024-05-12 11:10:31,391 INFO L471 CegarLoopForPetriNet]: Number of universal loopers: 9 out of 42 [2024-05-12 11:10:31,424 INFO L103 encePairwiseOnDemand]: Start differencePairwiseOnDemand. First operand has 40 places, 38 transitions, 85 flow. Second operand has 3 states, 3 states have (on average 11.0) internal successors, (33), 3 states have internal predecessors, (33), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-05-12 11:10:31,425 INFO L112 encePairwiseOnDemand]: Universal subtrahend loopers provided by user. [2024-05-12 11:10:31,425 INFO L113 encePairwiseOnDemand]: Number of universal subtrahend loopers: 9 of 42 [2024-05-12 11:10:31,426 INFO L73 FinitePrefix]: Start finitePrefix. Operand will be constructed on-demand [2024-05-12 11:10:31,766 INFO L124 PetriNetUnfolderBase]: 653/1156 cut-off events. [2024-05-12 11:10:31,767 INFO L125 PetriNetUnfolderBase]: For 30/30 co-relation queries the response was YES. [2024-05-12 11:10:31,772 INFO L83 FinitePrefix]: Finished finitePrefix Result has 2240 conditions, 1156 events. 653/1156 cut-off events. For 30/30 co-relation queries the response was YES. Maximal size of possible extension queue 68. Compared 5902 event pairs, 207 based on Foata normal form. 80/1072 useless extension candidates. Maximal degree in co-relation 2072. Up to 760 conditions per place. [2024-05-12 11:10:31,780 INFO L140 encePairwiseOnDemand]: 36/42 looper letters, 45 selfloop transitions, 2 changer transitions 0/54 dead transitions. [2024-05-12 11:10:31,781 INFO L145 encePairwiseOnDemand]: Finished differencePairwiseOnDemand. Result has 42 places, 54 transitions, 217 flow [2024-05-12 11:10:31,784 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2024-05-12 11:10:31,786 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 3 states. [2024-05-12 11:10:31,792 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 3 states to 3 states and 79 transitions. [2024-05-12 11:10:31,793 INFO L516 CegarLoopForPetriNet]: DFA transition density 0.626984126984127 [2024-05-12 11:10:31,795 INFO L175 Difference]: Start difference. First operand has 40 places, 38 transitions, 85 flow. Second operand 3 states and 79 transitions. [2024-05-12 11:10:31,795 INFO L82 GeneralOperation]: Start removeRedundantFlow. Operand has 42 places, 54 transitions, 217 flow [2024-05-12 11:10:31,798 INFO L88 GeneralOperation]: Finished removeRedundantFlow, result has has 39 places, 54 transitions, 209 flow, removed 0 selfloop flow, removed 3 redundant places. [2024-05-12 11:10:31,801 INFO L231 Difference]: Finished difference. Result has 40 places, 37 transitions, 90 flow [2024-05-12 11:10:31,802 INFO L264 CegarLoopForPetriNet]: {PETRI_ALPHABET=42, PETRI_DIFFERENCE_MINUEND_FLOW=76, PETRI_DIFFERENCE_MINUEND_PLACES=37, PETRI_DIFFERENCE_MINUEND_TRANSITIONS=36, PETRI_DIFFERENCE_SUBTRAHEND_LETTERS_WITH_MORE_CHANGERS_THAN_LOOPERS=1, PETRI_DIFFERENCE_SUBTRAHEND_LOOPER_ONLY_LETTERS=34, PETRI_DIFFERENCE_SUBTRAHEND_STATES=3, PETRI_FLOW=90, PETRI_PLACES=40, PETRI_TRANSITIONS=37} [2024-05-12 11:10:31,805 INFO L281 CegarLoopForPetriNet]: 40 programPoint places, 0 predicate places. [2024-05-12 11:10:31,806 INFO L495 AbstractCegarLoop]: Abstraction has has 40 places, 37 transitions, 90 flow [2024-05-12 11:10:31,806 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 11.0) internal successors, (33), 3 states have internal predecessors, (33), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-05-12 11:10:31,806 INFO L200 CegarLoopForPetriNet]: Found error trace [2024-05-12 11:10:31,806 INFO L208 CegarLoopForPetriNet]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-05-12 11:10:31,806 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2024-05-12 11:10:31,807 INFO L420 AbstractCegarLoop]: === Iteration 2 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONWITNESS_INVARIANT === [ULTIMATE.startErr0ASSERT_VIOLATIONWITNESS_INVARIANT, ULTIMATE.startErr1ASSERT_VIOLATIONWITNESS_INVARIANT, ULTIMATE.startErr0INUSE_VIOLATIONSUFFICIENT_THREAD_INSTANCES (and 5 more)] === [2024-05-12 11:10:31,807 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2024-05-12 11:10:31,807 INFO L85 PathProgramCache]: Analyzing trace with hash -1042235176, now seen corresponding path program 1 times [2024-05-12 11:10:31,807 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-05-12 11:10:31,808 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [346119026] [2024-05-12 11:10:31,808 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-05-12 11:10:31,808 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-05-12 11:10:31,843 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-05-12 11:10:31,923 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-05-12 11:10:31,923 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-05-12 11:10:31,923 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [346119026] [2024-05-12 11:10:31,924 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [346119026] provided 1 perfect and 0 imperfect interpolant sequences [2024-05-12 11:10:31,924 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-05-12 11:10:31,924 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2024-05-12 11:10:31,924 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1834513075] [2024-05-12 11:10:31,924 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-05-12 11:10:31,926 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2024-05-12 11:10:31,926 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-05-12 11:10:31,926 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2024-05-12 11:10:31,927 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2024-05-12 11:10:31,932 INFO L471 CegarLoopForPetriNet]: Number of universal loopers: 9 out of 42 [2024-05-12 11:10:31,932 INFO L103 encePairwiseOnDemand]: Start differencePairwiseOnDemand. First operand has 40 places, 37 transitions, 90 flow. Second operand has 4 states, 4 states have (on average 11.25) internal successors, (45), 4 states have internal predecessors, (45), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-05-12 11:10:31,933 INFO L112 encePairwiseOnDemand]: Universal subtrahend loopers provided by user. [2024-05-12 11:10:31,933 INFO L113 encePairwiseOnDemand]: Number of universal subtrahend loopers: 9 of 42 [2024-05-12 11:10:31,933 INFO L73 FinitePrefix]: Start finitePrefix. Operand will be constructed on-demand [2024-05-12 11:10:32,182 INFO L124 PetriNetUnfolderBase]: 760/1445 cut-off events. [2024-05-12 11:10:32,183 INFO L125 PetriNetUnfolderBase]: For 121/121 co-relation queries the response was YES. [2024-05-12 11:10:32,185 INFO L83 FinitePrefix]: Finished finitePrefix Result has 2846 conditions, 1445 events. 760/1445 cut-off events. For 121/121 co-relation queries the response was YES. Maximal size of possible extension queue 84. Compared 7865 event pairs, 264 based on Foata normal form. 41/1379 useless extension candidates. Maximal degree in co-relation 1427. Up to 619 conditions per place. [2024-05-12 11:10:32,191 INFO L140 encePairwiseOnDemand]: 34/42 looper letters, 48 selfloop transitions, 6 changer transitions 0/61 dead transitions. [2024-05-12 11:10:32,191 INFO L145 encePairwiseOnDemand]: Finished differencePairwiseOnDemand. Result has 44 places, 61 transitions, 254 flow [2024-05-12 11:10:32,192 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-05-12 11:10:32,192 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 5 states. [2024-05-12 11:10:32,193 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 99 transitions. [2024-05-12 11:10:32,193 INFO L516 CegarLoopForPetriNet]: DFA transition density 0.4714285714285714 [2024-05-12 11:10:32,194 INFO L175 Difference]: Start difference. First operand has 40 places, 37 transitions, 90 flow. Second operand 5 states and 99 transitions. [2024-05-12 11:10:32,194 INFO L82 GeneralOperation]: Start removeRedundantFlow. Operand has 44 places, 61 transitions, 254 flow [2024-05-12 11:10:32,195 INFO L88 GeneralOperation]: Finished removeRedundantFlow, result has has 43 places, 61 transitions, 251 flow, removed 0 selfloop flow, removed 1 redundant places. [2024-05-12 11:10:32,196 INFO L231 Difference]: Finished difference. Result has 45 places, 41 transitions, 129 flow [2024-05-12 11:10:32,197 INFO L264 CegarLoopForPetriNet]: {PETRI_ALPHABET=42, PETRI_DIFFERENCE_MINUEND_FLOW=88, PETRI_DIFFERENCE_MINUEND_PLACES=39, PETRI_DIFFERENCE_MINUEND_TRANSITIONS=37, PETRI_DIFFERENCE_SUBTRAHEND_LETTERS_WITH_MORE_CHANGERS_THAN_LOOPERS=2, PETRI_DIFFERENCE_SUBTRAHEND_LOOPER_ONLY_LETTERS=31, PETRI_DIFFERENCE_SUBTRAHEND_STATES=5, PETRI_FLOW=129, PETRI_PLACES=45, PETRI_TRANSITIONS=41} [2024-05-12 11:10:32,197 INFO L281 CegarLoopForPetriNet]: 40 programPoint places, 5 predicate places. [2024-05-12 11:10:32,198 INFO L495 AbstractCegarLoop]: Abstraction has has 45 places, 41 transitions, 129 flow [2024-05-12 11:10:32,198 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 11.25) internal successors, (45), 4 states have internal predecessors, (45), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-05-12 11:10:32,198 INFO L200 CegarLoopForPetriNet]: Found error trace [2024-05-12 11:10:32,198 INFO L208 CegarLoopForPetriNet]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-05-12 11:10:32,198 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2024-05-12 11:10:32,199 INFO L420 AbstractCegarLoop]: === Iteration 3 === Targeting t1Err0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONWITNESS_INVARIANT, ULTIMATE.startErr1ASSERT_VIOLATIONWITNESS_INVARIANT, ULTIMATE.startErr0INUSE_VIOLATIONSUFFICIENT_THREAD_INSTANCES (and 5 more)] === [2024-05-12 11:10:32,199 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2024-05-12 11:10:32,199 INFO L85 PathProgramCache]: Analyzing trace with hash 18027517, now seen corresponding path program 1 times [2024-05-12 11:10:32,199 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-05-12 11:10:32,200 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [662482502] [2024-05-12 11:10:32,200 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-05-12 11:10:32,200 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-05-12 11:10:32,216 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-05-12 11:10:32,284 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-05-12 11:10:32,285 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-05-12 11:10:32,285 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [662482502] [2024-05-12 11:10:32,285 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [662482502] provided 1 perfect and 0 imperfect interpolant sequences [2024-05-12 11:10:32,286 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-05-12 11:10:32,286 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2024-05-12 11:10:32,286 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2060359629] [2024-05-12 11:10:32,286 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-05-12 11:10:32,286 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2024-05-12 11:10:32,287 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-05-12 11:10:32,287 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2024-05-12 11:10:32,287 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2024-05-12 11:10:32,291 INFO L471 CegarLoopForPetriNet]: Number of universal loopers: 9 out of 42 [2024-05-12 11:10:32,291 INFO L103 encePairwiseOnDemand]: Start differencePairwiseOnDemand. First operand has 45 places, 41 transitions, 129 flow. Second operand has 4 states, 4 states have (on average 11.0) internal successors, (44), 4 states have internal predecessors, (44), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-05-12 11:10:32,291 INFO L112 encePairwiseOnDemand]: Universal subtrahend loopers provided by user. [2024-05-12 11:10:32,291 INFO L113 encePairwiseOnDemand]: Number of universal subtrahend loopers: 9 of 42 [2024-05-12 11:10:32,291 INFO L73 FinitePrefix]: Start finitePrefix. Operand will be constructed on-demand [2024-05-12 11:10:32,512 INFO L124 PetriNetUnfolderBase]: 861/1596 cut-off events. [2024-05-12 11:10:32,512 INFO L125 PetriNetUnfolderBase]: For 740/740 co-relation queries the response was YES. [2024-05-12 11:10:32,515 INFO L83 FinitePrefix]: Finished finitePrefix Result has 3686 conditions, 1596 events. 861/1596 cut-off events. For 740/740 co-relation queries the response was YES. Maximal size of possible extension queue 83. Compared 8770 event pairs, 209 based on Foata normal form. 0/1470 useless extension candidates. Maximal degree in co-relation 2655. Up to 990 conditions per place. [2024-05-12 11:10:32,522 INFO L140 encePairwiseOnDemand]: 38/42 looper letters, 66 selfloop transitions, 3 changer transitions 0/76 dead transitions. [2024-05-12 11:10:32,522 INFO L145 encePairwiseOnDemand]: Finished differencePairwiseOnDemand. Result has 48 places, 76 transitions, 372 flow [2024-05-12 11:10:32,523 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2024-05-12 11:10:32,523 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 4 states. [2024-05-12 11:10:32,523 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 4 states to 4 states and 99 transitions. [2024-05-12 11:10:32,524 INFO L516 CegarLoopForPetriNet]: DFA transition density 0.5892857142857143 [2024-05-12 11:10:32,524 INFO L175 Difference]: Start difference. First operand has 45 places, 41 transitions, 129 flow. Second operand 4 states and 99 transitions. [2024-05-12 11:10:32,524 INFO L82 GeneralOperation]: Start removeRedundantFlow. Operand has 48 places, 76 transitions, 372 flow [2024-05-12 11:10:32,526 INFO L88 GeneralOperation]: Finished removeRedundantFlow, result has has 46 places, 76 transitions, 369 flow, removed 0 selfloop flow, removed 2 redundant places. [2024-05-12 11:10:32,527 INFO L231 Difference]: Finished difference. Result has 47 places, 42 transitions, 140 flow [2024-05-12 11:10:32,527 INFO L264 CegarLoopForPetriNet]: {PETRI_ALPHABET=42, PETRI_DIFFERENCE_MINUEND_FLOW=126, PETRI_DIFFERENCE_MINUEND_PLACES=43, PETRI_DIFFERENCE_MINUEND_TRANSITIONS=41, PETRI_DIFFERENCE_SUBTRAHEND_LETTERS_WITH_MORE_CHANGERS_THAN_LOOPERS=2, PETRI_DIFFERENCE_SUBTRAHEND_LOOPER_ONLY_LETTERS=38, PETRI_DIFFERENCE_SUBTRAHEND_STATES=4, PETRI_FLOW=140, PETRI_PLACES=47, PETRI_TRANSITIONS=42} [2024-05-12 11:10:32,528 INFO L281 CegarLoopForPetriNet]: 40 programPoint places, 7 predicate places. [2024-05-12 11:10:32,528 INFO L495 AbstractCegarLoop]: Abstraction has has 47 places, 42 transitions, 140 flow [2024-05-12 11:10:32,528 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 11.0) internal successors, (44), 4 states have internal predecessors, (44), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-05-12 11:10:32,528 INFO L200 CegarLoopForPetriNet]: Found error trace [2024-05-12 11:10:32,529 INFO L208 CegarLoopForPetriNet]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-05-12 11:10:32,529 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2 [2024-05-12 11:10:32,529 INFO L420 AbstractCegarLoop]: === Iteration 4 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONWITNESS_INVARIANT === [ULTIMATE.startErr0ASSERT_VIOLATIONWITNESS_INVARIANT, ULTIMATE.startErr1ASSERT_VIOLATIONWITNESS_INVARIANT, ULTIMATE.startErr0INUSE_VIOLATIONSUFFICIENT_THREAD_INSTANCES (and 5 more)] === [2024-05-12 11:10:32,529 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2024-05-12 11:10:32,530 INFO L85 PathProgramCache]: Analyzing trace with hash -908822500, now seen corresponding path program 1 times [2024-05-12 11:10:32,530 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-05-12 11:10:32,530 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2003212426] [2024-05-12 11:10:32,530 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-05-12 11:10:32,530 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-05-12 11:10:32,546 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-05-12 11:10:32,633 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-05-12 11:10:32,634 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-05-12 11:10:32,634 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2003212426] [2024-05-12 11:10:32,634 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2003212426] provided 1 perfect and 0 imperfect interpolant sequences [2024-05-12 11:10:32,634 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-05-12 11:10:32,634 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2024-05-12 11:10:32,635 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1832315582] [2024-05-12 11:10:32,635 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-05-12 11:10:32,635 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2024-05-12 11:10:32,635 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-05-12 11:10:32,636 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2024-05-12 11:10:32,637 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2024-05-12 11:10:32,639 INFO L471 CegarLoopForPetriNet]: Number of universal loopers: 9 out of 42 [2024-05-12 11:10:32,639 INFO L103 encePairwiseOnDemand]: Start differencePairwiseOnDemand. First operand has 47 places, 42 transitions, 140 flow. Second operand has 4 states, 4 states have (on average 11.75) internal successors, (47), 4 states have internal predecessors, (47), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-05-12 11:10:32,639 INFO L112 encePairwiseOnDemand]: Universal subtrahend loopers provided by user. [2024-05-12 11:10:32,639 INFO L113 encePairwiseOnDemand]: Number of universal subtrahend loopers: 9 of 42 [2024-05-12 11:10:32,639 INFO L73 FinitePrefix]: Start finitePrefix. Operand will be constructed on-demand [2024-05-12 11:10:32,927 INFO L124 PetriNetUnfolderBase]: 1243/2298 cut-off events. [2024-05-12 11:10:32,927 INFO L125 PetriNetUnfolderBase]: For 1281/1287 co-relation queries the response was YES. [2024-05-12 11:10:32,932 INFO L83 FinitePrefix]: Finished finitePrefix Result has 5457 conditions, 2298 events. 1243/2298 cut-off events. For 1281/1287 co-relation queries the response was YES. Maximal size of possible extension queue 95. Compared 12915 event pairs, 249 based on Foata normal form. 42/2158 useless extension candidates. Maximal degree in co-relation 4475. Up to 913 conditions per place. [2024-05-12 11:10:32,942 INFO L140 encePairwiseOnDemand]: 37/42 looper letters, 73 selfloop transitions, 3 changer transitions 0/83 dead transitions. [2024-05-12 11:10:32,943 INFO L145 encePairwiseOnDemand]: Finished differencePairwiseOnDemand. Result has 49 places, 83 transitions, 423 flow [2024-05-12 11:10:32,943 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2024-05-12 11:10:32,943 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 4 states. [2024-05-12 11:10:32,944 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 4 states to 4 states and 102 transitions. [2024-05-12 11:10:32,946 INFO L516 CegarLoopForPetriNet]: DFA transition density 0.6071428571428571 [2024-05-12 11:10:32,946 INFO L175 Difference]: Start difference. First operand has 47 places, 42 transitions, 140 flow. Second operand 4 states and 102 transitions. [2024-05-12 11:10:32,946 INFO L82 GeneralOperation]: Start removeRedundantFlow. Operand has 49 places, 83 transitions, 423 flow [2024-05-12 11:10:32,949 INFO L88 GeneralOperation]: Finished removeRedundantFlow, result has has 47 places, 83 transitions, 418 flow, removed 0 selfloop flow, removed 2 redundant places. [2024-05-12 11:10:32,951 INFO L231 Difference]: Finished difference. Result has 48 places, 42 transitions, 144 flow [2024-05-12 11:10:32,951 INFO L264 CegarLoopForPetriNet]: {PETRI_ALPHABET=42, PETRI_DIFFERENCE_MINUEND_FLOW=130, PETRI_DIFFERENCE_MINUEND_PLACES=44, PETRI_DIFFERENCE_MINUEND_TRANSITIONS=41, PETRI_DIFFERENCE_SUBTRAHEND_LETTERS_WITH_MORE_CHANGERS_THAN_LOOPERS=2, PETRI_DIFFERENCE_SUBTRAHEND_LOOPER_ONLY_LETTERS=38, PETRI_DIFFERENCE_SUBTRAHEND_STATES=4, PETRI_FLOW=144, PETRI_PLACES=48, PETRI_TRANSITIONS=42} [2024-05-12 11:10:32,953 INFO L281 CegarLoopForPetriNet]: 40 programPoint places, 8 predicate places. [2024-05-12 11:10:32,953 INFO L495 AbstractCegarLoop]: Abstraction has has 48 places, 42 transitions, 144 flow [2024-05-12 11:10:32,953 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 11.75) internal successors, (47), 4 states have internal predecessors, (47), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-05-12 11:10:32,953 INFO L200 CegarLoopForPetriNet]: Found error trace [2024-05-12 11:10:32,953 INFO L208 CegarLoopForPetriNet]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-05-12 11:10:32,953 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3 [2024-05-12 11:10:32,954 INFO L420 AbstractCegarLoop]: === Iteration 5 === Targeting t2Err0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONWITNESS_INVARIANT, ULTIMATE.startErr1ASSERT_VIOLATIONWITNESS_INVARIANT, ULTIMATE.startErr0INUSE_VIOLATIONSUFFICIENT_THREAD_INSTANCES (and 5 more)] === [2024-05-12 11:10:32,954 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2024-05-12 11:10:32,954 INFO L85 PathProgramCache]: Analyzing trace with hash -991922220, now seen corresponding path program 1 times [2024-05-12 11:10:32,954 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-05-12 11:10:32,955 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [391382380] [2024-05-12 11:10:32,955 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-05-12 11:10:32,955 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-05-12 11:10:32,990 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-05-12 11:10:33,086 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-05-12 11:10:33,086 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-05-12 11:10:33,086 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [391382380] [2024-05-12 11:10:33,087 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [391382380] provided 1 perfect and 0 imperfect interpolant sequences [2024-05-12 11:10:33,087 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-05-12 11:10:33,087 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2024-05-12 11:10:33,087 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [648413599] [2024-05-12 11:10:33,088 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-05-12 11:10:33,089 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2024-05-12 11:10:33,089 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-05-12 11:10:33,092 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2024-05-12 11:10:33,092 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2024-05-12 11:10:33,098 INFO L471 CegarLoopForPetriNet]: Number of universal loopers: 10 out of 42 [2024-05-12 11:10:33,098 INFO L103 encePairwiseOnDemand]: Start differencePairwiseOnDemand. First operand has 48 places, 42 transitions, 144 flow. Second operand has 3 states, 3 states have (on average 13.666666666666666) internal successors, (41), 3 states have internal predecessors, (41), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-05-12 11:10:33,103 INFO L112 encePairwiseOnDemand]: Universal subtrahend loopers provided by user. [2024-05-12 11:10:33,104 INFO L113 encePairwiseOnDemand]: Number of universal subtrahend loopers: 10 of 42 [2024-05-12 11:10:33,104 INFO L73 FinitePrefix]: Start finitePrefix. Operand will be constructed on-demand [2024-05-12 11:10:33,376 INFO L124 PetriNetUnfolderBase]: 1142/2084 cut-off events. [2024-05-12 11:10:33,376 INFO L125 PetriNetUnfolderBase]: For 1260/1271 co-relation queries the response was YES. [2024-05-12 11:10:33,381 INFO L83 FinitePrefix]: Finished finitePrefix Result has 5055 conditions, 2084 events. 1142/2084 cut-off events. For 1260/1271 co-relation queries the response was YES. Maximal size of possible extension queue 95. Compared 11376 event pairs, 439 based on Foata normal form. 16/1952 useless extension candidates. Maximal degree in co-relation 4200. Up to 1457 conditions per place. [2024-05-12 11:10:33,390 INFO L140 encePairwiseOnDemand]: 39/42 looper letters, 47 selfloop transitions, 2 changer transitions 3/59 dead transitions. [2024-05-12 11:10:33,390 INFO L145 encePairwiseOnDemand]: Finished differencePairwiseOnDemand. Result has 50 places, 59 transitions, 301 flow [2024-05-12 11:10:33,391 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2024-05-12 11:10:33,391 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 3 states. [2024-05-12 11:10:33,393 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 3 states to 3 states and 76 transitions. [2024-05-12 11:10:33,393 INFO L516 CegarLoopForPetriNet]: DFA transition density 0.6031746031746031 [2024-05-12 11:10:33,393 INFO L175 Difference]: Start difference. First operand has 48 places, 42 transitions, 144 flow. Second operand 3 states and 76 transitions. [2024-05-12 11:10:33,393 INFO L82 GeneralOperation]: Start removeRedundantFlow. Operand has 50 places, 59 transitions, 301 flow [2024-05-12 11:10:33,396 INFO L88 GeneralOperation]: Finished removeRedundantFlow, result has has 48 places, 59 transitions, 297 flow, removed 0 selfloop flow, removed 2 redundant places. [2024-05-12 11:10:33,398 INFO L231 Difference]: Finished difference. Result has 49 places, 43 transitions, 154 flow [2024-05-12 11:10:33,398 INFO L264 CegarLoopForPetriNet]: {PETRI_ALPHABET=42, PETRI_DIFFERENCE_MINUEND_FLOW=140, PETRI_DIFFERENCE_MINUEND_PLACES=46, PETRI_DIFFERENCE_MINUEND_TRANSITIONS=42, PETRI_DIFFERENCE_SUBTRAHEND_LETTERS_WITH_MORE_CHANGERS_THAN_LOOPERS=1, PETRI_DIFFERENCE_SUBTRAHEND_LOOPER_ONLY_LETTERS=40, PETRI_DIFFERENCE_SUBTRAHEND_STATES=3, PETRI_FLOW=154, PETRI_PLACES=49, PETRI_TRANSITIONS=43} [2024-05-12 11:10:33,400 INFO L281 CegarLoopForPetriNet]: 40 programPoint places, 9 predicate places. [2024-05-12 11:10:33,400 INFO L495 AbstractCegarLoop]: Abstraction has has 49 places, 43 transitions, 154 flow [2024-05-12 11:10:33,400 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 13.666666666666666) internal successors, (41), 3 states have internal predecessors, (41), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-05-12 11:10:33,400 INFO L200 CegarLoopForPetriNet]: Found error trace [2024-05-12 11:10:33,401 INFO L208 CegarLoopForPetriNet]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-05-12 11:10:33,401 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4 [2024-05-12 11:10:33,401 INFO L420 AbstractCegarLoop]: === Iteration 6 === Targeting t1Err0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONWITNESS_INVARIANT, ULTIMATE.startErr1ASSERT_VIOLATIONWITNESS_INVARIANT, ULTIMATE.startErr0INUSE_VIOLATIONSUFFICIENT_THREAD_INSTANCES (and 5 more)] === [2024-05-12 11:10:33,402 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2024-05-12 11:10:33,402 INFO L85 PathProgramCache]: Analyzing trace with hash -1830051256, now seen corresponding path program 1 times [2024-05-12 11:10:33,402 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-05-12 11:10:33,402 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1634932374] [2024-05-12 11:10:33,402 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-05-12 11:10:33,402 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-05-12 11:10:33,425 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-05-12 11:10:33,552 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-05-12 11:10:33,552 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-05-12 11:10:33,553 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1634932374] [2024-05-12 11:10:33,553 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1634932374] provided 0 perfect and 1 imperfect interpolant sequences [2024-05-12 11:10:33,557 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [580704218] [2024-05-12 11:10:33,557 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-05-12 11:10:33,557 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-05-12 11:10:33,557 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-05-12 11:10:33,564 INFO L229 MonitoredProcess]: Starting monitored process 2 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-05-12 11:10:33,568 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2024-05-12 11:10:33,676 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-05-12 11:10:33,678 INFO L262 TraceCheckSpWp]: Trace formula consists of 159 conjuncts, 7 conjunts are in the unsatisfiable core [2024-05-12 11:10:33,693 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2024-05-12 11:10:33,788 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 1 [2024-05-12 11:10:33,892 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-05-12 11:10:33,893 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2024-05-12 11:10:33,992 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-05-12 11:10:33,993 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [580704218] provided 0 perfect and 2 imperfect interpolant sequences [2024-05-12 11:10:33,993 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-05-12 11:10:33,993 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 4, 4] total 10 [2024-05-12 11:10:33,993 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1002692214] [2024-05-12 11:10:33,993 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-05-12 11:10:33,995 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 11 states [2024-05-12 11:10:33,995 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-05-12 11:10:33,995 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2024-05-12 11:10:33,995 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=35, Invalid=75, Unknown=0, NotChecked=0, Total=110 [2024-05-12 11:10:33,999 INFO L471 CegarLoopForPetriNet]: Number of universal loopers: 9 out of 42 [2024-05-12 11:10:34,000 INFO L103 encePairwiseOnDemand]: Start differencePairwiseOnDemand. First operand has 49 places, 43 transitions, 154 flow. Second operand has 11 states, 11 states have (on average 12.545454545454545) internal successors, (138), 11 states have internal predecessors, (138), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-05-12 11:10:34,000 INFO L112 encePairwiseOnDemand]: Universal subtrahend loopers provided by user. [2024-05-12 11:10:34,000 INFO L113 encePairwiseOnDemand]: Number of universal subtrahend loopers: 9 of 42 [2024-05-12 11:10:34,000 INFO L73 FinitePrefix]: Start finitePrefix. Operand will be constructed on-demand [2024-05-12 11:10:35,045 INFO L124 PetriNetUnfolderBase]: 3600/6701 cut-off events. [2024-05-12 11:10:35,046 INFO L125 PetriNetUnfolderBase]: For 5093/5095 co-relation queries the response was YES. [2024-05-12 11:10:35,059 INFO L83 FinitePrefix]: Finished finitePrefix Result has 17109 conditions, 6701 events. 3600/6701 cut-off events. For 5093/5095 co-relation queries the response was YES. Maximal size of possible extension queue 184. Compared 42820 event pairs, 309 based on Foata normal form. 0/6429 useless extension candidates. Maximal degree in co-relation 15569. Up to 1529 conditions per place. [2024-05-12 11:10:35,093 INFO L140 encePairwiseOnDemand]: 36/42 looper letters, 214 selfloop transitions, 35 changer transitions 3/260 dead transitions. [2024-05-12 11:10:35,094 INFO L145 encePairwiseOnDemand]: Finished differencePairwiseOnDemand. Result has 62 places, 260 transitions, 1453 flow [2024-05-12 11:10:35,094 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2024-05-12 11:10:35,094 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 14 states. [2024-05-12 11:10:35,096 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 14 states to 14 states and 346 transitions. [2024-05-12 11:10:35,096 INFO L516 CegarLoopForPetriNet]: DFA transition density 0.5884353741496599 [2024-05-12 11:10:35,097 INFO L175 Difference]: Start difference. First operand has 49 places, 43 transitions, 154 flow. Second operand 14 states and 346 transitions. [2024-05-12 11:10:35,097 INFO L82 GeneralOperation]: Start removeRedundantFlow. Operand has 62 places, 260 transitions, 1453 flow [2024-05-12 11:10:35,101 INFO L88 GeneralOperation]: Finished removeRedundantFlow, result has has 61 places, 260 transitions, 1451 flow, removed 0 selfloop flow, removed 1 redundant places. [2024-05-12 11:10:35,103 INFO L231 Difference]: Finished difference. Result has 67 places, 81 transitions, 511 flow [2024-05-12 11:10:35,104 INFO L264 CegarLoopForPetriNet]: {PETRI_ALPHABET=42, PETRI_DIFFERENCE_MINUEND_FLOW=152, PETRI_DIFFERENCE_MINUEND_PLACES=48, PETRI_DIFFERENCE_MINUEND_TRANSITIONS=43, PETRI_DIFFERENCE_SUBTRAHEND_LETTERS_WITH_MORE_CHANGERS_THAN_LOOPERS=8, PETRI_DIFFERENCE_SUBTRAHEND_LOOPER_ONLY_LETTERS=35, PETRI_DIFFERENCE_SUBTRAHEND_STATES=14, PETRI_FLOW=511, PETRI_PLACES=67, PETRI_TRANSITIONS=81} [2024-05-12 11:10:35,106 INFO L281 CegarLoopForPetriNet]: 40 programPoint places, 27 predicate places. [2024-05-12 11:10:35,106 INFO L495 AbstractCegarLoop]: Abstraction has has 67 places, 81 transitions, 511 flow [2024-05-12 11:10:35,107 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 11 states, 11 states have (on average 12.545454545454545) internal successors, (138), 11 states have internal predecessors, (138), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-05-12 11:10:35,107 INFO L200 CegarLoopForPetriNet]: Found error trace [2024-05-12 11:10:35,107 INFO L208 CegarLoopForPetriNet]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-05-12 11:10:35,128 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Forceful destruction successful, exit code 0 [2024-05-12 11:10:35,328 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable5 [2024-05-12 11:10:35,328 INFO L420 AbstractCegarLoop]: === Iteration 7 === Targeting t2Err0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONWITNESS_INVARIANT, ULTIMATE.startErr1ASSERT_VIOLATIONWITNESS_INVARIANT, ULTIMATE.startErr0INUSE_VIOLATIONSUFFICIENT_THREAD_INSTANCES (and 5 more)] === [2024-05-12 11:10:35,328 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2024-05-12 11:10:35,328 INFO L85 PathProgramCache]: Analyzing trace with hash 985335707, now seen corresponding path program 1 times [2024-05-12 11:10:35,329 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-05-12 11:10:35,329 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [892669910] [2024-05-12 11:10:35,329 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-05-12 11:10:35,329 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-05-12 11:10:35,346 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-05-12 11:10:35,403 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-05-12 11:10:35,404 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-05-12 11:10:35,404 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [892669910] [2024-05-12 11:10:35,404 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [892669910] provided 1 perfect and 0 imperfect interpolant sequences [2024-05-12 11:10:35,404 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-05-12 11:10:35,404 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2024-05-12 11:10:35,405 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1103177060] [2024-05-12 11:10:35,405 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-05-12 11:10:35,405 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2024-05-12 11:10:35,405 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-05-12 11:10:35,406 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2024-05-12 11:10:35,406 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2024-05-12 11:10:35,406 INFO L471 CegarLoopForPetriNet]: Number of universal loopers: 11 out of 42 [2024-05-12 11:10:35,406 INFO L103 encePairwiseOnDemand]: Start differencePairwiseOnDemand. First operand has 67 places, 81 transitions, 511 flow. Second operand has 3 states, 3 states have (on average 16.0) internal successors, (48), 3 states have internal predecessors, (48), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-05-12 11:10:35,407 INFO L112 encePairwiseOnDemand]: Universal subtrahend loopers provided by user. [2024-05-12 11:10:35,407 INFO L113 encePairwiseOnDemand]: Number of universal subtrahend loopers: 11 of 42 [2024-05-12 11:10:35,407 INFO L73 FinitePrefix]: Start finitePrefix. Operand will be constructed on-demand [2024-05-12 11:10:35,810 INFO L124 PetriNetUnfolderBase]: 1579/3232 cut-off events. [2024-05-12 11:10:35,810 INFO L125 PetriNetUnfolderBase]: For 3328/3328 co-relation queries the response was YES. [2024-05-12 11:10:35,818 INFO L83 FinitePrefix]: Finished finitePrefix Result has 8337 conditions, 3232 events. 1579/3232 cut-off events. For 3328/3328 co-relation queries the response was YES. Maximal size of possible extension queue 87. Compared 18663 event pairs, 550 based on Foata normal form. 165/3352 useless extension candidates. Maximal degree in co-relation 7982. Up to 1507 conditions per place. [2024-05-12 11:10:35,833 INFO L140 encePairwiseOnDemand]: 38/42 looper letters, 56 selfloop transitions, 4 changer transitions 0/73 dead transitions. [2024-05-12 11:10:35,833 INFO L145 encePairwiseOnDemand]: Finished differencePairwiseOnDemand. Result has 67 places, 73 transitions, 482 flow [2024-05-12 11:10:35,834 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2024-05-12 11:10:35,834 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 3 states. [2024-05-12 11:10:35,834 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 3 states to 3 states and 75 transitions. [2024-05-12 11:10:35,834 INFO L516 CegarLoopForPetriNet]: DFA transition density 0.5952380952380952 [2024-05-12 11:10:35,835 INFO L175 Difference]: Start difference. First operand has 67 places, 81 transitions, 511 flow. Second operand 3 states and 75 transitions. [2024-05-12 11:10:35,835 INFO L82 GeneralOperation]: Start removeRedundantFlow. Operand has 67 places, 73 transitions, 482 flow [2024-05-12 11:10:35,848 INFO L88 GeneralOperation]: Finished removeRedundantFlow, result has has 61 places, 73 transitions, 427 flow, removed 21 selfloop flow, removed 6 redundant places. [2024-05-12 11:10:35,849 INFO L231 Difference]: Finished difference. Result has 61 places, 60 transitions, 286 flow [2024-05-12 11:10:35,850 INFO L264 CegarLoopForPetriNet]: {PETRI_ALPHABET=42, PETRI_DIFFERENCE_MINUEND_FLOW=278, PETRI_DIFFERENCE_MINUEND_PLACES=59, PETRI_DIFFERENCE_MINUEND_TRANSITIONS=60, PETRI_DIFFERENCE_SUBTRAHEND_LETTERS_WITH_MORE_CHANGERS_THAN_LOOPERS=4, PETRI_DIFFERENCE_SUBTRAHEND_LOOPER_ONLY_LETTERS=56, PETRI_DIFFERENCE_SUBTRAHEND_STATES=3, PETRI_FLOW=286, PETRI_PLACES=61, PETRI_TRANSITIONS=60} [2024-05-12 11:10:35,850 INFO L281 CegarLoopForPetriNet]: 40 programPoint places, 21 predicate places. [2024-05-12 11:10:35,850 INFO L495 AbstractCegarLoop]: Abstraction has has 61 places, 60 transitions, 286 flow [2024-05-12 11:10:35,851 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 16.0) internal successors, (48), 3 states have internal predecessors, (48), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-05-12 11:10:35,851 INFO L200 CegarLoopForPetriNet]: Found error trace [2024-05-12 11:10:35,851 INFO L208 CegarLoopForPetriNet]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-05-12 11:10:35,851 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6 [2024-05-12 11:10:35,851 INFO L420 AbstractCegarLoop]: === Iteration 8 === Targeting t2Err0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONWITNESS_INVARIANT, ULTIMATE.startErr1ASSERT_VIOLATIONWITNESS_INVARIANT, ULTIMATE.startErr0INUSE_VIOLATIONSUFFICIENT_THREAD_INSTANCES (and 5 more)] === [2024-05-12 11:10:35,852 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2024-05-12 11:10:35,852 INFO L85 PathProgramCache]: Analyzing trace with hash 830705398, now seen corresponding path program 1 times [2024-05-12 11:10:35,852 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-05-12 11:10:35,852 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [452525663] [2024-05-12 11:10:35,852 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-05-12 11:10:35,853 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-05-12 11:10:35,874 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-05-12 11:10:36,282 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-05-12 11:10:36,283 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-05-12 11:10:36,283 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [452525663] [2024-05-12 11:10:36,283 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [452525663] provided 1 perfect and 0 imperfect interpolant sequences [2024-05-12 11:10:36,283 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-05-12 11:10:36,283 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2024-05-12 11:10:36,284 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [746344963] [2024-05-12 11:10:36,284 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-05-12 11:10:36,284 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-05-12 11:10:36,285 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-05-12 11:10:36,285 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-05-12 11:10:36,285 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-05-12 11:10:36,293 INFO L471 CegarLoopForPetriNet]: Number of universal loopers: 9 out of 42 [2024-05-12 11:10:36,294 INFO L103 encePairwiseOnDemand]: Start differencePairwiseOnDemand. First operand has 61 places, 60 transitions, 286 flow. Second operand has 5 states, 5 states have (on average 12.2) internal successors, (61), 5 states have internal predecessors, (61), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-05-12 11:10:36,294 INFO L112 encePairwiseOnDemand]: Universal subtrahend loopers provided by user. [2024-05-12 11:10:36,294 INFO L113 encePairwiseOnDemand]: Number of universal subtrahend loopers: 9 of 42 [2024-05-12 11:10:36,294 INFO L73 FinitePrefix]: Start finitePrefix. Operand will be constructed on-demand [2024-05-12 11:10:36,765 INFO L124 PetriNetUnfolderBase]: 1629/3238 cut-off events. [2024-05-12 11:10:36,765 INFO L125 PetriNetUnfolderBase]: For 2934/2934 co-relation queries the response was YES. [2024-05-12 11:10:36,774 INFO L83 FinitePrefix]: Finished finitePrefix Result has 8158 conditions, 3238 events. 1629/3238 cut-off events. For 2934/2934 co-relation queries the response was YES. Maximal size of possible extension queue 92. Compared 18192 event pairs, 441 based on Foata normal form. 0/3195 useless extension candidates. Maximal degree in co-relation 6777. Up to 2256 conditions per place. [2024-05-12 11:10:36,788 INFO L140 encePairwiseOnDemand]: 37/42 looper letters, 82 selfloop transitions, 5 changer transitions 3/98 dead transitions. [2024-05-12 11:10:36,788 INFO L145 encePairwiseOnDemand]: Finished differencePairwiseOnDemand. Result has 65 places, 98 transitions, 580 flow [2024-05-12 11:10:36,789 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-05-12 11:10:36,789 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 5 states. [2024-05-12 11:10:36,790 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 115 transitions. [2024-05-12 11:10:36,790 INFO L516 CegarLoopForPetriNet]: DFA transition density 0.5476190476190477 [2024-05-12 11:10:36,790 INFO L175 Difference]: Start difference. First operand has 61 places, 60 transitions, 286 flow. Second operand 5 states and 115 transitions. [2024-05-12 11:10:36,790 INFO L82 GeneralOperation]: Start removeRedundantFlow. Operand has 65 places, 98 transitions, 580 flow [2024-05-12 11:10:36,796 INFO L88 GeneralOperation]: Finished removeRedundantFlow, result has has 63 places, 98 transitions, 558 flow, removed 0 selfloop flow, removed 2 redundant places. [2024-05-12 11:10:36,798 INFO L231 Difference]: Finished difference. Result has 65 places, 62 transitions, 306 flow [2024-05-12 11:10:36,799 INFO L264 CegarLoopForPetriNet]: {PETRI_ALPHABET=42, PETRI_DIFFERENCE_MINUEND_FLOW=278, PETRI_DIFFERENCE_MINUEND_PLACES=59, PETRI_DIFFERENCE_MINUEND_TRANSITIONS=60, PETRI_DIFFERENCE_SUBTRAHEND_LETTERS_WITH_MORE_CHANGERS_THAN_LOOPERS=3, PETRI_DIFFERENCE_SUBTRAHEND_LOOPER_ONLY_LETTERS=55, PETRI_DIFFERENCE_SUBTRAHEND_STATES=5, PETRI_FLOW=306, PETRI_PLACES=65, PETRI_TRANSITIONS=62} [2024-05-12 11:10:36,800 INFO L281 CegarLoopForPetriNet]: 40 programPoint places, 25 predicate places. [2024-05-12 11:10:36,800 INFO L495 AbstractCegarLoop]: Abstraction has has 65 places, 62 transitions, 306 flow [2024-05-12 11:10:36,803 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 12.2) internal successors, (61), 5 states have internal predecessors, (61), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-05-12 11:10:36,803 INFO L200 CegarLoopForPetriNet]: Found error trace [2024-05-12 11:10:36,803 INFO L208 CegarLoopForPetriNet]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-05-12 11:10:36,803 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7 [2024-05-12 11:10:36,804 INFO L420 AbstractCegarLoop]: === Iteration 9 === Targeting ULTIMATE.startErr1ASSERT_VIOLATIONWITNESS_INVARIANT === [ULTIMATE.startErr0ASSERT_VIOLATIONWITNESS_INVARIANT, ULTIMATE.startErr1ASSERT_VIOLATIONWITNESS_INVARIANT, ULTIMATE.startErr0INUSE_VIOLATIONSUFFICIENT_THREAD_INSTANCES (and 5 more)] === [2024-05-12 11:10:36,805 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2024-05-12 11:10:36,805 INFO L85 PathProgramCache]: Analyzing trace with hash 41326094, now seen corresponding path program 1 times [2024-05-12 11:10:36,805 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-05-12 11:10:36,807 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1637635355] [2024-05-12 11:10:36,808 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-05-12 11:10:36,808 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-05-12 11:10:36,834 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-05-12 11:10:36,986 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-05-12 11:10:36,986 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-05-12 11:10:36,986 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1637635355] [2024-05-12 11:10:36,987 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1637635355] provided 1 perfect and 0 imperfect interpolant sequences [2024-05-12 11:10:36,987 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-05-12 11:10:36,987 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2024-05-12 11:10:36,987 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1295012151] [2024-05-12 11:10:36,987 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-05-12 11:10:36,988 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-05-12 11:10:36,988 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-05-12 11:10:36,988 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-05-12 11:10:36,988 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=11, Unknown=0, NotChecked=0, Total=20 [2024-05-12 11:10:36,992 INFO L471 CegarLoopForPetriNet]: Number of universal loopers: 8 out of 42 [2024-05-12 11:10:36,993 INFO L103 encePairwiseOnDemand]: Start differencePairwiseOnDemand. First operand has 65 places, 62 transitions, 306 flow. Second operand has 5 states, 5 states have (on average 12.0) internal successors, (60), 5 states have internal predecessors, (60), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-05-12 11:10:36,993 INFO L112 encePairwiseOnDemand]: Universal subtrahend loopers provided by user. [2024-05-12 11:10:36,993 INFO L113 encePairwiseOnDemand]: Number of universal subtrahend loopers: 8 of 42 [2024-05-12 11:10:36,995 INFO L73 FinitePrefix]: Start finitePrefix. Operand will be constructed on-demand [2024-05-12 11:10:37,493 INFO L124 PetriNetUnfolderBase]: 2055/3912 cut-off events. [2024-05-12 11:10:37,494 INFO L125 PetriNetUnfolderBase]: For 2688/2688 co-relation queries the response was YES. [2024-05-12 11:10:37,504 INFO L83 FinitePrefix]: Finished finitePrefix Result has 9443 conditions, 3912 events. 2055/3912 cut-off events. For 2688/2688 co-relation queries the response was YES. Maximal size of possible extension queue 108. Compared 21489 event pairs, 253 based on Foata normal form. 18/3876 useless extension candidates. Maximal degree in co-relation 7955. Up to 1491 conditions per place. [2024-05-12 11:10:37,517 INFO L140 encePairwiseOnDemand]: 37/42 looper letters, 100 selfloop transitions, 9 changer transitions 3/118 dead transitions. [2024-05-12 11:10:37,518 INFO L145 encePairwiseOnDemand]: Finished differencePairwiseOnDemand. Result has 69 places, 118 transitions, 738 flow [2024-05-12 11:10:37,518 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-05-12 11:10:37,518 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 5 states. [2024-05-12 11:10:37,519 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 120 transitions. [2024-05-12 11:10:37,519 INFO L516 CegarLoopForPetriNet]: DFA transition density 0.5714285714285714 [2024-05-12 11:10:37,519 INFO L175 Difference]: Start difference. First operand has 65 places, 62 transitions, 306 flow. Second operand 5 states and 120 transitions. [2024-05-12 11:10:37,519 INFO L82 GeneralOperation]: Start removeRedundantFlow. Operand has 69 places, 118 transitions, 738 flow [2024-05-12 11:10:37,527 INFO L88 GeneralOperation]: Finished removeRedundantFlow, result has has 67 places, 118 transitions, 733 flow, removed 0 selfloop flow, removed 2 redundant places. [2024-05-12 11:10:37,529 INFO L231 Difference]: Finished difference. Result has 68 places, 65 transitions, 352 flow [2024-05-12 11:10:37,529 INFO L264 CegarLoopForPetriNet]: {PETRI_ALPHABET=42, PETRI_DIFFERENCE_MINUEND_FLOW=301, PETRI_DIFFERENCE_MINUEND_PLACES=63, PETRI_DIFFERENCE_MINUEND_TRANSITIONS=62, PETRI_DIFFERENCE_SUBTRAHEND_LETTERS_WITH_MORE_CHANGERS_THAN_LOOPERS=6, PETRI_DIFFERENCE_SUBTRAHEND_LOOPER_ONLY_LETTERS=53, PETRI_DIFFERENCE_SUBTRAHEND_STATES=5, PETRI_FLOW=352, PETRI_PLACES=68, PETRI_TRANSITIONS=65} [2024-05-12 11:10:37,530 INFO L281 CegarLoopForPetriNet]: 40 programPoint places, 28 predicate places. [2024-05-12 11:10:37,530 INFO L495 AbstractCegarLoop]: Abstraction has has 68 places, 65 transitions, 352 flow [2024-05-12 11:10:37,530 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 12.0) internal successors, (60), 5 states have internal predecessors, (60), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-05-12 11:10:37,530 INFO L200 CegarLoopForPetriNet]: Found error trace [2024-05-12 11:10:37,530 INFO L208 CegarLoopForPetriNet]: trace histogram [2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-05-12 11:10:37,531 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8 [2024-05-12 11:10:37,531 INFO L420 AbstractCegarLoop]: === Iteration 10 === Targeting t2Err0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONWITNESS_INVARIANT, ULTIMATE.startErr1ASSERT_VIOLATIONWITNESS_INVARIANT, ULTIMATE.startErr0INUSE_VIOLATIONSUFFICIENT_THREAD_INSTANCES (and 5 more)] === [2024-05-12 11:10:37,531 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2024-05-12 11:10:37,531 INFO L85 PathProgramCache]: Analyzing trace with hash 1477730341, now seen corresponding path program 1 times [2024-05-12 11:10:37,531 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-05-12 11:10:37,532 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [215036907] [2024-05-12 11:10:37,532 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-05-12 11:10:37,532 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-05-12 11:10:37,556 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-05-12 11:10:37,904 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-05-12 11:10:37,905 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-05-12 11:10:37,905 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [215036907] [2024-05-12 11:10:37,905 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [215036907] provided 0 perfect and 1 imperfect interpolant sequences [2024-05-12 11:10:37,905 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1455304741] [2024-05-12 11:10:37,905 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-05-12 11:10:37,906 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-05-12 11:10:37,906 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-05-12 11:10:37,907 INFO L229 MonitoredProcess]: Starting monitored process 3 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-05-12 11:10:37,919 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2024-05-12 11:10:38,046 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-05-12 11:10:38,048 INFO L262 TraceCheckSpWp]: Trace formula consists of 216 conjuncts, 11 conjunts are in the unsatisfiable core [2024-05-12 11:10:38,053 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2024-05-12 11:10:38,075 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 1 [2024-05-12 11:10:38,130 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 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 19 treesize of output 1 [2024-05-12 11:10:38,212 INFO L378 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 68 treesize of output 32 [2024-05-12 11:10:38,259 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-05-12 11:10:38,260 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2024-05-12 11:10:38,621 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 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 9 treesize of output 1 [2024-05-12 11:10:38,693 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-05-12 11:10:38,693 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1455304741] provided 0 perfect and 2 imperfect interpolant sequences [2024-05-12 11:10:38,693 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-05-12 11:10:38,693 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 5, 5] total 12 [2024-05-12 11:10:38,693 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [927326686] [2024-05-12 11:10:38,694 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-05-12 11:10:38,694 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 13 states [2024-05-12 11:10:38,694 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-05-12 11:10:38,695 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2024-05-12 11:10:38,695 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=38, Invalid=118, Unknown=0, NotChecked=0, Total=156 [2024-05-12 11:10:38,700 INFO L471 CegarLoopForPetriNet]: Number of universal loopers: 9 out of 42 [2024-05-12 11:10:38,701 INFO L103 encePairwiseOnDemand]: Start differencePairwiseOnDemand. First operand has 68 places, 65 transitions, 352 flow. Second operand has 13 states, 13 states have (on average 13.076923076923077) internal successors, (170), 13 states have internal predecessors, (170), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-05-12 11:10:38,701 INFO L112 encePairwiseOnDemand]: Universal subtrahend loopers provided by user. [2024-05-12 11:10:38,701 INFO L113 encePairwiseOnDemand]: Number of universal subtrahend loopers: 9 of 42 [2024-05-12 11:10:38,701 INFO L73 FinitePrefix]: Start finitePrefix. Operand will be constructed on-demand [2024-05-12 11:10:39,720 INFO L124 PetriNetUnfolderBase]: 3055/6030 cut-off events. [2024-05-12 11:10:39,720 INFO L125 PetriNetUnfolderBase]: For 6156/6156 co-relation queries the response was YES. [2024-05-12 11:10:39,736 INFO L83 FinitePrefix]: Finished finitePrefix Result has 14695 conditions, 6030 events. 3055/6030 cut-off events. For 6156/6156 co-relation queries the response was YES. Maximal size of possible extension queue 135. Compared 36921 event pairs, 638 based on Foata normal form. 99/6069 useless extension candidates. Maximal degree in co-relation 12967. Up to 772 conditions per place. [2024-05-12 11:10:39,754 INFO L140 encePairwiseOnDemand]: 36/42 looper letters, 181 selfloop transitions, 32 changer transitions 0/222 dead transitions. [2024-05-12 11:10:39,754 INFO L145 encePairwiseOnDemand]: Finished differencePairwiseOnDemand. Result has 78 places, 222 transitions, 1353 flow [2024-05-12 11:10:39,755 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2024-05-12 11:10:39,755 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 12 states. [2024-05-12 11:10:39,756 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 12 states to 12 states and 295 transitions. [2024-05-12 11:10:39,756 INFO L516 CegarLoopForPetriNet]: DFA transition density 0.5853174603174603 [2024-05-12 11:10:39,757 INFO L175 Difference]: Start difference. First operand has 68 places, 65 transitions, 352 flow. Second operand 12 states and 295 transitions. [2024-05-12 11:10:39,757 INFO L82 GeneralOperation]: Start removeRedundantFlow. Operand has 78 places, 222 transitions, 1353 flow [2024-05-12 11:10:39,767 INFO L88 GeneralOperation]: Finished removeRedundantFlow, result has has 75 places, 222 transitions, 1330 flow, removed 5 selfloop flow, removed 3 redundant places. [2024-05-12 11:10:39,770 INFO L231 Difference]: Finished difference. Result has 85 places, 86 transitions, 644 flow [2024-05-12 11:10:39,770 INFO L264 CegarLoopForPetriNet]: {PETRI_ALPHABET=42, PETRI_DIFFERENCE_MINUEND_FLOW=294, PETRI_DIFFERENCE_MINUEND_PLACES=64, PETRI_DIFFERENCE_MINUEND_TRANSITIONS=59, PETRI_DIFFERENCE_SUBTRAHEND_LETTERS_WITH_MORE_CHANGERS_THAN_LOOPERS=11, PETRI_DIFFERENCE_SUBTRAHEND_LOOPER_ONLY_LETTERS=40, PETRI_DIFFERENCE_SUBTRAHEND_STATES=12, PETRI_FLOW=644, PETRI_PLACES=85, PETRI_TRANSITIONS=86} [2024-05-12 11:10:39,771 INFO L281 CegarLoopForPetriNet]: 40 programPoint places, 45 predicate places. [2024-05-12 11:10:39,771 INFO L495 AbstractCegarLoop]: Abstraction has has 85 places, 86 transitions, 644 flow [2024-05-12 11:10:39,771 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 13 states, 13 states have (on average 13.076923076923077) internal successors, (170), 13 states have internal predecessors, (170), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-05-12 11:10:39,771 INFO L200 CegarLoopForPetriNet]: Found error trace [2024-05-12 11:10:39,771 INFO L208 CegarLoopForPetriNet]: trace histogram [2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-05-12 11:10:39,788 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2024-05-12 11:10:39,986 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,SelfDestructingSolverStorable9 [2024-05-12 11:10:39,986 INFO L420 AbstractCegarLoop]: === Iteration 11 === Targeting t2Err0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONWITNESS_INVARIANT, ULTIMATE.startErr1ASSERT_VIOLATIONWITNESS_INVARIANT, ULTIMATE.startErr0INUSE_VIOLATIONSUFFICIENT_THREAD_INSTANCES (and 5 more)] === [2024-05-12 11:10:39,987 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2024-05-12 11:10:39,987 INFO L85 PathProgramCache]: Analyzing trace with hash -972307287, now seen corresponding path program 1 times [2024-05-12 11:10:39,987 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-05-12 11:10:39,987 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [460975202] [2024-05-12 11:10:39,987 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-05-12 11:10:39,987 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-05-12 11:10:40,027 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-05-12 11:10:40,028 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-05-12 11:10:40,052 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-05-12 11:10:40,080 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-05-12 11:10:40,080 INFO L360 BasicCegarLoop]: Counterexample is feasible [2024-05-12 11:10:40,081 INFO L805 garLoopResultBuilder]: Registering result UNSAFE for location t2Err0ASSERT_VIOLATIONERROR_FUNCTION (7 of 8 remaining) [2024-05-12 11:10:40,083 INFO L805 garLoopResultBuilder]: Registering result UNKNOWN for location ULTIMATE.startErr0ASSERT_VIOLATIONWITNESS_INVARIANT (6 of 8 remaining) [2024-05-12 11:10:40,083 INFO L805 garLoopResultBuilder]: Registering result UNKNOWN for location ULTIMATE.startErr1ASSERT_VIOLATIONWITNESS_INVARIANT (5 of 8 remaining) [2024-05-12 11:10:40,083 INFO L805 garLoopResultBuilder]: Registering result UNKNOWN for location ULTIMATE.startErr0INUSE_VIOLATIONSUFFICIENT_THREAD_INSTANCES (4 of 8 remaining) [2024-05-12 11:10:40,083 INFO L805 garLoopResultBuilder]: Registering result UNKNOWN for location ULTIMATE.startErr1INUSE_VIOLATIONSUFFICIENT_THREAD_INSTANCES (3 of 8 remaining) [2024-05-12 11:10:40,084 INFO L805 garLoopResultBuilder]: Registering result UNKNOWN for location t1Err0ASSERT_VIOLATIONERROR_FUNCTION (2 of 8 remaining) [2024-05-12 11:10:40,084 INFO L805 garLoopResultBuilder]: Registering result UNKNOWN for location t2Err0ASSERT_VIOLATIONERROR_FUNCTION (1 of 8 remaining) [2024-05-12 11:10:40,084 INFO L805 garLoopResultBuilder]: Registering result UNKNOWN for location t1Err0ASSERT_VIOLATIONERROR_FUNCTION (0 of 8 remaining) [2024-05-12 11:10:40,084 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable10 [2024-05-12 11:10:40,084 INFO L445 BasicCegarLoop]: Path program histogram: [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-05-12 11:10:40,089 INFO L229 ceAbstractionStarter]: Analysis of concurrent program completed with 1 thread instances [2024-05-12 11:10:40,089 INFO L179 ceAbstractionStarter]: Computing trace abstraction results [2024-05-12 11:10:40,128 INFO L507 ceAbstractionStarter]: Automizer considered 2 witness invariants [2024-05-12 11:10:40,128 INFO L508 ceAbstractionStarter]: WitnessConsidered=2 [2024-05-12 11:10:40,129 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 12.05 11:10:40 BasicIcfg [2024-05-12 11:10:40,129 INFO L131 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2024-05-12 11:10:40,130 INFO L158 Benchmark]: Toolchain (without parser) took 10909.51ms. Allocated memory was 157.3MB in the beginning and 501.2MB in the end (delta: 343.9MB). Free memory was 90.7MB in the beginning and 224.5MB in the end (delta: -133.8MB). Peak memory consumption was 210.8MB. Max. memory is 16.1GB. [2024-05-12 11:10:40,130 INFO L158 Benchmark]: Witness Parser took 0.20ms. Allocated memory is still 96.5MB. Free memory was 51.2MB in the beginning and 51.1MB in the end (delta: 92.3kB). There was no memory consumed. Max. memory is 16.1GB. [2024-05-12 11:10:40,130 INFO L158 Benchmark]: CDTParser took 0.10ms. Allocated memory is still 96.5MB. Free memory is still 48.0MB. There was no memory consumed. Max. memory is 16.1GB. [2024-05-12 11:10:40,131 INFO L158 Benchmark]: CACSL2BoogieTranslator took 753.96ms. Allocated memory is still 157.3MB. Free memory was 90.7MB in the beginning and 98.7MB in the end (delta: -8.0MB). Peak memory consumption was 7.7MB. Max. memory is 16.1GB. [2024-05-12 11:10:40,131 INFO L158 Benchmark]: Boogie Procedure Inliner took 62.16ms. Allocated memory is still 157.3MB. Free memory was 98.7MB in the beginning and 96.2MB in the end (delta: 2.5MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. [2024-05-12 11:10:40,131 INFO L158 Benchmark]: Boogie Preprocessor took 66.57ms. Allocated memory is still 157.3MB. Free memory was 96.2MB in the beginning and 93.1MB in the end (delta: 3.1MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. [2024-05-12 11:10:40,132 INFO L158 Benchmark]: RCFGBuilder took 804.34ms. Allocated memory was 157.3MB in the beginning and 197.1MB in the end (delta: 39.8MB). Free memory was 93.1MB in the beginning and 133.1MB in the end (delta: -40.0MB). Peak memory consumption was 30.3MB. Max. memory is 16.1GB. [2024-05-12 11:10:40,132 INFO L158 Benchmark]: TraceAbstraction took 9214.69ms. Allocated memory was 197.1MB in the beginning and 501.2MB in the end (delta: 304.1MB). Free memory was 133.1MB in the beginning and 224.5MB in the end (delta: -91.3MB). Peak memory consumption was 212.7MB. Max. memory is 16.1GB. [2024-05-12 11:10:40,133 INFO L338 ainManager$Toolchain]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * Witness Parser took 0.20ms. Allocated memory is still 96.5MB. Free memory was 51.2MB in the beginning and 51.1MB in the end (delta: 92.3kB). There was no memory consumed. Max. memory is 16.1GB. * CDTParser took 0.10ms. Allocated memory is still 96.5MB. Free memory is still 48.0MB. There was no memory consumed. Max. memory is 16.1GB. * CACSL2BoogieTranslator took 753.96ms. Allocated memory is still 157.3MB. Free memory was 90.7MB in the beginning and 98.7MB in the end (delta: -8.0MB). Peak memory consumption was 7.7MB. Max. memory is 16.1GB. * Boogie Procedure Inliner took 62.16ms. Allocated memory is still 157.3MB. Free memory was 98.7MB in the beginning and 96.2MB in the end (delta: 2.5MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. * Boogie Preprocessor took 66.57ms. Allocated memory is still 157.3MB. Free memory was 96.2MB in the beginning and 93.1MB in the end (delta: 3.1MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. * RCFGBuilder took 804.34ms. Allocated memory was 157.3MB in the beginning and 197.1MB in the end (delta: 39.8MB). Free memory was 93.1MB in the beginning and 133.1MB in the end (delta: -40.0MB). Peak memory consumption was 30.3MB. Max. memory is 16.1GB. * TraceAbstraction took 9214.69ms. Allocated memory was 197.1MB in the beginning and 501.2MB in the end (delta: 304.1MB). Free memory was 133.1MB in the beginning and 224.5MB in the end (delta: -91.3MB). Peak memory consumption was 212.7MB. Max. memory is 16.1GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - CounterExampleResult [Line: 941]: a call to reach_error is reachable a call to reach_error is reachable We found a FailurePath: [L1] 0 //@ ghost int multithreaded = 0; [L1] 0 //@ ghost int m_locked = 0; [L935] 0 static int top=0; [L936] 0 static unsigned int arr[(800)]; [L936] 0 static unsigned int arr[(800)]; [L937] 0 pthread_mutex_t m; [L937] 0 pthread_mutex_t m; [L937] 0 pthread_mutex_t m; [L937] 0 pthread_mutex_t m; [L937] 0 pthread_mutex_t m; [L937] 0 pthread_mutex_t m; [L938] 0 _Bool flag=(0); [L1020] 0 pthread_t id1, id2; [L1022] 0 //@ ghost multithreaded = 1; [L1022] FCALL, FORK 0 pthread_create(&id1, ((void *)0), t1, ((void *)0)) VAL [arr={3:0}, flag=0, id1={6:0}, id2={5:0}, m={4:0}, top=0] [L989] 1 int i; [L990] 1 unsigned int tmp; [L991] 1 i=0 VAL [\old(arg)={0:0}, arg={0:0}, arr={3:0}, flag=0, i=0, m={4:0}, top=0] [L991] COND TRUE 1 i<(800) VAL [\old(arg)={0:0}, arg={0:0}, arr={3:0}, flag=0, i=0, m={4:0}, top=0] [L993] 1 //@ ghost m_locked = 1; [L1023] 0 //@ assert (!multithreaded || (m_locked || (((long long) flag + (long long) top) >= 0LL))); [L1023] FCALL, FORK 0 pthread_create(&id2, ((void *)0), t2, ((void *)0)) VAL [arr={3:0}, flag=0, id1={6:0}, id2={5:0}, m={4:0}, top=0] [L1005] 2 int i; [L1006] 2 i=0 VAL [\old(arg)={0:0}, arg={0:0}, arr={3:0}, flag=0, i=0, m={4:0}, top=0] [L994] 1 tmp = __VERIFIER_nondet_uint() [L995] CALL 1 assume_abort_if_not(tmp < (800)) [L23] COND FALSE 1 !(!cond) [L995] RET 1 assume_abort_if_not(tmp < (800)) [L996] CALL, EXPR 1 push(arr,tmp) [L961] COND FALSE 1 !(top==(800)) [L968] CALL, EXPR 1 get_top() [L953] 1 return top; [L968] RET, EXPR 1 get_top() [L968] 1 stack[get_top()] = x [L969] CALL 1 inc_top() [L945] 1 top++ [L969] RET 1 inc_top() [L971] 1 return 0; [L996] RET, EXPR 1 push(arr,tmp) [L996] COND FALSE 1 !(push(arr,tmp)==(-1)) [L998] 1 flag=(1) VAL [\old(arg)={0:0}, arg={0:0}, arr={3:0}, flag=1, i=0, m={4:0}, tmp=7, top=1] [L999] 1 //@ ghost m_locked = 0; [L1006] COND TRUE 2 i<(800) VAL [\old(arg)={0:0}, arg={0:0}, arr={3:0}, flag=1, i=0, m={4:0}, top=1] [L1008] 2 //@ ghost m_locked = 1; [L1009] COND TRUE 2 \read(flag) [L1011] CALL, EXPR 2 pop(arr) [L975] CALL, EXPR 2 get_top() [L953] 2 return top; [L975] RET, EXPR 2 get_top() [L975] COND FALSE 2 !(get_top()==0) [L982] CALL 2 dec_top() [L949] 2 top-- [L982] RET 2 dec_top() [L983] CALL, EXPR 2 get_top() [L953] 2 return top; [L983] RET, EXPR 2 get_top() [L983] EXPR 2 stack[get_top()] [L983] 2 return stack[get_top()]; [L1011] RET, EXPR 2 pop(arr) [L1011] COND FALSE 2 !(!(pop(arr)!=(-2))) [L1014] 2 //@ ghost m_locked = 0; [L1006] 2 i++ VAL [\old(arg)={0:0}, arg={0:0}, arr={3:0}, flag=1, i=1, m={4:0}, top=0] [L1006] COND TRUE 2 i<(800) VAL [\old(arg)={0:0}, arg={0:0}, arr={3:0}, flag=1, i=1, m={4:0}, top=0] [L1008] 2 //@ ghost m_locked = 1; [L1009] COND TRUE 2 \read(flag) [L1011] CALL, EXPR 2 pop(arr) [L975] CALL, EXPR 2 get_top() [L953] 2 return top; [L975] RET, EXPR 2 get_top() [L975] COND TRUE 2 get_top()==0 [L978] 2 return (-2); [L1011] RET, EXPR 2 pop(arr) [L1011] COND TRUE 2 !(pop(arr)!=(-2)) [L1012] CALL 2 error() [L941] 2 reach_error() VAL [arr={3:0}, flag=1, m={4:0}, top=0] - UnprovableResult [Line: 1023]: Unable to prove that invariant of correctness witness holds Unable to prove that invariant of correctness witness holds Reason: Not analyzed. - UnprovableResult [Line: 1024]: Unable to prove that invariant of correctness witness holds Unable to prove that invariant of correctness witness holds Reason: Not analyzed. - UnprovableResult [Line: 1023]: Unable to prove that petrification did provide enough thread instances (tool internal message) Unable to prove that petrification did provide enough thread instances (tool internal message) Reason: Not analyzed. - UnprovableResult [Line: 1022]: Unable to prove that petrification did provide enough thread instances (tool internal message) Unable to prove that petrification did provide enough thread instances (tool internal message) Reason: Not analyzed. - UnprovableResult [Line: 941]: Unable to prove that a call to reach_error is unreachable Unable to prove that a call to reach_error is unreachable Reason: Not analyzed. - StatisticsResult: Ultimate Automizer benchmark data with 1 thread instances CFG has 5 procedures, 62 locations, 8 error locations. Started 1 CEGAR loops. EmptinessCheckTime: 0.0s, RemoveRedundantFlowTime: 0.0s, RemoveRedundantFlowUnfoldingTime: 0.0s, BackfoldingTime: 0.0s, BackfoldingUnfoldingTime: 0.0s, FlowIncreaseByBackfolding: 0, BasicCegarLoop: OverallTime: 9.1s, OverallIterations: 11, TraceHistogramMax: 2, PathProgramHistogramMax: 1, EmptinessCheckTime: 0.0s, AutomataDifference: 5.2s, DeadEndRemovalTime: 0.0s, HoareAnnotationTime: 0.0s, InitialAbstractionConstructionTime: 0.0s, HoareTripleCheckerStatistics: 0 mSolverCounterUnknown, 890 SdHoareTripleChecker+Valid, 1.3s IncrementalHoareTripleChecker+Time, 0 mSdLazyCounter, 869 mSDsluCounter, 24 SdHoareTripleChecker+Invalid, 1.0s Time, 0 mProtectedAction, 0 SdHoareTripleChecker+Unchecked, 0 IncrementalHoareTripleChecker+Unchecked, 11 mSDsCounter, 71 IncrementalHoareTripleChecker+Valid, 0 mProtectedPredicate, 1580 IncrementalHoareTripleChecker+Invalid, 1651 SdHoareTripleChecker+Unknown, 0 mSolverCounterNotChecked, 71 mSolverCounterUnsat, 13 mSDtfsCounter, 1580 mSolverCounterSat, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Unknown, PredicateUnifierStatistics: 0 DeclaredPredicates, 129 GetRequests, 82 SyntacticMatches, 0 SemanticMatches, 47 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 86 ImplicationChecksByTransitivity, 0.3s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=644occurred in iteration=10, InterpolantAutomatonStates: 58, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 0.0s DumpTime, AutomataMinimizationStatistics: No data available, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TRACE_CHECK: 0.1s SsaConstructionTime, 0.2s SatisfiabilityAnalysisTime, 2.5s InterpolantComputationTime, 235 NumberOfCodeBlocks, 235 NumberOfCodeBlocksAsserted, 13 NumberOfCheckSat, 238 ConstructedInterpolants, 7 QuantifiedInterpolants, 2118 SizeOfPredicates, 21 NumberOfNonLiveVariables, 375 ConjunctsInSsa, 18 ConjunctsInUnsatCore, 14 InterpolantComputations, 8 PerfectInterpolantSequences, 0/30 InterpolantCoveringCapability, INVARIANT_SYNTHESIS: No data available, INTERPOLANT_CONSOLIDATION: No data available, ABSTRACT_INTERPRETATION: No data available, PDR: No data available, ACCELERATED_INTERPOLATION: No data available, SIFA: No data available, ReuseStatistics: No data available RESULT: Ultimate proved your program to be incorrect! [2024-05-12 11:10:40,160 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (1)] Forceful destruction successful, exit code 0 Received shutdown request... --- End real Ultimate output --- Execution finished normally Writing output log to file Ultimate.log Writing human readable error path to file UltimateCounterExample.errorpath Result: FALSE