[Safety Bug] State Divergence Due to Unprotected EXECUTED Instances in handleCommit

[SherlockShemol]

Summary

A safety violation can occur when a leader executes a command on the Fast Path before broadcasting the Commit message, then crashes. Recovery may assign different dependencies to the command, causing different replicas to execute commands in different orders, leading to state machine divergence.

Bug Type

Attribute	Value
Type	Safety Violation (State Divergence)
Severity	🔴 Critical
Threat Model	CFT (Compliant)

Problematic Code

Problem 1: Race Condition Between Execution and Commit Broadcast

File: src/epaxos/epaxos.go, Lines 1050-1071

// handlePreAcceptReply function
if inst.lb.preAcceptOKs >= r.N/2 && inst.lb.allEqual && allCommitted && isInitialBallot(inst.ballot) {
    // ① Status set to COMMITTED first
    r.InstanceSpace[pareply.Replica][pareply.Instance].Status = epaxosproto.COMMITTED  // Line 1053
    r.updateCommitted(pareply.Replica)
    
    // ... reply to clients ...
    
    r.recordInstanceMetadata(inst)
    r.sync()
    
    // ② Commit message sent AFTER status change
    r.bcastCommit(pareply.Replica, pareply.Instance, inst.Cmds, inst.Seq, inst.Deps)  // Line 1071
}

The executeCommands goroutine (line 429) may see COMMITTED status and execute the command before bcastCommit is called.

Problem 2: Recovery Can Recalculate Dependencies

File: src/epaxos/epaxos.go, Lines 1518-1522

// handlePrepareReply function
if conf, q, i := r.findPreAcceptConflicts(ir.cmds, preply.Replica, preply.Instance, ir.seq, ir.deps); conf {
    if r.InstanceSpace[q][i].Status >= epaxosproto.COMMITTED {
        // Found committed conflict! Restart Phase1 with NEW deps
        r.startPhase1(preply.Replica, preply.Instance, inst.ballot, inst.lb.clientProposals, ir.cmds, len(ir.cmds))
        return
    }
}

Problem 3: startPhase1 Recalculates Dependencies

File: src/epaxos/epaxos.go, Lines 831-837

func (r *Replica) startPhase1(...) {
    seq := int32(0)
    var deps [DS]int32
    for q := 0; q < r.N; q++ {
        deps[q] = -1
    }
    
    // ⚠️ Recalculates deps based on CURRENT conflict map!
    seq, deps, _ = r.updateAttributes(cmds, seq, deps, replica, instance)  // Line 837
}

Problem 4: handleCommit Does Not Protect EXECUTED Instances

File: src/epaxos/epaxos.go, Lines 1279-1281

// handleCommit function
if inst != nil {
    // ⚠️ NO CHECK for EXECUTED status!
    inst.Seq = commit.Seq       // Overwrites Seq
    inst.Deps = commit.Deps     // Overwrites Deps
    inst.Status = epaxosproto.COMMITTED  // Downgrades from EXECUTED!
}

Trigger Conditions

All of the following must occur:

1. Leader (R0) achieves Fast Path for command X with deps=[]
2. executeCommands goroutine executes X before bcastCommit (race condition)
3. R0 crashes before or during bcastCommit
4. A conflicting command Y is proposed and committed on other replicas
5. Recovery for X discovers Y (COMMITTED) via findPreAcceptConflicts
6. startPhase1 recalculates X's deps to include Y: deps=[Y]
7. X is committed with deps=[Y]
8. R0 recovers and receives Commit(X, deps=[Y])
9. handleCommit overwrites X's deps (X was already EXECUTED with deps=[])

Attack Scenario Timeline

T0: R0 proposes X (key=K, value=100)
    Fast Path: all responders return deps=[]

T1: R0 sets X.Status = COMMITTED (line 1053)

T2: executeCommands goroutine sees COMMITTED
    Executes X: state[K] = 100
    X.Status = EXECUTED

T3: R0 crashes (before bcastCommit at line 1071)
    Commit(X, deps=[]) message NOT sent

T4: R1 proposes Y (key=K, value=200)
    Y sees X as PREACCEPTED
    Y.deps = [X]
    Y commits and executes

T5: R2 initiates recovery for X
    TryPreAccept finds Y (COMMITTED)
    startPhase1 recalculates: deps=[Y]
    X committed with deps=[Y]

T6: R0 recovers
    Receives Commit(X, deps=[Y])
    handleCommit overwrites X.Deps = [Y]
    X.Status = COMMITTED (downgraded from EXECUTED!)

State Divergence Result

R0 (Early Executor):
  Execution order: X → Y
  Final state: K = 200

