💻 computer science

StateFi: Effectively Identifying Wi-Fi Devices through State Transitions

StateFi is a novel fingerprinting framework that effectively identifies Wi-Fi devices and defeats MAC address randomization by modeling their management frame behaviors as finite-state machines, achieving up to 97% re-identification accuracy across diverse environments.

Original authors: Abhishek K. Mishra, Mathieu Cunche

Published 2026-01-15

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Abhishek K. Mishra, Mathieu Cunche

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are walking through a crowded airport terminal. Everyone is wearing a name tag that changes every few seconds. One moment you see "John Smith," the next it's "Jane Doe," and then "Alex Johnson." If you were trying to track a specific person, these changing name tags would make it nearly impossible.

This is exactly how modern Wi-Fi devices work today. To protect your privacy, your phone and laptop constantly change their digital "name tags" (called MAC addresses) when they look for Wi-Fi networks. This is called MAC randomization.

However, the researchers behind this paper, StateFi, discovered that while the name tags change, the way the devices act remains the same. They found a new, powerful way to identify devices not by what they say, but by how they behave.

Here is a simple breakdown of their discovery:

1. The Problem: The "Chameleon" Effect

Think of a Wi-Fi device like a chameleon. When it tries to connect to a network, it sends out a series of digital "shouts" (called management frames) to say, "Hello, is anyone there?"

Old Method: Previous attempts to track these devices looked at the content of the shout. They checked the specific words used (like the list of features the phone supports) or the exact timing of the shout.
The Flaw: Just like a chameleon can change its colors, these "words" and "timings" can be easily faked, get messy in crowded places, or change when the phone updates its software. If the environment is noisy (like a busy cafe), these old methods often fail.

2. The Solution: The "Dance Routine" (StateFi)

The StateFi team realized that even if a device changes its name tag and its specific words, it still performs the same dance routine.

They modeled the device's behavior as a Finite State Machine (FSM).

The Analogy: Imagine a dancer. They might wear different costumes (randomized MAC addresses) and dance to different songs (different Wi-Fi networks), but their choreography is unique.
- Do they spin twice before jumping?
- Do they pause for a split second between moves?
- Do they repeat a move if the music stops?
- Do they jump immediately or wait for a cue?

StateFi doesn't care about the costume or the song. It watches the sequence of moves and the timing between them. It builds a map of the device's "dance steps."

3. How It Works

The researchers built a system that:

Watches the Dance: It records every time a device sends a signal.
Maps the Steps: It creates a flowchart showing how the device moves from one state to another (e.g., "I'm scanning" $\to$ "I'm asking" $\to$ "I'm waiting" $\to$ "I'm asking again").
Creates a Fingerprint: It turns this complex dance routine into a simple, compact list of numbers (a vector).
Matches the Dancer: Even if the device changes its name tag, the system compares the new dance routine to the old one. If the steps and timing match, it knows, "That's the same device!"

4. The Results: A Master Detective

The team tested this in five different real-world locations (a cafe, a lab, a classroom, a home, and a restaurant) and against massive public datasets containing millions of signals.

In the Network: When devices were already connected to Wi-Fi, StateFi could identify them with 94% to 97% accuracy. It could tell if a device was pretending to be someone else.
Against Randomization: Even when devices were using their "chameleon" mode (changing MAC addresses) and only sending out "Hello" signals, StateFi could still re-identify them with 92% to 97% accuracy.
Beating the Best: They compared their method to the current "gold standard" of tracking (which looks at name tags, word lists, and signal strength). StateFi beat the best existing method by up to 17%.

5. Why This Matters

The paper concludes that while changing your digital name tag is good, it's not enough. Your device's "personality"—the deep, hard-coded way its hardware and software handle connections—is like a fingerprint that is very hard to hide.

The researchers suggest that to truly protect privacy in the future, we might need to change how devices behave, not just what they say. But for now, StateFi proves that behavior is a powerful side channel that can identify devices even when they try to hide.

Technical Summary: StateFi – Effectively Identifying Wi-Fi Devices through State Transitions

1. Problem Statement

Wi-Fi devices continuously emit unencrypted management frames for discovery, authentication, and association. While these frames are essential for connectivity, they leak structured behavioral patterns that enable device fingerprinting and tracking. To mitigate this, modern operating systems employ MAC address randomization, frequently rotating locally administered MACs during probe-based discovery.

However, existing literature indicates that randomization only obscures identifiers, not the underlying behavioral logic encoded in management-frame sequences, timing, and retry dynamics. Prior attempts to defeat MAC randomization have relied on syntactic features derived from Information Elements (IEs), sequence numbers (SEQ), or RSSI correlations. These methods suffer from significant limitations:

Brittleness: Their discriminative power degrades sharply in realistic environments characterized by high contention, mobility, and heterogeneous Access Point (AP) deployments.
Sparsity: Probe activity is inherently sparse and highly variable, limiting the stability of syntactic signatures.
Obfuscation: Field-level identifiers (like IEs) can be easily obfuscated or altered by OS updates.

