tlaplus: Running liveness checking with multiple workers can cause unsoundness: TLC fails to report a violation of a property

---- MODULE Github710 ----
VARIABLE x

Init ==
    x = FALSE

Next ==
    x' \in BOOLEAN 

Spec == 
    /\ Init
    /\ [][Next]_x

AtMostOnce ==
    [](x => [](~x => []~x))
====
SPECIFICATION Spec
PROPERTY AtMostOnce

Observe that the Spec in Github710 above does not define a fairness constraints. Thus, some valid counterexamples to the property AtMostOnce are stuttering after some state (e.g. vio1), or a (prefix of a) behavior where x transitions from true, to false, to true (vio2):

vio1

@lemmy ➜ /workspaces/tlaplus/tlatools (a401ad390) $  cd /workspaces/tlaplus/tlatools ; /usr/bin/env /opt/java/11.0.14/bin/java -agentlib:jdwp=transport=dt_socket,server=n,suspend=y,address=localhost:36251 -cp /workspaces/tlaplus/tlatools/class tlc2.TLC Github866.tla -workers 2 
TLC2 Version 2.03 of 10 March 2011
Running in Model-Checking mode.
Parsing file Github866.tla
Semantic processing of module Github866
Starting... (2024-06-22 23:23:44)
Implied-temporal checking--satisfiability problem has 1 branches.
Computing initial states...
Finished computing initial states: 1 distinct state generated.
Progress(2) at 2024-06-22 23:23:47: 5 states generated, 2 distinct states found, 0 states left on queue.
Checking temporal properties for the complete state space...
Error: Temporal properties were violated.

Error: The following behavior constitutes a counter-example:

State 1: <Initial predicate>
x = FALSE

State 2: Stuttering
5 states generated, 2 distinct states found, 0 states left on queue.
Finished. (2024-06-22 23:24:00)

vio2

TLC2 Version 2.18 of Day Month 20?? (rev: c9dadac)
Running breadth-first search Model-Checking with fp 22 and seed -4588059740923214664 with 1 worker on 10 cores with 7282MB heap and 64MB offheap memory [pid: 44885] (Mac OS X 13.6.7 aarch64, Homebrew 11.0.23 x86_64, MSBDiskFPSet, DiskStateQueue).
Parsing file /Users/markus/src/TLA/tla/tlatools/org.lamport.tlatools/Github866.tla
Semantic processing of module Github866
Starting... (2024-06-22 16:42:06)
Implied-temporal checking--satisfiability problem has 1 branches.
Computing initial states...
Finished computing initial states: 1 distinct state generated at 2024-06-22 16:42:06.
Error: Temporal properties were violated.

Error: The following behavior constitutes a counter-example:

State 1: <Initial predicate>
x = FALSE

State 2: <Next line 9, col 5 to line 9, col 18 of module Github866>
x = TRUE

State 3: <Next line 9, col 5 to line 9, col 18 of module Github866>
x = FALSE

State 4: <Next line 9, col 5 to line 9, col 18 of module Github866>
x = TRUE

5 states generated, 2 distinct states found, 0 states left on queue.
The depth of the complete state graph search is 2.
Finished in 00s at (2024-06-22 16:42:06)

Since at least 2011, verifying the Github710 with two (or more) workers can result in TLC finishing without reporting a counterexample:

@lemmy ➜ /workspaces/tlaplus/tlatools (a401ad390) $  cd /workspaces/tlaplus/tlatools ; /usr/bin/env /opt/java/11.0.14/bin/java -agentlib:jdwp=transport=dt_socket,server=n,suspend=y,address=localhost:41763 -cp /workspaces/tlaplus/tlatools/class tlc2.TLC Github866.tla -workers 2 
TLC2 Version 2.03 of 10 March 2011
Running in Model-Checking mode.
Parsing file Github866.tla
Semantic processing of module Github866
Starting... (2024-06-22 23:24:06)
Implied-temporal checking--satisfiability problem has 1 branches.
Computing initial states...
Finished computing initial states: 1 distinct state generated.
Progress(2) at 2024-06-22 23:24:09: 5 states generated, 2 distinct states found, 0 states left on queue.
Checking temporal properties for the complete state space...
Model checking completed. No error has been found.
  Estimates of the probability that TLC did not check all reachable states
  because two distinct states had the same fingerprint:
  calculated (optimistic):  val = 3.3E-19
  based on the actual fingerprints:  val = 1.1E-19
