Skip to content
STIMSMITH

Finite State Machine

Concept WIKI v5 · 6/8/2026

A finite state machine (FSM) is a computational model that transitions among a finite set of states in response to inputs or events. In formal hardware verification, a synchronous circuit is modeled as an FSM M = (I, S, S0, Δ, Λ, O) with input alphabet, output alphabet, finite state set, initial states, next-state function, and output function. FSMs are used to model processors, communication protocols, pipeline stages, and FPGA control logic, and they underpin techniques such as Interval Property Checking (IPC) and datapath mapping functions for pipeline verification.

Overview

A finite state machine (FSM) is a computational model that transitions among a finite set of states in response to inputs or events. FSMs are widely used to model digital hardware, communication protocols, and other discrete-state systems. [C1][C2][C3]

Formal FSM model in hardware verification

In the cited automated processor-verification work, a synchronous circuit is modeled as a finite state machine

M = (I, S, S0, Δ, Λ, O)

with input alphabet I ⊆ B^n, output alphabet O ⊆ B^w, a finite set of states S ⊆ B^m, an output function Λ, and a next-state function Δ. The set S0 ⊆ S denotes the initial states. With next-state function Δ : B^n × B^m → B^m, the transition relation of the circuit is given by

T(s, s′) = ∃x ∈ B^n : s′ ≡ Δ(x, s).

A safety property f = AG(φ) is translated to a Boolean function [[f]]_t checking the validity of formula φ at time point t, where a satisfying assignment of [[f]]_t corresponds to a counterexample of φ. [C3]

This formalization underpins Interval Property Checking (IPC), which is described in the same paper as a powerful verification technique. IPC searches for counterexamples by solving the SAT instance formed by unrolling the transition relation T within a bounded time interval [0, c] and conjoining it with a single instantiation of [[f]]_t. To avoid unreachable counterexamples, invariants are added; in many cases such invariants can be generated automatically, and in the methodology's context the required invariants are usually less complex than the main properties and can be verified using inductive proof techniques such as k-induction. [C3]

Datapath modeling in pipelines

In the same processor-verification evidence, the architectural value of a register R with index i ∈ I_R in the forwarding target stage is captured by an automatically generated mapping function Data_R(s, i) that follows the pipeline mapping recursively. Because the value of Data_R may be invalid (the result of some instruction is not yet available), an additional mapping function Valid_R(s, i) is introduced to capture whether the forwarding data is indeed valid. The paper notes that this automatically generated function captures the complex mapping of the visible register R to the implementation: the architecture value of R for an instruction in the pipeline is the value of Data_R in the forwarding target stage of that instruction, gated by Valid_R. [C1][C2]

Multicycle instructions and pipeline dispatching

For refinements of the simple pipeline model, the paper notes that additional mappings are required. Exceptions are a crucial feature for practical applications; by nature, they interrupt normal instruction processing. The most general exception model compatible with the approach is an injection of a new instruction into the pipeline after an exception has been acknowledged. For more complex arithmetic operations or interactions with protocol-driven interfaces, multicycle instructions are frequently used in processor designs. Typically, an FSM in an early stage is responsible for dispatching partial instructions in the pipeline. [C1]

Hardware-verification context (processor fuzzing)

In the cited ProcessorFuzz evidence, a processor is described as a complex finite state machine (FSM). Control and status registers (CSRs) have direct control over the current processor state, while the architectural state of a processor is held in the register file and status registers and represents the state of the program running on the processor. [C4]

The paper's intuition is that certain CSRs dictated by the ISA readily expose the current processor FSM state (e.g., current privilege mode, the event that caused floating-point exception), and thus the transitions in these CSRs signify a new processor FSM state. [C4]

FSM state via register coverage

DIFUZZRTL's register coverage technique monitors many datapath registers, such as a remainder register, to determine the current FSM state. The ProcessorFuzz paper identifies this as a source of large state space when using current-state-style coverage for processor fuzzing. [C4][C5]

DIFUZZRTL's register coverage only stores the current state of the processor and does not consider the previous state. The paper argues that this design choice can lead to important test inputs being discarded by the fuzzer and the fuzzer can potentially miss out on the discovery of a bug. [C5]

