fuzzing: implement remaining shrinking enhancements from echidna's implementation

[anishnaik]

Overview

The call sequence shrinking implementation in PR #786 provides core functionality but still does not fully implement echidna's improved shrinking. This issue tracks the remaining enhancements that would improve shrinking quality and consistency.

Current Implementation Status

✅ Fully Implemented

• Main shrinking loop with limit checking
• Revert removal (simplified without delay transfer)
• Early exit optimization via canShrinkFurther()
• Two shrinking strategies (shorten vs shrink all)
• Individual aspect shrinking (value, gas price, delay, arguments)
• lower() functions with 50% zero bias
• Transaction shrinkability checks

⚠️ Partially Implemented

• Revert removal exists but doesn't use NoCall concept
• Argument shrinking shrinks all args instead of selective shrinking

Missing Features from Specification

1. NoCall Transaction Type (Medium Priority)

Spec Reference: Section 3, lines 170-189

What it is: A special transaction type that:

• Does NOT execute any contract code
• DOES advance timestamp and block number by delay values
• Has zero value, zero gas price

Why it matters:

• Properly handles timing-dependent bugs (addresses [Bug]: Medusa fails to shrink call (revert) + vm.roll + vm.warp into only vm.roll + vm.warp #752)
• Allows preserving time warps (vm.roll/vm.warp) when removing reverted calls
• Makes shrinking more effective for time-sensitive vulnerabilities

Current behavior: Reverted transactions are removed entirely, losing their timing information.

Implementation approach:

// Extend CallMessage or create new transaction type
type NoCallTransaction struct {
    BlockNumberDelay    uint64
    BlockTimestampDelay uint64
}

// In removeReverts(), replace reverted txs with NoCall instead of removing
if reverted {
    noCallTx := createNoCall(element.BlockNumberDelay, element.BlockTimestampDelay)
    result = append(result, noCallTx)
}

2. Collapse Consecutive NoCalls (Low Priority)

Spec Reference: Section 3, lines 246-279

What it does: After removing reverts, merge consecutive NoCall transactions by summing their delays.

Why it matters: Keeps sequences minimal by combining redundant timing-only transactions.

Implementation:

func collapseConsecutiveNoCalls(txs CallSequence) CallSequence {
    // Merge consecutive NoCalls by summing delays
}

3. Remove Useless NoCalls (Low Priority)

Spec Reference: Section 3, lines 286-290

What it does: Remove any NoCall with zero delay (completely useless).

Why it matters: Final cleanup to ensure no no-op transactions remain.

Implementation:

func removeUselessNoCalls(txs CallSequence) CallSequence {
    return filter(txs, func(tx) { 
        return !(tx.isNoCall && tx.delay == (0, 0))
    })
}

4. Remove Call Operation (Medium Priority)

Spec Reference: Section 5, lines 435-436

What it does: In shrinkOneTransactionAspect():

• 10% chance: Replace entire transaction with NoCall
• 90% chance: Pick one aspect to shrink (current behavior)

Why it matters: More aggressive shrinking that can discover entire calls are unnecessary.

Current behavior: Always picks one of 4 aspects uniformly (25% each).

Implementation:

func shrinkOneTransactionAspect(...) *CallSequenceElement {
    // 10% chance to replace with NoCall
    if randProvider.Float32() < 0.1 {
        return createNoCall(element.BlockNumberDelay, element.BlockTimestampDelay)
    }
    
    // 90% chance to shrink one aspect (existing logic)
    operations := []func(...){...}
    ...
}

5. Sender Shrinking (High Priority)

Spec Reference: Section 6, lines 589-637

What it does: Simplify sender addresses to numerically smaller values.

Why it matters:

• Produces more consistent and minimal reproducers
• Simpler addresses are easier to work with
• Matches Echidna's behavior

Algorithm:

1. Extract all unique senders from sequence
2. Sort senders numerically (ascending)
3. For each transaction, randomly pick from senders ≤ current sender
4. Over time, this biases toward smaller addresses

Implementation:

func extractOrderedSenders(sequence CallSequence) []common.Address {
    senderSet := make(map[common.Address]bool)
    for _, tx := range sequence {
        senderSet[tx.Call.From] = true
    }
    
    senders := make([]common.Address, 0, len(senderSet))
    for sender := range senderSet {
        senders = append(senders, sender)
    }
    
    // Sort numerically ascending
    sort.Slice(senders, func(i, j int) bool {
        return senders[i].Big().Cmp(senders[j].Big()) < 0
    })
    
    return senders
}

func shrinkSender(
    element *CallSequenceElement,
    orderedSenders []common.Address,
    randProvider *rand.Rand,
) *CallSequenceElement {
    currentSender := element.Call.From
    
    // Find current sender's position
    currentIndex := -1
    for i, sender := range orderedSenders {
        if sender == currentSender {
            currentIndex = i
            break
        }
    }
    
    if currentIndex <= 0 {
        return element // Already smallest or not found
    }
    
    // Pick randomly from senders <= current (includes current)
    candidates := orderedSenders[0 : currentIndex+1]
    newSender := candidates[randProvider.Intn(len(candidates))]
    
    if newSender == currentSender {
        return element // No change
    }
    
    cloned, _ := element.Clone()
    cloned.Call.From = newSender
    return cloned
}

// Integrate into shrinkAllTransactions()
func shrinkAllTransactions(...) CallSequence {
    result := make(CallSequence, len(txs))
    orderedSenders := extractOrderedSenders(txs)
    
    for i, tx := range txs {
        shrunk := shrinkOneTransactionAspect(tx, ...)
        result[i] = shrinkSender(shrunk, orderedSenders, randomProvider)
    }
    
    return result
}

6. Selective Argument Shrinking (Low Priority)

Spec Reference: Section 5, lines 538-584

What it does: Instead of shrinking ALL arguments, randomly decide how many to shrink (1, 2, halfway, all).

Why it matters: More fine-grained shrinking that may converge faster for complex functions.

Current behavior: Always shrinks all arguments.

Implementation complexity: Medium - requires integrating with existing ValueMutator system.

7. Test State Machine (Low Priority)

Spec Reference: Section 1

What it does: Track explicit states: Open, Large(n), Solved, Passed, Failed.

Why it matters:

• Better progress reporting
• Enables shrinking prioritization across multiple tests
• More sophisticated campaign management

Current behavior: Shrinking happens inline without explicit state tracking.

Impact: Low - current approach works fine for single-test shrinking.

Recommended Implementation Order

Phase 1 (High Priority) - Improves shrinking quality

1. Sender shrinking - Clear value, well-defined algorithm
2. NoCall transaction type - Required for [Bug]: Medusa fails to shrink call (revert) + vm.roll + vm.warp into only vm.roll + vm.warp #752, enables other features

Phase 2 (Medium Priority) - More aggressive shrinking

3. Remove call operation (10% chance) - Simple addition to existing code
4. Collapse consecutive NoCalls - Natural follow-up to NoCall implementation
5. Remove useless NoCalls - Simple cleanup

Phase 3 (Low Priority) - Refinements

6. Selective argument shrinking - More complex, lower value
7. Test state machine - Architectural change, mainly for multi-test scenarios

Dependencies

• NoCall type must be implemented before:

  • Collapse consecutive NoCalls
  • Remove useless NoCalls
  • Remove call operation

• Sender shrinking has no dependencies and can be implemented immediately

Related Issues

• [Bug]: Medusa fails to shrink call (revert) + vm.roll + vm.warp into only vm.roll + vm.warp #752 - Original motivation for NoCall transactions
• fuzzing: refactor shrinking #786 - PR that implemented core shrinking with early exit

Testing Considerations

Each enhancement should include:

• Unit tests for the new functions
• Integration tests with actual failing sequences
• Verification that shrunk sequences still trigger the bug
• Comparison of sequence lengths before/after enhancement