Modeling Implicit Instruction Dependencies in IR

[Chand-ra]

Background

In our current IR, instruction dependencies are primarily defined by explicit data flow: an instruction is dependent on another if it consumes the dependee's output as an input. Mutators must respect these dependencies, and the following mutators do so in different ways:

• InputSwapMutator: Sidesteps dependencies by only swapping inputs of matching types.
• InstructionDeleteMutator: Sidesteps dependencies by identifying type-matching variables to replace references to a deleted instruction.
• InstructionReorderMutator: Respects dependencies by ensuring instructions are not reordered if one consumes the other’s output.

The Problem

The IR does not currently capture implicit dependencies: semantic requirements where one operation must precede another despite having no direct data-flow link.

For example, A Recv* operation must always be preceded by a SendMessage operation. If a mutator (like reordering or deletion) breaks this implicit sequence, the program results in a 5-second timeout during execution. This significantly reduces fuzzing bandwidth and efficiency, and may lead to false positive hangs.

Proposed Goal

To achieve good fuzzing performance, we need a mechanism to represent these implicit dependencies within the IR. This will allow mutators to become more "structurally aware," ensuring they respect semantic ordering requirements and maintain greater program validity during mutation.

See Matt's comments on PR #60 and PR #61 for more context.

[Chand-ra]

Thought about different ways to solve this for quite some time, and here's what I came up with.

---

There are five core challenges we need to address:

1. Exact 1-to-1 Pairing: We must pair a specific Recv with a specific Send. A generic "a Recv needs a Send" rule causes false positives. The IR must explicitly track relationships so mutators know exactly which operations are mathematically tied together.

2. Chronological Ordering: Recv A cannot execute before Send A, and Send A cannot be deleted if Recv A exists.

3. Asynchronous Flexibility: Loose messages (e.g., pings, pongs, and gossip announcements) operate asynchronously. The IR must allow mutators to freely slide these instructions anywhere in the program.

4. Strict State Boundaries: Some messages are strictly sequential. For instance, if a node sends an open_channel message and immediately follows it with a state-altering message for that channel (like update_add_htlc) before receiving accept_channel, the counterparty will drop the connection. We need an "invisible fence" to prevent mutators from dropping strict instructions into these locked sequences.

5. Minimal Architectural Changes: We need to achieve all of this without introducing complex control-flow validations or rewriting the data-flow logic of the existing mutators.

The Solution

A robust way to achieve this is by introducing "state tokens," similar to how Haskell uses dummy tokens to prevent the compiler from rearranging, merging, or duplicating I/O side effects.

Explicit Edges (Problems 1):

Instead of outputting None, we modify SendMessage to output a new VariableType, say PendingRecv. The corresponding Recv* operation then consumes this token. This solves Problem 1 (explicit edges) and partially solves Problem 2 (mutators can no longer move Recv A above Send A).

Preventing State Healing (Problem 2):

However, consider this program flow:

Send(OpenChannel) -> Recv(AcceptChannel) -> [other stuff] -> Send(OpenChannel2) -> Recv(AcceptChannel2)

With the current solution, InstructionDeleteMutator could delete the second Send and try to "heal" the second Recv by wiring it to the PendingRecv token of the first Send. To prevent this, we introduce the concept of Affine Types. By enforcing that a PendingRecv token can be consumed at most once, the mutator is structurally forced to keep the second Send as long as the second Recv is present. Problem 2 is now fully solved.

State-Threading (Problem 4):

We must prevent the fuzzer from generating flows like this:

Send(OpenChannel1) -> Send(UpdateAddHtlc1) -> Recv(AcceptChannel1)

while allowing flows like this:

Send(OpenChannel2) -> Send(UpdateAddHtlc1) -> Recv(AcceptChannel2)

To model this channel lock, we again use the example of how Haskell handles I/O: State-Threading.

Recv(AcceptChannel) will now output an affine ActiveChannel variable. Any subsequent operation that modifies the channel (e.g., Send(UpdateAddHtlc), Send(UpdateFee)) must consume this token and output a new ActiveChannel token. This mathematically serializes the timeline. A state-transition operation will eventually consume the final ActiveChannel token and output a different affine type (or None).

Operation Specificity (Problems 3):

Because each strict message requires a distinct sequence of input and output tokens, trying to model everything through a single SendMessage operation will become cumbersome.

Instead, we leave the existing SendMessage as-is. It will handle the asynchronous, free-flowing messages (Problem 3) by accepting no state tokens and returning None. For synchronized messages, we will introduce specific operations like SendOpenChannel, SendUpdateAddHtlc, etc. This mirrors our existing Recv* architecture where each deserialized message gets its own operation.

Minimal Changes (Problem 5):

The IR only suffers three changes:

1. Two new variable types: PendingAccept, ChannelActive.
2. A new SendOpenChannel operation.
3. One addition each to the input & output for RecvAcceptChannel.

All new dependency semantics are encoded as ordinary data-flow edges (token inputs/outputs), with affine enforcement handled by the validator rather than by mutator-specific logic. The mutators themselves require no changes.

