Reading a State Machine from Its Power Draw

Each square is one step, and each step is one bit. A 0 sends the chip to Compute, a burst of arithmetic; a 1 sends it to Send, which hands a character to the chip’s serial port and then waits. Press Play to walk the eight steps. The line underneath is a simulated power recording: Compute draws more power in a busy pattern, Send draws less in a steady ripple, so the shading lines up with the shape of the line. Press Mystery byte and try to flip the steps until your shading matches the mystery recording.

The chip reads the lowest bit first, then shifts the byte one place to the right, so step 1 is the rightmost bit of the binary number. Byte 128 is 10000000 in binary: seven 0s come first, so the chip computes seven times and sends once at the end, exactly as the paper describes. Try 85 (01010101), which alternates, and 255, which sends eight times. Every one of the 256 bytes gives a different path, so naming the path and naming the byte are the same task.

The simulated firmware follows Fig. 1: a dispatch block reads and shifts the oracle register, then branches to state one (four soft-float multiplies, one subtract, and the 0x5f3759df bit trick, since the Cortex-M0 has no floating-point unit) or state two (a UART write followed by a status-polling loop). The block lengths (228 cycles for state one and 240 for state two, plus 14 for dispatch), the power levels, and the 0.035-unit leakage per set bit of the oracle register are the page’s choices; the paper describes the code, not its cycle counts. The two states take similar time here, so the attack has to use the shape of each step and the small timing drift that builds up across steps.

A real power recording is noisy: the same byte never produces exactly the same line twice. The authors smoothed their recordings by averaging every three of them together, point by point. Switch between Raw captures and Averaged in threes: the lines bunch closer to the clean shape underneath, and the readout shows the spread shrinking by about 1.7 times.

Averaging works because the noise is random: at any instant one capture reads a little high and another a little low, and the errors partly cancel. Averaging n captures shrinks random noise by the square root of n, so three captures cut it to about 58 percent (1 ÷ √3). The authors report two benefits: cleaner peaks (compare their Figure 3, raw, with Figure 4, averaged) and about three times less data to load.

Each simulated capture adds Gaussian noise with a standard deviation of 1.0 power units per sample, a trigger offset of zero to six cycles, and 2 percent gain drift, then averages three captures element-wise as the paper does. The paper attributes slightly better accuracy to the averaged traces than to raw ones. Averaging cannot remove what every capture shares, such as the trigger offset when it repeats, so a trace’s alignment, rather than its noise, can still limit the attack after averaging.

Choose how many bytes to tell apart and press Run the attack. Your browser simulates the recordings, keeps 80 percent of each byte’s recordings as labeled examples, and names each remaining recording by finding the k most similar examples and taking a vote. Two or four bytes come out nearly perfect. All 256 bytes is much harder; the round dots are the paper’s results on the real chip, which peaked at 81.02 percent with 111 neighbors voting. The dashed line is this page’s simulation at the paper’s full size.

Slide k to see how the vote size matters. With k = 1, one noisy example decides, and a single unlucky match gives the wrong byte. Larger k lets more examples vote, which steadies the answer until the vote starts pulling in examples of other bytes. Chance is 1 in the number of bytes, the dotted line: 50 percent for two, 0.39 percent for 256. The full paper-size run (256 bytes, 200 traces each) compares 10,240 traces with 40,960 others and takes minutes in a browser, so the page ships it precomputed.

The classifier is scikit-learn’s KNeighborsClassifier with uniform weights and Euclidean distance; a tie between labels goes to the lowest oracle value, as in scikit-learn. One pass sorts each held-out trace’s 501 nearest training traces, so the page draws the whole accuracy-by-k curve at once. The bars under the chart count, for the chosen k, how often each step’s state came out wrong. In the simulation, a wrong guess usually misses only one or two of the eight steps (1.23 on average at the paper’s size and k = 111), so the attack recovers most of the path even when it misses the byte.

At the paper’s size, the simulated curve rises from 17.10 percent at k = 1 and 31.58 percent at k = 11 to 64.13 percent at k = 111 and keeps rising, to 78.23 percent at k = 501. The measured curve rises faster (67.58 percent at k = 11), peaks at k = 111, and falls to 40.06 percent at k = 501. Independent Gaussian noise rewards large votes as long as each class’s 160 training traces dominate the neighborhood; a fall as steep as the paper’s needs particular oracle values whose traces resemble each other more than noise alone explains, which the simulation does not model. The Same work in both states firmware (not in the paper) runs both routines at every step, so only the oracle register’s set bits differ: with the same noise, the simulated attack falls to 0.51 percent at k = 111 for 256 values (chance: 0.39 percent), against 64.13 percent for the paper’s firmware.

