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, processors, pipeline stages, FPGA control logic, and software specification languages. [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 modes. [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]

Synchronized FSMs in SoC bus protocols

In the cited FuSS work on coverage-directed hardware fuzzing, hardware designs are described as FSMs that enable parallel execution, allowing multiple operations to occur simultaneously. To ensure proper coordination between different FSMs, various synchronization mechanisms are used, such as control signals, handshaking protocols, and status flags. The complex interactions between multiple FSMs coupled with rare conditional dependencies can create hard-to-activate regions in the implementation. [C10]

The paper illustrates this with the AXI-4 Lite interface, in which a Verilog implementation of a write transaction involves two parallel FSMs, a master and a slave, whose state transitions must be synchronized. In the master FSM (Figure 4a), transitions proceed IDLE → ADDR → WRITE → RESPOND → DONE → IDLE, while the slave FSM (Figure 4b) traverses IDLE → ADDR_READY → WR_READY → RESPOND → DONE → IDLE, with handshake signals such as awvalid, awready, wvalid, wready, bvalid, and bready coordinating each step. The paper states that correct ordering of these FSM transitions is crucial for ensuring compliance with the implementation protocol, while incorrect sequences may lead to deadlocks or incomplete transactions and ultimately a coverage plateau during fuzzing. [C10][C11]

FSMs in instruction-level processor fuzzing

In the cited TheHuzz instruction-fuzzing work, the "Component" column of the bug table classifies which sub-block of the processor a bug resides in, and explicitly tags certain bugs (e.g., Bug B4 in mor1kx: "Failure to detect cache coherency violation") as belonging to an FSM component (the cache controller), indicating that cache-coherency logic in the OpenRISC mor1kx core is itself modeled as an FSM. [C12]

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]

FSMs in software-test specification languages

In the cited constraint-logic-programming test-generation work, the specification language is inspired by contract-oriented programming and is extended with finite state machines. Beyond generating correct argument values for method calls, the approach generates full test scenarios through symbolic animation of the specifications, with a flexible CSP architecture that operates not only on integer or bounded domains but also on arbitrary types. The notion of a "type builder" links type semantics to the CSP framework, and a string builder is illustrated as one example that can automatically generate string instances depending on combinations of constraints. [C9]

FSMs in cache set protocols (WhisperFuzz)

In the cited WhisperFuzz work, a cache set is represented as an FSM with five states: LookUp, FreeBlock, Replace, Wait, and Ready. When a program accesses data, the cache first performs a look-up for the associated memory address in the LookUp state. On a cache hit, the FSM transitions {LookUp → Ready} in three clock cycles; on a miss with a free cache block it transitions {LookUp → FreeBlock → Wait → Ready} in 19 cycles; and on a miss without a free block it transitions {LookUp → FreeBlock → Replace → Wait → Ready} in 23 cycles. The paper notes that assuming each state takes constant time, a difference in execution time implies a difference in the FSM transition sequence. The paper also notes, however, that in practice FSM states do not always take constant execution time, and that an FSM model is abstract and cannot effectively represent complex microarchitectural details in digital circuits, motivating the introduction of Micro-Event Graphs (MEGs). [C13]

FSM coverage as a fuzzing metric

In WhisperFuzz's design exploration discussion, HyPFuzz is described as compatible with various coverage metrics, combining branch, condition, and FSM metrics for code coverage. Branch and condition metrics monitor the combinational logic of the DUT, while the FSM metric monitors the sequential logic of the DUT; any new points covered by inputs represent at least one new microarchitectural state transition triggered. [C14]

Micro-Event Graph (MEG) refinement of the FSM model

WhisperFuzz introduces Micro-Event Graphs (MEGs) to overcome the limitations of FSM models. In the cited MEG construction, an event graph G(D) has input nodes G(D).I, state nodes G(D).SI, output nodes G(D).O, signals G(D).S, and edges G(D).Σ built from RTL code, with edges annotated between operands and destination signals of assign statements. A Micro-Event Path (MEP) is defined as a sequence of directed edges P = ⟨(s1, s2), (s2, s3), ..., (sn-1, sn)⟩ where (si, sj) ∈ Σ, ∀(i, j), with s1 ∈ I and sn ∈ O. The paper maps MEPs to FSM paths at finer granularity: in a cache-hit case, the FSM path {LookUp → Ready} maps to MEP {addr → tag_addr → way}, while a cache-miss case with a free block maps the FSM path {LookUp → FreeBlock → Wait → Ready} to MEP {addr → tag_addr → hit → fetch → mem_call → complete → way}. WhisperFuzz compares these differing MEPs to identify the wire (e.g., tag_addr) responsible for the divergence in the two paths, and uses this information to trace the root cause of timing vulnerabilities. The paper also states three observations: (P1) if two inputs result in the same event transitions in the MEG, the execution time is the same; (P2) if the execution time differs, the sequence of microarchitectural events followed differs; and (P3) if two inputs result in different event transitions in the MEG, the execution time may differ. [C15]

