Patent Publication Number: US-11651126-B2

Title: Recovery of a hierarchical functional representation of an integrated circuit

Description:
This application is a continuation of U.S. application Ser. No. 16/897,642 filed Jun. 10, 2020 and titled “BEHAVIORAL DESIGN RECOVERY FROM FLATTENED NETLIST”, now issued as U.S. Pat. No. 11,010,519, which claims the benefit of U.S. Provisional Application No. 62/859,466 filed Jun. 10, 2019 and titled “BEHAVIORAL DESIGN RECOVERY FROM FLATTENED NETLIST”. U.S. application Ser. No. 16/897,642 filed Jun. 10, 2020 is incorporated herein by reference in its entirety. U.S. Provisional Application No. 62/859,466 filed Jun. 10, 2019 is incorporated herein by reference in its entirety. 
    
    
     BACKGROUND 
     The following relates to the integrated circuit (IC) arts, IC replacement arts, IC hardware trust/assurance arts, IC verification arts, IC reverse engineering arts, applications of the foregoing to Application-Specific Integrated Circuit (ASIC) and/or Field Programmable Gate Array (FPGA) devices, and the like. 
     In a typical IC design workflow, the design specified at a system level is converted to a Register Transfer Level (RTL) representation expressed in Verilog (standardized as IEEE 1364), SystemVerilog (standardized as IEEE 1800), VHDL, or another hardware description language (HDL). The RTL representation is a hierarchical functional or behavioral representation of the IC logic. The RTL representation is then converted to a gate level representation expressed as a netlist, which is a list of the electronic components in the IC and the connection nodes. In generating the netlist, the hierarchical structure of the RTL is recursively flattened, resulting in a flat netlist that fully captures the content of the hierarchical and behavioral RTL representation. The physical layout of the electronic components and their interconnects as set forth in the netlist is then designed to enable fabrication of the IC. This conversion depends upon the type of IC: in the case of an ASIC, the electronic components are directly fabricated, whereas in an FPGA the electronic components are implemented by way of configuring an array of configurable logic blocks and programming the interconnects between the logic blocks. The logic blocks of the FPGA typically include look-up tables (LUTs), flip-flops (FFs), multiplexors, and other electronic components. An IC fabrication task can be outsourced by supplying either the RTL or the netlist. Providing the netlist is usually considered to be more secure, as it is difficult or impossible to reverse engineer the functional behavior of the IC given only the netlist representation. 
     However, there can be legitimate reasons to desire to recover the functional behavioral representation of an IC (that is, to recover the RTL representation). In one situation, an IC serving as a component of a system becomes obsolete or otherwise unavailable and needs to be re-fabricated. In another situation, an entity may need hardware assurance, that is, develop trust that an IC component performs as intended with no malicious behavior. In this situation, RTL recovery allows advanced verification and validation techniques to be applied to establish high confidence in the hardware prior to insertion into a critical system. 
     Certain improvements are disclosed herein. 
     BRIEF SUMMARY 
     In accordance with some illustrative embodiments disclosed herein, a non-transitory storage medium stores instructions which are readable and executable by an electronic processor to perform a Register Transfer Level (RTL) representation recovery method. The instructions include: instructions readable and executable by the electronic processor to convert a netlist representing an integrated circuit (IC) design to a graph comprising nodes belonging to a set of node types and edges connecting the nodes, wherein the set of node types includes an instance node type representing an electronic component and a wire node type representing signal transfer between components; instructions readable and executable by the electronic processor to convert the graph to a standardized graph by replacing subgraphs of the graph with standardized subgraphs; and instructions readable and executable by the electronic processor to generate an RTL representation of the standardized graph by operations including building signal declarations in a hardware description language (HDL) from the wire nodes of the standardized graph and building signal assignments in the HDL from instance nodes of the standardized graph. 
     In accordance with some illustrative embodiments disclosed herein, a device for recovering an RTL representation from a netlist representing an IC design is disclosed. This comprises of an electronic processor and a non-transitory storage medium storing instructions readable and executable by the electronic processor to perform an RTL representation recovery method. The instructions include: instructions readable and executable by the electronic processor to convert a netlist representing an IC design to a graph comprising nodes belonging to a set of node types and edges connecting the nodes, wherein the set of node types includes an instance node type representing an electronic component and a wire node type having a single input signal and one or more output signals with the value of each output signal being equal to the value of the single input signal; instructions readable and executable by the electronic processor to convert the graph to a standardized graph by replacing subgraphs of the graph with standardized subgraphs; and instructions readable and executable by the electronic processor to generate an RTL representation of the standardized graph. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
       Any quantitative dimensions shown in the drawing are to be understood as non-limiting illustrative examples. Unless otherwise indicated, the drawings are not to scale; if any aspect of the drawings is indicated as being to scale, the illustrated scale is to be understood as non-limiting illustrative example. 
         FIGS.  1  and  2    diagrammatically illustrate an apparatus and a process for recovering an RTL representation of an IC from a netlist representation. 
         FIGS.  3 - 13    diagrammatically illustrate embodiments and examples of various operations of the process of  FIGS.  1  and  2    as described herein. 
     
    
    
     DETAILED DESCRIPTION 
     With reference to  FIGS.  1  and  2   , an electronic processor  10  is programmed by instructions stored on a non-transitory storage medium  12  to perform a Register Transfer Level (RTL) representation recovery method. Said another way, the non-transitory storage medium  12  stores instructions which are readable and executable by the electronic processor  10  to perform the RTL representation recovery method. The illustrative electronic processor  10  comprises a desktop or notebook computer. More generally, the electronic processor  10  may be a desktop computer, server computer, cluster of server computers, cloud computing resource comprising an ad hoc network of computers, or so forth. The non-transitory storage medium may be: a hard disk drive (optionally internal to the computer  10 ) or other magnetic storage medium; a solid state drive (SSD), flash memory, or other electronic storage medium; an optical disk/drive or other optical storage medium; various combinations thereof, or the like. A display  14  is operatively connected with the electronic processor  10  to display results generated by the RTL representation recovery method. These results may, for example, include a listing of the RTL representation (or a selected portion thereof) in a Hardware Description Language, and/or test results comprising outputs generated by the RTL representation for chosen test inputs. One or more user input devices, such as an illustrative keyboard  16 , mouse  18 , touch-sensitive overlay of the display  14 , various combinations thereof, and/or so forth are provided via which a user interacts with the RTL representation recovery method, for example by operating a graphical user interface (GUI) via which a netlist  20  is provided as input to the RTL representation recovery method (whereby the RTL representation recovery method generates an RTL representation of the netlist) and/or via which the user selects a portion of the RTL representation to view on the display  14  or so forth. 
     The netlist  20  which serves as input to the RTL representation recovery method may be generated in various ways. In general, it is assumed that the original RTL from which the netlist was generated is unavailable (which is why the RTL representation recovery method is being applied). Rather, in the case of an FPGA the netlist  20  may be reverse engineered based on outputs generated by the FPGA in response to test inputs. See, e.g., Benz et al., “BIL: A Tool-Chain for Bitstream Reverse-Engineering”, 22nd International Conference on Field Programmable Logic and Applications (FPL) (Aug. 29-31, 2012); Ding et al., “Deriving an NCD file from an FPGA bitstream: Methodology, architecture and evaluation”, Microprocessors and Microsystems vol. 37, pp. 299-312 (2013); Jean-Baptist Note &amp; Eric Rannaud, “From the bitstream to the netlist”, in Proc. of the 16th International ACM/SIGDA Symposium on Field Programmable Gate Arrays”, Monterey, Calif., Feb. 24-26, 2008. In the case of an ASIC, the netlist  20  may be generated by scanning electron microscope (SEM) imaging and/or other forensic analysis of the ASIC, optionally along with analysis of outputs generated by the ASIC in response to test inputs. The netlist  20  is typically a flat netlist without a hierarchy. 
     With brief reference to  FIG.  3   , an illustrative netlist  20   1  for a 2-bit counter is shown, along with a corresponding RTL representation  22 . As seen in  FIG.  3   , the netlist is a text file that lists electronic components and their connections. It is a flat list, with no hierarchy, and provides no information about component functionality. It only contains the connectivity of the most primitive and fundamental circuit blocks (e.g. NAND, NOR, INV, DFF, etc. gates) The RTL representation is also a text file, in a HDL, specifically employing the IEEE 1164 VHDL standard in the illustrative RTL  22 . The RTL representation is a high level hierarchical functional description. 
     With reference back to  FIG.  1   , the RTL representation recovery method starts with text parsing and pruning operations  30  to pre-process the netlist  20 . This may entail, for example, removing comments, headers, and other extraneous information in the netlist  20 . The preprocessing resolves any portions that would not be recognized as syntactically valid Verilog (or other employed HDL). Some manual preprocessing of the netlist is contemplated. 
     With continuing reference to  FIG.  1    and further reference to  FIGS.  4  and  5   , the preprocessed netlist is then converted into a multi-typed graph. To achieve this, in an operation  34  the preprocessed netlist is converted to an Abstract Syntax Tree (AST)  36 .  FIG.  4    presents an illustrative example of a preprocessed netlist  20   2  and corresponding AST  36   2 . In this illustrative example, the root of the AST is the “Netlist” node, from which the “Timescale” and “Module” nodes branch, with the components and their connections being represented by nodes branching off the “Module” node. The AST  36  is then converted in an operation  38  to a multi-typed graph  40 .  FIG.  5    shows an illustrative typing ontology for the multi-typed graph  40 , which includes a set of node types including: an instance node type representing an electronic component; a wire node type representing signal transfer between components; an input node type representing an input terminal of the netlist; an output node type representing an output terminal of the netlist; and a constant node type representing a constant signal source (e.g., V cc  or ground, or alternatively logical “1” or logical “0”, or another suitable representation of the constant values of a binary system). 
     The instance node type represents a component that performs an operation on one or more input signals and drives an output signal. Typically, an instance node has one or more input signals and a single output signal (although two or more outputs from a node of the instance node type is also contemplated). For example, an AND gate may be represented by an instance node with two (or more) input signals and a single output signal whose value is the logical AND of the two (or more) input signals. As another example, an instance node representing a buffer has a single input signal and a single output signal whose value is equal to that of the input signal. An instance node representing a LUT has one or more input signals and an output signal corresponding to the output of the LUT for the input signal(s). An instance node representing a flip-flop (FF) has one or more inputs and an output whose value depends on the inputs and on an internal state of the FF. 
     The wire node type has a single input signal and one or more output signals, with the value of each output signal being equal to the value of the single input signal. The wire node thus efficiently captures the possibility of a signal being fed into multiple other components by way of a single node of the wire node type. In this way, the wire nodes can later be directly converted to signal declarations in the RTL, followed by signal assignments obtained from the wire node connections to instance nodes. 
     With continuing reference to  FIG.  1    and with further reference to  FIGS.  6  and  7   , in the operation  38 , the graph  40  is generated from the AST  36  by stepping through the tree representation and generating lists of node names of the various node types as the AST  36  is traversed. For components and signals designated by standard nomenclature, the directionality of edges connecting nodes of the graph  40  are assigned. However, some nodes or signals may employ manufacture-specific nomenclature such that directionality cannot be determined from the AST  36  alone—these ambiguities will be resolved in the next stage. The AST  36  is a data structure that provides a list of the netlist&#39;s components and connections between them in a way that is easily traversable. The graph  40  is created by instantiating each component listed in the AST  36  as a node in the graph and creating connections between these nodes based on connection information from the AST. By way of non-limiting illustrative example,  FIG.  6    illustrates a graph for a simple two-input logic gate (e.g., a 2-input AND gate, 2-input OR gate, or so forth). In general, each pair of nodes from the group consisting of instance nodes, terminal nodes, and constant nodes are interconnected by way of an intervening wire node. This, again, facilitates conversion of the wire nodes to RTL signal declarations later in the RTL recovery process.  FIG.  7    shows a diagrammatic representation of a graph for a 32-bit single precision Floating Point Unit (FPU) from RISC Processor (5 stage pipeline). The graph of  FIG.  7    shows the nodes as points without distinguishing the node type, but illustrates the high degree of complexity of the graph representation of the netlist for a more complex IC design and shows that there is inherent hierarchy that can be observed in the flattened netlist when observed in this way. 
     With continuing reference to  FIG.  1    and with further reference to  FIG.  8   , the operation  38  preferably further includes graph pruning to remove unused or redundant nodes, such as unconnected devices, buffers, LUTs acting as buffers, double inverters, doubly-connected wires, or so forth. Processing time and graph readability can be improved by such pruning.  FIG.  8    illustrates two examples of pruning operations: removal of a redundant wire (left-hand diagram), and removal of a redundant buffer (right-hand diagram). 
     The resulting graph  40  advantageously captures the components and connections of the netlist  20  in a format that is more readily converted to RTL as described herein. For components and signals designated by standard nomenclature, the directionality of edges connecting nodes of the graph  40  are assigned in the operation  38 . However, some nodes or signals may employ manufacture-specific nomenclature (that is, the node and signal nomenclature may be specific to the IC manufacturer). In such cases, directionality cannot be determined at operation  38 . Similarly, different manufacturers and device families use different primitives. Functionality of primitives by different manufacturers may be identical, but port information and primitive names typically vary. 
     Thus, with continuing reference to  FIG.  1    and with further reference to  FIG.  9   , in an operation  42 , node standardization is performed. This entails replacing nodes of the graph  40  with standardized nodes using an IC nomenclature database  44 .  FIG.  9    shows an example of this operation  42 . In general, the nodes may employ manufacturer-specific naming conventions, for which port (and hence graph edge) directionality is unknown, and functionality of the instance nodes is unspecified. This is diagrammatically shown by two examples of nodes with manufacturer-specific nomenclature (top two diagrams of  FIG.  9    with node names “GFG LUT3-L” and “X_LUT3” respectively, and manufacturer-specific signal names as shown in the top diagrams of  FIG.  9   ). The IC nomenclature database  44  provides this manufacturer-specific nomenclature so as to resolve these manufacturer-specific node and signal names to standardized names (e.g., the top diagram nodes of  FIG.  9    are resolved to the standardized node named “LUT_3”, with standardized signal names as shown in the bottom diagram of  FIG.  9   . Additionally, the resolution of the node “LUT_3” (or more generally, replacement of a manufacture-specific node with an equivalent standardized node) allows the directionality of the node ports to be resolved. Hence, the output of operation  42  is a fully directed graph. 
     With continuing reference to  FIG.  1    and with further reference to  FIG.  10   , in an operation  46 , LUTs and primitives are decomposed. In general, higher-level components such as LUTs and higher level primitives compress structural information and make pattern recognition and structural identification more difficult. In the case of primitives, the IC nomenclature and primitives database  44  may be referenced to identify manufacturer-specific primitives and their decomposed equivalents consisting of logic gates and FFs (and possibly also LUTs). To decompose a LUT, a process as shown in  FIG.  10    is suitably employed. The LUT initialization vectors (which define the LUT output for any combination of inputs) is represented as a truth table having columns corresponding to the inputs and a final column corresponding to the LUT output. The truth table is expanded into an equivalent simplified Boolean expression that is minimized by standard minimization techniques such as identifying and merging groups of inputs with a common output value. The simplified Boolean expression is then represented as a subgraph with instance nodes representing the logic gates of the Boolean expression. A subgraph that includes a LUT node is thereby replaced with a standardized subgraph that does not include a LUT node. It should be noted that the illustrative LUT decomposition of  FIG.  10    is for an FPGA. In the case of an ASIC, LUT decomposition is typically not performed; whereas, for an FPGA the LUT decomposition facilitates obtaining a useful graph from the netlist. More generally, higher-order functionality can typically be recovered more quickly from an FPGA netlist (as compared with an ASIC) when onboard hardware of the FPGA cells (such as adders or multipliers) is used instead of synthesizing this functionality into logic cells. 
     The output of the operation  46  is a standardized graph  50 , which is a fully directed graph and which employs standardized nomenclature, and which has LUTs and higher level primitives decomposed into subgraphs consisting of logic gate instance nodes and (usually) FF instance nodes. The standardized graph  50  consists of basic logic nodes (e.g. AND, OR, NOT) and FF nodes, in addition to input and output terminal nodes and constant signal source nodes (see  FIG.  5   ). 
     With reference to  FIG.  2   , the standardized graph  50  is used to recover the RTL representation of the netlist  20 . The structure of the standardized graph  50  lends itself well to creating an RTL representation in VHDL code or another HDL such as Verilog or SystemVerilog, as each wire node is analogous to a VHDL ‘signal’ (or, equivalently, a Verilog or SystemVerilog ‘signal’), as it has one driver and unlimited outputs (that is, a single input signal and one or more output signals, wherein the value of each output signal is equal to the value of the single input signal). Hence, an operation  60  builds VHDL signal declarations from the wire nodes of the standardized graph  50 . That is, signals are declared for each wire node. An operation  62  builds signal assignments from instance nodes. Signal states are assigned to logical operations on other signals and design inputs. 
     However, some standard cells and FPGA primitives do not have simple gate-level equivalents. Some examples include: multiplication stages, RAM, ROM, or so forth. The use of these primitives is useful for determining hierarchy, but is not advantageous for simulation. Additionally, many slight variations of simple components like flop-flops exist, e.g. active high vs active low, bus width, inclusion of set/reset ports, a/synchronous set/reset, and so forth. 
     To address these situations, an operation  64  defines synchronous devices from templates. In an illustrative embodiment, rather than code simulation primitives for every case, a modular template system is employed, which makes use of a template VHDL library  66  of VHDL ‘Generics’ and enables or disables functionality as appropriate for a given standard cell or FPGA primitive. The information from the template VHDL library  66  is stored in nodes during classification. A component-to-template map  68  provides manufacturer- or device family-specific information as to the modifications to the VHDL template standard cell or FPGA primitive appropriate for the specific IC whose RTL representation is being recovered. An operation  70  instantiates and connects the synchronous logic. Each node corresponding to a standard cell or FPGA primitive in the standardized graph  50  is represented in the VHDL code by an instance of the synchronous device primitive defined in the operation  64 , with connections to the surrounding circuitry of that node in the standardized graph  50 . This introduces some hierarchy into the RTL representation. An operation  72  then introduces (further) hierarchy to the RTL for repeated structures. An operation  74  writes the RTL to a VHDL file  76 , thus completing the RTL recovery process. It should be noted that while VHDL is employed in  FIG.  2    as an illustrative Hardware Description Language (HDL), the RTL may be coded in accord with another HDL such as Verilog or SystemVerilog by employing the appropriate Declarations notation for the chosen HDL in coding operations  60 ,  62  and a template library and mapping for the chosen HDL in place of the illustrative template VHDL library  66  and mapping  68 , respectively. 
     With continuing reference to  FIG.  2    and with further reference to  FIGS.  11 - 13   , the operation  72  introducing (further) hierarchy to the RTL for repeated structures can be implemented in various ways. The structure of the standardized graph  50  lends itself well to structural identification of components. Identified repeated structures can be replaced by a single higher-level structural declaration in the HDL, and then instances of the structure can be replaced by instantiations of the declared higher level structure.  FIG.  11    illustrates an example of this approach, in which a graph of an 8-bit counter is identified (i.e. matched) as a sub-graph of a graph of a Central Processing Unit (CPU) integrated circuit. It is particularly noteworthy here that the 8-bit counter graph includes an outer loop of flip-flop dependencies (shown in darker lines in the graph for the 8-bit counter. This graph topological feature can be leveraged in identifying the 8-bit counter sub-graph in the CPU graph (sub-graph depicted in lighter lines in the lower right diagram of  FIG.  11   ). 
     With continuing reference to  FIG.  2    and with further reference to  FIG.  12   , another way to leverage the standardized graph  50  for identifying hierarchical structures in the operation  72  is by way of simulation. Combinational logic processing can be simulated by assigning signal values to selected wire nodes and simulating the result. In this way, components such as adders can be identified by simulating combinational logic chunks between flip-flops. More generally, frequent patterns identified from graph mining can be simulated and compared to a list of known components. Again, identifying flip-flop interdependencies can be useful in identifying repeated patterns.  FIG.  12    illustrates a flowchart of a method  80  for identifying flip-flop dependencies, which can be used to create a reduced graph  82  of flip-flop interdependencies for the pattern mining. The reduced graph  82  produced by the method  80  contains each flip-flop in the netlist represented as a vertex. The logical path from each flip-flop to the others (if one exists) is represented as an edge. The reduced graph  82  of flip-flop dependencies is useful for reducing the computation required to identify patterns such as state machines. For example, as previously noted the 8-bit counter of  FIG.  11    can be identified by searching for the circular dependencies of the eight flip-flops of the counter. The method  80  of  FIG.  12    would advantageously provide a reduced graph  82  isolating these flip-flop interdependencies. More generally, state machines contain a set of flip-flops with outputs that feedback through combinatorial logic to the flip-flop inputs. The combinatorial logic in the feedback path along with the state machine inputs make up the next state expression. The reduced flip-flop graph  82  can be used with graph searching techniques to quickly identify the sets of flip-flops that meet these criteria. 
     With continuing reference to  FIGS.  2  and  12    and with further references to  FIG.  13   , using the reduced flip-flop graph output by the method of  FIG.  12   , a strongly connected components search can be performed that, in the directed graph (i.e. edges between vertices of the reduced graph of flip-flop dependencies have directionality), will identify all sets of flip-flops that collectively feedback to each other. These flip-flops, in many cases, combine to make up memory that stores the state variables of a state machine.  FIG.  13    illustrates a flow diagram of a method for state machine extraction from an ASIC netlist  20  according to this approach. (Note, in  FIG.  13    flip-flops are referred to as “registers”). In  FIG.  13   , the processing described with reference to  FIG.  1    for producing the standardized graph  50  shown in the left branch of  FIG.  13    is represented in  FIG.  13    by blocks  90 ,  92 , while the process  80  for producing the reduced graph  82  of flip-flop (i.e. register) dependencies is shown in the right branch of  FIG.  13   . Operation  94  is the “strongly connected components” search. A loop  96  selects strongly connected components with between 1 and 100 component vertices in the reduced flip-flop graph  82  as possible state machines. (This range of 1-100 is merely illustrative, and may be tuned to maximize performance for a particular family of ICs undergoing RTL recovery). For each possible state machine (i.e. each sub-graph of the reduced graph  82 ), a process  98  retrieves the corresponding sub-graph of the standardized graph  50  (this sub-graph will include the interconnecting combinational logic of the possible state machine), generates the state transition tables for the sub-graph of the standardized graph  50 , and produces behavioral-level HDL code representing the state transition tables. 
     The illustrative RTL recovery methods can be incorporated into various types of IC analysis tools. For example, with reference back to  FIGS.  1  and  2   , a graphical user interface (GUI) may be provided via which the netlist  20  is provided as input to the RTL representation recovery method, for example by selecting a text file containing the netlist using the mouse  18  to navigate a file manager to select the netlist file. The RTL representation recovery method then generates the RTL representation  76  of the netlist, and the user selects a portion of the RTL representation  76  to view on the display  14 . If IC performance simulation software is also provided, the user may perform simulations on the netlist  20  and the RTL representation  76  to verify that they exhibit the same functionality. An extracted netlist from an IC could range from tens of thousands of lines long for a simple design up to several million lines for a reasonably complex design. As such, navigating through the flat netlist to identify areas of assurance concern is not practical for a human to perform. Understanding the functionality or locating portions of the design is also not realistic or feasible. By representing the netlist with as recovered RTL with hierarchy and in a more condensed and readable format, a user can more readily identify and understand the regions of interest to determine if the design was modified to alter design functionality. In another application, engineers who are addressing legacy part problems may need to extract the design in order to remanufacture it into a modern technology node. For example, a design that was fabricated in a 500 nanometer technology node, an obsolete technology not readily available today, could be fabricated in a 90 or 45 nanometer technology. In order to perform this, an RTL representation of the design is obtained using the disclosed RTL recovery in order for the designer to resynthesize into the modern node size. A netlist typically cannot be remanufactured; hence the extracted legacy netlist is generally not sufficient to remanufacture the IC. By contrast, the disclosed RTL recovery allows the legacy netlist to be converted into a format that permits resynthesizing into the modern node, thus saving large amounts of resources on a complete redesign of the component. 
     The preferred embodiments have been illustrated and described. Obviously, modifications and alterations will occur to others upon reading and understanding the preceding detailed description. It is intended that the invention be construed as including all such modifications and alterations insofar as they come within the scope of the appended claims or the equivalents thereof.