The paper illustrates this limitation with a real-world bug (Bug 2 in Table IV) identified in a RISC-V processor. The processor starts out in state N0. The bug triggers in state N2 only if the previous state is N1. During a coverage-guided fuzzing session, if both N1 (through P0 transition) and N2 (through P2 transition) are covered individually, there will not be a coverage increase for the P1 state transition. Hence, the unique P1 transition is not particularly driven towards, and the fuzzing session fails to trigger the bug. [C5]

Transition-oriented coverage

ProcessorFuzz proposes CSR-transition coverage as an alternative feedback metric for generating qualitatively distinct processor tests. By monitoring transitions, ProcessorFuzz can detect P1 as a new transition even though N1 and N2 states are already covered. The paper notes that the rationale is similar to widely-used software fuzzers' rationale that monitor edges in a program instead of basic blocks. [C5][C4]

The approach selects CSRs according to two stated criteria: CSRs that contain processor status information, and CSRs used to set processor configuration. For example, an exception-cause CSR such as mcause can distinguish different exception reasons, while medeleg can configure which traps are delegated to lower privilege levels. [C6]

Transition map representation

ProcessorFuzz maintains a transition map for CSR transitions. Each transition is stored as (Im, S0, S1), where Im is the mnemonic of the instruction whose execution produced the transition, S0 is the CSR value before the transition, and S1 is the CSR value after the transition. The instruction mnemonic is included because different instructions can trigger the same CSR-value transition; the paper gives floating-point division and square-root instructions as examples that can trigger the same fflags transition for invalid operations. [C6]

Managing state-space size

ProcessorFuzz reduces transition-state-space pressure by grouping CSR transitions. The paper states that designers can group transitions for architectural units and treat those groups as independent events, improving exploration within each group. It gives privileged and unprivileged RISC-V architectures as an example of groups that can be verified individually before fuzzing the processor as a whole. [C6]

ProcessorFuzz also avoids transitions that are not useful for architectural-state feedback. For example, a counter such as instret would transition after every committed instruction, causing almost any input to appear interesting even though such changes would rarely expose a bug. The paper also states that transitions from explicit writes to status CSRs are filtered out because those transition types do not affect the architectural state of the processor. [C5][C6]

Transition Unit workflow

ProcessorFuzz's Transition Unit (TU) takes an extended ISA trace log as input and communicates with the Transition Map (TM) to output whether the trace log contains any new transitions. As a first step, the TU extracts all CSR transitions in the trace log. Then, ProcessorFuzz applies a filter to remove unnecessary transitions. For example, if a test program writes to a status CSR such as mstatus in RISC-V, and the write is legal, the processor continues execution and overwrites the CSR with the updated status. Such transitions do not affect the architectural state of the processor and are filtered out. [C5]

Communicating FSMs in protocol verification

Beyond processor verification, FSMs are used to model communication protocols. In the cited arXiv work on reachability problems for communicating finite state machines, the state transition model consists of finite state machines connected by potentially unbounded FIFO channels. Reachability properties for this model are undecidable in general, but become decidable for protocols with the recognizable channel property; the question remains open for the rational channel property. [C7]

FSMs in FPGA design

FSMs are also a target for FPGA implementation support. The cited arXiv work on a scalable, low-overhead FSM overlay addresses the limited scalability and flexibility of prior FSM overlays by using memory decomposition on transitional logic. The overlay provides modest average improvements of 15% to 29% fewer lookup tables for individual finite-state machines, and a 77% to 99% reduction in lookup tables for the more common usage of an overlay supporting different finite-state machines, while reducing compilation time to tenths of a second. [C8]