Implementation Plan

Here is the comprehensive set of changes needed to implement this architecture:

• Introduce PendingAccept and ChannelActive to the VariableType enum.
• Add a SendOpenChannel operation that accepts a VariableType::Message and outputs a PendingAccept.
• Modify RecvAcceptChannel to accept PendingAccept in addition to its usual inputs.
• Update AcceptChannelField (fields extractable from the AcceptChannel compound variable) to include ChannelActive.
• Modify the ProgramBuilder to automatically append an ExtractAcceptChannel(VariableType::ChannelActive) operation immediately after every RecvAcceptChannel.
• Modify the ProgramBuilder to reference count every variable.
• Add an is_affine() method to the VariableType enum.
• Update the validator to return a new error type if any affine type is consumed more than once.
• Update the validator to return a new error type if any compound variable (like AcceptChannel) has more than one Extract(*, AffineType) instruction referencing it. This prevents InputSwapMutator from cloning affine states and voiding the program timeline.
• Update the AFL++ custom mutator C ABI shim to clone the program, mutate the clone, and validate. If clone.validate() doesn't return an error, yield the mutation. Otherwise, discard and retry the mutation cycle for a finite number of attempts.
• Modify the existing OpenChannel generator.
• Update the IR design plan to reflect these token-passing mechanics so future developers can reference it when implementing subsequent strict operations (e.g., SendUpdateAddHtlc, SendCommitmentSigned, SendUpdateFee).

---

Let me know what you think @NishantBansal2003 @morehouse.

[NishantBansal2003]

3. Asynchronous Flexibility: Loose messages (e.g., pings, pongs, and gossip) operate asynchronously. The IR must allow mutators to freely slide these instructions anywhere in the program.

For gossip, we could receive announcements at any time, and for that we do not need any dependency on Send. However, gossip queries do depend on Send, so for those it should be send -> recv.

4. Strict State Boundaries: Some messages are strictly sequential. For instance, if a node sends an open_channel message and immediately follows it with a state-altering message for that channel (like update_add_htlc) before receiving accept_channel, the counterparty will drop the connection. We need an "invisible fence" to prevent mutators from dropping strict instructions into these locked sequences.

I am not sure whether, in the future, we are going to do some cross-state fuzzing starting from open_channel -> shutdown. Right now, the plan is only what is outlined in the milestones of #5, but I still think we should keep this in case we proceed with cross state fuzzing later, so that we do not have to change the mutator design.

Explicit Edges (Problems 1):

Instead of outputting None, we modify SendMessage to output a new VariableType, say PendingRecv. The corresponding Recv* operation then consumes this token. This solves Problem 1 (explicit edges) and partially solves Problem 2 (mutators can no longer move Recv A above Send A).

I think these explicit edges make sense, with that we can make any Recv dependent on a Send 👍

Preventing State Healing (Problem 2):

However, consider this program flow:

Send(OpenChannel) -> Recv(AcceptChannel) -> [other stuff] -> Send(OpenChannel2) -> Recv(AcceptChannel2)

With the current solution, InstructionDeleteMutator could delete the second Send and try to "heal" the second Recv by wiring it to the PendingRecv token of the first Send. To prevent this, we introduce the concept of Affine Types. By enforcing that a PendingRecv token can be consumed at most once, the mutator is structurally forced to keep the second Send as long as the second Recv is present. Problem 2 is now fully solved.

How will this new affine type be wired into the current design? Currently, pick_variable has the strategy 75% most recent, 15% any existing, 10% fresh. So, if we already used the recent affine type, then we cannot use that one again. I think this may starve generators.

Send(OpenChannel1) -> Send(UpdateAddHtlc1) -> Recv(AcceptChannel1)

while allowing flows like this:

Send(OpenChannel2) -> Send(UpdateAddHtlc1) -> Recv(AcceptChannel2)

To model this channel lock, we again use the example of how Haskell handles I/O: State-Threading.

Recv(AcceptChannel) will now output an affine ActiveChannel variable. Any subsequent operation that modifies the channel (e.g., Send(UpdateAddHtlc), Send(UpdateFee)) must consume this token and output a new ActiveChannel token. This mathematically serializes the timeline. A state-transition operation will eventually consume the final ActiveChannel token and output a different affine type (or None).

how will we proceed with this approach when we are doing independent normal channel operations scenario? In that case, we already set up the funding flow during init, so there would be no ActiveChannel token to start with. Do we need to hardcode or manually add the ActiveChannel token ourselves in that case?

IIUC, normal channel operations also need to be wired with this ActiveChannel. So that means the commitment dance would also need to be wired with this affine ActiveChannel type for each shared message, which should not be required if we are doing independent fuzzing of normal channel operations.

Also, what about cases like MineBlocks? Those are time-consuming operations as well, and should only be done at the appropriate points, for example after FundingSigned has been received, and in a much less repetitive manner. Otherwise, they could cause timeouts.

[Chand-ra]

