{"id":"51f86ec6-f1c7-4f6d-b477-c8f26028d334","arxiv_id":"1908.01979","paper_version":1,"verdict":"REJECT","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"high","formal_verification":"none","parameter_count":3,"one_line_summary":"A SAT-based reverse engineering method combines power-analysis-derived Hamming distances with input-output observations to recover 90-100% of finite state machine transitions in small benchmark circuits.","lead":"This paper describes an attack that recovers the internal state diagram of a small digital chip by watching its power use while feeding it random inputs and solving a logic puzzle. The authors claim the method is faster and handles larger circuits than earlier black-box reverse engineering techniques.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Algorithm 1 never forces revisits through non-self-loop paths to share an encoding, so cyclic FSMs can be solved as unrolled trees; isomorphic recovery is underdetermined by the constraints.","rationale":"The central claim is that the SAT model is isomorphically equivalent to the target FSM. For that to be true, the constraints must force, up to renaming, exactly the target state partition and transition function. They do not: equality between non-consecutive states is never required unless a self-loop HD of 0 was observed, and no constraint references inputs, so determinism is not enforced either. This is not a disagreement with consensus; it is an internal gap between Algorithm 1 and the claimed result, acknowledged in part by the paper's own remarks about suboptimal state folding and by the * entries in Table IV. The power-analysis correlation measurements (Tables I-II) and the SAT-encoding idea are useful components, but they do not support the strong recovery claim. The reader's REJECT verdict is appropriate; no verdict change is needed.","tokens_in":6216,"tokens_out":8397,"duration_ms":92786,"concrete_test":"Use a no-self-loop cyclic machine such as a 3-state ring counter (A--0-->B, B--0-->C, C--0-->A, unique Moore outputs, fixed 2-bit encoding). Generate a long input sequence (N >= 2*3*2) of all-0 vectors with exact Hamming distances from the known encoding, run Algorithm 1 exactly as written in the paper using Z3, and inspect the printed model: count distinct state encodings and check whether each (state encoding, input) pair has a unique successor. If more than 3 distinct encodings appear, or if any (state,input) pair forks, the constraint set does not force isomorphism. As a control, add an explicit determinism constraint (same (state,input) must imply same next state) and observe whether the original formulation allowed additional models.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Algorithm 1 (Section III-B) creates a fresh bit-vector s_i for each of the N+1 observed time positions and adds only IdenticalStates (Eq. 2) when an inferred HD is exactly 0, InferredHD (Eq. 3) for each transition's ±1 range, and DistinctStates (Eq. 4) for endpoints whose Moore outputs differ. Nothing in these constraints merges a state reached at time i with the same physical state reached later via a path of non-zero-HD transitions. A cyclic machine without self-loops is therefore consistent with a model in which every visit to the same state receives a distinct encoding, provided per-step HD ranges and output inequalities are met. Because the solver returns any satisfying assignment and R is increased until one exists, the assertion in Section III-B that the encodings 'lead to recovery of a state machine which is isomorphically equivalent' is unsupported; the constraints do not even mention the input vectors, so determinism of the recovered graph is not enforced. The paper itself concedes (Section IV, item 3) that non-minimal encodings cause 'many indistinguishable states [to] be misidentified as distinct,' and Table IV marks several benchmarks where the equivalent machine was not recovered. Those admissions, plus the lack of any uniqueness or isomorphism argument, break the central recovery claim as stated.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a non-invasive reverse-engineering attack that recovers finite state machines from synchronous sequential circuit implementations using power analysis and a SAT/SMT solver. The authors measure average current consumption during state transitions, build a lookup table mapping current ranges to Hamming distance ranges (Table III), and then encode the observed HD ranges and output differences as Boolean constraints (Equations 2-4) over unknown state encodings. Algorithm 1 solves these constraints with the Z3 SMT solver, increasing the encoding length until a satisfying assignment is found. Experiments on LGSynth'91 benchmarks report 90-100% transition recovery and faster runtime than prior black-box techniques. The central claim is that the generated state encodings yield a state machine isomorphically equivalent to the target implementation.","tokens_in":6461,"tokens_out":3764,"duration_ms":43066,"significance":"If the central claim were correct, this would be a practical contribution to hardware security, showing that power side channels plus SAT solving can reconstruct small FSMs non-invasively. The paper's experimental apparatus is concrete: it provides Pearson correlations (Table I), an inference accuracy table (Table II), a current-to-HD mapping (Table III), and a detailed algorithm description, which makes the work easy to inspect. The strength of the paper lies in the idea of encoding HD-range constraints as a SAT problem. However, the central equivalence claim is not supported by the presented constraints, and the reported success metric relies on knowledge of the target transition graph, which an attacker does not possess. The paper is best read as a proof-of-concept for a constrained state-encoding search, not as a demonstration of isomorphically equivalent FSM recovery.","major_comments":[{"comment":"Algorithm 1 creates a fresh bit-vector s_i for every observed time position and merges states only when the inferred HD of a transition is exactly zero via the IdenticalStates constraint (Equation 2). There is no constraint that forces two occurrences of the same physical state reached through different non-self-loop paths to receive equal encodings. A cyclic machine without self-loops is therefore consistent with a model in which every visit to the same state is assigned a distinct code, as long as the per-step HD ranges and output inequality constraints are satisfied. The assertion in Section III-B that the encodings 'lead to recovery of a state machine which is isomorphically equivalent' is not supported by the stated constraints.","section":"Section III-B, Algorithm 1 and Equations (2)-(4)"},{"comment":"The paragraph explaining the termination condition states that the process stops 'when it recovers 90% of state transitions from the target machine.' This presupposes that the attacker already knows the full target transition set, which is precisely the information the attack is supposed to recover. The 90-100% recovery percentages reported in Table IV and Figure 4 are therefore not a meaningful end-to-end attack metric; they measure agreement with ground truth that an attacker would not have. This circularity directly undermines the claim of successful recovery.","section":"Section III-B, termination criterion"},{"comment":"The SAT formulation does not include the input vector values as variables or constraints. Equations (2)-(4) relate state encodings only through HD ranges and output differences; they do not encode the transition function δ as a function of primary inputs, nor do they enforce that the recovered transitions are deterministic with respect to each input. Consequently, the solver output is a set of state encodings, not a fully specified finite state machine with an input-to-state mapping. The paper does not establish that this output is 'logically equivalent' to the target machine in the usual sense of input-output behavior.","section":"Section III-A.3, Boolean SAT formulation"},{"comment":"The power-to-HD lookup table is calibrated empirically on a small set of sample FSMs in one 90nm technology, and the inference error model of Equation (1) assumes that non-self-loop HD values are always inferred within ±1. Table II shows that 14.8% of the measured transitions have an error of exactly ±1, and Figure 2 shows overlapping average-current distributions for consecutive HD values. The paper provides no analysis of how threshold calibration transfers across different circuits, process corners, or supply voltages, so the reliability of the inferred HD ranges outside the calibration environment is unquantified.","section":"Section II and Table III"},{"comment":"The paper concedes that non-minimal state encodings cause 'many indistinguishable states [to] be misidentified as distinct.' This concession is the concrete manifestation of the missing merging mechanism: since Algorithm 1 increments R until a satisfying assignment is found, the first satisfiable model can over-distinguish states that are actually the same. Table IV marks several benchmarks where the equivalent machine was not recovered. These admissions contradict the unqualified isomorphism claim and indicate that the reported 'recovery' is not a reliable reconstruction of the target FSM.","section":"Section IV, item 3"}],"minor_comments":[{"comment":"Equation (1) contains typographical artifacts such as 'HD inf erred' and '≤' rendering issues; the notation should be cleaned up and the HD inference error should be defined more precisely as a range, e.g., HD_actual ∈ [HD_inferred − 1, HD_inferred + 1].","section":"Section II, Equation (1)"},{"comment":"The sentence 'The attacker can find out it has 7 inputs, 7 outputs and atleast 16 states' contains a typo ('atleast' → 'at least') and it is not explained how the attacker can determine these parameters, especially the state count, before running the attack.","section":"Section II, paragraph on SSE benchmark"},{"comment":"The derivation of the current thresholds in Table III is not described; the authors should state whether the thresholds come from the calibration machines or from the SSE-specific attack, and how overlapping distributions were resolved when setting the boundaries.","section":"Section II, Table III"},{"comment":"Several references are incomplete, e.g., [7] and [9] lack full publisher information, and [5] has a malformed date string ('4 1 1999'); the reference list needs to be formatted consistently.","section":"References"}],"recommendation":"reject","confidential_remarks":"The central claim of isomorphically equivalent recovery is unsupported by the algorithm's constraints, and the reported success metric is partly circular because it uses ground truth for the stopping rule and for the 90-100% recovery percentages. The lack of an input-aware determinism constraint and the absence of any merging mechanism for non-self-loop revisits are fundamental, not cosmetic, issues. The work might serve as a component in a larger reverse-engineering pipeline if the authors add explicit state-revisit constraints and evaluate the attack without access to the target transition graph, but the manuscript as written does not deliver the claimed result."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"One thing to know: this paper has a decent idea and a broken central claim. The combination of power-trace Hamming-distance inference with a SAT/SMT encoding for FSM recovery is new relative to the brute-force functional analysis cited in [6]–[9]. The authors calibrate average current against HD on a 90nm cell library, report Pearson correlations above 0.93, and show that inferred HDs land within ±1 on 500 transitions of one benchmark. That part is honest and mostly reproducible from the description.\n\nThe soft spot is load-bearing. Algorithm 1 creates a fresh bit-vector for every observed time step and only adds IdenticalStates when the inferred HD is exactly zero (self-loops). It never forces states reached via non-self-loop paths to share an encoding. So a cyclic FSM without self-loops can be satisfied by an unrolled tree of distinct encodings. The claim in Section III-B that the encodings yield an isomorphically equivalent machine is not supported by the constraints; the solver can return any satisfying assignment. The paper itself concedes in Section IV item 3 that non-minimal encodings misidentify indistinguishable states, and Table IV marks several benchmarks where the equivalent machine was not recovered. That admission is to the authors' credit, but it undercuts the abstract's recovery claim.\n\nSecond issue: the 90–100% recovery metric. The test procedure terminates when it recovers 90% of transitions \"from the target machine\"—which an attacker does not know. There is no way to measure recovery percentage during an actual attack, so this is a circular success criterion. The runtime comparison with prior work is also qualitative, not a head-to-head measurement against their implementations, so the speedup claim is plausible but not demonstrated.\n\nWhat remains is a promising early idea with an empirical power model and a straightforward SAT formulation. If the state-merging problem were fixed (e.g., by adding uniqueness or minimality constraints, or by using trace-equivalence), the approach could work for small FSMs. As it stands, I would not cite the recovery result, but the power-to-HD calibration and the SAT setup are useful groundwork.\n\nRecommendation: send to peer review if the venue handles methods papers, but expect reviewers to require a real isomorphism argument and measurements on silicon or emulation rather than simulation only. The paper deserves serious refereeing because the core combination is of interest and the main flaw is identifiable and fixable.","headline":"Plausible SAT-plus-power technique with a load-bearing gap: the constraints never merge revisits through non-self-loop paths, so the isomorphic-recovery claim is unsupported.","tokens_in":6983,"tokens_out":2173,"would_cite":false,"duration_ms":21627,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"A side-channel attack that observes a chip's power draw while feeding it random inputs can reconstruct its finite state machine without opening the chip.","keywords":["black-box analysis","finite state machine","power analysis","reverse engineering","satisfiability checking","Hamming distance model","side-channel attack","sequential circuits"],"falsifier":"Run the algorithm on a known two-state machine that toggles between its states and feed a long random input sequence that crosses the cycle several times; if the solver produces an encoding with more than two distinct states instead of the true cyclic machine, the claim of isomorphic equivalence is refuted.","tokens_in":5968,"feed_emoji":"⚡","tokens_out":9312,"duration_ms":92737,"temperature":0.7,"pith_summary":"This paper tries to show that a synchronous sequential circuit's finite state machine can be reverse engineered non-invasively by combining two observable channels: the chip's power draw during each clock transition and the input-output behavior on random stimulus. The idea is that power consumption reveals the Hamming distance between consecutive state-register contents, which becomes a numerical constraint on an unknown Boolean state encoding. These constraints, together with output observations that distinguish states, are solved by an SMT solver to produce a state encoding for a machine that is claimed to be isomorphically equivalent to the target. On benchmark circuits the method recovers 90-100% of transitions in under eleven minutes, and the authors argue it scales to machines several dozen times larger than earlier brute-force input-output techniques. A sympathetic reader would care because successful recovery means an attacker with only an oscilloscope and I/O access can learn the full behavior of a small embedded chip without opening it.","feed_headline":"Power traces alone rebuild a chip's state machine","feed_subtitle":"Feeding random inputs while watching current draw recovers 90-100 percent of transitions without opening the chip.","key_machinery":"The load-bearing mechanism is the Hamming-distance power model: average dynamic current of a state-register update is strongly correlated with the Hamming distance between the old and new state encodings, so measured power traces can be thresholded into HD estimates with ±1 error. These estimates become three Boolean predicates over R-bit state variables: IdenticalStates forces a sum of XORs to equal zero when a self-loop is detected, InferredHD forces the sum into the observed range, and DistinctStates forces it to be positive when output values differ. The SAT/SMT formulation lets the solver search over all state encodings simultaneously, which is what turns an exponential black-box exploration into a constraint-satisfaction problem.","core_discovery":"The central claim is that FSM recovery reduces to a Boolean constraint satisfaction problem over bit-vector state encodings, where the constraints come from power-derived Hamming distance ranges and from output observations. For N random input vectors the attacker obtains N+1 state variables; power traces are converted through a calibrated lookup table into a range [hd_i-1, hd_i+1] for each transition's Hamming distance (with exact zero for self-loops), and output vectors force distinctness when outputs differ. The algorithm starts with the smallest encoding length R consistent with the observed output alphabet and increments R until the SMT solver returns a satisfiable assignment. The resulting assignment gives a state encoding whose transition graph is logically equivalent to the implemented machine; the paper reports 90-100% transition recovery on the benchmark machines tested, with runtime roughly growing with the number of test vectors.","pith_inferences":["Editorial extension: if the power-to-Hamming-distance lookup table transfers across chips of the same process technology, the attack could be automated for a class of devices without per-device calibration, which the paper only demonstrates on known circuits from the same library.","A testable extension would be to run the same constraint framework using only output observations and dropping the power constraints; the runtime difference would isolate how much of the speedup is attributable to the side channel.","The method's reliance on exact self-loop detection suggests a targeted countermeasure: make self-loop transitions consume power far from the zero-Hamming-distance cluster, or decorrelate power from Hamming distance, which would remove the anchor the solver uses for state merging."],"forward_implications":["A device can be behaviorally cloned from the outside: recording input vectors, output vectors, and supply-current traces is sufficient to reconstruct a logically equivalent state machine.","The method extends practical non-invasive reverse engineering to machines far beyond the reach of earlier black-box functional analysis, which was limited to roughly 25 transitions; the paper demonstrates machines with up to 1600 transitions.","Self-loop-heavy machines converge fastest, because exact zero-Hamming-distance detection sharply restricts the solver's search space.","Recovery is not guaranteed to be complete in one pass: coverage of transitions depends on the random input sequence, and the paper stops after 90% recovery in later rounds."],"supporting_citations":[{"why":"Supplies the benchmark finite-state machines used as targets and for calibrating the power-to-Hamming-distance lookup table.","marker":"[12]"},{"why":"Establishes the differential power analysis method that motivates reading data-dependent information from power consumption.","marker":"[10]"},{"why":"Provides the Hamming-distance power model for CMOS state-register transitions that connects average current to state change.","marker":"[11]"},{"why":"Supplies the SMT solver used to solve the bit-vector constraints for a valid state encoding.","marker":"[13]"},{"why":"Is the prior black-box input-output analysis that provides the runtime and transition-count baseline the paper improves upon.","marker":"[8]"},{"why":"Is the prior FSM identification method whose terminating-state requirement and long runtime define the scalability gap the paper addresses.","marker":"[7]"}],"fun_headline_variants":["Power traces expose chip's finite state machine","Reverse engineer FSM with power and SAT solver","Non-invasive FSM recovery from power analysis","Power side-channel reconstructs state machines"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The recovery hinges on the solver recognizing that a state visited a second time is the same state, even though the constraints only force that identity when power analysis sees a transition that changes no register bits.","fun_headline_variants_meta":{"raw":{"variants":["Power traces expose chip's finite state machine","Reverse engineer FSM with power and SAT solver","Non-invasive FSM recovery from power analysis","Power side-channel reconstructs state machines"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000185,"raw_usage":{"total_tokens":1254,"prompt_tokens":811,"completion_tokens":443,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":427,"completion_tokens_details":{"reasoning_tokens":388}},"tokens_in":427,"tokens_out":443,"duration_ms":5131,"temperature":1.0,"reasoning_tokens":388,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T14:57:35.871650+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the algorithm on a known two-state machine that toggles between its states and feed a long random input sequence that crosses the cycle several times; if the solver produces an encoding with more than two distinct states instead of the true cyclic machine, the claim of isomorphic equivalence is refuted.","supporting_citations":[{"cited_title":"Brutscheck, Systematic analysis of unknown integrated circuits (Doc- toral Thesis), Dublin Institute of Technology, 2009","cited_arxiv_id":null,"evidence_quote":"Supplies the benchmark finite-state machines used as targets and for calibrating the power-to-Hamming-distance lookup table."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Establishes the differential power analysis method that motivates reading data-dependent information from power consumption."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the Hamming-distance power model for CMOS state-register transitions that connects average current to state change."},{"cited_title":"Brutscheck, B","cited_arxiv_id":null,"evidence_quote":"Supplies the SMT solver used to solve the bit-vector constraints for a valid state encoding."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Is the prior black-box input-output analysis that provides the runtime and transition-count baseline the paper improves upon."},{"cited_title":"Torrance and D","cited_arxiv_id":null,"evidence_quote":"Is the prior FSM identification method whose terminating-state requirement and long runtime define the scalability gap the paper addresses."}],"review_version":1}