Overview
Breadth-first search (BFS) is a classical graph traversal algorithm that explores a graph level by level, starting from a source node and visiting all neighbors before moving deeper. It is used as a subroutine in many domains, including program analysis, hardware verification, and security testing.
Use in Hardware Fuzzing (WhisperFuzz)
The WhisperFuzz fuzzer, a white-box tool for detecting and locating timing vulnerabilities in processors, employs BFS inside its Diagnozer component. The Diagnozer compares two sets of simulation traces to identify combinational signals whose behavior differs and then traces dependencies from those combinational signals to the sequential elements in the Micro-Event Graph (MEG) of the affected module. This dependency tracing step uses a breadth-first search over the MEG to identify the subsequent sequential elements that originate the timing difference observed between the two trace sets. Within the overall WhisperFuzz pipeline, the Diagnozer's BFS-based dependency tracing sits between (1) identifying the first deviating signals between two simulation trace sets and (2) mapping those signals back to line numbers in the register-transfer level (RTL) description of the device under test, where the corresponding sequential element is located. By doing so, BFS enables WhisperFuzz to localize the source of a timing difference inside a hardware module.
Related Applications
- Take-Grant protection model. A bridge-searching algorithm over protection graphs in the Take-Grant model is built on top of a classical breadth-first search.
- Symbolic execution engines. Some symbolic execution tools, such as Pinaka (a tool layered on CProver/Symex), support breadth-first search as one of the state-exploration strategies available alongside depth-first search, with options for partial or full incremental solving modes.
Relationship with WhisperFuzz
WhisperFuzz USES breadth-first search as part of its Diagnozer routine for tracing combinational-to-sequential dependencies in the Micro-Event Graph when localizing timing differences in processor RTL.