For gossip, we could receive announcements at any time, and for that we do not need any dependency on Send. However, gossip queries do depend on Send, so for those it should be send -> recv.

We can use our existing mechanism to model the queries. For example,

• Send(QueryChannelRange) $\rightarrow$ outputs a PendingGossipReply affine token.
• Recv(ReplyChannelRange) $\rightarrow$ consumes the PendingGossipReply affine token.

I will update the plan to mention 'gossip announcements' instead of 'gossip' for asynchronous messages. Thanks.

How will this new affine type be wired into the current design? Currently, pick_variable has the strategy 75% most recent, 15% any existing, 10% fresh. So, if we already used the recent affine type, then we cannot use that one again. I think this may starve generators.

You're right, we'll need to add a separate logical branch for when var_type.is_affine() returns true. Since we're reference counting each variable, we can pick the latest non-used matching type.

We'll still have to deal with the scenario when SpliceMutator mismatches payload and token, but the Generator problem should be fixed with this.

how will we proceed with this approach when we are doing independent normal channel operations scenario? In that case, we already set up the funding flow during init, so there would be no ActiveChannel token to start with. Do we need to hardcode or manually add the ActiveChannel token ourselves in that case?

We can add the required affine type in the corresponding ProgramContext struct, and add a LoadContext* operation to extract this field at the start of the program.

IIUC, normal channel operations also need to be wired with this ActiveChannel. So that means the commitment dance would also need to be wired with this affine ActiveChannel type for each shared message, which should not be required if we are doing independent fuzzing of normal channel operations.

If we make ChannelActive non-affine instead, we won't be able to prevent mutators from moving commitment messages after a ShutdownChannel, which is something I don't think we want the fuzzer to test.

About fuzzing normal channel operations, InputSwapMutator should still be able to swap messages of the same type, InstructionDeleteMutator can, in some capacity, test occurrence of one type of message before another, and SpliceMutator, GeneratorInsertMutator, should be able to inject entirely new chains of HTLCs in different orders.

I think constraining only InstructionReorderMutator to guarantee generation of valid protocol flow is an acceptable tradeoff, but let me know what you think.

Also, what about cases like MineBlocks? Those are time-consuming operations as well, and should only be done at the appropriate points, for example after FundingSigned has been received, and in a much less repetitive manner. Otherwise, they could cause timeouts.

We can introduce another affine type, say WaitChain, which will be consumed by MineBlocks and output by Recv(FundingSigned) and similar operations.

As for the "in a much less repetitive manner" part, an affine type can only be consumed once, which means there can only ever be a maximum of one MineBlocks operation corresponding to one Recv(FundingSigned)-like operation.

[morehouse]

I think affine types with custom send/receive operation pairs makes a lot of sense. My gut feeling is that we should start there, and it will probably be good enough for now.

I think we can largely ignore problems 3 and 4 for now.

For problem 3, we already handle pings in Recv* operations, and we can do something similar for gossip if it becomes an issue, though currently we don't get any unexpected gossip from the target since we disable the query feature bits and there's no other LN nodes on our test network.

AFAIK problem 4 is not that big of a problem right now -- sending messages in the wrong order should generally cause the target to close the connection, which we quickly detect on the next Recv* operation and can move on to the next input. In this case we want the connection to be closed so that we don't end up waiting 5s for a message that never comes (causing a hang to be reported). Our main tool for creating correct message sequences is the full-flow generators (not implemented yet), and I'm hopeful they're good enough to get hit the deeper code paths, so we can allow mutators to create incorrect sequences and test corner cases that way.

[Chand-ra]

I think affine types with custom send/receive operation pairs makes a lot of sense. My gut feeling is that we should start there, and it will probably be good enough for now.

I think we can largely ignore problems 3 and 4 for now.

For problem 3, we already handle pings in Recv* operations, and we can do something similar for gossip if it becomes an issue, though currently we don't get any unexpected gossip from the target since we disable the query feature bits and there's no other LN nodes on our test network.

Okay, so for asynchronous messages, we get Sends for free by introducing custom sends for synchronous types. We get RecvPing for free because it's already handled in the Recv* operations, which could be later extended to receive unexpected gossips as well.

That should handle problem 3 completely.

AFAIK problem 4 is not that big of a problem right now -- sending messages in the wrong order should generally cause the target to close the connection, which we quickly detect on the next Recv* operation and can move on to the next input. In this case we want the connection to be closed so that we don't end up waiting 5s for a message that never comes (causing a hang to be reported). Our main tool for creating correct message sequences is the full-flow generators (not implemented yet), and I'm hopeful they're good enough to get hit the deeper code paths, so we can allow mutators to create incorrect sequences and test corner cases that way.

Right, adding architectural boundaries for program scenarios that don't exist right now might over-constrain the mutators. We should be able to extend this architecture if we do want to do that in the future.

[Chand-ra]

Since we all agree that the base architecture of 'custom sends + affine types' is a viable solution, I'll go ahead and start implementing the plan for it.