5 states generated, 2 distinct states found, 0 states left on queue.
The depth of the complete state graph search is 2.
Finished. (2024-06-22 23:24:20)
-> % java -cp class tlc2.TLC -note Github866 -workers 2
TLC2 Version 2.18 of Day Month 20??
Warning: Please run the Java VM, which executes TLC with a throughput optimized garbage collector, by passing the "-XX:+UseParallelGC" property.
(Use the -nowarning option to disable this warning.)
Running breadth-first search Model-Checking with fp 48 and seed 5508516891815624630 with 2 workers on 10 cores with 8192MB heap and 64MB offheap memory [pid: 47210] (Mac OS X 13.6.7 aarch64, Homebrew 11.0.23 x86_64, MSBDiskFPSet, DiskStateQueue).
Parsing file /Users/markus/src/TLA/tla/tlatools/org.lamport.tlatools/Github866.tla
Semantic processing of module Github866
Starting... (2024-06-22 17:01:02)
Implied-temporal checking--satisfiability problem has 1 branches.
Computing initial states...
Finished computing initial states: 1 distinct state generated at 2024-06-22 17:01:02.
Progress(2) at 2024-06-22 17:01:02: 5 states generated, 2 distinct states found, 0 states left on queue.
Checking temporal properties for the complete state space with 2 total distinct states at (2024-06-22 17:01:02)
Finished checking temporal properties in 00s at 2024-06-22 17:01:02
Model checking completed. No error has been found.
  Estimates of the probability that TLC did not check all reachable states
  because two distinct states had the same fingerprint:
  calculated (optimistic):  val = 3.3E-19
5 states generated, 2 distinct states found, 0 states left on queue.
The depth of the complete state graph search is 2.
The average outdegree of the complete state graph is 1 (minimum is 0, the maximum 1 and the 95th percentile is 1).
Finished in 00s at (2024-06-22 17:01:02)

This can occur if TLC follows the following worker (thread) schedule, leading it to incorrectly report that the specification satisfies AtMostOnce.

1. w1 pops x=FALSE from state queue
2. w2 blocks on the empty state queue
3. w1 pushes x=TRUE into the state queue (having evaluated Next for x=FALSE)
4. w2 pops x=TRUE from the state queue
5. w2 adds x=TRUE to the behavior graph before w1 adds x=FALSE to the graph

This issue was initially discovered by @FedericoPonzi when reproducing Github issue #866 by repurposing a spec from Github issue #710. However, Github #866 is an issue where TLC may report a counterexample when the RandomElement operator is used. Moreover, the relevant code is not for the issue above is not exercised by Github issue #866 (regardless of SpanTreeRandom!Safety being checked as an invariant or property).

About this issue

  • Original URL
  • State: closed
  • Created 2 years ago
  • Reactions: 1
  • Comments: 20 (18 by maintainers)

Commits related to this issue

Most upvoted comments

@craft095 []P and [][A]_v are not affected by this bug. Properties without a + in the tableau column of https://github.com/tlaplus/tlaplus/issues/971#issuecomment-2222089564 are not affected.

Posted: https://groups.google.com/g/tlaplus/c/A-YhwUfIHZ4/m/7xqyseTRAQAJ


I plan to send the following announcement to the TLA+ Google group later today. Please provide your feedback if you have any suggestions.

/cc @muenchnerkindl @xxyzzn @cnewcom


