Modern embedded Linux devices, such as routers, IP cameras, and IoT gateways, rely on complex software stacks where numerous daemons interact to provide services. Testing these devices is crucial from a security perspective since vendors often use custom closed- or open-source software without documenting releases and patches. Recent coverage-guided fuzzing solutions primarily test individual processes, ignoring deep dependencies between daemons and their persistent internal state. This article presents STAFF, a firmware fuzzing framework for discovering bugs in Linux-based firmware built around three key ideas: (a) user-driven multi-request recording, which monitors user interactions with emulated firmware to capture request sequences involving application-layer protocols (e.g., HTTP); (b) intra- and inter-process dependency detection, which uses whole-system taint analysis to track how input bytes influence user-space states, including files, sockets, and memory areas; (c) protocol-aware taint-guided fuzzing, which applies mutations to request sequences based on identified dependencies, exploiting multi-staged forkservers to efficiently checkpoint protocol states. When evaluating STAFF on 15 Linux-based firmware targets, it identifies 42 bugs involving multiple network requests and different firmware daemons, significantly outperforming existing state-of-the-art fuzzing solutions in both the number and reproducibility of discovered bugs.