Related techniques and tools

  • [[Interval Property Checking]] (IPC): a verification technique that unrolls the FSM transition relation within a bounded time interval [0, c] and searches for counterexamples by solving a SAT instance; uses the FSM model M = (I, S, S0, Δ, Λ, O). [C3]
  • [[Data Path Modeling]]: uses mapping functions such as Data_R(s, i) and Valid_R(s, i) to capture how the architectural value of a register maps to its pipeline-implementation state, and recursively defines pipeline stages; an FSM in an early stage is typically responsible for dispatching partial multicycle instructions. [C1][C2]
  • [[register coverage]]: the coverage technique described as monitoring many datapath registers to determine the current FSM state. [C4][C5]
  • [[CSR-transition coverage]]: a coverage metric that monitors transitions in CSRs to expose the current processor FSM state. [C4][C5]
  • [[DIFUZZRTL]]: uses register coverage to infer the current FSM state in the cited processor-fuzzing context. [C4][C5]
  • [[ProcessorFuzz]]: proposes CSR-transition coverage and the Transition Unit workflow for FSM-state exploration. [C4][C5][C9]

LINKED ENTITIES

2 links
Interval Property Checking USES
Data Path Modeling USES

CITATIONS

11 sources
11 citations
[1] A synchronous circuit is modeled as an FSM M = (I, S, S0, Δ, Λ, O) with input alphabet I ⊆ B^n, output alphabet O ⊆ B^w, finite set of states S ⊆ B^m, output function Λ, and next-state function Δ, with initial states S0 ⊆ S and transition relation T(s, s′) = ∃x ∈ B^n : s′ ≡ Δ(x, s). Automated Formal Verification of Processors
[2] A safety property f = AG(φ) is translated to a Boolean function [[f]]_t such that a satisfying assignment of [[f]]_t corresponds to a counterexample of φ. Automated Formal Verification of Processors
[3] IPC unrolls the FSM transition relation within a bounded time interval [0, c] and conjoins it with [[f]]_t to form a SAT instance for counterexample search; invariants (often automatically generated, verifiable by k-induction) are added to avoid unreachable counterexamples. Automated Formal Verification of Processors
[4] Multicycle instructions in processor designs are dispatched by an FSM in an early pipeline stage; the most general exception model compatible with the approach injects a new instruction into the pipeline after exception acknowledgement. Automated Formal Verification of Processors
[5] An automatically generated mapping function Data_R(s, i) captures the complex mapping of the visible register R to the implementation; an additional mapping function Valid_R(s, i) captures whether the forwarding data is indeed valid. Automated Formal Verification of Processors
[6] A processor is described as a complex FSM whose current state is exposed via CSRs, with the architectural state held in the register file and status registers. ProcessorFuzz: Processor Fuzzing with Control and Status Register Transition Analysis
[7] DIFUZZRTL's register coverage only stores the current FSM state without the previous state, causing important test inputs to be discarded — illustrated by a RISC-V bug (Bug 2) that triggers in state N2 only if the previous state is N1. ProcessorFuzz: Processor Fuzzing with Control and Status Register Transition Analysis
[8] ProcessorFuzz applies a transition filter that drops transitions from writes to status CSRs (e.g., mstatus in RISC-V) because such transitions do not affect the architectural state of the processor, and avoids using counters like instret that would mark nearly every input as interesting. ProcessorFuzz: Processor Fuzzing with Control and Status Register Transition Analysis
[9] ProcessorFuzz's transition map stores each CSR transition as (Im, S0, S1) where Im is the producing instruction mnemonic, and groups CSR transitions by architectural unit (e.g., privileged vs unprivileged) to reduce state-space pressure. ProcessorFuzz: Processor Fuzzing with Control and Status Register Transition Analysis
[10] Reachability properties for communicating FSMs connected by unbounded FIFO channels are undecidable in general but decidable for protocols with the recognizable channel property; the question remains open for the rational channel property. Reachability problems for communicating finite state machines
[11] A scalable FSM overlay for FPGAs uses memory decomposition on transitional logic, achieving 15%–29% fewer LUTs for individual FSMs and 77%–99% fewer LUTs for overlays supporting different FSMs, with compilation reduced to tenths of a second. A Scalable, Low-Overhead Finite-State Machine Overlay for Rapid FPGA Application Development

VERSION HISTORY

v5 · 6/8/2026 · minimax/minimax-m3 (current)
v4 · 6/8/2026 · minimax/minimax-m3
v3 · 5/29/2026 · gpt-5.5
v2 · 5/28/2026 · gpt-5.5
v1 · 5/26/2026 · gpt-5.5