Consequently, randomized identifiers provide incomplete protection against behavioral re-identification, necessitating a shift from content-based features to behavioral dynamics.

2. Methodology: StateFi Framework

StateFi introduces a fingerprinting framework that models device behavior as Finite-State Machines (FSMs). Rather than analyzing individual frame types or metadata fields in isolation, StateFi captures the complete structure and timing of management-plane interactions.

2.1 Behavioral Modeling via FSMs

The core insight is that management-plane behavior arises from deep firmware and chipset design choices (e.g., scan strategies, association sequences, backoff timing) that remain stable across MAC randomization events.

State Definition: The set of states ( $Q$ ) corresponds to management-frame subtypes (e.g., ProbeReq, Auth, AssocReq).
Transitions: The transition function ( $\delta$ ) records observed transitions between successive subtypes within a "burst" (a sequence of packets emitted by the same MAC where inter-packet gaps do not exceed one second).
Temporal Logic: The model captures not just structural transitions (e.g., retries, self-transitions) but also temporal execution logic, such as inter-state delays and scan pacing.

2.2 Two Operational Regimes

StateFi operates in two distinct modes depending on the threat model:

Full-Management FSMs: Used in network-internal settings where devices may remain associated. These FSMs capture the full spectrum of interactions, including probe traffic, authentication/association exchanges, reassociation attempts, and deauthentication logic.
Probe-Only FSMs: Used in adversarial pre-association settings where devices emit randomized MACs. These FSMs are constructed solely from probe requests and responses. Despite the reduced alphabet, they retain rich behavioral structure regarding IE ordering, scanning patterns, and chipset-specific retry dynamics.

2.3 Feature Embedding and Classification

Directly comparing FSM graphs is computationally expensive due to graph isomorphism requirements. To enable scalable analysis, StateFi embeds each FSM into a compact, real-valued feature vector.

Feature Vector: Includes structural features (number of unique states, total transitions, self-transitions), temporal features (transition rates, inter-burst time gaps, sequence-number gaps), and a binary encoding of Probe Request IEs.
Classification: The framework employs a supervised learning pipeline to predict whether two bursts originate from the same physical device. It utilizes pairwise similarity features (Euclidean distance, cosine similarity, L1 distance, and IE overlap) fed into standard classifiers: Random Forest (RF), Support Vector Machine (SVM), and Logistic Regression (LR).

3. Evaluation and Results

The authors evaluated StateFi across eight datasets, including five heterogeneous campus environments (Café, Laboratory, Classroom, Residence, Restaurant) and three large public datasets (Infocom'21, Cagliari, MITIK).

3.1 In-Network Fingerprinting

In a network-internal setting (post-association), StateFi achieved 94–97% accuracy across five campus environments using full-management FSMs. Random Forest consistently outperformed SVM and Logistic Regression. This demonstrates that full-management FSMs provide stable, highly discriminative signatures for behavioral integrity monitoring and intrusion detection, even when MAC addresses are only session-stable.

3.2 Defeating MAC Randomization

In the adversarial pre-association setting (randomized MACs), StateFi utilized probe-only FSMs to re-identify devices.

Across three large public datasets containing over a million frames, StateFi achieved 92–97% accuracy.
Using the discrimination accuracy metric from the state-of-the-art Infocom'21 framework, StateFi reached 93–98%.
This represents an improvement of up to 17 percentage points over the strongest prior signature (IE+SEQ+RSSI), which plateaued at 86%.
The performance gap widened at longer time windows, highlighting the sensitivity of syntactic signatures to burst boundaries and channel contention, whereas FSM-based behavioral modeling remained robust.

4. Key Contributions

The paper makes the following specific contributions:

Behavioral Modeling via FSMs: The introduction of the first fingerprinting framework that captures both structural and temporal management-frame dynamics using finite-state machine modeling.
Compact and Scalable Embeddings: The derivation of an efficient vector representation of FSMs that supports scalable distance-based matching and supervised classification, avoiding the computational cost of direct graph comparison.
Comprehensive Real-World Evaluation: Demonstration of high accuracy for both in-network fingerprinting and re-identification under MAC randomization across diverse environments, improving upon the state-of-the-art by up to 17%.
Revealing a Behavioral Side Channel: The identification that MAC randomization fails to conceal implementation-level behavioral fingerprints, motivating the need for behavioral obfuscation in future wireless standards.

5. Significance and Claims

The paper posits that FSM-level behavioral dynamics form a powerful and largely unmitigated side channel. Unlike syntactic features that are easily randomized or obfuscated, the behavioral logic encoded in state transitions and timing is deeply rooted in firmware and chipset design, making it difficult to mask without harming network performance (e.g., increasing latency or power consumption).

StateFi demonstrates that device identification can be achieved with high precision and robustness even in the presence of aggressive MAC randomization. The authors conclude that while current privacy defenses focus on identifier randomization, they are insufficient against behavioral re-identification. Future privacy defenses must address the leakage of FSM-level behavioral signatures to effectively protect user anonymity in Wi-Fi networks.