./Ultimate.py --spec ../../../trunk/examples/svcomp/properties/unreach-call.prp --file ../../../trunk/examples/svcomp/pthread/stack-2.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-2.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-2.i ./goblint.2024-05-07_14-17-48.files/mutex-meet/stack-2.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:22,709 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-05-12 11:10:22,766 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:22,769 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-05-12 11:10:22,773 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-05-12 11:10:22,798 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-05-12 11:10:22,800 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-05-12 11:10:22,800 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-05-12 11:10:22,801 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2024-05-12 11:10:22,804 INFO L153 SettingsManager]: * Use memory slicer=true [2024-05-12 11:10:22,804 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2024-05-12 11:10:22,804 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2024-05-12 11:10:22,805 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2024-05-12 11:10:22,806 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2024-05-12 11:10:22,806 INFO L153 SettingsManager]: * Use SBE=true [2024-05-12 11:10:22,806 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-05-12 11:10:22,807 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2024-05-12 11:10:22,807 INFO L153 SettingsManager]: * sizeof long=4 [2024-05-12 11:10:22,807 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2024-05-12 11:10:22,807 INFO L153 SettingsManager]: * sizeof POINTER=4 [2024-05-12 11:10:22,807 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-05-12 11:10:22,808 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2024-05-12 11:10:22,808 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2024-05-12 11:10:22,808 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2024-05-12 11:10:22,809 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-05-12 11:10:22,809 INFO L153 SettingsManager]: * sizeof long double=12 [2024-05-12 11:10:22,809 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-05-12 11:10:22,809 INFO L153 SettingsManager]: * Use constant arrays=true [2024-05-12 11:10:22,810 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2024-05-12 11:10:22,810 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2024-05-12 11:10:22,811 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2024-05-12 11:10:22,811 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2024-05-12 11:10:22,811 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-05-12 11:10:22,811 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-05-12 11:10:22,811 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2024-05-12 11:10:22,812 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2024-05-12 11:10:22,812 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2024-05-12 11:10:22,812 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2024-05-12 11:10:22,812 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2024-05-12 11:10:22,813 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2024-05-12 11:10:22,813 INFO L153 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2024-05-12 11:10:22,813 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2024-05-12 11:10:22,813 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2024-05-12 11:10:22,814 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:23,016 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-05-12 11:10:23,034 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-05-12 11:10:23,037 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-05-12 11:10:23,037 INFO L270 PluginConnector]: Initializing CDTParser... [2024-05-12 11:10:23,038 INFO L274 PluginConnector]: CDTParser initialized [2024-05-12 11:10:23,039 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/svcomp/pthread/stack-2.i [2024-05-12 11:10:24,084 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-05-12 11:10:24,286 INFO L384 CDTParser]: Found 1 translation units. [2024-05-12 11:10:24,287 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/trunk/examples/svcomp/pthread/stack-2.i [2024-05-12 11:10:24,303 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/dc984fcd9/8f71d22d25dd4caeb966c47b083c9d90/FLAG6999e98f8 [2024-05-12 11:10:24,316 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/dc984fcd9/8f71d22d25dd4caeb966c47b083c9d90 [2024-05-12 11:10:24,318 INFO L270 PluginConnector]: Initializing Witness Parser... [2024-05-12 11:10:24,319 INFO L274 PluginConnector]: Witness Parser initialized [2024-05-12 11:10:24,325 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-2.yml/witness.yml [2024-05-12 11:10:24,408 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-05-12 11:10:24,409 INFO L133 ToolchainWalker]: Walking toolchain with 5 elements. [2024-05-12 11:10:24,410 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-05-12 11:10:24,410 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-05-12 11:10:24,414 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-05-12 11:10:24,415 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 12.05 11:10:24" (1/2) ... [2024-05-12 11:10:24,416 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@11370cbe and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.05 11:10:24, skipping insertion in model container [2024-05-12 11:10:24,416 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 12.05 11:10:24" (1/2) ... [2024-05-12 11:10:24,418 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.CACSL2BoogieTranslatorObserver@2a715912 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.05 11:10:24, skipping insertion in model container [2024-05-12 11:10:24,418 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:24" (2/2) ... [2024-05-12 11:10:24,418 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@11370cbe and model type witness.yml de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator CORRECTNESS_WITNESS 12.05 11:10:24, skipping insertion in model container [2024-05-12 11:10:24,418 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:24" (2/2) ... [2024-05-12 11:10:24,419 INFO L83 nessWitnessExtractor]: Extracting all invariants from correctness witness [2024-05-12 11:10:24,446 INFO L95 edCorrectnessWitness]: Found the following entries in the witness: [2024-05-12 11:10:24,448 INFO L97 edCorrectnessWitness]: Location invariant before [L1024-L1024] ! multithreaded || (m_locked || (long long )flag + (long long )top >= 0LL) [2024-05-12 11:10:24,448 INFO L97 edCorrectnessWitness]: Location invariant before [L1025-L1025] ! multithreaded || (m_locked || (long long )flag + (long long )top >= 0LL) [2024-05-12 11:10:24,448 INFO L103 edCorrectnessWitness]: ghost_variable m_locked = 0 [2024-05-12 11:10:24,448 INFO L103 edCorrectnessWitness]: ghost_variable multithreaded = 0 [2024-05-12 11:10:24,448 INFO L106 edCorrectnessWitness]: ghost_update [L1000-L1000] m_locked = 0; [2024-05-12 11:10:24,449 INFO L106 edCorrectnessWitness]: ghost_update [L994-L994] m_locked = 1; [2024-05-12 11:10:24,449 INFO L106 edCorrectnessWitness]: ghost_update [L1009-L1009] m_locked = 1; [2024-05-12 11:10:24,449 INFO L106 edCorrectnessWitness]: ghost_update [L1015-L1015] m_locked = 0; [2024-05-12 11:10:24,450 INFO L106 edCorrectnessWitness]: ghost_update [L1023-L1023] multithreaded = 1; [2024-05-12 11:10:24,494 INFO L177 MainTranslator]: Built tables and reachable declarations [2024-05-12 11:10:24,865 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-2.i[41520,41533] [2024-05-12 11:10:24,894 INFO L207 PostProcessor]: Analyzing one entry point: main [2024-05-12 11:10:24,903 INFO L202 MainTranslator]: Completed pre-run Start Parsing Local Start Parsing Local [2024-05-12 11:10:24,970 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-2.i[41520,41533] 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:24,995 INFO L207 PostProcessor]: Analyzing one entry point: main [2024-05-12 11:10:25,126 INFO L206 MainTranslator]: Completed translation [2024-05-12 11:10:25,127 INFO L201 PluginConnector]: Adding new model witness.yml de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator CORRECTNESS_WITNESS 12.05 11:10:25 WrapperNode [2024-05-12 11:10:25,127 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-05-12 11:10:25,128 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-05-12 11:10:25,128 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-05-12 11:10:25,129 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-05-12 11:10:25,134 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "witness.yml de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator CORRECTNESS_WITNESS 12.05 11:10:25" (1/1) ... [2024-05-12 11:10:25,163 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "witness.yml de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator CORRECTNESS_WITNESS 12.05 11:10:25" (1/1) ... [2024-05-12 11:10:25,193 INFO L138 Inliner]: procedures = 278, calls = 46, calls flagged for inlining = 12, calls inlined = 12, statements flattened = 179 [2024-05-12 11:10:25,194 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-05-12 11:10:25,195 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-05-12 11:10:25,195 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-05-12 11:10:25,195 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-05-12 11:10:25,203 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "witness.yml de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator CORRECTNESS_WITNESS 12.05 11:10:25" (1/1) ... [2024-05-12 11:10:25,203 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "witness.yml de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator CORRECTNESS_WITNESS 12.05 11:10:25" (1/1) ... [2024-05-12 11:10:25,217 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "witness.yml de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator CORRECTNESS_WITNESS 12.05 11:10:25" (1/1) ... [2024-05-12 11:10:25,235 INFO L175 MemorySlicer]: Split 18 memory accesses to 5 slices as follows [2, 2, 5, 2, 7]. 39 percent of accesses are in the largest equivalence class. The 12 initializations are split as follows [2, 0, 5, 0, 5]. The 3 writes are split as follows [0, 1, 0, 1, 1]. [2024-05-12 11:10:25,240 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "witness.yml de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator CORRECTNESS_WITNESS 12.05 11:10:25" (1/1) ... [2024-05-12 11:10:25,240 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "witness.yml de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator CORRECTNESS_WITNESS 12.05 11:10:25" (1/1) ... [2024-05-12 11:10:25,248 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "witness.yml de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator CORRECTNESS_WITNESS 12.05 11:10:25" (1/1) ... [2024-05-12 11:10:25,253 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "witness.yml de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator CORRECTNESS_WITNESS 12.05 11:10:25" (1/1) ... [2024-05-12 11:10:25,257 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "witness.yml de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator CORRECTNESS_WITNESS 12.05 11:10:25" (1/1) ... [2024-05-12 11:10:25,261 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "witness.yml de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator CORRECTNESS_WITNESS 12.05 11:10:25" (1/1) ... [2024-05-12 11:10:25,264 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-05-12 11:10:25,265 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2024-05-12 11:10:25,266 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2024-05-12 11:10:25,266 INFO L274 PluginConnector]: RCFGBuilder initialized [2024-05-12 11:10:25,267 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "witness.yml de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator CORRECTNESS_WITNESS 12.05 11:10:25" (1/1) ... [2024-05-12 11:10:25,271 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-05-12 11:10:25,277 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-05-12 11:10:25,301 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:25,322 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:25,335 INFO L130 BoogieDeclarations]: Found specification of procedure t1 [2024-05-12 11:10:25,348 INFO L138 BoogieDeclarations]: Found implementation of procedure t1 [2024-05-12 11:10:25,349 INFO L130 BoogieDeclarations]: Found specification of procedure t2 [2024-05-12 11:10:25,349 INFO L138 BoogieDeclarations]: Found implementation of procedure t2 [2024-05-12 11:10:25,349 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnStack [2024-05-12 11:10:25,349 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2024-05-12 11:10:25,349 INFO L130 BoogieDeclarations]: Found specification of procedure #PthreadsMutexUnlock [2024-05-12 11:10:25,350 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#0 [2024-05-12 11:10:25,351 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#1 [2024-05-12 11:10:25,351 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#2 [2024-05-12 11:10:25,352 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#3 [2024-05-12 11:10:25,352 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#4 [2024-05-12 11:10:25,352 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#0 [2024-05-12 11:10:25,353 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#1 [2024-05-12 11:10:25,353 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#2 [2024-05-12 11:10:25,353 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#3 [2024-05-12 11:10:25,353 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#4 [2024-05-12 11:10:25,353 INFO L130 BoogieDeclarations]: Found specification of procedure #PthreadsMutexLock [2024-05-12 11:10:25,353 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2024-05-12 11:10:25,353 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2024-05-12 11:10:25,354 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#1 [2024-05-12 11:10:25,354 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#2 [2024-05-12 11:10:25,354 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#3 [2024-05-12 11:10:25,354 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#4 [2024-05-12 11:10:25,354 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-05-12 11:10:25,354 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-05-12 11:10:25,356 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:25,478 INFO L244 CfgBuilder]: Building ICFG [2024-05-12 11:10:25,480 INFO L270 CfgBuilder]: Building CFG for each procedure with an implementation [2024-05-12 11:10:25,707 INFO L289 CfgBuilder]: Ommited future-live optimization because the input is a concurrent program. [2024-05-12 11:10:25,707 INFO L293 CfgBuilder]: Performing block encoding [2024-05-12 11:10:25,933 INFO L315 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-05-12 11:10:25,934 INFO L320 CfgBuilder]: Removed 2 assume(true) statements. [2024-05-12 11:10:25,934 INFO L201 PluginConnector]: Adding new model witness.yml de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 12.05 11:10:25 BoogieIcfgContainer [2024-05-12 11:10:25,935 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2024-05-12 11:10:25,937 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2024-05-12 11:10:25,938 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2024-05-12 11:10:25,940 INFO L274 PluginConnector]: TraceAbstraction initialized [2024-05-12 11:10:25,940 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 12.05 11:10:24" (1/4) ... [2024-05-12 11:10:25,941 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@65682af4 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 12.05 11:10:25, skipping insertion in model container [2024-05-12 11:10:25,941 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:24" (2/4) ... [2024-05-12 11:10:25,942 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@65682af4 and model type witness.yml de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CORRECTNESS_WITNESS 12.05 11:10:25, skipping insertion in model container [2024-05-12 11:10:25,942 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "witness.yml de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator CORRECTNESS_WITNESS 12.05 11:10:25" (3/4) ... [2024-05-12 11:10:25,943 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@65682af4 and model type witness.yml de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CORRECTNESS_WITNESS 12.05 11:10:25, skipping insertion in model container [2024-05-12 11:10:25,943 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "witness.yml de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 12.05 11:10:25" (4/4) ... [2024-05-12 11:10:25,945 INFO L112 eAbstractionObserver]: Analyzing ICFG stack-2.i [2024-05-12 11:10:25,959 INFO L204 ceAbstractionStarter]: Automizer settings: Hoare:false NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2024-05-12 11:10:25,960 INFO L163 ceAbstractionStarter]: Applying trace abstraction to program that has 4 error locations. [2024-05-12 11:10:25,960 INFO L522 ceAbstractionStarter]: Constructing petrified ICFG for 1 thread instances. [2024-05-12 11:10:26,013 INFO L144 ThreadInstanceAdder]: Constructed 2 joinOtherThreadTransitions. [2024-05-12 11:10:26,048 INFO L73 FinitePrefix]: Start finitePrefix. Operand has 44 places, 42 transitions, 98 flow [2024-05-12 11:10:26,076 INFO L124 PetriNetUnfolderBase]: 5/40 cut-off events. [2024-05-12 11:10:26,077 INFO L125 PetriNetUnfolderBase]: For 2/2 co-relation queries the response was YES. [2024-05-12 11:10:26,081 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:26,082 INFO L82 GeneralOperation]: Start removeDead. Operand has 44 places, 42 transitions, 98 flow [2024-05-12 11:10:26,084 INFO L88 GeneralOperation]: Finished RemoveDead, result has has 40 places, 38 transitions, 85 flow [2024-05-12 11:10:26,095 INFO L356 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2024-05-12 11:10:26,103 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;@3a9721d8, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2024-05-12 11:10:26,103 INFO L358 AbstractCegarLoop]: Starting to check reachability of 8 error locations. [2024-05-12 11:10:26,112 INFO L185 PetriNetUnfolderBase]: Found word, exiting Unfolder. [2024-05-12 11:10:26,112 INFO L124 PetriNetUnfolderBase]: 0/6 cut-off events. [2024-05-12 11:10:26,112 INFO L125 PetriNetUnfolderBase]: For 0/0 co-relation queries the response was YES. [2024-05-12 11:10:26,112 INFO L200 CegarLoopForPetriNet]: Found error trace [2024-05-12 11:10:26,113 INFO L208 CegarLoopForPetriNet]: trace histogram [1, 1, 1, 1, 1, 1] [2024-05-12 11:10:26,113 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:26,117 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2024-05-12 11:10:26,117 INFO L85 PathProgramCache]: Analyzing trace with hash 396314095, now seen corresponding path program 1 times [2024-05-12 11:10:26,125 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-05-12 11:10:26,126 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [190313950] [2024-05-12 11:10:26,126 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-05-12 11:10:26,126 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-05-12 11:10:26,324 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-05-12 11:10:26,487 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:26,488 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-05-12 11:10:26,488 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [190313950] [2024-05-12 11:10:26,489 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [190313950] provided 1 perfect and 0 imperfect interpolant sequences [2024-05-12 11:10:26,489 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-05-12 11:10:26,489 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [1] imperfect sequences [] total 1 [2024-05-12 11:10:26,490 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [445254998] [2024-05-12 11:10:26,491 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-05-12 11:10:26,497 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2024-05-12 11:10:26,501 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-05-12 11:10:26,528 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2024-05-12 11:10:26,529 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2024-05-12 11:10:26,532 INFO L471 CegarLoopForPetriNet]: Number of universal loopers: 9 out of 42 [2024-05-12 11:10:26,534 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:26,534 INFO L112 encePairwiseOnDemand]: Universal subtrahend loopers provided by user. [2024-05-12 11:10:26,534 INFO L113 encePairwiseOnDemand]: Number of universal subtrahend loopers: 9 of 42 [2024-05-12 11:10:26,535 INFO L73 FinitePrefix]: Start finitePrefix. Operand will be constructed on-demand [2024-05-12 11:10:26,757 INFO L124 PetriNetUnfolderBase]: 661/1158 cut-off events. [2024-05-12 11:10:26,757 INFO L125 PetriNetUnfolderBase]: For 27/27 co-relation queries the response was YES. [2024-05-12 11:10:26,761 INFO L83 FinitePrefix]: Finished finitePrefix Result has 2254 conditions, 1158 events. 661/1158 cut-off events. For 27/27 co-relation queries the response was YES. Maximal size of possible extension queue 71. Compared 6005 event pairs, 201 based on Foata normal form. 80/1074 useless extension candidates. Maximal degree in co-relation 2086. Up to 761 conditions per place. [2024-05-12 11:10:26,768 INFO L140 encePairwiseOnDemand]: 36/42 looper letters, 45 selfloop transitions, 2 changer transitions 0/54 dead transitions. [2024-05-12 11:10:26,768 INFO L145 encePairwiseOnDemand]: Finished differencePairwiseOnDemand. Result has 42 places, 54 transitions, 217 flow [2024-05-12 11:10:26,769 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2024-05-12 11:10:26,771 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 3 states. [2024-05-12 11:10:26,777 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 3 states to 3 states and 79 transitions. [2024-05-12 11:10:26,778 INFO L516 CegarLoopForPetriNet]: DFA transition density 0.626984126984127 [2024-05-12 11:10:26,780 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:26,780 INFO L82 GeneralOperation]: Start removeRedundantFlow. Operand has 42 places, 54 transitions, 217 flow [2024-05-12 11:10:26,785 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:26,788 INFO L231 Difference]: Finished difference. Result has 40 places, 37 transitions, 90 flow [2024-05-12 11:10:26,790 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:26,792 INFO L281 CegarLoopForPetriNet]: 40 programPoint places, 0 predicate places. [2024-05-12 11:10:26,793 INFO L495 AbstractCegarLoop]: Abstraction has has 40 places, 37 transitions, 90 flow [2024-05-12 11:10:26,793 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:26,793 INFO L200 CegarLoopForPetriNet]: Found error trace [2024-05-12 11:10:26,793 INFO L208 CegarLoopForPetriNet]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-05-12 11:10:26,793 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2024-05-12 11:10:26,794 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:26,794 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2024-05-12 11:10:26,794 INFO L85 PathProgramCache]: Analyzing trace with hash 1313163419, now seen corresponding path program 1 times [2024-05-12 11:10:26,794 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-05-12 11:10:26,794 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1285029989] [2024-05-12 11:10:26,795 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-05-12 11:10:26,795 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-05-12 11:10:26,829 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-05-12 11:10:26,909 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:26,910 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-05-12 11:10:26,910 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1285029989] [2024-05-12 11:10:26,910 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1285029989] provided 1 perfect and 0 imperfect interpolant sequences [2024-05-12 11:10:26,910 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-05-12 11:10:26,911 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2024-05-12 11:10:26,911 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2109377989] [2024-05-12 11:10:26,911 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-05-12 11:10:26,912 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2024-05-12 11:10:26,913 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-05-12 11:10:26,914 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2024-05-12 11:10:26,914 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2024-05-12 11:10:26,920 INFO L471 CegarLoopForPetriNet]: Number of universal loopers: 9 out of 42 [2024-05-12 11:10:26,921 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:26,922 INFO L112 encePairwiseOnDemand]: Universal subtrahend loopers provided by user. [2024-05-12 11:10:26,922 INFO L113 encePairwiseOnDemand]: Number of universal subtrahend loopers: 9 of 42 [2024-05-12 11:10:26,922 INFO L73 FinitePrefix]: Start finitePrefix. Operand will be constructed on-demand [2024-05-12 11:10:27,114 INFO L124 PetriNetUnfolderBase]: 760/1440 cut-off events. [2024-05-12 11:10:27,114 INFO L125 PetriNetUnfolderBase]: For 111/111 co-relation queries the response was YES. [2024-05-12 11:10:27,116 INFO L83 FinitePrefix]: Finished finitePrefix Result has 2841 conditions, 1440 events. 760/1440 cut-off events. For 111/111 co-relation queries the response was YES. Maximal size of possible extension queue 82. Compared 7937 event pairs, 264 based on Foata normal form. 41/1374 useless extension candidates. Maximal degree in co-relation 1426. Up to 619 conditions per place. [2024-05-12 11:10:27,122 INFO L140 encePairwiseOnDemand]: 34/42 looper letters, 48 selfloop transitions, 6 changer transitions 0/61 dead transitions. [2024-05-12 11:10:27,127 INFO L145 encePairwiseOnDemand]: Finished differencePairwiseOnDemand. Result has 44 places, 61 transitions, 254 flow [2024-05-12 11:10:27,127 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-05-12 11:10:27,127 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 5 states. [2024-05-12 11:10:27,128 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 99 transitions. [2024-05-12 11:10:27,129 INFO L516 CegarLoopForPetriNet]: DFA transition density 0.4714285714285714 [2024-05-12 11:10:27,129 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:27,129 INFO L82 GeneralOperation]: Start removeRedundantFlow. Operand has 44 places, 61 transitions, 254 flow [2024-05-12 11:10:27,131 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:27,132 INFO L231 Difference]: Finished difference. Result has 45 places, 41 transitions, 129 flow [2024-05-12 11:10:27,132 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:27,133 INFO L281 CegarLoopForPetriNet]: 40 programPoint places, 5 predicate places. [2024-05-12 11:10:27,133 INFO L495 AbstractCegarLoop]: Abstraction has has 45 places, 41 transitions, 129 flow [2024-05-12 11:10:27,133 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:27,133 INFO L200 CegarLoopForPetriNet]: Found error trace [2024-05-12 11:10:27,133 INFO L208 CegarLoopForPetriNet]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-05-12 11:10:27,133 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2024-05-12 11:10:27,135 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:27,135 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2024-05-12 11:10:27,135 INFO L85 PathProgramCache]: Analyzing trace with hash 1313204803, now seen corresponding path program 1 times [2024-05-12 11:10:27,135 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-05-12 11:10:27,136 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1107980107] [2024-05-12 11:10:27,136 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-05-12 11:10:27,136 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-05-12 11:10:27,158 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-05-12 11:10:27,294 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:27,294 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-05-12 11:10:27,294 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1107980107] [2024-05-12 11:10:27,294 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1107980107] provided 1 perfect and 0 imperfect interpolant sequences [2024-05-12 11:10:27,294 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-05-12 11:10:27,295 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2024-05-12 11:10:27,295 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1866830630] [2024-05-12 11:10:27,295 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-05-12 11:10:27,296 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2024-05-12 11:10:27,296 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-05-12 11:10:27,296 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2024-05-12 11:10:27,299 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2024-05-12 11:10:27,302 INFO L471 CegarLoopForPetriNet]: Number of universal loopers: 9 out of 42 [2024-05-12 11:10:27,302 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:27,302 INFO L112 encePairwiseOnDemand]: Universal subtrahend loopers provided by user. [2024-05-12 11:10:27,303 INFO L113 encePairwiseOnDemand]: Number of universal subtrahend loopers: 9 of 42 [2024-05-12 11:10:27,303 INFO L73 FinitePrefix]: Start finitePrefix. Operand will be constructed on-demand [2024-05-12 11:10:27,473 INFO L124 PetriNetUnfolderBase]: 869/1595 cut-off events. [2024-05-12 11:10:27,473 INFO L125 PetriNetUnfolderBase]: For 753/753 co-relation queries the response was YES. [2024-05-12 11:10:27,476 INFO L83 FinitePrefix]: Finished finitePrefix Result has 3707 conditions, 1595 events. 869/1595 cut-off events. For 753/753 co-relation queries the response was YES. Maximal size of possible extension queue 83. Compared 8812 event pairs, 215 based on Foata normal form. 0/1466 useless extension candidates. Maximal degree in co-relation 2661. Up to 990 conditions per place. [2024-05-12 11:10:27,482 INFO L140 encePairwiseOnDemand]: 38/42 looper letters, 66 selfloop transitions, 3 changer transitions 0/76 dead transitions. [2024-05-12 11:10:27,482 INFO L145 encePairwiseOnDemand]: Finished differencePairwiseOnDemand. Result has 48 places, 76 transitions, 372 flow [2024-05-12 11:10:27,483 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2024-05-12 11:10:27,483 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 4 states. [2024-05-12 11:10:27,485 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 4 states to 4 states and 99 transitions. [2024-05-12 11:10:27,487 INFO L516 CegarLoopForPetriNet]: DFA transition density 0.5892857142857143 [2024-05-12 11:10:27,487 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:27,487 INFO L82 GeneralOperation]: Start removeRedundantFlow. Operand has 48 places, 76 transitions, 372 flow [2024-05-12 11:10:27,489 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:27,489 INFO L231 Difference]: Finished difference. Result has 47 places, 42 transitions, 140 flow [2024-05-12 11:10:27,490 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:27,490 INFO L281 CegarLoopForPetriNet]: 40 programPoint places, 7 predicate places. [2024-05-12 11:10:27,490 INFO L495 AbstractCegarLoop]: Abstraction has has 47 places, 42 transitions, 140 flow [2024-05-12 11:10:27,491 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:27,491 INFO L200 CegarLoopForPetriNet]: Found error trace [2024-05-12 11:10:27,491 INFO L208 CegarLoopForPetriNet]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-05-12 11:10:27,491 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2 [2024-05-12 11:10:27,491 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:27,492 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2024-05-12 11:10:27,492 INFO L85 PathProgramCache]: Analyzing trace with hash 1890580347, now seen corresponding path program 1 times [2024-05-12 11:10:27,492 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-05-12 11:10:27,492 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [553946086] [2024-05-12 11:10:27,492 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-05-12 11:10:27,492 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-05-12 11:10:27,504 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-05-12 11:10:27,551 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:27,551 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-05-12 11:10:27,551 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [553946086] [2024-05-12 11:10:27,551 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [553946086] provided 1 perfect and 0 imperfect interpolant sequences [2024-05-12 11:10:27,551 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-05-12 11:10:27,551 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2024-05-12 11:10:27,552 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [355953784] [2024-05-12 11:10:27,552 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-05-12 11:10:27,552 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2024-05-12 11:10:27,552 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-05-12 11:10:27,553 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2024-05-12 11:10:27,553 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2024-05-12 11:10:27,554 INFO L471 CegarLoopForPetriNet]: Number of universal loopers: 9 out of 42 [2024-05-12 11:10:27,554 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:27,554 INFO L112 encePairwiseOnDemand]: Universal subtrahend loopers provided by user. [2024-05-12 11:10:27,554 INFO L113 encePairwiseOnDemand]: Number of universal subtrahend loopers: 9 of 42 [2024-05-12 11:10:27,554 INFO L73 FinitePrefix]: Start finitePrefix. Operand will be constructed on-demand [2024-05-12 11:10:27,763 INFO L124 PetriNetUnfolderBase]: 1251/2297 cut-off events. [2024-05-12 11:10:27,764 INFO L125 PetriNetUnfolderBase]: For 1301/1307 co-relation queries the response was YES. [2024-05-12 11:10:27,767 INFO L83 FinitePrefix]: Finished finitePrefix Result has 5479 conditions, 2297 events. 1251/2297 cut-off events. For 1301/1307 co-relation queries the response was YES. Maximal size of possible extension queue 97. Compared 12986 event pairs, 255 based on Foata normal form. 42/2154 useless extension candidates. Maximal degree in co-relation 4482. Up to 913 conditions per place. [2024-05-12 11:10:27,774 INFO L140 encePairwiseOnDemand]: 37/42 looper letters, 73 selfloop transitions, 3 changer transitions 0/83 dead transitions. [2024-05-12 11:10:27,774 INFO L145 encePairwiseOnDemand]: Finished differencePairwiseOnDemand. Result has 49 places, 83 transitions, 423 flow [2024-05-12 11:10:27,775 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2024-05-12 11:10:27,775 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 4 states. [2024-05-12 11:10:27,775 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 4 states to 4 states and 102 transitions. [2024-05-12 11:10:27,775 INFO L516 CegarLoopForPetriNet]: DFA transition density 0.6071428571428571 [2024-05-12 11:10:27,775 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:27,776 INFO L82 GeneralOperation]: Start removeRedundantFlow. Operand has 49 places, 83 transitions, 423 flow [2024-05-12 11:10:27,777 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:27,778 INFO L231 Difference]: Finished difference. Result has 48 places, 42 transitions, 144 flow [2024-05-12 11:10:27,778 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:27,779 INFO L281 CegarLoopForPetriNet]: 40 programPoint places, 8 predicate places. [2024-05-12 11:10:27,779 INFO L495 AbstractCegarLoop]: Abstraction has has 48 places, 42 transitions, 144 flow [2024-05-12 11:10:27,779 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:27,779 INFO L200 CegarLoopForPetriNet]: Found error trace [2024-05-12 11:10:27,779 INFO L208 CegarLoopForPetriNet]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-05-12 11:10:27,779 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3 [2024-05-12 11:10:27,780 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:27,780 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2024-05-12 11:10:27,780 INFO L85 PathProgramCache]: Analyzing trace with hash -625887353, now seen corresponding path program 1 times [2024-05-12 11:10:27,780 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-05-12 11:10:27,780 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2101308027] [2024-05-12 11:10:27,780 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-05-12 11:10:27,781 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-05-12 11:10:27,791 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-05-12 11:10:27,829 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:27,830 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-05-12 11:10:27,830 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2101308027] [2024-05-12 11:10:27,830 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2101308027] provided 1 perfect and 0 imperfect interpolant sequences [2024-05-12 11:10:27,830 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-05-12 11:10:27,830 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2024-05-12 11:10:27,830 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [325302184] [2024-05-12 11:10:27,831 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-05-12 11:10:27,831 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2024-05-12 11:10:27,831 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-05-12 11:10:27,831 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2024-05-12 11:10:27,832 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2024-05-12 11:10:27,837 INFO L471 CegarLoopForPetriNet]: Number of universal loopers: 10 out of 42 [2024-05-12 11:10:27,837 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:27,837 INFO L112 encePairwiseOnDemand]: Universal subtrahend loopers provided by user. [2024-05-12 11:10:27,837 INFO L113 encePairwiseOnDemand]: Number of universal subtrahend loopers: 10 of 42 [2024-05-12 11:10:27,837 INFO L73 FinitePrefix]: Start finitePrefix. Operand will be constructed on-demand [2024-05-12 11:10:28,014 INFO L124 PetriNetUnfolderBase]: 1141/2069 cut-off events. [2024-05-12 11:10:28,015 INFO L125 PetriNetUnfolderBase]: For 1282/1288 co-relation queries the response was YES. [2024-05-12 11:10:28,018 INFO L83 FinitePrefix]: Finished finitePrefix Result has 5040 conditions, 2069 events. 1141/2069 cut-off events. For 1282/1288 co-relation queries the response was YES. Maximal size of possible extension queue 93. Compared 11259 event pairs, 439 based on Foata normal form. 14/1930 useless extension candidates. Maximal degree in co-relation 4195. Up to 1457 conditions per place. [2024-05-12 11:10:28,024 INFO L140 encePairwiseOnDemand]: 39/42 looper letters, 47 selfloop transitions, 2 changer transitions 3/59 dead transitions. [2024-05-12 11:10:28,024 INFO L145 encePairwiseOnDemand]: Finished differencePairwiseOnDemand. Result has 50 places, 59 transitions, 301 flow [2024-05-12 11:10:28,025 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2024-05-12 11:10:28,025 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 3 states. [2024-05-12 11:10:28,025 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 3 states to 3 states and 76 transitions. [2024-05-12 11:10:28,026 INFO L516 CegarLoopForPetriNet]: DFA transition density 0.6031746031746031 [2024-05-12 11:10:28,026 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:28,026 INFO L82 GeneralOperation]: Start removeRedundantFlow. Operand has 50 places, 59 transitions, 301 flow [2024-05-12 11:10:28,027 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:28,028 INFO L231 Difference]: Finished difference. Result has 49 places, 43 transitions, 154 flow [2024-05-12 11:10:28,028 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:28,029 INFO L281 CegarLoopForPetriNet]: 40 programPoint places, 9 predicate places. [2024-05-12 11:10:28,029 INFO L495 AbstractCegarLoop]: Abstraction has has 49 places, 43 transitions, 154 flow [2024-05-12 11:10:28,029 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:28,029 INFO L200 CegarLoopForPetriNet]: Found error trace [2024-05-12 11:10:28,030 INFO L208 CegarLoopForPetriNet]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-05-12 11:10:28,030 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4 [2024-05-12 11:10:28,030 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:28,030 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2024-05-12 11:10:28,030 INFO L85 PathProgramCache]: Analyzing trace with hash -1042583990, now seen corresponding path program 1 times [2024-05-12 11:10:28,031 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-05-12 11:10:28,031 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1842094114] [2024-05-12 11:10:28,031 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-05-12 11:10:28,031 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-05-12 11:10:28,047 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-05-12 11:10:28,139 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:28,140 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-05-12 11:10:28,140 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1842094114] [2024-05-12 11:10:28,140 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1842094114] provided 0 perfect and 1 imperfect interpolant sequences [2024-05-12 11:10:28,140 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1948854121] [2024-05-12 11:10:28,140 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-05-12 11:10:28,141 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-05-12 11:10:28,141 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-05-12 11:10:28,175 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:28,203 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:28,308 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-05-12 11:10:28,310 INFO L262 TraceCheckSpWp]: Trace formula consists of 167 conjuncts, 5 conjunts are in the unsatisfiable core [2024-05-12 11:10:28,315 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2024-05-12 11:10:28,387 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:28,474 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:28,474 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2024-05-12 11:10:28,553 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:28,554 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1948854121] provided 0 perfect and 2 imperfect interpolant sequences [2024-05-12 11:10:28,554 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-05-12 11:10:28,554 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 4, 4] total 8 [2024-05-12 11:10:28,554 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [266650717] [2024-05-12 11:10:28,554 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-05-12 11:10:28,555 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2024-05-12 11:10:28,555 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-05-12 11:10:28,556 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2024-05-12 11:10:28,556 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=27, Invalid=45, Unknown=0, NotChecked=0, Total=72 [2024-05-12 11:10:28,561 INFO L471 CegarLoopForPetriNet]: Number of universal loopers: 9 out of 42 [2024-05-12 11:10:28,561 INFO L103 encePairwiseOnDemand]: Start differencePairwiseOnDemand. First operand has 49 places, 43 transitions, 154 flow. Second operand has 9 states, 9 states have (on average 13.11111111111111) internal successors, (118), 9 states have internal predecessors, (118), 0 states have call successors, (0), 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:28,562 INFO L112 encePairwiseOnDemand]: Universal subtrahend loopers provided by user. [2024-05-12 11:10:28,562 INFO L113 encePairwiseOnDemand]: Number of universal subtrahend loopers: 9 of 42 [2024-05-12 11:10:28,562 INFO L73 FinitePrefix]: Start finitePrefix. Operand will be constructed on-demand [2024-05-12 11:10:29,398 INFO L124 PetriNetUnfolderBase]: 3631/6718 cut-off events. [2024-05-12 11:10:29,398 INFO L125 PetriNetUnfolderBase]: For 5105/5107 co-relation queries the response was YES. [2024-05-12 11:10:29,412 INFO L83 FinitePrefix]: Finished finitePrefix Result has 17185 conditions, 6718 events. 3631/6718 cut-off events. For 5105/5107 co-relation queries the response was YES. Maximal size of possible extension queue 166. Compared 42149 event pairs, 347 based on Foata normal form. 0/6430 useless extension candidates. Maximal degree in co-relation 15655. Up to 1346 conditions per place. [2024-05-12 11:10:29,441 INFO L140 encePairwiseOnDemand]: 36/42 looper letters, 218 selfloop transitions, 31 changer transitions 3/260 dead transitions. [2024-05-12 11:10:29,442 INFO L145 encePairwiseOnDemand]: Finished differencePairwiseOnDemand. Result has 62 places, 260 transitions, 1453 flow [2024-05-12 11:10:29,442 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2024-05-12 11:10:29,442 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 14 states. [2024-05-12 11:10:29,443 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 14 states to 14 states and 346 transitions. [2024-05-12 11:10:29,443 INFO L516 CegarLoopForPetriNet]: DFA transition density 0.5884353741496599 [2024-05-12 11:10:29,443 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:29,443 INFO L82 GeneralOperation]: Start removeRedundantFlow. Operand has 62 places, 260 transitions, 1453 flow [2024-05-12 11:10:29,447 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:29,449 INFO L231 Difference]: Finished difference. Result has 70 places, 73 transitions, 472 flow [2024-05-12 11:10:29,450 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=6, PETRI_DIFFERENCE_SUBTRAHEND_LOOPER_ONLY_LETTERS=35, PETRI_DIFFERENCE_SUBTRAHEND_STATES=14, PETRI_FLOW=472, PETRI_PLACES=70, PETRI_TRANSITIONS=73} [2024-05-12 11:10:29,450 INFO L281 CegarLoopForPetriNet]: 40 programPoint places, 30 predicate places. [2024-05-12 11:10:29,450 INFO L495 AbstractCegarLoop]: Abstraction has has 70 places, 73 transitions, 472 flow [2024-05-12 11:10:29,451 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 9 states have (on average 13.11111111111111) internal successors, (118), 9 states have internal predecessors, (118), 0 states have call successors, (0), 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:29,451 INFO L200 CegarLoopForPetriNet]: Found error trace [2024-05-12 11:10:29,451 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:29,464 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Ended with exit code 0 [2024-05-12 11:10:29,664 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:29,665 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:29,665 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2024-05-12 11:10:29,665 INFO L85 PathProgramCache]: Analyzing trace with hash 2079318118, now seen corresponding path program 1 times [2024-05-12 11:10:29,666 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-05-12 11:10:29,666 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1897824667] [2024-05-12 11:10:29,666 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-05-12 11:10:29,666 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-05-12 11:10:29,679 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-05-12 11:10:29,723 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:29,723 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-05-12 11:10:29,724 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1897824667] [2024-05-12 11:10:29,724 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1897824667] provided 1 perfect and 0 imperfect interpolant sequences [2024-05-12 11:10:29,724 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-05-12 11:10:29,724 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2024-05-12 11:10:29,724 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [585292113] [2024-05-12 11:10:29,724 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-05-12 11:10:29,725 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2024-05-12 11:10:29,725 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-05-12 11:10:29,725 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2024-05-12 11:10:29,725 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2024-05-12 11:10:29,726 INFO L471 CegarLoopForPetriNet]: Number of universal loopers: 11 out of 42 [2024-05-12 11:10:29,726 INFO L103 encePairwiseOnDemand]: Start differencePairwiseOnDemand. First operand has 70 places, 73 transitions, 472 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:29,726 INFO L112 encePairwiseOnDemand]: Universal subtrahend loopers provided by user. [2024-05-12 11:10:29,726 INFO L113 encePairwiseOnDemand]: Number of universal subtrahend loopers: 11 of 42 [2024-05-12 11:10:29,726 INFO L73 FinitePrefix]: Start finitePrefix. Operand will be constructed on-demand [2024-05-12 11:10:30,013 INFO L124 PetriNetUnfolderBase]: 1623/3314 cut-off events. [2024-05-12 11:10:30,014 INFO L125 PetriNetUnfolderBase]: For 4831/4831 co-relation queries the response was YES. [2024-05-12 11:10:30,023 INFO L83 FinitePrefix]: Finished finitePrefix Result has 8860 conditions, 3314 events. 1623/3314 cut-off events. For 4831/4831 co-relation queries the response was YES. Maximal size of possible extension queue 85. Compared 18976 event pairs, 561 based on Foata normal form. 175/3430 useless extension candidates. Maximal degree in co-relation 8502. Up to 1579 conditions per place. [2024-05-12 11:10:30,038 INFO L140 encePairwiseOnDemand]: 38/42 looper letters, 53 selfloop transitions, 4 changer transitions 0/70 dead transitions. [2024-05-12 11:10:30,039 INFO L145 encePairwiseOnDemand]: Finished differencePairwiseOnDemand. Result has 70 places, 70 transitions, 480 flow [2024-05-12 11:10:30,039 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2024-05-12 11:10:30,039 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 3 states. [2024-05-12 11:10:30,040 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 3 states to 3 states and 75 transitions. [2024-05-12 11:10:30,040 INFO L516 CegarLoopForPetriNet]: DFA transition density 0.5952380952380952 [2024-05-12 11:10:30,040 INFO L175 Difference]: Start difference. First operand has 70 places, 73 transitions, 472 flow. Second operand 3 states and 75 transitions. [2024-05-12 11:10:30,040 INFO L82 GeneralOperation]: Start removeRedundantFlow. Operand has 70 places, 70 transitions, 480 flow [2024-05-12 11:10:30,062 INFO L88 GeneralOperation]: Finished removeRedundantFlow, result has has 64 places, 70 transitions, 423 flow, removed 22 selfloop flow, removed 6 redundant places. [2024-05-12 11:10:30,064 INFO L231 Difference]: Finished difference. Result has 64 places, 57 transitions, 288 flow [2024-05-12 11:10:30,064 INFO L264 CegarLoopForPetriNet]: {PETRI_ALPHABET=42, PETRI_DIFFERENCE_MINUEND_FLOW=280, PETRI_DIFFERENCE_MINUEND_PLACES=62, PETRI_DIFFERENCE_MINUEND_TRANSITIONS=57, PETRI_DIFFERENCE_SUBTRAHEND_LETTERS_WITH_MORE_CHANGERS_THAN_LOOPERS=4, PETRI_DIFFERENCE_SUBTRAHEND_LOOPER_ONLY_LETTERS=53, PETRI_DIFFERENCE_SUBTRAHEND_STATES=3, PETRI_FLOW=288, PETRI_PLACES=64, PETRI_TRANSITIONS=57} [2024-05-12 11:10:30,065 INFO L281 CegarLoopForPetriNet]: 40 programPoint places, 24 predicate places. [2024-05-12 11:10:30,066 INFO L495 AbstractCegarLoop]: Abstraction has has 64 places, 57 transitions, 288 flow [2024-05-12 11:10:30,066 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:30,066 INFO L200 CegarLoopForPetriNet]: Found error trace [2024-05-12 11:10:30,066 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:30,066 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6 [2024-05-12 11:10:30,067 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:30,067 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2024-05-12 11:10:30,067 INFO L85 PathProgramCache]: Analyzing trace with hash 1092617145, now seen corresponding path program 1 times [2024-05-12 11:10:30,067 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-05-12 11:10:30,067 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [520495866] [2024-05-12 11:10:30,067 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-05-12 11:10:30,068 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-05-12 11:10:30,094 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-05-12 11:10:30,486 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:30,486 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-05-12 11:10:30,487 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [520495866] [2024-05-12 11:10:30,487 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [520495866] provided 1 perfect and 0 imperfect interpolant sequences [2024-05-12 11:10:30,487 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-05-12 11:10:30,487 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2024-05-12 11:10:30,487 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1748616035] [2024-05-12 11:10:30,488 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-05-12 11:10:30,488 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-05-12 11:10:30,488 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-05-12 11:10:30,489 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-05-12 11:10:30,489 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-05-12 11:10:30,493 INFO L471 CegarLoopForPetriNet]: Number of universal loopers: 9 out of 42 [2024-05-12 11:10:30,493 INFO L103 encePairwiseOnDemand]: Start differencePairwiseOnDemand. First operand has 64 places, 57 transitions, 288 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:30,493 INFO L112 encePairwiseOnDemand]: Universal subtrahend loopers provided by user. [2024-05-12 11:10:30,493 INFO L113 encePairwiseOnDemand]: Number of universal subtrahend loopers: 9 of 42 [2024-05-12 11:10:30,493 INFO L73 FinitePrefix]: Start finitePrefix. Operand will be constructed on-demand [2024-05-12 11:10:30,794 INFO L124 PetriNetUnfolderBase]: 1673/3321 cut-off events. [2024-05-12 11:10:30,794 INFO L125 PetriNetUnfolderBase]: For 3560/3560 co-relation queries the response was YES. [2024-05-12 11:10:30,801 INFO L83 FinitePrefix]: Finished finitePrefix Result has 8587 conditions, 3321 events. 1673/3321 cut-off events. For 3560/3560 co-relation queries the response was YES. Maximal size of possible extension queue 91. Compared 18455 event pairs, 478 based on Foata normal form. 0/3263 useless extension candidates. Maximal degree in co-relation 7949. Up to 2328 conditions per place. [2024-05-12 11:10:30,810 INFO L140 encePairwiseOnDemand]: 37/42 looper letters, 79 selfloop transitions, 5 changer transitions 3/95 dead transitions. [2024-05-12 11:10:30,810 INFO L145 encePairwiseOnDemand]: Finished differencePairwiseOnDemand. Result has 68 places, 95 transitions, 577 flow [2024-05-12 11:10:30,811 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-05-12 11:10:30,811 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 5 states. [2024-05-12 11:10:30,811 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 115 transitions. [2024-05-12 11:10:30,811 INFO L516 CegarLoopForPetriNet]: DFA transition density 0.5476190476190477 [2024-05-12 11:10:30,811 INFO L175 Difference]: Start difference. First operand has 64 places, 57 transitions, 288 flow. Second operand 5 states and 115 transitions. [2024-05-12 11:10:30,812 INFO L82 GeneralOperation]: Start removeRedundantFlow. Operand has 68 places, 95 transitions, 577 flow [2024-05-12 11:10:30,818 INFO L88 GeneralOperation]: Finished removeRedundantFlow, result has has 66 places, 95 transitions, 555 flow, removed 0 selfloop flow, removed 2 redundant places. [2024-05-12 11:10:30,819 INFO L231 Difference]: Finished difference. Result has 68 places, 59 transitions, 309 flow [2024-05-12 11:10:30,819 INFO L264 CegarLoopForPetriNet]: {PETRI_ALPHABET=42, PETRI_DIFFERENCE_MINUEND_FLOW=280, PETRI_DIFFERENCE_MINUEND_PLACES=62, PETRI_DIFFERENCE_MINUEND_TRANSITIONS=57, PETRI_DIFFERENCE_SUBTRAHEND_LETTERS_WITH_MORE_CHANGERS_THAN_LOOPERS=3, PETRI_DIFFERENCE_SUBTRAHEND_LOOPER_ONLY_LETTERS=52, PETRI_DIFFERENCE_SUBTRAHEND_STATES=5, PETRI_FLOW=309, PETRI_PLACES=68, PETRI_TRANSITIONS=59} [2024-05-12 11:10:30,821 INFO L281 CegarLoopForPetriNet]: 40 programPoint places, 28 predicate places. [2024-05-12 11:10:30,821 INFO L495 AbstractCegarLoop]: Abstraction has has 68 places, 59 transitions, 309 flow [2024-05-12 11:10:30,821 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:30,822 INFO L200 CegarLoopForPetriNet]: Found error trace [2024-05-12 11:10:30,822 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:30,822 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7 [2024-05-12 11:10:30,822 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:30,822 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2024-05-12 11:10:30,822 INFO L85 PathProgramCache]: Analyzing trace with hash 1362058859, now seen corresponding path program 1 times [2024-05-12 11:10:30,823 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-05-12 11:10:30,823 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1828917136] [2024-05-12 11:10:30,824 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-05-12 11:10:30,824 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-05-12 11:10:30,838 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-05-12 11:10:30,932 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:30,933 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-05-12 11:10:30,933 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1828917136] [2024-05-12 11:10:30,933 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1828917136] provided 1 perfect and 0 imperfect interpolant sequences [2024-05-12 11:10:30,933 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-05-12 11:10:30,935 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2024-05-12 11:10:30,936 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [88229474] [2024-05-12 11:10:30,936 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-05-12 11:10:30,936 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-05-12 11:10:30,937 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-05-12 11:10:30,937 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-05-12 11:10:30,937 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=11, Unknown=0, NotChecked=0, Total=20 [2024-05-12 11:10:30,943 INFO L471 CegarLoopForPetriNet]: Number of universal loopers: 8 out of 42 [2024-05-12 11:10:30,943 INFO L103 encePairwiseOnDemand]: Start differencePairwiseOnDemand. First operand has 68 places, 59 transitions, 309 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:30,943 INFO L112 encePairwiseOnDemand]: Universal subtrahend loopers provided by user. [2024-05-12 11:10:30,943 INFO L113 encePairwiseOnDemand]: Number of universal subtrahend loopers: 8 of 42 [2024-05-12 11:10:30,943 INFO L73 FinitePrefix]: Start finitePrefix. Operand will be constructed on-demand [2024-05-12 11:10:31,331 INFO L124 PetriNetUnfolderBase]: 2240/4267 cut-off events. [2024-05-12 11:10:31,331 INFO L125 PetriNetUnfolderBase]: For 3878/3878 co-relation queries the response was YES. [2024-05-12 11:10:31,340 INFO L83 FinitePrefix]: Finished finitePrefix Result has 10613 conditions, 4267 events. 2240/4267 cut-off events. For 3878/3878 co-relation queries the response was YES. Maximal size of possible extension queue 107. Compared 23501 event pairs, 261 based on Foata normal form. 27/4213 useless extension candidates. Maximal degree in co-relation 9003. Up to 1572 conditions per place. [2024-05-12 11:10:31,352 INFO L140 encePairwiseOnDemand]: 37/42 looper letters, 100 selfloop transitions, 7 changer transitions 3/116 dead transitions. [2024-05-12 11:10:31,352 INFO L145 encePairwiseOnDemand]: Finished differencePairwiseOnDemand. Result has 72 places, 116 transitions, 751 flow [2024-05-12 11:10:31,352 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-05-12 11:10:31,352 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 5 states. [2024-05-12 11:10:31,353 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 120 transitions. [2024-05-12 11:10:31,353 INFO L516 CegarLoopForPetriNet]: DFA transition density 0.5714285714285714 [2024-05-12 11:10:31,353 INFO L175 Difference]: Start difference. First operand has 68 places, 59 transitions, 309 flow. Second operand 5 states and 120 transitions. [2024-05-12 11:10:31,353 INFO L82 GeneralOperation]: Start removeRedundantFlow. Operand has 72 places, 116 transitions, 751 flow [2024-05-12 11:10:31,360 INFO L88 GeneralOperation]: Finished removeRedundantFlow, result has has 70 places, 116 transitions, 746 flow, removed 0 selfloop flow, removed 2 redundant places. [2024-05-12 11:10:31,363 INFO L231 Difference]: Finished difference. Result has 71 places, 61 transitions, 349 flow [2024-05-12 11:10:31,363 INFO L264 CegarLoopForPetriNet]: {PETRI_ALPHABET=42, PETRI_DIFFERENCE_MINUEND_FLOW=304, PETRI_DIFFERENCE_MINUEND_PLACES=66, PETRI_DIFFERENCE_MINUEND_TRANSITIONS=59, PETRI_DIFFERENCE_SUBTRAHEND_LETTERS_WITH_MORE_CHANGERS_THAN_LOOPERS=5, PETRI_DIFFERENCE_SUBTRAHEND_LOOPER_ONLY_LETTERS=52, PETRI_DIFFERENCE_SUBTRAHEND_STATES=5, PETRI_FLOW=349, PETRI_PLACES=71, PETRI_TRANSITIONS=61} [2024-05-12 11:10:31,364 INFO L281 CegarLoopForPetriNet]: 40 programPoint places, 31 predicate places. [2024-05-12 11:10:31,364 INFO L495 AbstractCegarLoop]: Abstraction has has 71 places, 61 transitions, 349 flow [2024-05-12 11:10:31,364 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:31,364 INFO L200 CegarLoopForPetriNet]: Found error trace [2024-05-12 11:10:31,365 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:31,365 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8 [2024-05-12 11:10:31,365 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:31,365 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2024-05-12 11:10:31,365 INFO L85 PathProgramCache]: Analyzing trace with hash 1770766832, now seen corresponding path program 1 times [2024-05-12 11:10:31,365 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-05-12 11:10:31,366 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1437318198] [2024-05-12 11:10:31,366 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-05-12 11:10:31,366 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-05-12 11:10:31,405 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-05-12 11:10:31,743 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:31,743 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-05-12 11:10:31,743 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1437318198] [2024-05-12 11:10:31,743 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1437318198] provided 0 perfect and 1 imperfect interpolant sequences [2024-05-12 11:10:31,744 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [300528989] [2024-05-12 11:10:31,744 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-05-12 11:10:31,744 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-05-12 11:10:31,744 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-05-12 11:10:31,745 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:31,771 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:31,851 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-05-12 11:10:31,852 INFO L262 TraceCheckSpWp]: Trace formula consists of 224 conjuncts, 13 conjunts are in the unsatisfiable core [2024-05-12 11:10:31,855 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2024-05-12 11:10:31,877 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:31,916 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:31,979 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:32,021 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:32,021 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2024-05-12 11:10:32,331 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:32,386 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:32,387 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [300528989] provided 0 perfect and 2 imperfect interpolant sequences [2024-05-12 11:10:32,387 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-05-12 11:10:32,387 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 5, 5] total 13 [2024-05-12 11:10:32,387 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1545767264] [2024-05-12 11:10:32,387 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-05-12 11:10:32,388 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2024-05-12 11:10:32,388 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-05-12 11:10:32,388 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2024-05-12 11:10:32,388 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=40, Invalid=142, Unknown=0, NotChecked=0, Total=182 [2024-05-12 11:10:32,392 INFO L471 CegarLoopForPetriNet]: Number of universal loopers: 9 out of 42 [2024-05-12 11:10:32,392 INFO L103 encePairwiseOnDemand]: Start differencePairwiseOnDemand. First operand has 71 places, 61 transitions, 349 flow. Second operand has 14 states, 14 states have (on average 13.5) internal successors, (189), 14 states have internal predecessors, (189), 0 states have call successors, (0), 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,392 INFO L112 encePairwiseOnDemand]: Universal subtrahend loopers provided by user. [2024-05-12 11:10:32,392 INFO L113 encePairwiseOnDemand]: Number of universal subtrahend loopers: 9 of 42 [2024-05-12 11:10:32,392 INFO L73 FinitePrefix]: Start finitePrefix. Operand will be constructed on-demand [2024-05-12 11:10:33,399 INFO L124 PetriNetUnfolderBase]: 3418/6707 cut-off events. [2024-05-12 11:10:33,399 INFO L125 PetriNetUnfolderBase]: For 8360/8360 co-relation queries the response was YES. [2024-05-12 11:10:33,416 INFO L83 FinitePrefix]: Finished finitePrefix Result has 16984 conditions, 6707 events. 3418/6707 cut-off events. For 8360/8360 co-relation queries the response was YES. Maximal size of possible extension queue 162. Compared 41991 event pairs, 608 based on Foata normal form. 45/6674 useless extension candidates. Maximal degree in co-relation 14943. Up to 1809 conditions per place. [2024-05-12 11:10:33,434 INFO L140 encePairwiseOnDemand]: 36/42 looper letters, 202 selfloop transitions, 38 changer transitions 0/249 dead transitions. [2024-05-12 11:10:33,434 INFO L145 encePairwiseOnDemand]: Finished differencePairwiseOnDemand. Result has 83 places, 249 transitions, 1570 flow [2024-05-12 11:10:33,435 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2024-05-12 11:10:33,435 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 14 states. [2024-05-12 11:10:33,436 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 14 states to 14 states and 337 transitions. [2024-05-12 11:10:33,436 INFO L516 CegarLoopForPetriNet]: DFA transition density 0.5731292517006803 [2024-05-12 11:10:33,436 INFO L175 Difference]: Start difference. First operand has 71 places, 61 transitions, 349 flow. Second operand 14 states and 337 transitions. [2024-05-12 11:10:33,436 INFO L82 GeneralOperation]: Start removeRedundantFlow. Operand has 83 places, 249 transitions, 1570 flow [2024-05-12 11:10:33,450 INFO L88 GeneralOperation]: Finished removeRedundantFlow, result has has 79 places, 249 transitions, 1522 flow, removed 17 selfloop flow, removed 4 redundant places. [2024-05-12 11:10:33,454 INFO L231 Difference]: Finished difference. Result has 86 places, 91 transitions, 706 flow [2024-05-12 11:10:33,455 INFO L264 CegarLoopForPetriNet]: {PETRI_ALPHABET=42, PETRI_DIFFERENCE_MINUEND_FLOW=299, PETRI_DIFFERENCE_MINUEND_PLACES=66, PETRI_DIFFERENCE_MINUEND_TRANSITIONS=57, PETRI_DIFFERENCE_SUBTRAHEND_LETTERS_WITH_MORE_CHANGERS_THAN_LOOPERS=16, PETRI_DIFFERENCE_SUBTRAHEND_LOOPER_ONLY_LETTERS=40, PETRI_DIFFERENCE_SUBTRAHEND_STATES=14, PETRI_FLOW=706, PETRI_PLACES=86, PETRI_TRANSITIONS=91} [2024-05-12 11:10:33,455 INFO L281 CegarLoopForPetriNet]: 40 programPoint places, 46 predicate places. [2024-05-12 11:10:33,455 INFO L495 AbstractCegarLoop]: Abstraction has has 86 places, 91 transitions, 706 flow [2024-05-12 11:10:33,456 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 14 states, 14 states have (on average 13.5) internal successors, (189), 14 states have internal predecessors, (189), 0 states have call successors, (0), 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,456 INFO L200 CegarLoopForPetriNet]: Found error trace [2024-05-12 11:10:33,456 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:33,469 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Ended with exit code 0 [2024-05-12 11:10:33,667 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:33,668 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:33,668 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2024-05-12 11:10:33,668 INFO L85 PathProgramCache]: Analyzing trace with hash -1315737650, now seen corresponding path program 1 times [2024-05-12 11:10:33,669 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-05-12 11:10:33,669 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [918431817] [2024-05-12 11:10:33,669 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-05-12 11:10:33,670 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-05-12 11:10:33,744 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-05-12 11:10:33,745 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-05-12 11:10:33,798 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-05-12 11:10:33,824 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-05-12 11:10:33,824 INFO L360 BasicCegarLoop]: Counterexample is feasible [2024-05-12 11:10:33,825 INFO L805 garLoopResultBuilder]: Registering result UNSAFE for location t2Err0ASSERT_VIOLATIONERROR_FUNCTION (7 of 8 remaining) [2024-05-12 11:10:33,826 INFO L805 garLoopResultBuilder]: Registering result UNKNOWN for location ULTIMATE.startErr0ASSERT_VIOLATIONWITNESS_INVARIANT (6 of 8 remaining) [2024-05-12 11:10:33,826 INFO L805 garLoopResultBuilder]: Registering result UNKNOWN for location ULTIMATE.startErr1ASSERT_VIOLATIONWITNESS_INVARIANT (5 of 8 remaining) [2024-05-12 11:10:33,827 INFO L805 garLoopResultBuilder]: Registering result UNKNOWN for location ULTIMATE.startErr0INUSE_VIOLATIONSUFFICIENT_THREAD_INSTANCES (4 of 8 remaining) [2024-05-12 11:10:33,827 INFO L805 garLoopResultBuilder]: Registering result UNKNOWN for location ULTIMATE.startErr1INUSE_VIOLATIONSUFFICIENT_THREAD_INSTANCES (3 of 8 remaining) [2024-05-12 11:10:33,827 INFO L805 garLoopResultBuilder]: Registering result UNKNOWN for location t1Err0ASSERT_VIOLATIONERROR_FUNCTION (2 of 8 remaining) [2024-05-12 11:10:33,827 INFO L805 garLoopResultBuilder]: Registering result UNKNOWN for location t2Err0ASSERT_VIOLATIONERROR_FUNCTION (1 of 8 remaining) [2024-05-12 11:10:33,827 INFO L805 garLoopResultBuilder]: Registering result UNKNOWN for location t1Err0ASSERT_VIOLATIONERROR_FUNCTION (0 of 8 remaining) [2024-05-12 11:10:33,828 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable10 [2024-05-12 11:10:33,828 INFO L445 BasicCegarLoop]: Path program histogram: [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-05-12 11:10:33,832 INFO L229 ceAbstractionStarter]: Analysis of concurrent program completed with 1 thread instances [2024-05-12 11:10:33,832 INFO L179 ceAbstractionStarter]: Computing trace abstraction results [2024-05-12 11:10:33,880 INFO L507 ceAbstractionStarter]: Automizer considered 2 witness invariants [2024-05-12 11:10:33,881 INFO L508 ceAbstractionStarter]: WitnessConsidered=2 [2024-05-12 11:10:33,881 INFO L201 PluginConnector]: Adding new model witness.yml de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 12.05 11:10:33 BasicIcfg [2024-05-12 11:10:33,881 INFO L131 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2024-05-12 11:10:33,882 INFO L158 Benchmark]: Toolchain (without parser) took 9472.71ms. Allocated memory was 203.4MB in the beginning and 599.8MB in the end (delta: 396.4MB). Free memory was 120.3MB in the beginning and 213.1MB in the end (delta: -92.7MB). Peak memory consumption was 305.0MB. Max. memory is 16.1GB. [2024-05-12 11:10:33,882 INFO L158 Benchmark]: CDTParser took 0.16ms. Allocated memory is still 203.4MB. Free memory is still 153.4MB. There was no memory consumed. Max. memory is 16.1GB. [2024-05-12 11:10:33,882 INFO L158 Benchmark]: Witness Parser took 6.15ms. Allocated memory is still 203.4MB. Free memory is still 123.5MB. There was no memory consumed. Max. memory is 16.1GB. [2024-05-12 11:10:33,882 INFO L158 Benchmark]: CACSL2BoogieTranslator took 717.40ms. Allocated memory was 203.4MB in the beginning and 310.4MB in the end (delta: 107.0MB). Free memory was 120.0MB in the beginning and 274.3MB in the end (delta: -154.3MB). Peak memory consumption was 49.8MB. Max. memory is 16.1GB. [2024-05-12 11:10:33,883 INFO L158 Benchmark]: Boogie Procedure Inliner took 65.84ms. Allocated memory is still 310.4MB. Free memory was 274.3MB in the beginning and 271.1MB in the end (delta: 3.1MB). Peak memory consumption was 4.2MB. Max. memory is 16.1GB. [2024-05-12 11:10:33,883 INFO L158 Benchmark]: Boogie Preprocessor took 70.27ms. Allocated memory is still 310.4MB. Free memory was 271.1MB in the beginning and 269.0MB in the end (delta: 2.1MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. [2024-05-12 11:10:33,883 INFO L158 Benchmark]: RCFGBuilder took 669.97ms. Allocated memory is still 310.4MB. Free memory was 269.0MB in the beginning and 218.7MB in the end (delta: 50.3MB). Peak memory consumption was 50.3MB. Max. memory is 16.1GB. [2024-05-12 11:10:33,883 INFO L158 Benchmark]: TraceAbstraction took 7944.33ms. Allocated memory was 310.4MB in the beginning and 599.8MB in the end (delta: 289.4MB). Free memory was 217.7MB in the beginning and 213.1MB in the end (delta: 4.6MB). Peak memory consumption was 295.1MB. Max. memory is 16.1GB. [2024-05-12 11:10:33,885 INFO L338 ainManager$Toolchain]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * CDTParser took 0.16ms. Allocated memory is still 203.4MB. Free memory is still 153.4MB. There was no memory consumed. Max. memory is 16.1GB. * Witness Parser took 6.15ms. Allocated memory is still 203.4MB. Free memory is still 123.5MB. There was no memory consumed. Max. memory is 16.1GB. * CACSL2BoogieTranslator took 717.40ms. Allocated memory was 203.4MB in the beginning and 310.4MB in the end (delta: 107.0MB). Free memory was 120.0MB in the beginning and 274.3MB in the end (delta: -154.3MB). Peak memory consumption was 49.8MB. Max. memory is 16.1GB. * Boogie Procedure Inliner took 65.84ms. Allocated memory is still 310.4MB. Free memory was 274.3MB in the beginning and 271.1MB in the end (delta: 3.1MB). Peak memory consumption was 4.2MB. Max. memory is 16.1GB. * Boogie Preprocessor took 70.27ms. Allocated memory is still 310.4MB. Free memory was 271.1MB in the beginning and 269.0MB in the end (delta: 2.1MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. * RCFGBuilder took 669.97ms. Allocated memory is still 310.4MB. Free memory was 269.0MB in the beginning and 218.7MB in the end (delta: 50.3MB). Peak memory consumption was 50.3MB. Max. memory is 16.1GB. * TraceAbstraction took 7944.33ms. Allocated memory was 310.4MB in the beginning and 599.8MB in the end (delta: 289.4MB). Free memory was 217.7MB in the beginning and 213.1MB in the end (delta: 4.6MB). Peak memory consumption was 295.1MB. 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 m_locked = 0; [L1] 0 //@ ghost int multithreaded = 0; [L935] 0 static int top=0; [L936] 0 static unsigned int arr[(5)]; [L936] 0 static unsigned int arr[(5)]; [L936] 0 static unsigned int arr[(5)]; [L936] 0 static unsigned int arr[(5)]; [L936] 0 static unsigned int arr[(5)]; [L936] 0 static unsigned int arr[(5)]; [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); [L1021] 0 pthread_t id1, id2; [L1023] 0 //@ ghost multithreaded = 1; [L1023] FCALL, FORK 0 pthread_create(&id1, ((void *)0), t1, ((void *)0)) VAL [arr={3:0}, flag=0, id1={5:0}, id2={6:0}, m={4:0}, top=0] [L990] 1 int i; [L991] 1 unsigned int tmp; [L992] 1 i=0 VAL [\old(arg)={0:0}, arg={0:0}, arr={3:0}, flag=0, i=0, m={4:0}, top=0] [L992] COND TRUE 1 i<(5) VAL [\old(arg)={0:0}, arg={0:0}, arr={3:0}, flag=0, i=0, m={4:0}, top=0] [L994] 1 //@ ghost m_locked = 1; [L1024] 0 //@ assert (!multithreaded || (m_locked || (((long long) flag + (long long) top) >= 0LL))); [L1024] FCALL, FORK 0 pthread_create(&id2, ((void *)0), t2, ((void *)0)) VAL [arr={3:0}, flag=0, id1={5:0}, id2={6:0}, m={4:0}, top=0] [L1006] 2 int i; [L1007] 2 i=0 VAL [\old(arg)={0:0}, arg={0:0}, arr={3:0}, flag=0, i=0, m={4:0}, top=0] [L995] 1 tmp = __VERIFIER_nondet_uint() [L996] CALL 1 assume_abort_if_not(tmp < (5)) [L23] COND FALSE 1 !(!cond) [L996] RET 1 assume_abort_if_not(tmp < (5)) [L997] CALL, EXPR 1 push(arr,tmp) [L962] COND FALSE 1 !(top==(5)) [L969] CALL, EXPR 1 get_top() [L954] 1 return top; [L969] RET, EXPR 1 get_top() [L969] 1 stack[get_top()] = x [L970] CALL 1 inc_top() [L946] 1 top++ [L970] RET 1 inc_top() [L972] 1 return 0; [L997] RET, EXPR 1 push(arr,tmp) [L997] COND FALSE 1 !(push(arr,tmp)==(-1)) [L999] 1 flag=(1) VAL [\old(arg)={0:0}, arg={0:0}, arr={3:0}, flag=1, i=0, m={4:0}, tmp=1, top=1] [L1007] COND TRUE 2 i<(5) VAL [\old(arg)={0:0}, arg={0:0}, arr={3:0}, flag=1, i=0, m={4:0}, top=1] [L1000] 1 //@ ghost m_locked = 0; [L1009] 2 //@ ghost m_locked = 1; [L1010] COND TRUE 2 \read(flag) [L1012] CALL, EXPR 2 pop(arr) [L976] CALL, EXPR 2 get_top() [L954] 2 return top; [L976] RET, EXPR 2 get_top() [L976] COND FALSE 2 !(get_top()==0) [L983] CALL 2 dec_top() [L950] 2 top-- [L983] RET 2 dec_top() [L984] CALL, EXPR 2 get_top() [L954] 2 return top; [L984] RET, EXPR 2 get_top() [L984] EXPR 2 stack[get_top()] [L984] 2 return stack[get_top()]; [L1012] RET, EXPR 2 pop(arr) [L1012] COND FALSE 2 !(!(pop(arr)!=(-2))) [L1015] 2 //@ ghost m_locked = 0; [L1007] 2 i++ VAL [\old(arg)={0:0}, arg={0:0}, arr={3:0}, flag=1, i=1, m={4:0}, top=0] [L1007] COND TRUE 2 i<(5) VAL [\old(arg)={0:0}, arg={0:0}, arr={3:0}, flag=1, i=1, m={4:0}, top=0] [L1009] 2 //@ ghost m_locked = 1; [L1010] COND TRUE 2 \read(flag) [L1012] CALL, EXPR 2 pop(arr) [L976] CALL, EXPR 2 get_top() [L954] 2 return top; [L976] RET, EXPR 2 get_top() [L976] COND TRUE 2 get_top()==0 [L979] 2 return (-2); [L1012] RET, EXPR 2 pop(arr) [L1012] COND TRUE 2 !(pop(arr)!=(-2)) [L1013] CALL 2 error() [L941] 2 reach_error() VAL [arr={3:0}, flag=1, m={4:0}, top=0] - 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: 1025]: 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 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: 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: 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: 7.8s, OverallIterations: 11, TraceHistogramMax: 2, PathProgramHistogramMax: 1, EmptinessCheckTime: 0.0s, AutomataDifference: 4.2s, DeadEndRemovalTime: 0.0s, HoareAnnotationTime: 0.0s, InitialAbstractionConstructionTime: 0.0s, HoareTripleCheckerStatistics: 0 mSolverCounterUnknown, 877 SdHoareTripleChecker+Valid, 1.1s IncrementalHoareTripleChecker+Time, 0 mSdLazyCounter, 855 mSDsluCounter, 25 SdHoareTripleChecker+Invalid, 0.9s Time, 0 mProtectedAction, 0 SdHoareTripleChecker+Unchecked, 0 IncrementalHoareTripleChecker+Unchecked, 12 mSDsCounter, 73 IncrementalHoareTripleChecker+Valid, 0 mProtectedPredicate, 1631 IncrementalHoareTripleChecker+Invalid, 1704 SdHoareTripleChecker+Unknown, 0 mSolverCounterNotChecked, 73 mSolverCounterUnsat, 13 mSDtfsCounter, 1631 mSolverCounterSat, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Unknown, PredicateUnifierStatistics: 0 DeclaredPredicates, 133 GetRequests, 82 SyntacticMatches, 1 SemanticMatches, 50 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 82 ImplicationChecksByTransitivity, 0.3s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=706occurred in iteration=10, InterpolantAutomatonStates: 60, 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.2s InterpolantComputationTime, 235 NumberOfCodeBlocks, 235 NumberOfCodeBlocksAsserted, 13 NumberOfCheckSat, 238 ConstructedInterpolants, 7 QuantifiedInterpolants, 2057 SizeOfPredicates, 21 NumberOfNonLiveVariables, 391 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:33,918 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