R1 (Normal Executor):
  X.deps = [Y], Y.deps = [X]
  Cycle detected: X ↔ Y
  Order by Seq: Y.Seq < X.Seq
  Execution order: Y → X
  Final state: K = 100

❌ SAFETY VIOLATION: State machines diverged!
   R0: K = 200
   R1: K = 100

Impact

• Different replicas may execute the same commands in different orders
• State machines diverge permanently
• Violates the fundamental EPaxos guarantee of consistent execution order

[SherlockShemol]

Additional Attack Vector: The Shifting Sands Attack

We discovered another manifestation of the same root cause bug during SCC (Strongly Connected Component) execution.

Attack Scenario

When two commands form a dependency cycle (SCC) with the same Seq value, and handleCommit modifies Seq during SCC execution, different replicas may execute commands in different orders.

Timeline

┌─────────────────────────────────────────────────────────────────┐
│ R1 (Executor)              │ R2 (Recovery)                      │
├─────────────────────────────────────────────────────────────────┤
│ T1: Find SCC [X, Y]        │                                    │
│     X.Seq=10, Y.Seq=10     │                                    │
│                            │                                    │
│ T2: Sort SCC by Seq        │                                    │
│     Order: [X, Y]          │                                    │
│                            │                                    │
│ T3: Execute X              │                                    │
│     X.Status = EXECUTED    │                                    │
│                            │                                    │
│ ─────── RACE WINDOW ─────  │ T4: Recovery updates Y             │
│                            │     Commit(Y, Seq=1)               │
│                            │     handleCommit sets Y.Seq=1      │
│                            │                                    │
│ T5: Execute Y              │                                    │
│     (order already fixed!) │                                    │
│                            │                                    │
│ Final order: X → Y         │                                    │
└─────────────────────────────────────────────────────────────────┘

Meanwhile, R3 sorts with Y.Seq=1:
  Order: [Y, X] (Y.Seq=1 < X.Seq=10)
  Final order: Y → X

❌ R1 and R3 have different execution orders!

Root Cause (Same as Original Bug)

The execution engine's SCC sorting (epaxos-exec.go line 111) happens once:

// Line 106-129
if v.Lowlink == v.Index {
    list := stack[l:len(stack)]
    
    // Sorting happens ONCE
    sort.Sort(nodeArray(list))  // Line 111
    
    // Execution loop
    for _, w := range list {
        // If w.Seq is modified here by handleCommit,
        // it does NOT affect the already-sorted order!
        w.Status = epaxosproto.EXECUTED
    }
}

And handleCommit can modify Seq without any protection:

// Line 1279-1281
if inst != nil {
    inst.Seq = commit.Seq    // Can change during SCC execution!
    inst.Deps = commit.Deps
    inst.Status = epaxosproto.COMMITTED
}

State Divergence Result

R1 (sorted with Y.Seq=10):
  Execute X: K = 100
  Execute Y: K = 200
  Final: K = 200

R3 (sorted with Y.Seq=1):
  Execute Y: K = 200
  Execute X: K = 100
  Final: K = 100

❌ SAFETY VIOLATION: State divergence!

Trigger Conditions

1. Two commands in same SCC (dependency cycle)
2. Both have same Seq initially (tie-breaker scenario)
3. handleCommit updates Seq during SCC execution
4. Different replica sees updated Seq before sorting

Suggested Fix (Same as Original)

Protecting COMMITTED instances in handleCommit would fix both attack vectors:

if inst != nil {
    if inst.Status == epaxosproto.COMMITTED || inst.Status == epaxosproto.EXECUTED {
        // Do not modify Seq/Deps of already committed/executed instances
        if inst.Seq != commit.Seq || inst.Deps != commit.Deps {
            log.Warnf("Ignoring conflicting Commit for instance %d.%d", commit.Replica, commit.Instance)
        }
        return
    }
    inst.Seq = commit.Seq
    inst.Deps = commit.Deps
    inst.Status = epaxosproto.COMMITTED
}

Conclusion

Both the Latent Conflict Attack and the Shifting Sands Attack stem from the same root cause: handleCommit can modify Seq and Deps of instances that are already COMMITTED or EXECUTED, without any protection mechanism.

[SherlockShemol]

Additional Attack Vector: The Broken Ladder Attack

We discovered a third manifestation of the same root cause bug that corrupts Tarjan's SCC algorithm during dependency graph traversal.

Attack Scenario

When handleCommit modifies Deps during Tarjan's recursive traversal, the algorithm can produce incorrect SCC groupings because it reads Deps once per loop iteration and doesn't re-read after recursive calls.

