Apparatus, method and article of manufacture for partially resisting hardware trojan induced data leakage in sequential logics

Abstract

Apparatus, method and article of manufacture providing a randomized encoding scheme for sequential logics, for resistance to data leakage. Invention employs dual-rail encoding to randomize the information in the chip, and employs three-dimensional integration technology to protect the critical information that is needed to decode the data anywhere on-chip. With the present invention, even when the entire design is completely known to the attacker who also has full access to the outsourced portion, it is still not always possible to identify the information in the chip using data leakage Trojans.

Claims

1. A sequential logic circuit security apparatus, comprising: at least two combinational logic circuit functions each having an output and at least one pair of logic inputs; at least two random logic state generators each randomly outputting a logic state 1 or 0; a first encoder for encoding each logic input of said at least one pair of logic inputs with a Boolean operation on a preselected one of said at least two random logic state generators; a multiplexer having an output, and at least two selectable inputs each being connected to a respective said output of said at least two combinational logic circuit functions, wherein said multiplexer selects one of said outputs of said at least two combinational logic circuit functions according to said logic state of said at least two random logic state generators; a latch having an input connected to said output of said multiplexer, an output, and a clock input; an exclusive OR circuit having an output, a first input connected to said latch output, and a second input, wherein said second input is encoded by a second encoder performing said Boolean operation on a current clock cycle state and a prior clock cycle state of said preselected one of said at least two random logic state generators.

2. The apparatus of claim 1, wherein said Boolean operation is an exclusive OR operation.

3. The apparatus of claim 2, wherein said second input is encoded by a second encoder performing said Boolean operation on: a current clock cycle state of a non-preselected one of said at least two random logic state generators; and a prior clock cycle state of said preselected one of said at least two random logic state generators.

4. The method of claim 2, wherein said Boolean operation is an exclusive OR operation.

5. The method of claim 4, wherein said second input is encoded by a step of performing said Boolean operation on: a current clock cycle state of a non-preselected one of said at least two random logic states; and a prior clock cycle state of said preselected one of said at least two random logic states.

6. In a sequential logic circuit having at least two combinational logic circuit functions each having an output and at least one pair of logic inputs, a security method for use therewith, comprising the steps of: generating at least two random logic states each randomly comprising a logic state 1 or 0; encoding each logic input of said at least one pair of logic inputs with a Boolean operation on a preselected one of said at least two random logic states; selectively multiplexing said output of said at least two combinational logic circuit functions according to a logic state of said at least two random logic states; latching said multiplexed output of said at least two combinational logic circuit functions; exclusively OR'ing a first input comprising said multiplexed output of said at least two combinational logic circuit functions, with an encoded second input, wherein said second input is encoded by a step of performing said Boolean operation on a current clock cycle state and a prior clock cycle state of said preselected one of said at least two random logic states.

7. A secure logic chip as an article of manufacture comprising a logic portion and a security portion, wherein said logic portion comprises a plurality of combinational logic circuits each having inputs and an output; said security portion comprises: a random logic state generator producing two randomly generated logic states; a multiplexer, having as inputs said outputs of said combinational logic circuits; and having a selection among said inputs based upon the logic state of said two randomly generated logic states; a latch for latching an output of said multiplexer; and an exclusive OR for decoding an output of said latch as a function of at least one of said two randomly generated logic states; and wherein said logic portion and said security portion are manufactured as separate chips and thereafter functionally integrated into said secure logic chip; and wherein said logic portion and said secure portion are functionally integrated by: arrangement as a physical stack; and through-silicon-vias to establish electrical connections between said logic portion and said secure portion.

8. A semiconductor chip as an article of manufacture for securely encoding logic circuits, comprising: an array of security encoding cells fabricated onto said semiconductor chip, wherein each said cell further comprises: a multiplexer, having as inputs those outputs of said logic circuits to be securely encoded; and having a selection among said inputs based upon the logic state of one or more randomly generated logic states; a latch for latching an output of said multiplexer; and an exclusive OR for decoding an output of said latch as a function of said one or more randomly generated logic states; a crossbar structure for electrically interconnecting said one or more randomly generated logic states to all said security encoding cells in said semiconductor chip; and through-silicon-vias to establish electrical connections between said security encoding cells and said logic circuits.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

