[Liveness Bug] Execution Engine Deadlock in strongconnect Due to Unbounded Busy-Wait

[SherlockShemol]

Summary

The execution engine in epaxos-exec.go contains an unbounded busy-wait loop that can cause system-wide deadlock when processing transitive dependencies.

Bug Type

Attribute	Value
Type	Liveness Violation
Severity	🔴 Critical
Threat Model	CFT (Compliant)

Problematic Code

File: src/epaxos/epaxos-exec.go, Lines 71-83

func (e *Exec) strongconnect(v *Instance, index *int) bool {
    // ...
    for q := int32(0); q < int32(e.r.N); q++ {
        inst := v.Deps[q]
        for i := e.r.ExecedUpTo[q] + 1; i <= inst; i++ {
            // BUG: Unbounded wait for instance to exist
            for e.r.InstanceSpace[q][i] == nil || e.r.InstanceSpace[q][i].Cmds == nil || v.Cmds == nil {
                time.Sleep(1000 * 1000)  // ← NO TIMEOUT! Can wait forever!
            }
            // ...
            // BUG: Unbounded wait for instance to be COMMITTED
            for e.r.InstanceSpace[q][i].Status != epaxosproto.COMMITTED {
                time.Sleep(1000 * 1000)  // ← NO TIMEOUT! INFINITE WAIT!
            }
            // ...
        }
    }
}

Root Cause

1. strongconnect (Tarjan's SCC algorithm) busy-waits for dependencies to become COMMITTED
2. The main executeCommands loop (which triggers recovery) is blocked waiting for strongconnect to return
3. Recovery for uncommitted dependencies cannot be initiated because the recovery trigger is in the blocked loop
4. Circular dependency: Execution waits for recovery, but recovery cannot start because execution is blocked

Trigger Conditions

1. Command X is COMMITTED with dependencies
2. One of X's transitive dependencies (e.g., Z) is PREACCEPTED but not COMMITTED
3. Z's leader has crashed
4. executeCommand(X) is called, which calls strongconnect
5. strongconnect enters unbounded busy-wait for Z to become COMMITTED
6. Recovery for Z cannot be triggered (blocked by strongconnect)
7. System deadlock

Deadlock Scenario

Dependency Chain: X → Y → Z

State:
  X: COMMITTED
  Y: COMMITTED  
  Z: PREACCEPTED (leader crashed)

Execution Flow:
  executeCommands() 
    → executeCommand(X)
      → findSCC(X)
        → strongconnect(X)
          → check dependency Y
            → strongconnect(Y)
              → check dependency Z
                → for Z.Status != COMMITTED {
                      time.Sleep(...)  // INFINITE WAIT!
                  }
                  // Recovery CANNOT be triggered!
                  // Because executeCommands is blocked here!

Impact

• System-wide execution deadlock
• All commands depending on the stuck chain cannot execute
• No automatic recovery possible
• Requires manual intervention (restart)

[SherlockShemol]

Additional Attack Vector: The Future Gap Attack

We discovered another manifestation of the same liveness bug when handling log holes (gaps in the instance sequence).

Scenario

When a command X depends on a "future" instance (e.g., R2.5) that has never been proposed, the execution engine's strongconnect function will busy-wait indefinitely for all instances from R2.0 to R2.5 to exist.

Problematic Code Path

// epaxos-exec.go line 70-83
for q := int32(0); q < int32(e.r.N); q++ {
    inst := v.Deps[q]  // e.g., deps[2] = 5 (depends on R2.5)
    for i := e.r.ExecedUpTo[q] + 1; i <= inst; i++ {
        // If ExecedUpTo[2] = -1, this iterates i = 0, 1, 2, 3, 4, 5
        // BUG: Waits forever for R2.0, R2.1, etc. to exist!
        for e.r.InstanceSpace[q][i] == nil || ... {
            time.Sleep(1000 * 1000)  // INFINITE WAIT for nil instances!
        }
    }
}

Why This Causes Deadlock

1. X is COMMITTED with deps[2] = 5 (depends on R2.5)
2. Instances R2.0 through R2.4 were never created (log holes)
3. strongconnect iterates from ExecedUpTo[2]+1 to 5
4. For each hole (R2.0, R2.1, ...), it busy-waits for the instance to exist
5. These instances will never exist unless explicitly recovered
6. But recovery is blocked because executeCommands is stuck in strongconnect!

Same Root Cause

This is the same root cause as the Daisy Chain attack:

• strongconnect has unbounded busy-wait loops
• The recovery trigger is in executeCommands, which is blocked by strongconnect
• Circular dependency: Execution waits for recovery, recovery cannot start

Additional Issue: crtInstance Blind Spot

The executeCommands loop only iterates up to crtInstance[q]:

for inst = r.ExecedUpTo[q] + 1; inst < r.crtInstance[q]; inst++ {
    // Recovery trigger here
}

If the hole is beyond what executeCommands iterates, recovery may never be triggered at all!

Suggested Fix (Same as Original)

Add timeout mechanism to strongconnect and trigger recovery for missing instances:

for e.r.InstanceSpace[q][i] == nil || ... {
    if time.Since(startTime) > MAX_WAIT_TIME {
        e.r.instancesToRecover <- &instanceId{q, i}
        return false  // Abort SCC, retry later
    }
    time.Sleep(1000 * 1000)
}

Conclusion

Both the Daisy Chain Attack (uncommitted transitive dependencies) and the Future Gap Attack (log holes) stem from the same root cause: unbounded busy-wait loops in strongconnect that block the recovery mechanism.