Paper 2022/1582

FSMx-Ultra: Finite State Machine Extraction from Gate-Level Netlist for Security Assessment

Rasheed Kibria, University of Florida
Farimah Farahmandi, University of Florida
Mark Tehranipoor, University of Florida

Numerous security vulnerability assessment techniques urge precise and fast finite state machines (FSMs) extraction from the design under evaluation. Sequential logic locking, watermark insertion, fault-injection assessment of a System-ona- Chip (SoC) control flow, information leakage assessment, and reverse engineering at gate-level abstraction, to name a few, require precise FSM extraction from the synthesized netlist of the design. Unfortunately, no reliable solutions are currently available for fast and precise extraction of FSMs from the highly unstructured gate-level netlist for effective security evaluation. The major challenge in developing such a solution is precise recognition of FSM state flip-flops in a netlist having a massive collection of flip-flops. In this paper, we propose FSMx-Ultra, a framework for extracting FSMs from extremely unstructured gate-level netlists. FSMx-Ultra utilizes state-of-the-art graph theory concepts and algorithms to distinguish FSM state registers from other registers and then constructs gate-level state transition graphs (STGs) for each identified FSM state register using automatic test pattern generation (ATPG) techniques. The results of our experiments on 14 open-source benchmark designs illustrate that FSMx-Ultra can recover all FSMs quickly and precisely from synthesized gate-level netlists of diverse complexity and size utilizing various state encoding schemes.

Available format(s)
-- withdrawn --
Publication info
FSM Automata TheoryFSM ExtractionNetlist AnalysisSecurity Assessment
Contact author(s)
rasheed kibria @ ufl edu
farimah @ ece ufl edu
tehranipoor @ ece ufl edu
2023-04-12: withdrawn
2022-11-14: received
See all versions
Short URL
Creative Commons Attribution
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.