(1) FIG. 1 depicts a design with a hardware Trojan injected according to an embodiment of the present invention

(2) FIG. 2 is an example of a two-bit randomized encoding (dual-rail encoding).

(3) FIG. 3 shows an example of converting the state transition table of a conventional sequential logic into one with randomized dual-rail logic, which is useful for understanding various arrangements described herein.

(4) FIG. 4 is one embodiment of the MUX-based implementation method of randomized encoding scheme for a sequential logic with two random bits.

(5) FIG. 5 is one embodiment of an alternative MUX-based implementation method of randomized encoding scheme for a sequential logic with two random bits.

(6) FIG. 6 is one embodiment of the partition method for designs implemented with the MUX-based methods in FIG. 4 and FIG. 5.

(7) FIG. 7 illustrates one layout based on the partition method in FIG. 6. It is useful for understanding the concepts described herein.

(8) The figures depict an embodiment of the present invention for purposes of illustration only. One skilled in the art will readily recognize from the following description that alternative embodiments of the structures and methods illustrated herein may be employed without departing from the principles of the invention described herein.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT

(9) While the specification concludes with claims defining features of the embodiments described herein that are regarded as novel, it is believed that these embodiments will be better understood from a consideration of the description in conjunction with the drawings. As required, detailed arrangements of the present embodiments are disclosed herein; however, it is to be understood that the disclosed arrangements are merely exemplary of the embodiments, which can be embodied in various forms. Therefore, specific structural and functional details disclosed herein are not to be interpreted as limiting, but merely as a basis for the claims and as a representative basis for teaching one skilled in the art to variously employ the present embodiments in virtually any appropriately detailed structure. Further, the terms and phrases used herein are not intended to be limiting but rather to provide an understandable description of the present arrangements.

(10) An invention for addressing the data leakage issue in sequential logics fabricated in untrustworthy fabrication facilities are discussed below. First, an embodiment will be shown describing designs with data leakage hardware Trojans injected, the target application of this invention. Second, several embodiments will be presented to show a new randomized encoding scheme to randomize the information processed in a sequential logic. Third, a procedure will be shown for implementing and using the randomized encoding scheme in designing logic functions with resistance to information leakage caused by hardware Trojans injected. Fourth, the conditions under which the information can still be uncovered will be summarized.

(11) Referring to FIG. 1, one type of embodiment for a sequential logic 100 is shown. A hardware Trojan in the form of a MUX 101 is injected. When the select signal 101a is set to 0, the virus is not triggered and the sequential logic 102 operates normally. When the select signal 101a is set to 1, the virus is triggered and some binary bits 101b selected by the attacker from selected registers in the sequential logic is sent directly to an unused RS232 port 103, which can then be obtained by an attacker. Similar mechanisms can be used to create other types of side channels for data leakage.

(12) To successfully inject a data leakage Trojan an attacker must be able to identify the gates and understand the function of a design. With this in mind, existing methods have focused on making the design harder to interpret. The current state of the art revolves around obfuscation, layout camouflaging, and split manufacturing. Obfuscation aims to make the function of the circuit less obvious by using nonstandard designs for common functions. Obfuscation can also be performed on state machines in the design, additional states are added leading to dead ends or black hole states. Layout camouflaging attempts to disguise the design by making the layouts of each gate indistinguishable. Extracting the netlist using image based techniques on the layout mask then becomes difficult. Finally, split manufacturing attempts to break up the design into front-end and back-end layers. The front-end consists of the lower silicon layers and first metal layers, the back-end being the remaining metal layers. Splitting the fabrication prevents an attacker in one location from having access to the complete design.

(13) All of these existing countermeasures attempt to hide design information from attackers, and can be defeated if the same design is to be manufactured by multiple fabrication runs and an attacker can procure a chip in between and reverse engineer the design to obtain the full design information. The present invention is a useful, novel and a non-trivial solution to address this unsolved problem, and may be shown by several different embodiments.

