Abstract:
According to embodiments of the present invention are systems and methods for using scan chains for the creation of unique physically uncloneable function (PUF). In particular, the present invention uses existing circuitry on an integrated circuit and the internal-scan or boundary-scan register to create a unique identifier for each integrated chip. The unique nature of the scan chains results from the inherent variability of the manufacturing process.

Description:
CROSS-REFERENCE TO RELATED APPLICATIONS 
       [0001]    This application claims the benefit under 35 U.S.C. § 119 of Provisional Ser. No. 62/070,988, filed Sep. 10, 2014, which is incorporated herein by reference. 
     
    
     STATEMENT REGARDING FEDERALLY SPONSORED RESEARCH 
       [0002]    Not applicable. 
       BACKGROUND OF THE INVENTION 
       [0003]    The invention relates generally to physically unclonable functions (PUF). More specifically, the invention relates to a system and method that utilizes a subset of the scan chain power-up states of an integrated circuit (IC) as a type of PUF to authenticate the IC, among other uses. 
         [0004]    PUFs are structures with many applications, including device authentication, identification, and cryptographic key generation. In the context of a silicon-based circuit, a PUF is a die-specific random function that is based on an underlying manufacturing variability, such as random dopant fluctuations or line edge roughness. Because the variability is beyond the resolution of modern manufacturing techniques, creating an exact physical copy of a PUF is practically infeasible. 
         [0005]    Generally, device authentication involves using the unique properties that every IC exhibits as a result of the imperfections in the fabrication process. Specifically, although every chip is designed to be exactly the same, the inability to fabricate identical chips is exploited to create a unique key for each chip. This key is typically referred to as a physically uncloneable function, or PUF, since it is based on physical properties that are unique to each IC and it cannot be predicted since it depends on the variations of the manufacturing process. 
         [0006]    To use this manufacturing variability as part of a PUF, the variability is translated into a random bit. In turn, a string of these random bits is typically combined with a challenge (input) in the PUF to create a returned response (output). Because the string of random bits will be unique to each IC, the response will be unique as well and can be used to identify the IC. In other words, when a stimulus is applied to an individual circuit, it responds in an unpredictable, but unique and repeatable way. 
         [0007]    With many ICs being fabricated overseas, it is imperative that techniques be developed to ensure the authenticity of each IC. Not only is it possible to receive an inferior, counterfeit product, it is also possible that malicious circuits have been added to the IC for various nefarious purposes that range from IC destruction to communication eavesdropping. This concern is especially critical for applications involving the nation&#39;s security. 
         [0008]    There are many types of PUFs used to authenticate ICs. For example, various types of PUFs include ring oscillators, arbiters, SRAM, sense amplifiers, and D-type flip flops. Of the various types of PUFs, some require specialized circuits while others can leverage existing circuitry within the design. The latter approach is typically referred to as an intrinsic PUF. An example of an intrinsic PUF is one that uses the power-on state of an existing SRAM circuit. 
         [0009]    Another example of an intrinsic PUF is one that uses an arbiter to exploit the race condition created by two symmetrical circuit paths. Under ideal circumstances, the circuit paths will produce identical delays. However, due to manufacturing imperfections, the delays will be slightly different. The arbiter determines which path is faster and uses the result to create a binary result (logic 0 or 1), which of course will randomly vary from chip to chip. Having multiple copies of the same circuitry setup within the IC allows the creation of a string of binary bits that, due to the randomness, is unique for each chip. 
         [0010]    Intrinsic PUFs are obviously more desirable since the cost of implementing the PUF is mitigated by the use of existing circuitry. But all the approaches developed thus far incur some overhead in that they require (i) additional circuitry for accessing the PUF and/or (ii) modifications to the existing circuitry which undoubtedly has performance and power penalties. Therefore a need exists for an approach that does not exhibit any of these shortcomings. 
       BRIEF SUMMARY OF THE INVENTION 
       [0011]    According to embodiments of the present disclosure are systems and methods for using scan chains to create physically uncloneable functions (PUF). In particular, the present invention uses, without any alteration, existing circuitry on the chip and the boundary and internal scan circuitry to create a unique identifier for each integrated chip. The unique identifier is based on the power-up state of the scan elements. While a portion of the scan elements are unreliable and do not consistently power-up to the same state, a selection method is used to determine a subset of stable scan elements, which can be used as a PUF. Because scan is ubiquitous for every IC and typically consists of hundreds of thousands to millions of flip-flops, there is a virtual unlimited supply of bits for directly creating an easily-accessible PUF without any performance or area overhead. 
     
    
     
       BRIEF DESCRIPTION OF THE SEVERAL VIEWS OF THE DRAWINGS 
         [0012]      FIG. 1  is a flowchart of the method according to one embodiment of the present invention. 
           [0013]      FIG. 2  is a flowchart depicting a subroutine of the method according to an alternative embodiment. 
           [0014]      FIG. 3  as an example of a power-on state of a 20-bit scan chain, with the stable subset denoted by asterisks. 
           [0015]      FIG. 4  shows a series of mappings of scan chain power-up states for three different chips at different temperatures. 
           [0016]      FIG. 5  shows a schematic of a reconfiguration of a general synchronous circuit so that virtually all flip-flops are accessible via a scan chain shift register. 
           [0017]      FIG. 6  shows a state diagram of the boundary scan controller. 
           [0018]      FIGS. 7A-7B  show a schematic of a printed circuit board without boundary scan ( FIG. 7A ) and modified to include boundary scan ( FIG. 7B ) according to an embodiment of the present invention. 
           [0019]      FIG. 8  is a graph showing the average error rate for a single observation using a unanimous selection scheme, according to one embodiment. 
           [0020]      FIG. 9  is a graph showing the number of unanimous elements remaining after a series of enrollment observations. 
       
    
    
     DETAILED DESCRIPTION OF THE INVENTION 
       [0021]    Embodiments of the present invention and its advantages are best understood by referring to the figures.  FIG. 1  is a flowchart of the method of creating a PUF from a scan chain according to a preferred embodiment. At step  100 , the IC or board is powered-up to initiate the scan chain. Scan is a design-for-testability technique that adds another mode of operation to an IC for improving testability and debugging. In its simplest form, scan design adds a single control input (typically called the scan enable) to reconfigure virtually all the flip-flops into one or more shift registers called scan chains. The input and output of each chain are dynamically routed to the I/O of the chip during testing. 
         [0022]    After the scan is enabled, at step  200  the power-up state of the scan chain is observed. From this observation or multiple observations, a subset of the scan chain is identified at step  300 . The subset comprises a grouping of stable scan elements that consistently power-up to the same state. The identification method is generally shown in  FIG. 2 , and comprises performing several power-up cycles (step  301 ), observing the power-up state after each cycle (step  302 ), and determining which scan elements are stable (step  303 ). 
         [0023]      FIG. 3  shows a 20-bit string scan chain as an example of the power-up state observed at step  200 . The subset of the scan chain identified at step  300  is marked with asterisks. Only the marked scan elements, or subset, would be used in the PUF. By way of further example,  FIG. 4  is a mapping of scan chain data observed at step  200 . In this particular example, chips having a scan chain comprised of 6,057 D-type flip-flops were observed. Each row represents one of the three chips. The first three columns represent power-up initiation at different temperatures: −20° C., 27° C., and 85° C., respectively. The final column shows an aggregation of the first three columns. As shown in the mapping, each of the 6,057 scan elements is shown in a first state (black) or a second state (white) in the mapping comprising 61×100 pixels. The mappings shown in  FIG. 4  indicate the uniqueness of the scan chains, since no pattern is readily detectable among the different chips. 
         [0024]    If a manufacturer is using this method as a way to provide authentication to a customer at a later date, the stable subset can be determined during the manufacturing tests. It can be expected that the additional costs to the manufacturer would be less than 1% of the typically testing costs. In this example, the manufacturer would keep a database where each chip is referenced to the stable subset for that particular chip. When a customer wants to authenticate a chip, it will send a scan chain readout to the manufacturer, such as via the internet or some other means. Using  FIG. 3  as an example, the customer would send the entire 20-bit string to the manufacturer along with the chip serial number. Using its database, the manufacturer would determine that a chip with that serial number should have a stable subset that is 11 bits long and comprised of bits  1 ,  2 ,  5 ,  6 ,  7 ,  8 ,  12 ,  15 ,  16 ,  18 , and  20 . Also, the manufacturer would know the states for each of these bits. 
         [0025]    By comparing the readout provided by the customer to its database, the manufacturer could confirm the chip as authentic. It is not necessary to reveal to the customer which scan locations have been chosen to make up the PUF. At the board and system level, the customer would access the power-on state specified by each board or system manufacturer for all chips. This state along with the part number would again be provided to the manufacturer for verification. 
         [0026]    After observing the power-up state, several methods can be used to determine what constitutes a stable scan element, depending on the level of consistency and accuracy required for a given use. For example, chip identification may only require a &gt;90% accuracy rate, whereas a cryptographic use may require near 100% accuracy. Methods of finding a stable scan element can include selecting scan elements that revert to a particular state after a majority of power-up cycles (majority selection method) or only selecting the scan elements that always revert to a particular state (unanimous selection method). 
         [0027]    In the unanimous selection method, the power-up cycle is repeated several times and elements that exhibit a different state from a previous cycle are removed from consideration for the stable subset. In other words, only elements that consistently evaluate to the same state after a certain number of observations can be considered stable elements. As the number of observations is increased, accuracy increases. For example, the probability that a flip-flop will be observed in a first state is much higher if that flip-flop was observed in that state consistently for 500 power-up cycles as opposed to only 5 power-up cycles. 
         [0028]    This concept is shown in  FIG. 8 , which shows the average error rate as a function of the number of enrollment observations for three separate chips. The error rate is defined as the percentage of elements in the scan chain that did not match the expected state in a given observation. As shown in  FIG. 8 , the error rate for all three chips falls below 0.1% after 300 enrollment observations. A user, such as a manufacturer authenticating chips, will be able to determine the number of observations based on an acceptable error rate for their use. 
         [0029]    When using the unanimous selection method, the number of observations conducted must be balanced against the need to have a minimum number of elements in the stable subset. Certainly, an infinite number of observations could produce an error rate of zero, but no scan elements would remain for consideration since the number of elements considered for the stable subset decreases after each power-up cycle, or enrollment observation.  FIG. 9  shows the number of elements remaining after each observation for the three different chips observed in  FIG. 8 . As shown in  FIG. 9 , even after 750 observations, there are 944 out of 6,057 elements remaining. This subset is sufficiently large to enable use as a PUF. Thus, a user will have the ability to select the stable subset from a wide range of possibilities based on the error rate and subset size. 
         [0030]    Given the manufacturing variability inherent in each IC, the stable subset will be unique to each IC. Moreover, the scan elements that form part of the stable subset cannot be predicted—that is, they are random. However, the randomness of the PUF can be further increased by selecting only a fraction of the stable subset determined by the unanimous selection method. For example, a random selection of 100 of the 944 stable elements discussed in  FIG. 9  can be used as a unique identifier for the IC. The selection process can vary. For example, in a second IC, 133 elements could be chosen. Moreover, the location of the elements could change from IC to IC. 
         [0031]    Unlike existing PUF designs, the method and system of the present invention re-use the scan chain for PUF purposes while preserving their original testing functionality.  FIG. 5  shows how a general synchronous sequential circuit is reconfigured so that virtually all flip-flops are accessible via a scan chain shift register, with normal operation shown on the right and scan mode shown on the left. When the scan enable signal is active (not shown in  FIG. 5 ), it allows the flip-flop state of all the scan chains to be (i) completely controllable by shifting in any string of binary values through the scan-chain input(s), and (ii) completely observable by simultaneously shifting out the held state through the scan-chain output(s). Having comprehensive access to the flip-flop state makes IC testing and debug much more tractable. 
         [0032]    In alternative embodiments, the scan chains of individual chips of a printed circuit board (PCB) are used in a board-wide PUF. Since the major components of a PCB (printed circuit board) consist of ICs with scan, a hierarchical SCAN-PUF can be easily formed using the boundary-scan register that always exists at the board level. Specifically, a board-level SCAN-PUF is simply the combination of its individual IC SCAN-PUFs that are all easily accessible through the board-level boundary scan, or implemented via the boundary scan itself. Finally, since full systems consist of multiple PCBS, then system-level authentication is achieved by accessing and combining the individual board-level SCAN-PUFs, thus creating a freely-accessible, system-level PUF.  FIG. 7A  shows a PCB without a boundary scan, whereas  FIG. 7B  shows a PCB with a boundary scan. 
         [0033]    In one alternative embodiment, the board level SCAN-PUF is created through the adherence to the IEEE standard 1149.1. Specifically, because the 1149.1 standard allows access to each IC&#39;s boundary and internal scan registers, it will also allow seamless access to each IC&#39;s individual PUF. The PUFs can then be combined (e.g., concatenated) to form a board-level PUF. Moreover, since a system can be viewed as collection of PCBs, the board-level PUFs can be also combined to form a system-level PUF. With a board-level PUF, the process confirms that the board is authentic and that no chips have been replaced during transport from the manufacturer to the customer. 
         [0034]    Internal or boundary scan can be used. The form of scan depicted in  FIG. 5  is referred to as internal scan since it involves the flip-flops used during the normal operation of the IC. Boundary scan has been developed to ease printed circuit board (PCB) testing. In boundary scan, a shift register called the ‘boundary scan chain’ is connected to the signal inputs and outputs of the IC. Daisy chaining the boundary scan registers of each IC on the PCB provides complete (serial) controllability/observability of all chip inputs and outputs for test and debug. Because of its ubiquity, boundary scan was further developed by the Joint Test Action Group (JTAG) and adopted as a standard by the Institute of Electrical and Electronics Engineers (IEEE). Virtually all chip makers have adopted this standard, thus ensuring that PCBs consisting of ICs that contain compliant implementations of the boundary scan standard (IEEE 1149.1) are fully accessible during test. 
         [0035]      FIG. 6  shows a board containing several chips altered to include boundary scan. Reading the boundary scan register via the ‘Shift DR’ requires the transitioning through the ‘Capture DR’ state. A capture operation updates the power-on state with a likely unpredictable, non-deterministic state. In this embodiment, to prevent a non-deterministic state, a new private instruction is added that disables the capture data register operation. 
         [0036]    The boundary-scan standard also specifies a specific 16-state finite-state machine for controlling the boundary scan chain along with some specific architectural features for implementing several mandatory operations, one of which includes shifting-in/shifting-out bit values into/from the boundary-scan register. Another optional, but typically-implemented, operation involves providing access to the internal scan chains under the control of the boundary- scan controller. Thus, at the board level, both the internal and boundary scan chains of each chip are serially accessible. 
         [0037]    As previously described, after power-up, flip-flops will initialize themselves to some particular state based on the individual transistor characteristics imposed by the variations in the manufacturing process, where the state is unpredictable but stable. Since the impact of the variations will differ for each IC, it is expected that each IC will have its own unique state. 
         [0038]    For a manufacturer determine the stable subset, the IC can be powered up and before any operation is conducted, the uncorrupted power-up state is shifted out of all the scan chains (both internal and boundary). The power-on, shift cycle is repeated several times to determine which flip-flops consistently power-up in the same 1-bit state, where the number of cycles is chosen to ensure a sufficient level of confidence in the power-on state for some subset of the scan-chain flip-flops. During manufacturing testing, the scan chains are shifted thousands of times, so it is anticipated that the extra cost for characterizing a given chip&#39;s SCAN-PUF will be minimal. 
         [0039]    While the disclosure has been described in detail and with reference to specific embodiments thereof, it will be apparent to one skilled in the art that various changes and modification can be made therein without departing from the spirit and scope of the embodiments. Thus, it is intended that the present disclosure cover the modifications and variations of this disclosure provided they come within the scope of the appended claims and their equivalents.