Each row is a contest among a smaller set of bytes, from two at the top to all 256 at the bottom, and each column is a vote size. Stronger color means more right answers, from this page’s simulation. The outlined squares are where the paper reports a result from the real chip; press one to compare. Telling two bytes apart was perfect on the chip, and the simulation comes close.

The paper’s smaller contests use the first bytes in order: 0 and 1, then 0 to 3, then 0 to 7, and so on. Byte 0 to byte 3 differ only in their first two bits, so in those contests only steps 1 and 2 change and every later step is Compute. Fewer choices and fewer changing steps both make the task easier, and the paper’s accuracy falls as the number of bytes grows: 100 percent for two, up to 97.5 percent for four, and up to 87.5 percent for eight.

The simulated heatmap reuses the 256-value traces and distances, restricting both training and held-out traces to oracle values below N, so every row comes from the same captures. Cells where k exceeds the training set (320 traces for two values) are blank, as scikit-learn would refuse them. For two values the simulation misses one of 80 held-out traces at most k (98.75 percent, and 87.5 percent at k = 1) where the paper reports 100 percent at every k; for eight values at k = 21 it gives 90.94 percent against the paper’s peak of 87.5 percent. Toward the right end of each row, the vote approaches the whole training set and every value ties, so accuracy falls to the lowest value’s share (50 percent for two values at k = 320, when every training trace votes, as scikit-learn would give).

• Power recordings alone revealed the order of a small chip’s states: the attack named the exact eight-step order out of 256 in 81 percent of tries.
• With only two possible orders, it was right every time.
• The more possibilities it had to choose among, the lower its accuracy, but it stayed far above guessing.
• The authors conclude that devices whose state machines handle sensitive actions (their example is an internet-connected IV drip) need protection against power-based attacks, and that even the number of states a device has may be worth keeping secret.

• Using 200 recordings per byte and a nearest-neighbor classifier, the attack named the byte (and so the full path) in 81.02 percent of held-out recordings across all 256 bytes, with 111 neighbors voting.
• Accuracy depended on the vote size: 67.58 percent with 11 neighbors and only 40.06 percent with 501.
• Among the first two bytes, the attack was perfect for every vote size; among four, it reached 97.5 percent; among eight, 87.5 percent.
• The abstract adds that sets of 32 bytes were classified above 95 percent.

• Full path recovery. Over 256 oracle values, accuracy rises monotonically from 67.58 percent at k = 11 to 81.02 percent at k = 111, dips to 78.73 percent at k = 121, reaches a local maximum of 80.12 percent at k = 171, and falls steadily to 40.06 percent at k = 501 (Fig. 5).
• Class count. On the first N oracle values, two classes give 100 percent at every k; four give 87.5 to 97.5 percent, constant at 97.5 percent for k ≥ 15; eight peak at 87.5 percent (k = 21 and 23); 256 reach 72.52 percent within that experiment’s range of k (Fig. 6).
• Averaging. Element-wise means of three traces reduce peak noise (Figs. 3 and 4), slightly improve accuracy, and cut the data loaded by about a factor of three.
• Tooling. Out-of-the-box scikit-learn 1.1.2 k-NN with uniform votes, accelerated with the Intel extension for scikit-learn on a small GPU cluster; only k was varied.

Computed by this page, beyond the paper: every Section IV-A percentage equals a whole number of correct traces out of 10,240 (for example, 81.02 percent is 8,296 of 10,240), the held-out count for 40 traces per oracle value (20 percent of 200). The smallest per-value count that fits all six printed values is 20 (5,120 traces). Averaging 200 captures in separate groups of three would leave 66 traces per value and about 13 held out per value (3,380 in all at 20 percent), which fits none of them.

Power analysis began as a way to pull secret keys out of encryption chips. This study turns it on something designers rarely think of as secret: the order of a device’s own steps. For a device whose steps control a physical action, knowing the order (or even how many states there are) is the first move toward predicting or steering it. The attack needed only an open-source measurement board and a textbook classifier. Ultimately, treating control flow as information worth protecting belongs at the start of an embedded design, alongside its encryption keys.

Classic differential power analysis targets data in registers and buses. Here the target is control flow, where different branches run different instruction streams and so draw different power over time, a leak that no amount of data masking addresses. The result connects to the lab’s earlier work on side-channel-resistant FSM encodings (S*FSM, 2012) and state encodings that trade security against power (VLSID 2019), which were evaluated in simulation; this paper measures the threat on hardware and calls for protections when FSM-controlled components handle sensitive information.