(14) The following embodiments of the present invention utilize randomized encoding to hide information. To accomplish this, the present invention uses a set of non-overlapping codes to encode logic values. To provide multiple representations (redundancy) so that randomness can be introduced, more than one bit to encode logic zero and logic one is needed.

(15) Referring to FIG. 2, an example 200 is given where two bits are used. In this example (referred to as randomized dual-rail encoding), among the four code combinations 00, 01, 10, and 11, the present invention uses 00 and 11 to encode zero, and 01 and 10 to encode one. There are other embodiments where the code length and assignment can be different, but for the purpose of this embodiment and the embodiments described hereon, it is used so one skilled in the art may follow all the examples easily.

(16) One of the two rails in the randomized dual-rail encoding will be generated from a random number generator, the value of which changes every clock cycle. In this embodiment and the embodiments hereafter, the rail from which the random number is generated is referred to as the random rail. The conversion between conventional logic and the corresponding randomized dual-rail logic then becomes straightforward. For any conventional binary logic value x and given the random logic value r on one of the two rails in dual-rail representation, the logic on the other rail can be decided through an XOR gate as t=xr. Note that the values of t, x and r must be from the same clock cycle for the equation to hold. In randomized dual-rail logic, the signals on both rails must be known at the same time to decode the value. Protecting the value then converts to protecting the random bit r of each signal from being identified by hardware Trojans.

(17) The following embodiment shows an approach of converting conventional sequential logic to randomized dual-rail logic through state transit table. Referring to FIG. 3 for an example 300, which can help to better understand the various arrangements described herein. The binary values in each row in the state transition table 301 of the conventional sequential logic can be converted into the randomized dual-rail representation in the corresponding state transition table 302, which can then in turn be implemented. As the state transition table 302 is not unique, there can be many different corresponding implementations.

(18) The above approach, though straightforward, may result in significant area and power overhead, and is not efficient for large-scale designs where the state transition diagram can be huge. The following embodiment shows an alternative approach that is more systematic and scalable. To reduce overhead yet maintain security, we let all the gates in a sequential logic share two random rails, which requires a minimum of two random number generators. A single random rail with one random number generator is not sufficient to hide the information for sequential logic and an attacker will still be able to identify the information. In other words, each signal is randomly selected to use one of the two rails to form its dual-rail representation. As such, any given Boolean function (x.sub.1,x.sub.2,x.sub.3) with x.sub.1, x.sub.2, x.sub.3, . . . as Boolean variables between two registers can be converted to the corresponding randomized dual-rail representation
(x.sub.1,x.sub.2,x.sub.3, . . . ).fwdarw.(t.sub.1r.sub.1,t.sub.2r.sub.2,t.sub.3r.sub.1, . . . )r.sub.1(EQN. 1)
where r.sub.1, r.sub.2 are the random logic values on the two common random rails, and t.sub.1, t.sub.2, . . . are the logic values on the other rail for signals x.sub.1, x.sub.2, . . . , respectively. We have assumed that the conversion uses random rail r.sub.1; that t.sub.1, t.sub.3 use r.sub.1 when forming the randomized dual-rail representation, while t.sub.2 uses r.sub.2. i.e., x.sub.1=t.sub.1r.sub.1, x.sub.2=t.sub.2r.sub.2. x.sub.3=t.sub.3r.sub.1, . . . . These can be arbitrarily chosen for primary inputs, and are decided from the implementation of upstream logic blocks otherwise. We have also assumed that all the values are from the same clock cycle T. Based on the following logic equivalency which uses De Morgan's Theorem
(t.sub.1r.sub.1,t.sub.2r.sub.2,t.sub.3r.sub.1, . . . )r.sub.1=r.sub.1r.sub.2(t.sub.1,t.sub.2,t.sub.3, . . . )+r.sub.1r.sub.2(t.sub.1,t.sub.2,t.sub.3, . . . )+r.sub.1r.sub.2(t.sub.1,t.sub.2,t.sub.3, . . . )+r.sub.1r.sub.2(t.sub.1,t.sub.2,t.sub.3, . . . )(EQN.2)
EQN. 2 forms the structure of a MUX.

