S*FSM: Rebuilding State Machines So the Power Meter Reads the Same Every Tick

This controller guesses whether a program will take its next branch. Four states (strongly taken, weakly taken, weakly not taken, strongly not taken) remember the last few outcomes. Press the branch buttons and watch the two bar rows. With the ordinary Binary codes, a weight of two can only mean strongly taken and a weight of zero only strongly not taken, so the meter names the state about half the time. Switch to S*FSM and S*Optimal: every state holds two ones, every tick flips two bits, and both rows go flat.

The original predictor needs only two bits (ST = 11, WT = 10, WNT = 01, SNT = 00), and those codes carry zero, one, or two ones. One-hot fixes the weight row (every code has exactly one 1), yet the flips row still drops to zero whenever the predictor stays in ST or SNT. That zero is the self-loop, and no choice of codes can remove it. The S*FSM button splits each of those states into a pair (ST1 and ST2, SNT1 and SNT2) that hand the job back and forth, so even “staying put” flips bits. Then a four-bit code with two ones per state keeps both rows constant.

The codes are the 2012 paper’s: Figure 2 for the original machine and Table 1 for the unrolled one. Under minimal binary, the unrolled predictor shows weights 0 to 2 and distances 1 to 3; one-hot (six bits) and S*Optimal (four bits) show a single weight and a single distance. Applied to the original machine, the S*Optimal codes keep the weight constant but the distances read 0 or 2, which is the paper’s point: encoding alone cannot secure an FSM with self-loops, and structure alone cannot secure one with a minimal encoding. The readout counts the states (or transitions) that share the current reading, the ambiguity an attacker faces with one noiseless sample.

The 2012 paper drove a high-level simulator with random transition vectors of 10 to 50,000 steps and reported the average correlation over 100 runs between each Hamming model and the state or transition (Table 2), for example 0.63 between state and weight under binary codes at 50,000 cycles. The paper does not say how a state or transition becomes a number for a Pearson correlation, so this page does not repeat that table; the researcher notes explain what the page tried. The demo reports the reading sets instead, which match Figure 2 and Table 1 exactly.

A state that can stay where it is causes the trouble: staying put flips no bits, and no other move looks like that. The fix copies the state. The copy, drawn with a dashed outline, takes over whenever the machine would have stayed, so the machine bounces between the two instead. Everything that left the original state now leaves the copy too, so the controller still does exactly the same job. Press Unroll the next self-loop and count what it costs.

Try the three-state machine from the 2014 paper first: B can stay in B, so the method adds Bn. The machine grows from three states and four transitions to four states and six, the same counts as the paper’s Figure 2. The branch predictor grows from four states to six. Each new state can raise the number of bits a binary code needs, since n bits can only number 2ⁿ states.

Algorithm 1 removes each self-loop e(v, v, t), adds a state v′ with transitions v → v′ and v′ → v on condition t, and copies every outgoing transition of v to v′. Transitions into v stay as they were. For a KISS2 description, every product term of a looping state is duplicated, so the term count grows by the number of terms those states had. The 2013 paper’s FSM 137 grew from four states and 11 transitions to seven and 20; across the 52 MCNC machines here, unrolling adds 48 percent more states and 52 percent more product terms on average.

Unrolling is the inverse of state minimization: it adds states that are equivalent in the automata sense, so a synthesis flow must be told not to merge them back. The MCNC benchmarks span the full range, from machines with no self-loops (DK27, DK512, EX2, EX3, MARK1, SCF, TAV) to machines where every state loops (BBARA, CSE, DONFILE, LION, MODULO12, TBK, and others), which doubles both states and terms. Rows that apply in every state (present state “*”, in KISS2 for KIRKMAN, MARK1, OPUS, and SCF) are kept as written.

Now every state needs a pattern with the same number of ones, and every arrow must connect two patterns that differ in the same number of places. For the branch predictor, the six four-bit patterns with two ones fit exactly, as long as no arrow joins two opposite patterns (0101 and 1010 differ everywhere). Press Shuffle the codes to scramble them: the dashed arrows are moves a power meter could now tell apart. Press Search again in your browser to find a secure arrangement.

Every pattern of four bits with two ones has exactly four others that differ in two places and one, its opposite, that differs in all four. The search places codes state by state and backs up whenever a move would flip the wrong number of bits. Try the other machines. LION and MC need five bits for eight states; DK15 needs seven, two more than a count of states alone would suggest, because so many of its states connect to each other.

The search fixes a code length n and a weight c₁, requires distance c₂ on every transition between distinct states, and increases n until a code exists; at the shortest n it reports the smallest c₂. With weight fixed, every distance is even, and c₂ = 2 means each move swaps one 1 for one 0. Low power: distance 2 and Distance 4 fix c₂ as in the 2014 paper’s Table V, and One-hot (c₁ = 1, c₂ = 2) always works with one bit per state. Peak current per edge, N_peak = c₂ / 2 (2014, Eq. 5), so shorter distances also mean smaller current spikes.