The contribution is a hardware demonstration that profiled, nonparametric classification of raw traces recovers an FSM’s input-driven path on a commodity Cortex-M0, with a known-input oracle as the threat model. The evidence is preliminary by design: one target, one two-state machine with deliberately different state bodies, one train/test split, and no countermeasure. The authors list the next steps: 16-bit oracles, non-discrete inputs such as a potentiometer, the structure of more complex machines, counting transitions and timing them within a trace, measuring state execution time, and changing the data each state receives.

Notes from building this page

• The printed percentages imply 40 held-out traces per oracle value. All six Section IV-A accuracies are exact counts over 10,240 (8,296, 6,920, 8,062, 8,204, 4,102, and 7,426 correct), and so are the four- and eight-class values (97.5 and 87.5 percent are 156 and 140 of 160, and 280 of 320). The text says 200 captures per value were averaged in threes to reduce the number of traces, which would leave about 66 per value; one reading consistent with the counts is 200 averaged traces per value (600 captures), or averaging that does not shrink the set. The page uses 200 averaged traces per value, three captures each, and asks the authors which applies.
• The peak at k = 111 fits 160 training traces per value. With about 53 (80 percent of 66), any vote above 53 must include other values and, above about 106, the true value can hold at most half the votes, so a curve still rising at k = 111 supports the larger training set.
• Path and input are the same thing here. The next state depends only on the input bit, never on the current state, so recovering the transition order is equivalent to recovering the oracle byte. The attack demonstrates input recovery through control flow; machines whose transitions depend on the current state would separate the two questions.
• Class count and step position move together in Experiment 2. The first N oracle values differ only in their lowest log₂ N bits, which are the earliest steps after the trigger, and every later step is state one. Smaller sets therefore test fewer and earlier steps, where alignment to the trigger is tightest. Drawing random subsets of the 256 values would separate the two effects.
• The fall to 40.06 percent at k = 501. With 160 training traces per value, a 501-vote must draw at least 341 traces from other values, but in the page’s independent-noise simulation accuracy keeps rising to k = 501 (78.23 percent). A fall that steep suggests that some oracle values’ traces cluster together, for example values that differ only in late steps if the capture window clipped the end of the program, or drift that moved late steps between captures. The paper does not report the capture length, so this is the page’s hypothesis.
• Experiment 2’s 256-class maximum. Section IV-B reports 72.52 percent for 256 classes within its range of k, and refers to 81.02 percent from Experiment 1 with larger k; the k grid of Fig. 6 is not stated (the text mentions k = 15, 21, and 23).
• Text against results. The discussion says it is “promising to see improved classification accuracy as the number of classes increase”; the results show accuracy falling as classes increase, so the sentence likely means increasing k. The abstract’s “over 95% in classes with 32 elements” appears only in Fig. 6, not in the text.
• Misses are near misses (page computation). In the simulation at the paper’s size and k = 111, a wrong guess gets 1.23 of eight steps wrong on average, and later steps are wrong more often (step 8 in 888 of 10,240 held-out traces, step 1 in 324), as timing drift accumulates along the trace. Reporting per-step accuracy alongside exact-byte accuracy would show how much of the path a real attacker recovers even when the byte is wrong.
• Equal work removes most of the simulated signal (page computation). Running both routines at every step removes the timing and shape differences between states; only the dispatch block’s handling of the oracle register still varies, by 0.035 power units per set bit. At the page’s noise and 200 traces per value, the attack then sits near chance: 0.31 to 0.54 percent across k for 256 values (chance 0.39 percent) and 40 to 65 percent for two values (chance 50 percent, on 80 held-out traces). The register leak remains in the model, so more traces or a stronger leak could still expose it; constant-weight state encodings, the property S*FSM was designed to provide, target that residue.
• What the simulation can and cannot say. The cycle counts, power levels, leakage, noise, and trigger offset are the page’s choices; the noise was set so the simulated 256-value accuracy lands near the paper’s best. The simulated trends (perfect small sets, near misses, the effect of equal work) show mechanisms, not predictions of the real traces.

Try this in class

1. Write 128, 85, and 200 in binary. For each, list the eight states the chip runs, reading the bits from right to left (0 = Compute, 1 = Send). Check your lists with the first demo.
2. In the second demo, record the spread for raw captures and for averages of three. Divide one by the other and compare with √3. Predict the spread for averages of 12 captures, and explain why averaging cannot fix every kind of error.
3. In the attack demo, run four bytes, then 64 bytes, with 50 traces each and k = 11. Record both accuracies and the chance level for each. In two sentences, explain why more choices make the attack harder, and why it stays far above chance.