(19) Refer to FIG. 4 for the corresponding randomized dual-rail implementation 400 of . The four logic blocks 401, 402, 403 and 404 are identical except the additional inverters 402b, 403b, 404b at some of the inputs 402a, 403a, 404a (t.sub.1, t.sub.2, . . . ) and the additional inverter at the outputs 403c, 404c. A 4:1 MUX 406 with two randomly generated bits r.sub.1r.sub.2 as select signal 406a is used to decide its output 405 to the register 407. The output 405 is also in dual-rail representation with random rail r.sub.1 when r.sub.1 is preselected as random rail or random state to be used, and with r.sub.2 as the non-preselected as random rail or random state. The output of the register 407 is sent to an XOR gate 408 with r.sub.1r.sub.1 as the second input 408a, where r.sub.1 is the value of r.sub.1 in the past clock cycle or as depicted in FIG. 4; the representation r.sub.1 is the same as r.sub.1(t1). In this way the output 409 is in dual-rail representation with r.sub.1 when r.sub.1 is preselected as random rail or random state to be used. We can also set the select signal 408a to r.sub.2r.sub.1, in which case the output 409 is in dual-rail representation with r.sub.2 when r.sub.2 is preselected as random rail or random state to be used. Note that the final XOR 408 uses r.sub.1r.sub.1 or r.sub.2r.sub.1 only if its output is still intermediate (i.e., will be used by the next block). If its output is primary output, then only r.sub.1 needs to be used so its value is converted back to the single rail representation to be used externally.

(20) The MUX-based conversion can have another variation in terms of practical implementation. We can let the conversion use random rail r.sub.2 and rewrite EQN 1 as
(x.sub.1,x.sub.2,x.sub.3, . . . ).fwdarw.(t.sub.1r.sub.1,t.sub.2r.sub.2,t.sub.3r.sub.1, . . . )r.sub.2(EQN. 3)
in which case the converted dual-rail representation uses r.sub.2. t.sub.1, t.sub.2 use r.sub.1 when forming the randomized dual-rail representation, while t.sub.3 uses r.sub.2. i.e., x.sub.1=t.sub.1r.sub.1, x.sub.2=t.sub.2r.sub.1. x.sub.3=t.sub.3r.sub.2, . . . . The first rail can be re-cast as
(t.sub.1r.sub.1,t.sub.2r.sub.2,t.sub.3r.sub.1, . . . )r.sub.2=r.sub.1r.sub.2(t.sub.1t.sub.2,t.sub.3, . . . )+r.sub.1r.sub.2(t.sub.1,t.sub.2,t.sub.3, . . . )+r.sub.1r.sub.2(t.sub.1,t.sub.2,t.sub.3, . . . )+r.sub.1r.sub.2(t.sub.1,t.sub.2,t.sub.3, . . . ) (EQN. 4)

(21) Refer to FIG. 5 for the corresponding randomized dual-rail implementation 500. Compared with 400, the four logic blocks 501, 502, 503 and 504 are identical except the locations of the inverters 502c and 504c at the outputs. A 4:1 MUX 506 with two bits r.sub.1r.sub.2 as select signal 506a is used to decide its output 505. The output 505 is also in dual-rail representation with random rail r.sub.2. The output of the register 507 is sent to an XOR gate 508 with r.sub.1r.sub.2 as the second input, where r.sub.2 is the value of r.sub.2 in the past clock cycle, which is the same as r.sub.2(t1). This configuration will render the final output 509. Note that the final XOR 508 uses r.sub.1r.sub.2 or r.sub.2r.sub.2 only if its output is still intermediate (i.e., will be used by the next block). If its output is a primary output, then only r.sub.2 needs to be used so its value is converted back to the single rail representation to be used externally. Compared with the implementation 400 (see FIG. 4), this different implementation will result in different power and area overhead. One skilled in the art can easily create other variations following similar process described in this embodiment.