The search is exact: it visits states in a connectivity order, fixes the first code and its first neighbor up to bit permutation, and draws candidates only from codes at distance c₂ from an already-placed neighbor, so a failure at length n is a proof that no such code exists. Across the 52 benchmarks it settled the shortest secure length for 40 machines within its budget, and an independent Z3 model of the same constraints, run on 22 of the smaller machines, agreed on all 75 shortest lengths it could settle. The papers do not describe their own encoding search; the 2014 paper cites Z3.

Keeping every pattern’s count of ones the same leaves fewer patterns to choose from. With six bits, binary offers 64 patterns, but only 20 have exactly three ones. Move the slider to see how many bits each style needs for a controller of your size.

The number of n-bit patterns with c ones is “n choose c,” written C(n, c). It peaks when c is half of n, which is why the paper calls that choice S*Opt. One-hot is the special case c = 1: simple, always secure, and one bit per state.

The 2013 paper’s S*Opt chooses c = ⌊n/2⌋, which maximizes the number of states, SMAX = C(n, ⌊n/2⌋) (Eq. 9), and the number of codes reachable by one swap, TMAX = c(n − c) = ⌊n²/4⌋ (Eq. 10). A machine with s states whose busiest state connects to t others needs at least the smallest n with SMAX ≥ s and TMAX ≥ t. The bound assumes c₂ = 2. The benchmark search below shows the bound is neither sufficient nor tight: 13 of the 40 settled machines need fewer bits once c₂ = 4 is allowed (BBARA needs eight, not nine), and seven need more because their transitions cannot all be realized as single swaps (DK15 needs seven, not five).

Each bar is one standard test controller. The first view shows how many states unrolling adds; the others show how much longer the codes become. The dotted line marks the average the 2014 paper reported for its own 12 test controllers; the solid line marks this page’s average across the controllers on screen.

Unrolling adds about half again as many states on average, close to the 49 percent the 2014 paper reports. Secure codes cost more: the shortest code that hides both weight and flips averages about 90 percent longer than the original binary code here, against 70 percent in the paper. One-hot is the most expensive, more than four times the binary length for these machines.

All lengths are relative to ⌈log₂ s⌉ bits for the original machine, the baseline the papers use. For the 38 machines with at most 32 states after unrolling, the page finds +48 percent states, +51 percent product terms, +18 percent binary length after unrolling, +92 percent for the shortest secure code (37 settled), +34 percent for RHD, +70 percent for RHD plus constant weight, +102 percent at c₂ = 4 (37 settled), and +129 percent at c₂ = 2 (25 settled). The 2014 paper reports +49, +57, +15, +70, +30, +55, +70, and +112 percent on its unnamed 12 machines. A machine whose search hits the budget is listed but left out of the mean.

RHD keeps the self-loops and requires constant distance only between distinct states (2014, Eq. 3); RHD + HW adds constant weight. Both leave the zero-distance self-loop visible, so they trade the security of the full S*FSM for no added states. The (1, 2) family is one-hot on the unrolled machine; the page computes +328 percent for the 38 smaller machines and +520 percent for all 52, against 400 percent in the paper, a figure that depends heavily on which large machines are included.

• Ordinary state codes let a power meter identify a controller’s state, and even its moves, from the simplest power models.
• Changing the codes alone cannot hide a controller that sometimes stays put; the controller has to be rebuilt first.
• Rebuilt controllers with balanced codes give a power meter the same reading every tick, in theory removing what these attacks rely on.
• The protection costs size: about 50 to 70 percent more states and roughly twice the chip area in the authors’ tests, comparable to protecting every logic gate.

• Two rules make both power models constant: every state has the same number of ones, and every move flips the same number of bits.
• Self-loops break the second rule for any code, so they must be unrolled into pairs of states.
• On seven test machines, securing them needed 72 percent more states, 77 percent more transitions, and 79 percent more bits on average (2013).
• On 12 standard test machines, rebuilding cost 49 percent more states, and the shortest secure codes were 70 percent longer than binary (2014).
• Relaxed rules save bits or reduce power spikes, at the price of leaving some information visible.