Problematic Code

// epaxos-exec.go lines 68-103
for q := int32(0); q < int32(e.r.N); q++ {
    inst := v.Deps[q]  // ← Deps read HERE, ONCE per q
    for i := e.r.ExecedUpTo[q] + 1; i <= inst; i++ {
        // ...
        w := e.r.InstanceSpace[q][i]
        if w.Index == 0 {
            e.strongconnect(w, index)  // ← Recursive call
            // During recursion, v.Deps can be modified by handleCommit!
            // But loop bounds 'inst' won't change!
        }
    }
}
// After recursion, B.Deps[0] may have changed, but q=0 was already iterated!

Attack Timeline

Initial Ladder: A → B → C (chain)

Tarjan Traversal:
  1. strongconnect(A): push A
  2. A.Deps[1]=0, recurse to B
  3. strongconnect(B): push B
  4. B.Deps[0]=-1, skip (q=0 already processed!)
  5. B.Deps[2]=0, recurse to C
  
  *** MUTATION: handleCommit changes B.Deps from [C] to [A] ***
  
  6. strongconnect(C): push C, no deps, SCC [C]
  7. Return to B, B does NOT re-iterate q=0!
     B misses the new B→A edge!
  8. SCC [B] found (WRONG!)
  9. Return to A, SCC [A] found

Result: C → B → A (three separate SCCs)
Correct: [A,B] + [C] (A↔B should be one SCC!)

❌ SCC CORRUPTION!

Race Window

strongconnect(A)
  └── q=1: recurse to B
      └── strongconnect(B)
          ├── q=0: B.Deps[0]=-1, SKIP
          │   ┌────────────────────────────────┐
          │   │ RACE WINDOW                    │
          │   │ handleCommit can modify B.Deps │
          │   │ But q=0 was already processed! │
          │   └────────────────────────────────┘
          └── q=2: recurse to C
              └── MUTATION HAPPENS HERE
                  B.Deps changes to [A]
                  But B won't re-iterate q=0!

Consequences

1. Incorrect SCC Detection: Nodes that should be grouped together are split
2. Wrong Execution Order: Commands in a cycle may be executed incorrectly
3. State Machine Divergence: Different replicas may detect different SCCs

Root Cause (Same as Original)

All three attack variants stem from the same root cause:

Attack	What Gets Modified	When
Latent Conflict	Deps	After execution
Shifting Sands	Seq	During SCC sorting
Broken Ladder	Deps	During Tarjan traversal

Core Issue: handleCommit can modify COMMITTED instances without any protection for ongoing operations.

Suggested Fix

Protecting COMMITTED instances in handleCommit would fix all three attack variants:

if inst != nil {
    if inst.Status == epaxosproto.COMMITTED || inst.Status == epaxosproto.EXECUTED {
        // Do not modify already committed/executed instances
        return
    }
    inst.Seq = commit.Seq
    inst.Deps = commit.Deps
    inst.Status = epaxosproto.COMMITTED
}

Alternatively, Tarjan could take a snapshot of the dependency graph before traversal:

func findSCC(root *Instance) {
    snapshot := snapshotDeps(root)  // Take snapshot
    return strongconnect(root, snapshot)  // Use snapshot
}

[SherlockShemol]

Root Cause Confirmation: Simple Coding Oversight

We conducted a comparative analysis of all message handlers and confirmed that handleCommit is the ONLY handler missing state protection.

Handler Protection Comparison

Handler	Line	Protection Code	Safe?
handlePreAccept	906	if (Status == COMMITTED || ACCEPTED) return	✅ YES
handleAccept	1157	if (Status == COMMITTED || EXECUTED) return	✅ YES
handleCommit	1270	if inst != nil { // NO CHECK! }	❌ NO

Code Evidence

handleAccept (CORRECT):

// Line 1157-1159
if inst != nil && (inst.Status == epaxosproto.COMMITTED || inst.Status == epaxosproto.EXECUTED) {
    return  // ✅ Protected!
}

handlePreAccept (CORRECT):

// Line 906-916
if inst != nil && (inst.Status == epaxosproto.COMMITTED || inst.Status == epaxosproto.ACCEPTED) {
    // ...
    return  // ✅ Protected!
}

handleCommit (BUG):

// Line 1270-1281
if inst != nil {
    // ❌ NO STATUS CHECK!
    inst.Seq = commit.Seq
    inst.Deps = commit.Deps
    inst.Status = epaxosproto.COMMITTED
}

Conclusion

This confirms the bug is a simple coding oversight, not a design issue:

• The protection pattern exists in two other handlers
• handleCommit simply missed adding the same check