(22) For the randomized dual-rail logic to be effective, it must protect the two random rails as well as the input and output of all the registers. This is a significant advantage over any existing methods, where part of the information can be obtained if any part of the chip is compromised. The following embodiment will explain how the randomized dual-rail implementation can be effectively protected from data leakage hardware Trojans.

(23) The protection is based on the existing technology of three-dimensional integration, which allows two chips to be fabricated separately and then stacked vertically. The electrical interconnections between the two chips when vertically stacked, are enabled by through-silicon-vias (TSVs). Based on three-dimensional integration, it is within the scope of the invention to place the random number generators, all the registers and the MUXes in the top die, which is fabricated in a secure facility, and the rest of the sequential logic in the bottom die, which can be outsourced and fabricated in an untrustworthy facility. The two dies can then be stacked together in a secure facility. In addition, since the only designs needed in the top die are registers and MUXes in a regular structure, which are independent of the function of the sequential logic in the bottom die, it is possible to pre-fabricate a generic top die in an array structure, which contains regularly placed cells of registers and MUXes. Depending on the detailed placement of the bottom die, only some of the cells will be used. Refer to FIG. 6 for an illustration 600 of the structure. Each cell 601 contains the regular structure 602 formed by a 4:1 MUX, a register and an XOR, and the two random rails 603 and 604 send the two random bits to each cell in a crossbar structure.

(24) It is important to point out that the method does not always protect the information in the chip. In certain scenarios it is possible for an attacker to infer the information based on the data collected at the I/Os of the top die. To successfully infer an internal signal, an attacker will need to inject Trojans to monitor all the inputs at the corresponding MUX and as well as the output of the XOR. For example, referring back to FIG. 4, in design 400, although the MUXes and the register are in the top die where an attacker has no access, the inputs 406b, 406c, 406d, 406e to the 4:1 MUX 406 and the output 409 of the XOR gate 408 are all on the bottom die and are accessible to an attacker. An attacker will need to inject Trojans at these locations to monitor them. As 409 comes from 406b, 406c, 406d, 406e (selected by the two random rails r.sub.1 and r.sub.2), it is possible to identify the values of r.sub.1 and r.sub.2. For example, assume a scenario where 406b and 406c are 0's and 406d and 406e are 1's. Then if r.sub.1 is 0, either 406b or 406c will be selected and 405 will always be 0. If r.sub.1 is 1, either 406d or 406e will be selected and 405 will always be 1. Since 405 is in dual-rail representation with r.sub.1 as the random rail, we can know that the corresponding data on 405 is 0 (either 00 or 11 correspond to 0). Furthermore, based on the logic value at 409 in the next cycle and comparing it with this value at 405, we can infer the value of either r.sub.1 or r.sub.2 in the next cycle, depending on whether the output is set to dual-rail signal with r.sub.1 or r.sub.2. Assuming that 409 is set to dual-rail signal with r.sub.1, following the same logic reasoning, all the scenarios where attackers can infer data from design 400 are illustrated in FIG. 7. The scenarios 701 assume the attacker has no knowledge of the values of the two random rails r.sub.1 and r.sub.2 in the previous clock cycle. The scenarios 702 assume the attacker has knowledge of the value of the random rail r.sub.1 in the previous clock cycle. The scenarios 703 assume the attacker has knowledge of the value of the random rails r.sub.2 in the previous clock cycle. The scenarios 704 assume the attacker has knowledge of the values of both of the random rails r.sub.1 and r.sub.2 in the previous clock cycle. Compared with the total number of possible scenarios, however, the chances are still low.

(25) It is worthwhile to point out that the different possible variations in implementation create an additional layer of protection. The above discussion assumes that an attacker knows the detailed circuit implementation to identify the information. However, with the many possible variations, unless an attacker can know directly from the fabrication which one is exactly used in the chip he intends to hack, which is a very challenging task, the only way he would be able to know so would be through reverse-engineering, which will damage the chip and no information can be obtained.

(26) Clearly many modifications and variations of the present invention are possible in light of the above teachings. It should therefore be understood that, within the scope of the inventive concept, the invention may be practiced otherwise than as specifically claimed.