Federico Ponzi has identified a soundness bug in TLC that affects the verification of temporal properties, when TLC is configured with more than the default number of worker threads. This bug has existed since at least 2009 and possibly since support for the verification of temporal properties was first introduced.

The bug is caused by a concurrency issue in TLC, and we consider the likelihood of encountering this bug to be very low. However, it remains a critical issue that needs to be addressed.

For immediate mitigation, please check temporal properties using only a single worker (command line flag: -workers 1). By default, TLC runs with a single worker.

We are working on a fix and will release a new version of TLC once the bug is resolved. Announcements regarding the new release will be made here. For technical details or to offer assistance, please refer to the GitHub issue at https://github.com/tlaplus/tlaplus/issues/971.

With multithreaded TLC, successor states may be added to the behavior graph before their predecessor state, leading to the omission of these successor states from the graph. This situation occurs when a worker w_t dequeues state t from the state queue and addst to the behavior graph in the time between worker w_s enqueuing t in the state queue and adding s to the behavior graph. The omission of state t in the behavior graph can cause TLC to miss violations of temporal properties. Ignoring unusually shaped state graphs, such as a single behavior (think a counter spec), the probability of omitting t is particularly high at the beginning of the model checking process when the state queue is empty or nearly empty.

Spec Github971a (violation found)

Insertion order behavior graph: x=0, x=1 Exploration order x=1:

addNextState addNextState s->s addNextState s->s1 addNextState s->s
x=1 tid=2
(x=0 tid=7)
x=0 tid=8
(x=0 tid=5)
x=0 tid=6
(x=0 tid=5)
x=0 tid=6
(x=0 tid=5)
(x=0 tid=6)
x=1 tid=5
x=1 tid=4

Parents indicates ~TBGraphNode#isConsistent.

VioFound

Spec Github971a (violation missed)

Insertion order: x=1, x=0

addNextState addNextState s->s addNextState s->s1 addNextState s->s addNextState s->s addNextState s->s1
x=1 tid=- (setDone only)
x=0 tid=3
(x=0 tid=0)
(x=0 tid=1)
(x=0 tid=2)
x=0 tid=3
(x=1 tid=0)
(x=1 tid=1)
x=1 tid=2
(x=1 tid=7)
(x=1 tid=8)
x=1 tid=9
(x=1 tid=7)
(x=1 tid=8)
x=1 tid=9
(x=0 tid=7)
x=0 tid=8
(x=0 tid=5)
x=0 tid=6
(x=0 tid=5)
x=0 tid=6
(x=0 tid=5)
(x=0 tid=6)
x=1 tid=5 (why isDone = false?)
x=1 tid=6
(x=0 tid=5)
(x=0 tid=6)
x=1 tid=5
x=1 tid=6
x=0 tid=9
(x=0 tid=7)
x=0 tid=8
x=0 tid=9
(x=0 tid=7)
x=0 tid=8
x=0 tid=9
x=1 tid=7
x=1 tid=8
x=1 tid=9
x=1 tid=7
x=1 tid=8
x=1 tid=9
…
x=1 tid=3
(x=1 tid=0)
x=1 tid=1
x=1 tid=2
x=1 tid=3
x=0 tid=0
x=0 tid=1
x=0 tid=2
x=0 tid=3
x=1 tid=0
x=1 tid=1
x=1 tid=2
x=1 tid=3

Untitled

This is interesting issue. [](x => [](~x => []~x)) is a safety property. Therefore, any stuttering-like counterexample is invalid one. The correct counterexample should be: FALSE, TRUE, FALSE, TRUE, which is minimal and finite.

Agreed: https://github.com/tlaplus/tlaplus/pull/972/files#diff-edd1211b4ce3ff9ab7692c42399f066338f5bc153939bc7268b8a007ce8ac730R42 and https://github.com/tlaplus/tlaplus/commit/b740eef4056fdf58d664cf495bbcb2588e93eba8#diff-edd1211b4ce3ff9ab7692c42399f066338f5bc153939bc7268b8a007ce8ac730R78-R94