• Two sufficient conditions. Constant HW over states and constant HD over transitions make both Hamming models constant, so their correlation with power is undefined (2012 Section 3; 2013 Eq. 3 to 6).
• Structure is necessary. A self-loop has HD = 0, so condition 2 fails for any encoding of a multi-state FSM with self-loops; Algorithm 1 removes them (2012).
• Encoding is necessary. Minimal binary codes vary in both models even after unrolling (2012 Table 1); one-hot and S*Optimal codes do not.
• Measured cost. Seven BenGen machines: +71.6 percent states, +77.0 percent transitions, +78.6 percent encoding bits, and +96.4 percent layout area at 90 nm, which the authors compare with one-to-one duplication in low-level logic styles (2013 Tables II to V).
• Relaxations. Twelve MCNC machines: +49 percent states and +57 percent product terms; encoding length +15 percent (binary), +70 percent (S*Optimal), +30 percent (RHD), and +55 percent (RHD + HW); peak-current constraints cost +70 percent (c₂ = 4), +112 percent (c₂ = 2), and +400 percent (one-hot) (2014 Tables III to V).

Controllers sit inside almost everything that runs on a chip, from door badges and pacemakers to drones and network cards. Most side channel defenses protect the cryptography and redesign individual logic gates, which is expensive. These papers move the defense up to a choice every designer already makes, which pattern stands for which state, and show that a controller can be made unreadable to the common power models before a single gate is drawn.

State assignment and FSM restructuring happen before logic synthesis, so the countermeasure needs no custom cells and no change to the downstream flow, provided synthesis is told not to minimize the unrolled states back together. The 2013 layout results put the cost near that of low-level duplication methods without their design effort. The 2014 relaxations then give designers a dial: keep self-loops to save states, fix the weight to save static power, or fix a small distance to limit peak current.

The S*FSM conditions target the state register and first-order Hamming models; they say nothing about the next-state and output logic, glitches, routing imbalance, or higher-order attacks, and the papers’ validation is at the model and synthesis level, with silicon attacks listed as future work. The approach became the base for later secure encoding work in the DRACO lineage, including Agrawal, Vemuri, and Borowczak’s reachability-based encodings, which relax the conditions to sets of states reachable at the same time; the interactive page on that work carries the idea forward.

Notes from building this page

• 2012 Table 2 does not reproduce. The paper reports average Pearson correlations between each Hamming model and “State” or “Transition” without saying how those become numbers. For the four-state predictor under uniform random branches, labeling the states 0 to 3 in either natural order gives |r| = 0.95 against weight; only labelings such as ST = 3, WT = 2, SNT = 1, WNT = 0 give the printed 0.63. The binary and one-hot transition columns are identical at every length (0.61, 0.17, 0.17, 0.18), which only happens if every non-loop transition has the same binary distance, as in the two-state machine of Figure 3 rather than the predictor; for that machine, however, state and weight would correlate perfectly. The page therefore reports reading sets, not correlations.
• 2013 Table IV’s large machines. By state count alone, S*Opt allows nine bits for the four large machines (C(9, 4) = 126 ≥ 117), while the table lists ten. The TMAX condition (20 neighbors at n = 9) or the “near S*Opt” encodings of the experimental flow may explain the extra bit; the BenGen machines are not public, so the page cannot check.
• The S*Opt bound is a necessary condition for c₂ = 2 only. On the MCNC machines the exact search finds shorter secure codes than the bound for 13 machines (all with c₂ = 4) and longer ones for seven, so the bound neither guarantees nor limits the true length.
• 2013 Table V units. The layout areas are labeled nm²; at 90 nm a single flip-flop occupies several square micrometers, so the values (407 to 88,445) read as µm².
• 2014 Figure 2 caption. The caption gives A = 01, but the table’s weights and distances (HW(A) = 0, HD(C → A) = 1) require A = 00. The page uses 00.
• 2014 summary figures. The abstract and conclusion give 53 to 67 percent for the relaxed encodings, while Table IV lists 30 percent (RHD) and 55 percent (RHD + HW). Eq. 3 prints i = j where the text describes transitions between distinct states (i ≠ j), and Eq. 5 reads N_peak = c₂ / 2.
• The 12 MCNC machines are not named. A search over 12-machine subsets of the 52 LGSynth’91 machines found many that match the reported +49 percent states, +57 percent terms, and +15 percent binary length, so the paper’s set cannot be recovered from its averages. The page reports its own means with their machine counts.
• What the page counts as a transition. Product terms follow the 2014 paper’s wording; the graph views count distinct state pairs. Unrolled BBARA has 20 states and 74 directed state pairs, the same counts as the restructured BBARA in the 2019 follow-up.

Try this in class

1. Write the branch predictor’s four states with the two-bit codes ST = 11, WT = 10, WNT = 01, SNT = 00. For each state, count the ones; for each of the eight transitions, count the bits that flip. Which readings name a single state?
2. Unroll ST and SNT on paper as the demo does. List the four-bit codes with exactly two ones and assign them so every arrow flips exactly two bits. Check your answer with the demo’s shuffle and search buttons.
3. Using the capacity demo, find the shortest balanced code for a 30-state controller. In a short paragraph, explain what a designer gains and what the designer pays compared with a five-bit binary code.