2022 · 11 citations · 18 references
EngineeringComputer EngineeringComputer ScienceComputer ArchitectureComputer SecuritySystem-on-chip DesignFinite State Machine ModelingLogic LockingLogic SynthesisFinite State Machine ExtractionFlip-flop DesignHardware Security Reverse EngineeringInformation Leakage DetectionLeakage AssessmentSecurity Vulnerability AnalysisSecurity Vulnerability AssessmentState Transition Graphs
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.
18
Depth-First Search and Linear Graph Algorithms
Robert E. Tarjan · SIAM Journal on Computing · 1972 · 6K citations
Finding All the Elementary Circuits of a Directed Graph
D. Barton Johnson · SIAM Journal on Computing · 1975 · 828 citations
Trustworthy Hardware: Identifying and Classifying Hardware Trojans
Ramesh Karri, Jeyavijayan Rajendran, Kurt Rosenfeld et al. · Computer · 2010 · 517 citations
Adib Nahiyan, Kan Xiao, Kun Yang et al. · 2016 · 105 citations · Full text