FSMx: Finite State Machine Extraction from Flattened Netlist With Application to Security
Rasheed Kibria, Nusrat Farzana, Farimah Farahmandi, Mark Mohammad Tehranipoor · 2022
A number of security vulnerability assessments require accurate and fast extraction of the finite state machines (FSMs) in the circuit. FSM should be accurately extracted for watermark insertion, FSM-based logic locking, fault injection assessment of control paths in a system-on-chip (SoC), information leakage assessment, and reverse engineering at gate-level. Unfortunately, as of today, there are no good solutions available that can provide very fast and accurate extraction of FSMs from the flattened netlist to perform effective security assessment. The difficulty of developing such a solution lies in precisely identifying FSM state flip-flops present in a netlist that contains numerous circuit flip-flops. In this paper, we propose to develop a framework called FSMx to extract FSMs from highly unstructured synthesized designs. FSMx utilizes graph theory to identify FSM state registers from other registers. FSMx automatically extracts gate-level state transition graphs (STGs) for each of the detected FSM state registers. Experimental results demonstrate that FSMx efficiently recovers FSMs from synthesized netlists with various complexity and size in less than 7 minutes in the worst case of NIST AES 128-bit design with 12,976 gates on a personal desktop.