  In this paper, we present a non-invasive reverse engineering attack based on
a novel approach that combines functional and power analysis to recover finite
state machines from their synchronous sequential circuit implementations. The
proposed technique formulates the machine exploration and state identification
problem as a Boolean constraint satisfaction problem and solves it using a SMT
(Satisfiability Modulo Theories) solver. It uses power measurements to achieve
fast convergence. Experimental results using the LGSynth'91 benchmark suite
show that the satisfiability-based approach is several times faster compared to
existing techniques and can successfully recover 90%-100% of the transitions of
a target machine.