Formal FSM modeling for SEU evaluation in RISC-V

In the cited Ibex formal-verification work, the Ibex core's ibex_controller module is represented as an FSM whose current state is stored in the 4-bit register ctrl_fsm_cs. The paper identifies this as the most vulnerable register to Single Event Upsets (SEUs) producing Silent Data Corruption (SDCs) in the controller. The LSB of register cpuctrl_q is also flagged as vulnerable to SEUs. [C16]

The paper describes three categories of hang scenarios for an FSM-modeled core: (i) WFI, in which a retired WFI instruction leaves the core in sleep until externally reactivated; (ii) Dead State, in which the FSM is stuck in a state and cannot leave that state; and (iii) Live State, in which the FSM is trapped in a state sequence and cannot return to a state reachable from other states. The paper develops formal properties for each scenario, including a_hang_WFI over halt, valid, and the WFI instruction encoding 32'h10500073, and discusses the difficulty of distinguishing genuine Dead-State and Live-State hangs from designed FSM behavior using 'assert' versus 'cover' statements. [C17]

RISC-V FSM verification strategies (review)

In the cited ESP JETA review of scalable formal-verification strategies for RISC-V control paths, multiple FSM-related verification techniques are surveyed: SMT-based bounded model checking for RISC-V control logic, CSRFormal for verifying CSRs (including access control and transition behaviors), DIFV dynamic interpolation framework for RISC-V pipelines (which detects deadlocks and instruction hazards), AI-assisted proof strategy selection in Coq/Isabelle, parameterized invariants for configurable cores, and a Hybrid Automata model of a 5-stage RISC-V pipeline (Fetch, Decode, Execute, Memory, WriteBack) with invariants and timing conditions, checked with model checkers such as Uppaal and HyTech for safety criteria such as liveness, deadlock-freedom, and finite latency. [C18][C19]

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][C6]
• [[FuSS]]: coverage-directed hardware fuzzing that targets synchronized FSMs in SoC designs such as the AXI-4 Lite master/slave pair and uses selective symbolic execution to drive FSM transitions past coverage plateaus. [C10][C11]
• [[TheHuzz]]: instruction-level processor fuzzer that classifies processor bugs by component, including FSM-classified bugs such as cache-coherency failures in the mor1kx cache controller. [C12]
• [[Specification language]]: the contract-oriented specification language used in constraint-based test generation is extended with finite state machines to drive symbolic animation and full test-scenario synthesis. [C9]
• [[WhisperFuzz]]: uses FSMs as a model for cache-set protocols, FSM coverage as a fuzzing metric for sequential logic, and Micro-Event Graphs (MEGs) as a finer-grained refinement of the FSM model for localizing timing side channels. [C13][C14][C15]
• [[Micro-Event Graph (MEG)]]: a graph-based model of a digital circuit built from RTL assign statements that refines FSM paths into Micro-Event Paths (MEPs); used by WhisperFuzz to localize the wire responsible for divergent execution paths. [C15]
• [[HyPFuzz]]: hardware fuzzer that combines branch, condition, and FSM coverage metrics to drive microarchitectural state-transition coverage. [C14]
• [[Ibex formal verification]]: a study using formal verification to evaluate Single Event Upsets in the RISC-V Ibex core, treating the ibex_controller module as an FSM with state register ctrl_fsm_cs. [C16][C17]
• [[RISC-V formal verification survey (ESP JETA 2025)]]: a review of scalable formal-verification strategies for RISC-V control paths, including SMT-based bounded model checking for control FSMs, CSRFormal, parameterized invariants, and Hybrid Automata pipeline modeling. [C18][C19]