Hardware Security - Intellectual Property Protection - Week 2

Introduction to IP Protection

Welcome back to Hardware Security. This week we will talk about how hardware designers can protect their design intellectual properties from being misused. We will learn what design intellectual properties are and why they are important in modern hardware design. We will show that in addition to law enforcement, there are several techniques available for you to protect design intellectual, intellectual properties by yourself. These techniques include digital watermarking, digital fingerprinting, integrated circuit metering, and design obfuscation. So, the discussion of this message we will also see how to make the tradeoff amount, security, cost, and system performance. No special background is needed to understand these concepts. However, the examples we will use require some basics of digital logic design. We will also introduce the concept of graph coloring problems and graph partitioning problems. How we use them? According to the Cambridge International Dictionary of English, intellectual property is an original idea, which can be used to earn money. Original reflects the novelty of the intellectual property and that the phrase can be used implies the usability of the intellectual property. Examples of intellectual properties are products, technologies, softwares, and so on. Meanwhile, it also states that's the person or group who is recognized as having the idea can use the law to prevent other people from earning money by copying it. This law enforcement includes, patents, copyrights, trade secrets, and so on. In VLSI design, an intellectual property is a dig, is a design unity that can be reasonably viewed as a stand-alone sub-components of a complete system on-chip design. It can be any innovation and the technology that make designs better. For example, a place design algorithm, a power management technique, or a noble design or testing method. These are all considered as Design IPs. More tangible examples include, microprocessor course, on-chip memories, PISA interface micro, fully routed netlist, Verilog chip descriptions, and so on. These are also as virtual components, blocks, cores, or sometimes called a macros. Based on their performance and the flexibility. Design, design intellectual properties can be categorized into three groups. Hard IPs, they include GDSII files with test the list and high level models, customer physical layout, fully placed in a routed netlist for a given partic, technology library. These hard IPs have predictable performance, and most of the time, optimized. But they are very, very inflexible. On the other hand, soft IPs are delivered in the form of synthesizable HDL code, like Verilog or VHDL programs. They offer great design flexibilities despite the la, the last predictable performance. Examples of Firm IPs are placed RTL sub-blocks and the fully place netlist for, for generic technology library. They can be, they can be considered as a compromise of hard IPs and soft IPs. The driven force behind intellectual properties is the design productive, productivity gap. The gap between what can be built and what can be designed? This figure is available from Wikipedia. It shows the CPU transistor counts in the past of 40 years, following the Moore's law. The Moore's law says, that the number of transistors on a chip is doubled every 18 months. I don't want you to read all the words in small font in this figure. What is important is that back, back in 1971 the Intel 40, 4, 4004 processor has 2300 transistors and they're 10 micrometer technology. Now, technology has advanced to 20 nanometres and more than processors have buildings of transistors. The capacity of si, silicon has increased for almost 1 billion times in the past of 40 years. But designers ability to do meaningful design. With such transistors has not increased at the same pace. This creates the design productivity gap. One of the most effective way to close the gap is reuse-base, reuse-base the design. Starting, starting from the mid 1990s. There are many industry initiatives on IP reuse. In the US, there are Virtual Software Interface Alliance, also known as VSIA, and Virtual, Virtual Component Exchange. At the design and reuse this, organisation in Europe, Europe. An IP-Highway is the one in the Asia. In reuse-base design IPs are developed not only for use, but also for reuse. Design engineers are forced to cooperate and share their data, expertise, and experience. These are details I encourage to be documented and made public to make reuse more convenient. But, at the same time, these efforts has made IP piracy and the infringement much easier than ever. Since the early 1990's litigation cases and semiconductor related to IP infringement have been increased very, very fast causing an estimated annual revenue loss of billions of dollars. The most dangerous threat of IP pi, piracy came in the form of reverse engineering, chip overbuilding, and counterfeiting. Reverse engineering is the process, where a product is taken apart and analyzed in order to improve or duplicate the product. For hardware design IPs, the cost and the schemes required for reverse engineering are much less than those to develop the original IP. This gives a taggers incent, incentive for IP piracy. Chip overbuilding refers to the scenario, where our foundering fabricates more chips than the order. And then sells those extra copies to the market to make profits. Counterfeiting is the case when a low quality product, or IP, is manufactured but is sold as a high quality brand name. The Virtual Software Interface Alliance has listed the following four goals for intellectual property protection. Number one, enable IP providers to protect their IPs against unauthorized use. Number two, protect all types of design data use to produce and deliver IPs. Number three, detect use of IPs. And finally, trace of IPs. [NOISE] In practice, most design, design IPs are secured by deterrents and the protection mag, mechanisms. Commonly used the deterrents, includes patents, copyrights, contracts, trademarks, and the trade secrets. They do not directly provide IP piracy they do not directly prevent IP piracy. But rather discourage the misuse of IPs because the attacker was being caught. They face lawsuit and severe penalty to recover the financial loss of the IP provider. However, it is the IP provider's task to identify and report IP infringement and find the attacker. Protection mechanisms, on the other hand, use means such as encryption, chemicals, obfuscation, and dedicated hardwares to prevent and authorize the access to the IP. Standard encryptions can be applied to protect these IPs. For example Both Xilinx and Altera have offered encryption on their IFPG boards. Chemicals can also be integrated into the chip for a passive protections, mainly from military devices. When the surface of the, the chip is scratched and exposed to the a, to the air it will damage the exposed silicon. And thus, prevents reverse engineering. Meanwhile, obfuscation method have been proposed at various design phases in order to disguise the design and make reverse engineering much more difficult. In addition, industry organizations have been working on establishing standards for IP reuse and IP protection. For example, Virtual Socket Interface Alliance has published two tagging standards to protect hard IPs and soft IPs. Law enforcement is the only means to get back the revenue lost to IP piracy. The encryption and other protection mechanisms make IP piracy more difficult, and more expensive. But only the detection schemes such as digital watermark. digital fingerprinting, and integrated circuit metering can enable IP providers to identify the occurrence of IP piracy. This identification will be the first step towards legal fight against IP infringement. We will focus on this message this week.  


Watermarking Basics

Let's continue our discussion of IP protection with digital watermarking. This cartoon shows how watermarking can be used as a deterrent for IP piracy. Alice is IP provider. And Bob gets a copy of the IP from Alice. Seeing the value of the IP, Bob decides to make profit illegally from Alice's IP. He can reverse engineer the IP, and reproduce it or he can also integrate the IP into his own product. Then, Bob can sell the I, reverse engineered IP or his new design to another user without the authorization from Alice. This type of IP infringement can happen very easily because of the IP we use, particularly with the soft IPs. It is also very hard to detect and trace. Even when Bob is caught, Alice may not have sufficient evidence to prove her authorship of the IP. Now suppose Alice embeds her signature as watermark into the, into the IP. After Bob reproduces the IP or integrates the IP into his own design, before he can resell it, he has to think about whether he has removed Alice's signature or watermark completely. If not, he might get caught and face penalty because this time Alice can prove her authorship of the IP from the watermark or from the, her signature. Therefore, we see that watermark can deter attackers from illegally copying or using IPs. Digital watermarking has been widely used for identification, and notation and copyright of multimedia data such as text, image, audio, and the video. Traditional watermarking techniques take advantage of the limitations of human visual and auditory systems and embed the signature to the original data as small er, errors. This actually changes the original multimedia data and cannot be directly applied for the protection of hardware design intellectual properties. This is because the value of these IPs rely on their correct functionalities and their performance. We observe that for a given system specification, there are normally many different ways to implement the system, or develop the IPs. Therefore, if the IP designer can intentionally create certain structures in the implementation of the IP to make it rather unique, then this evidence can be used as watermark to prove IP's authorship. For example, this is the gate-level view of two implementations of a four-bit arithmetic and logical unit. On the left is the original design. The one on the right is upturned after we embed the message UMCP TERPS in the original varial code. We can easily see the different appearance of the two implementations. For example, here, here, and here. But it is hard to tell which one has watermark and which one does not have. The next example is a FPGA implementation of the data encryption standard. One with no watermark, another one with a message, more than 4700 bits embedded. Again, we see difference of the two designs here and here. Now we analyze the constraint based watermarking from the perspective of steganography system. Here is the classical steganography system. Secret data is hidden in the stego data, behind the cover data, using a stego key. The secret can also be extracted from the stego data, if necessary. Here is a similar drawing showing the concept of the constraint-based watermarking system. The original problem for the system specification, specification of the IP, will be used as the cover constraint to hide the watermark and author's signature. To do this, the IP designer will first create a set of constraints. These constraints are selected in such a way that they do not conflict with the cover constraints. This is because conflicting constraints my turn the problem into unsolvable. Then the original constraint and this additional constraint will be combined together to form a stego-problem. The stago-problem, instead of the original problem, will then be solved to obtain a stego-solution. This stego-solution will satisfy both the original and the additional constraints. To claim the authorship, the designer has to demonstrate that the Stegno solution carries information based on his signature here. The Stegno solution necessarily satisfies a set of additional constraints. These constraints may look random. However, the designer can regenerate these constraints using his signature together with his Stego-key. Cryptograph, cry, cryptography functions, such as one-way hash function and stream cipher, can be used to generate this embedded constraints to enhance the credibility of the authorship. Finally, we consider I, IP invention as solving a hard problem. The requirements for the IP are the constraints that any solution is to meet to be a solution for the problem. The value of the IP will be measured by the quality of the solution. We now show the concept of charting solution space behind the constraint-based watermarking approach. This green area shows a solution space to our original problem. The purple are in the middle shows the solution space of better solutions. This point is a randomly found, found the solution to the problem. After we add extra constraints some of the solutions failed to satisfy these additional constraints and they become invalid. Suppose this shaded area is the solution space after watermarking. Now, if we report the same solution it is more convincing to say that we find this solution by solving it, by solving the watermarked problem instead of solving the original problem. To see this, suppose there are, there are n solutions to the original problem and m solutions to the watermarked solutions. When n is greater, when n is greater than m or in many cases when n is much greater, much larger than m, the chance that finding a solution from the m solutions, which is 1 over m, will be much bigger than the chance of finding the solution from n solutions. And this can be used as a very strong proof of the authorship of this reported solution, which is in some sense the authorship of the IP. 

Watermarking Examples


We have learnt the importance of intellectual property protection, and the basics of digital watermarking. Now, we will show a couple of examples to see how to embed digital watermarks into hardware design intellectual properties. [SOUND] The first example is on Boolean expression optimization. The problem, is to rewrite a Boolean formula don't care conditions using the minimum number of literals. Our goal is to protect, to minimize the formula, which is the design intellectual property in this case. The approach we've used is to embed, one bit of information behind each don't care conditions. When we want to hide a bit of one, we force the don't care condition to be one, and when we want to a bit zero, we force the formula to be zero on the don't care condition. For example, to had, to hide the message 01, we make the first don't care condition to be zero, and, the second don't care condition, after that condition the formula will be evaluated at one, and thus, the formula becomes, this new form, which has a well additional term, abcd, corresponds to the second don't care condition. And we can find, the optimal solution in this case, which F becomes a prime, b, c prime plus bd. And similarly to hide message 10, we can include the first don't care condition into the Boolean formula and then leave the second don't care condition away, so this is because the second bit is 0, and, as a result we upturn this solution which is distinct or different from the first one. To summarize this example, we see that, we can hide watermark by specifying values to don't care conditions. In this example, any 2-bit message can be embedded and will get distinct watermarked solutions, as shown here, or we add either 00, 01, 10, or, or 11, and we get four completely different solutions. However, we see some of the solutions are better than others. For example, the solution with 01, and 11 as watermark, they both have five letters as the solution, and, however, the other two have nine literals. This is one of the challenges for watermarking, which is known as fairness, and we will talk about this later. Let's see another example. This example is a radix-4 to binary encoder, what we have here is, this is the truth table where we have each of the four symbols, the radix-4 member system, and we'll convert each of the symbols into a binary representation, with fo, two bits. And the window that's the input has four bits, and so we have two to the power for 16 different input combinations, however, the truth table has only four of them, that means there are a total of 12 don't care conditions and we list them, listed them there numerically, start from page 0000 all the way to 1111, and output, the oldest cases are don't cares, which are represented by this double cross. And assume that we want to add, a two-digit letter, DA, as our watermark, DA stands for design automation in this case. The first thing we do is, we represent this, these two letters into, binary information. And what we do is, we consider that ASCII code, D and A, and then we also add a parity bit at the end, so this gives us a 15 bit watermark. And we embedded this 15 bit watermark into the original truth table for the original design, what we do here is, we see there are 12 don't care conditions. With don't care con, 12 don't care conditions we can embed three bits, this is because, if you want embed four bits, we may end up with the situation that, it does not exist in these 12 don't care conditions, because 12 can represent 8 different combinations for, of 3 bits, but not 4 bits. So what we do is we consider the last 3 bits of the watermark which is 010, which is a binary 2, so what we do is we come to our list of don't care conditions, see zero, one, and the two. So this is the don't care condi, condition, we are going to specify a deterministic value to embed our signature. And, what value should the system output in this don't care condition, that depends on what is the message you want to embed here. So, what we see in the original watermark, the next two bits, which because, our, our output has two bits. So, the next two bits are 00, so that is why, I replace these don't cares by two zeroes. And similarly, I can move out to the next three bits, I can do this because now, the don't care table has 11 don't cares, I can still do, three bits. So this 3-bit is 100, which is the binary four, so what I do is I count zero, one, two, three, four, so this is the don't care condition, I'm going to force a value, and the value happens to again to be 00, because the next two bits in the watermark are 00. And then, we keep on this process, and then the next one bit is 001, which is the binary of one, so 01, and then the massive logo add, add the, the leading bits, which is 10. So now we have successfully convert, this 15-bit watermark into three pairs of input and output, and we added them into the original truth table, and then we got an augmented truth table, which we called the watermarked truth table. Now we will show how design will be conducted with the original truth table and the watermarked truth table. So from here, we can easily see that, the two outputs x and y can be represented by c plus d, and b plus d, or simply two And however, to implement the watermark truth table. The expression becomes a little bit more complicated. So in this case, instead of four literals, two logical gates, we need one, two, three, four, five, six, seven, eight literals. This is something we know called design overhead, and again, we'll discuss about the design overhead later. The final example is our problem that has a lot of applications in hardware design and optimization, the problem is known as graph vertex covering, coloring problem. So what we have in this problem is, we have an undirected graph, and we want to color the graph by giving each vertex or each node a color, such that, whenever two nodes are connected they must get, we must give them different colors, for example, node B, and nodes D, they are connected, so B and the D, they have to receive different colors. So this is one of the sample solutions here, you see, I mean, A, B, C, D, they all get different colors and then H has the same color with D because they're not connected, and H has to have a different color with G because they are connected. And usually this problem is not that hard to solve, but what is harder is, well we tried to minimize the number of colors we, we need. As a matter of fact, if we consider whether a, a graph can be colored by two colorful nodes, which is known as the two, 2-colorable problem, that problem is trivial to solve. However, when I ask you whether a graph is three, can be colored by three colors or not, the 3-colorable problem turns to be NP-complete, and in fact ,the 3-colorable problem is one of the most important NP-complete problems, and it has a lot of applications, in particular for digital VLSI design. Now we will show how we can embed watermark into a solution to graph coloring problem. So what we ha, have here is, we have a graph with 11 nodes, and a, probably around 20 edges. [COUGH] What we want to do here is, we want to protect our solution to, to a scheme of this graph, and what we do is, by hiding a message 2000 into the solution, to achieve such protection. The first thing we do as we show previously, we, we need to convert our signature, well our message into binary, in this case, the decimal number 2000 will be converted into binary bit sequence here. And what I do now is, I want to show you, step by step how I can hide this, bitstream into the graph, and then solve the graph, find a solution. The first thing I do is I take a look, look at note 0, I want to find, the next two note that are not connected to note 0, in this case, I see 0 and 1 they're connected, so 1 is not a candidate, but, both note 2 and 3, they are not connected to note 0, so 2 and 3 will be candidate in this case. And to hide a bit of information, what I'll do is, I'm going to add one additional edge starting from 0, and what is the receiving end or the receiving note of this edge that depends on the [INAUDIBLE] I'm going to invite, so, if want to invite a 1, I'm going to connect a 0 to 3, if I'm going to invite a 0, I'm going to connect the 0 and a 2.In this case, because I want to invite a 2, so what I do is connect a 0 and the 3, and similarly, I move on to the next one, know the 1, 3 and 4, they are the next two nodes that are not connected to 1, and to add another bit-1, I connected 1 and a 4. So I can repeat this process, and at the end, all these 11 bits will be embedded into the, into this new graph, which we called a watermarked graph, and these are the dotted edges correspond to one, one, one, and so on. So now I use my tool or find another smart way to color this graph, and the solution I get is, this is one of the examples, and we see that it requires 0, 1, 2, 3, so all together, four different colors. And, in this solution we noticed some interesting things, so for example, note 8 and note 7, they received different colors, however, this is not required in the original graph. As a matter of fact, indeed I can also put note 8 as blue, which also satisfies all the requirements, which means that for all notes that are connected to 8, they're not, they're not in the same color in the original graph, but not in the watermarked graph. So, the fact that this solution satisfies a set of additional constraints, will be used as the proof of our authorship. 

Good Watermarks

Now we discuss what's the requirements of a good watermark are and some of the advanced techniques to design digital watermark. First a good watermark has to preserve the correct functionality of the intellectual property. Because otherwise the watermarked IP fails to meet the design requirements and will have no value. Second, the desired overhead introduced by the watermark must be negligible or very low. Well that's the value of many intellectual properties are not only their functionalities. But also how these functionalities are implemented with high performance and the low cost. High design overhead, or performance degradation, will reduce the value of the intellectual property. Third, the watermark has to provide high credibility of the authorship or the probability of coincidence, that others will implement identical IPs, should be low. Next, the embedded watermark should be easy to detect as the proof of the authorship. However, it must also be resilient, in the sense that's it will be difficult or impossible for an adversary to remove or modify the author's watermark. Transparency means that the addition of watermark and it's detection should be transparent to existing design tools and design softwares. Otherwise it will be difficult for a watermarking scheme [NOISE] to be adopted. Ideally, a good watermark can also be used to protect specific parts of the design in addition to the entire design. This is important in the reused space then design practice. Because IPs will be integrated and the designer may not be able to insert watermarks to hold IP's. Finally as we have seen before, a good watermark should be fair to all the designers or all the possible signi, signatures. [NOISE] Next we will use low overhead and easy detectability to demonstrates how these features can be achieved. The design overhead and the performance degradation caused by watermarking is unpredictable. And in man, many cases they are uncontrollable. This is due to the random, randomness of the additional design constraints based on the random watermark. And also the fact that's most of the design tools contain Non-Deterministic Algorithms. In addition, if we want to control the design overhead, the security of the watermark may be compromised. To solve this problem, we can use the 2-phase, zero-overhead watermarking approach. In this approach we first do the design without any watermark to obtain the best possible performance. Then we identify places where we can embed watermark without introducing performance degradation. Next we embed watermark. And then we redo the design to obtain a watermarked intellectual property. This line shows how we can apply [NOISE] this strategy to FPGA design. The FPGA design, we start by reading the design constraint files, and then to a synthesis, and then, to the place and the route. And the last step is to generate the configuration bitstream file. If we try to embed a zero-overhead watermark, what we do is we follow the first to three steps. And however, we're not going to generate the configuration bitstream ff, file right away. What we do is, we try to extract timing information on certain passes from the place and route result. And we'll combine this with the author's signature, to have, to use, the author's signature. To modify the delay information on the certain nets. And then we do the place and route again. And then we check whether the timing requirements are satisfied or not. If they're not, we come back, and we potentially, we may have to reselect nets and then do the place and route again. Until all the timing constraints are satisfied. And in this, and then we generate the configuration bitstream file. So what we see here is, because we are checking the timing constraints are satisfied or not. So there shouldn't be any timing degradation. And also we are going to show later using industrial benchmarks to see whether there was any resource overhead. The only thing we can see here is, we have to do this step multiple times to meet the timing requirement and embed the users signature. And we'll also sh, show by results see how much this additional time will cost. So this is an example of Watermarking Scheme. So what we do is, after we've finished the optimal design, we try to select non-critical paths. So for example, the first column shows the starting Flip-Flop. And then the second column shows the Des, Destination Flip-Flop. Then the, the third column shows the Delay in the optimal design from this Source Flip-Flop to the Destination Flip-Flop. And then none of these delay are critical. In the sense that the critical delay are all, are all shorter than these delay constraints. So, for us to embed watermark, what we do is we try to modify the last digit of these delay constraints. For example, if these are the watermarking bits we want to embed into the FPGA design, what we do is we replace the last bit by the watermarking bit. To obtain a constrained delay profile. And then we use this as the additional constraint to the original problem, trying to do the place and result again. As a result, we have seen this, this result here. So these are the Four Industrial FPGA Design benchmarks. And to this column shows the resource requirement in terms of the number of FPGA slices. And then we see the Original one and the Watermarked the designed. In the older cases the required slices for the original design are the same as the Watermarked the design. Which shows that there's no resource overhead. And the second row for each benchmark shows the timing requirement for each application. And the check mark means here we have satisfied the timing requirement. See all the cases the timing requirement with performance are match. There is again no overhead. And finally we mention that there is design time overhead to do the place and route again and again. And in all these cases the time to do that is in seconds. Finally, we want to show that this give us a very strong proof of authorship. And this is measured by the humming distance of the configuration bitstream file of the Original one and the Watermarked design. And this shows the humming distance in percentage, 1.09% up to 4%. And to pay attention to that for this benchmarks, the configuration bits first, bitstream files, in terms of megabyte, megabytes. So even 1% is a lot of difference between the two, two designs. So that can be used as a very strong proof of the authorship. Next, we discuss the detectability problem of the watermark. We have seen these slides before, so it shows the basic concept of the steganography system. And also the constraint-based watermarking system as an example of the steno, stenography system. Where we embed the author's signature in the Stego-problem using additional constraints to the Original Problem. However, the problem in this approach is how do we di, di, detect the Embedded watermark and use it to prove the authorship. The Public Watermark approach solves this problem. In this approach, instead of hide the author's signature everywhere in the Original Problem. We've select certain places, and then embed watermark only on those certain places. So, we will highlight how do we solve several problems in the following slides. Question number 1. How we can embed the signature. Number 2. How to detect the signature? How much do we lose by doing this? And how much can the attackers gain by knowing this Public Watermark? We first use the Graph Partitioning Problem to show the basic ideas behind the Public Watermark. In this problem we have a graph and we want to partition the vertices in the graph into two disjoint subset. Such that the subsets are balanced and also the connections between the subset will be minimized. For example, here is a partition that cc, cuts the graph into the top-half and the bottom-half. For this partition it is perfectly balanced. Because there are exactly 12 nodes on the top-half, half, and also 12 nodes on the bottom-half. And those are when we count, we have one, two, three, four, five, six, seven, eight, nine, ten. So 10 edges has been cut, which means the connection between the two subsets are ten. It is not easy to find a very good solution for a Graph Partitioning Problem. But indeed, this Graph Partitioning Problem is also a NP-complete problem. This slide shows how we can embed Public Watermarks. First we make the following information public. The 8 pairs of nodes, as shown here. A pair of 0, 0, a pair of 1, 1 all the way to a pair of 7 and 7. And the second, the scheme we use to embed public watermark. If you want to embed a bit 0, we keep the pair of nodes in the same subset. If we want to embed a 1, we keep the pair of nodes in a different subset. For example, if we want to embed a capital letter O, what we do is, let's assume that we encode O in ASCII code and put it to pairitive bits. And what we do is, we first, the partition, the eight pairs following the public watermarking rule. For example, the leading bit is 0, which means that's the two 7s will be in the same subset. And the second bit is 1. Which means the two 6 will be on different subset. And then we partition the rest of the node and then we get a partition like this. So if we do the partition this way, now everyone can detect the watermark, and then verify it. That is why we call this one a public watermark. Now we consider the security and detectability of public watermark. The Public Signature will be encoded in ASCII and then embedded into the problem using a, using a scheme that is known to the public. Therefore, it is very easy for the attacker to come and modify the watermark. For example, he can change one of the bits, and then to completely I mean remove the watermark, or modify it to another watermark. To solve this problem we can use some Crypto Primitives. So, for example, We can Hash the Bitstream file and then encrypted the Hash using the Bitstream itself as the key. In this way, we can have the public watermark into two parts. Which in the first one called the Public Watermark Header. Which is the plain text ASCII code of the Public Signature. And then we have a much longer Watermark Body which is being encrypted and encrypted of the Hash. And this is the entire will form the public watermark. Now, with this new Public Watermark, the attacker's job becomes much more difficult. Why? What we see here is, it is still easy for the attacker to modify the Public Watermark Header. And however, because of randomness involved here, even if the attacker changes only one bit or a few bits in the P, Public Watermark Header. Rel, relatively half of the bits in the Public Watermark Body will have to be changed. And then this makes the attacker's job much more difficult, even if he knows where to change all these bits. And finally, once we do all this, how difficult it is to verify or authenticate the watermark. We claim this is also very easy. So for a person to verify the claimed Public Watermark. He or she can start with the Public Signature to a client [INAUDIBLE] ASCII Encoding and then check the Public Watermark Header. If the Header matches, that is a, a good sign, since this probably the authenticated user. And if the, and if, if the, if the user wants further verification, she can also Hash the Bitstream file from the Public Signature and then use this as the key to encrypt a Hash. And then get, find out, what is the Body of the Public Watermark. And then go to the design to verify whether the Public Watermark Body has been changed to and then eventually, verify or detect the Public Watermark.  


Fingerprinting

We have learned the digital watermarking, hitting bad information about the three intellectual property designer into the IP, as additional design constraints. The watermark the intellectual property was satisfied this additional constraints. And therefore, has certain properties that can be verified to prove IP's authorship. We now started digital fingerprinting. First, why do we need fingerprinting? We know that digital watermark can be used to prove IP's authorship. However, it cannot distinguish different users who are using the same IP. When you sell your IP to ten different customers and you find someone else who's also using your IP, can you find out from your ten different customers who has misused the IP? I'll say it's no, unless you can find a way to identify each copy of the, of the IP. Or you have to make different copies of the same IP. Digital fingerprint is a protocol that can make each copy of the object unique and distinguishable. [NOISE] Here is some comparison between digital watermark and digital fingerprint. First, they're both invisible identifiers that are embedded in the design permanently for the purpose of intellectual property protection. Watermark remains the same for all copies of the IP, while fingerprints must be unique for each copy. In other words, fingerprint is equivalent to multiple copies of distinct watermarks. Any fingerprinting techniques has to address the following two fundamental problems. How to generate IPs with different fingerprints effectively. And, how to distribute the solutions to the users. We now elaborate challenges for digital fingerprinting. First, in the face of IP generation, the challenges are, how to create multiple, or in many cases, a large amount of solutions. And second, how to maintain the high quality of these solutions to keep the value of these IPs. And a search how to minimize the time and the complexity to generate multiple solutions. Ideally, we want to keep it close to the time and effort at the same level of funding one single solution. In the second phase, of IP distribution, there are also several challenges. Uniqueness means that different users must receive distinct, distinct fingerprinted IPs, in order to provide high credibility about their identity. And robustness requires it to be very difficult for attackers to remove or change the fingerprints. Finally, the fingerprinted IPs should be very different from each other in order to prevent collusion. This second phase is similar to the scheme that distribute fingerprinted copies of multimedium data or other artifacts. There are plenty of such established schemes that we can use. Therefore, in the rest of this lecture, we will focus on the first phase, which is the solution generation particles. [NOISE] This slides highlights two different fingerprinting techniques. The first one is called constraint addition, where we start from the original problem although we consider a set of fingerprint constraints. Combining these two we'll form the augmented solu, problem. We use the problem solver to solve this augmented solution to obtain a seed solution. The seed solution meets the original problem constraints. Which means it has, it is, has a valid as a IP. In addition, it also meets the fingerprinted constraints. We can design these fingerprinting constraints in a way, such that we can generate multiple solutions from this seed solution. This is what we called the set of rules for solution generation, which is based on the fingerprinting constraints, and also the problems. And from one solution, this set of rules will create multiple solutions for us. From this flowchart, we'll see that the problem solver will be used only once, which means the runtime to create multiple solutions by constraint addition will be similar or in some sense identical to the time complexity for finding this seed solution. However, how to design this fingerprinting constraints, and then how to create the rule, the rules for solution generation. This can be very, very challenging. The second technique is called iterative approach. In this approach, we start from the original problem, which might be watermarked to re, reflect the designer's signature. We solve the problem to find a seed solution. And then to generate fingerprinted copies, we take the user, or the buyer's fingerprint, and then combined with the original problem and the seed solution. To first construct a sub-problem, which is a small portion of the original problem. Then we use the problem solver to solve this small problem, to find a solution for the sub-problem. By combining this sub-solution, the sub-problem, and the seed solution for the original problem, we can form a new solution for the original problem. This will be put in the solution pool with this buyer's fingerprint. If we need more copies of the fingerprinted copies, we can repeat this process and potentially using this new solution as the seed solution to repeat this process. And from this flowchart, we see the problem solver will be used many, many times. More precisely, to generate each fingerprinted copy, we need to use this problem solver here once. However, notice that here we're solving a sub-problem which potentially will be much, less much less com, complex than the original problem. So hopefully the runtime overhead will not be as high as solving the original problem. Now let's see an example. We use the graph coloring problem as the example here. Remember the question is, how to give each node in a graph of color, such that any two nodes which are connected by the edge will get different colors and we ought to minimize the number of colors. And here is the solution to this problem. And assume that we now we want to find a fingerprinted solution, which will be different from this original solution. We can achieve this by connecting this nodes, B and E. And then, instead of solving the original problem, we can take a look at their locality. And then we can easily find we can change the color of E from yellow to green and then form a new solution. And, if we want more solutions we can add more constraints as from our fingerprint. And as one can imagine, eventually, thus, the quality of the solution maybe dropped. And this problem can be solved by the constraint manipulation method. In this example we consider as, as smaller graph, and a solution to this small graph. What we observe here is you see the node E can also be colored yellow. And, as a matter of fact it can also be colored by red. But however, node A cannot be colored by red. And node A cannot be colored by yellow either, and what we have learned from here is a node's color can be changed to a node to obtain another solution. It all depends on the colors it neighbor has got. But checking then the colors of its neighbors takes time, and there's no guarantee that we can always find a new solution, like in the case of A. It would be very nice if we can create more solutions by changing the color of specific nodes without checking their neighbors, or their adjacent nodes. And we can achieve this by node duplication method. In this example, we duplicate node A by adding a new node, A complement, or A compri, A, A prime. And we connect A prime with A, and all the neighbors of A, B and E in this case. Now we have this new graph and we're going to cover this new graph which we call the fingerprinted graph. And we can obtain a solution such like this. And in this solution one thing which is for sure is A and A prime will get different colors because they are connected by an edge. And also, these two colors which is green and the red can be used to color A in the original graph. Either one of them, either green or red. This is because both nodes are connected to the same set of neighbors. So, what we see here is by duplicating node A, we can get two different solutions. If we duplicate key nodes, we can easily created 2 to the power key distinct solutions, from one solution. Now let's see another example. Here is a, a, a graph and a coloring solution for this graph. We see here node B, C, and D, they form a triangle, or a clique of size three. So we need three colors to color these three nodes. None of them can get the same color because they are all connected. And, we can also swap the colors of node C and the D to form a new solution. However, none of C or D can get the color of B because they share, they share the same neighbor E which has the same color as B. So now, if we connect it to pair of nodes, B and the E and also D and the G. And now this fingerprinted graph has a very special structure. We see that triangle BCD. Now they share the same set of neighbors, A, E and the G, outside of triangle. So now if we color this new augmented graph or fingerprinted graph we can find solution scheme here. And with this solution, we can easily generate a lot of different solutions. So for example, starting from this original solution, we can replace where we swap the color of the C and the D to find a new solution. Or, we can change the color of B from yellow to brown and then that C and the D pick any of the remaining two colors to form two different solutions. And for the same reason when we keep B as red, C and the D can also take any of the two remaining colors, and have two other solutions. In total, what we have here is we can build 3 factorial which is 6 distinct solutions from solving the problem only once. So this shows that we can generate a lot of different fingerprinting solutions by solving the problem only once and that without compromise the quality of the IP. The final examples of how to utilize Don't Care conditions to generate fingerprinted copies. We first to consider the observability don't cares in the following circuits. Where X is the end of A and the B, Y is the or of C and the D, and output F is the end of X and the Y. In this case we see that when Y is 0, signal X cannot be observed from output F. Therefore we know that Y equal to 0, X equal to 0, Y equal to 0, X equal to 1 is the observability don't cares. Now we modified this circuit by connecting signal Y into the end gauge. Therefore, signal X becomes the end of A, B and the Y. And we know that when Y equal to 1, this is the same as A and B. And the Y equal to 0 this becomes 0 regardless of the value of A and the B. But however, while 0 this X is our observability don't care. So what we have here is these two circuits, they are functionally identical. And so we can do placement route, based on this circuit with this additional connection. And then we decide whether we want to keep this connection or not, to embed one bit of fingerprint. And when we can find n such substructures in the circuit, we will be able to create 2 to the power n distinct copies of the same IP. Good [INAUDIBLE] bad any embed fingerprint. The next example is on the satisfiability don't care. In this circuit, X equal to A and B. Y equals to A prime and B prime. From the truth table, we see that X and Y cannot be 1 at the same time. Therefore, we have a satisfiability don't care condition. X equal to Y. X equal to Y, and equal to 1. We know that, the OR gate and exclusive OR gate, they're different. For example, when both X and Y are 1, or give you an output of 1, and exclusive OR give you output of 0. However, we know this condition X equal to 1, Y equal to 1, is a satisfiability don't care. Therefore in that case, we are seeing this X, the OR of X and Y will be the same as the exclusive OR of X and Y. Or we can replace this circuit by this circuit where the only difference is the OR gate or the exclusive OR gate. So, if we can find n distinct satisfiability don't cares, we should be able to generate 2 to the power n distinct copies. To summarize digital watermarking and the digital fingerprint. You see di. We see that in this simp, simple flow of traditional IP development, without any protection, we can get a IP with the highest possible quality by synthesize, by synthesis tools based on the original design specification but however, we will not be able to prove our authorship. Or, if there's IP piracy happens, we cannot trace where is the source of the IP piracy. The idea behind digital f- Watermarking is to convert IP author's signature into additional design constraints. And then add it into the original design spec and use the synthesis tools to self IP that satisfies both set of constraints. In this way, we can hide IP author's signature into the IP, and then can retrieve this signature to prove the authorship. On the other side, fingerprint adds IP user's signature into IPs, into IPs as well. It will enable us to distinguish who gets each copy of the IP, and allow us to trace the use of IPs. Finally, it is important to mention that both digital watermarking and digital fingerprinting, they are deterrent of IP piracy. They do not prevent attackers from misusing IPs. But they do make the attackers to think twice before doing anything illegally. In addition, law enforcement is the only way to get the lost revenue back so the IP piracy happens. However, digital watermarking, and digital fingerprint are strong evidence to facilitate law enforcement.  


Hardware Metering

Which takes financial increase in the complexity and the cost of building a chip manufacturing line. Most chip makers are fabless now. In other words, today's design houses can not afford the in-house chip fabrication cost and that they have to outsource this fabrication to foundries elsewhere. This gives the foundries access to the details of the chips and the possibility of overbuilding them without the authorization from the, the design house. Integrated circuits metering, or hardware metering, is an effective method to defend against this IP infringement. Integrated circuit metering is a set of security protocols that enable the design house to achieve post-fabrication control over their ICs. IC metering techniques are developed to defend against IC overbuilding attacks. As we have mentioned earlier, in the integrated circuit fabrication process, these houses and foundries play asymmetric roles. These houses have to disclose the details of their IPs and pay the cost to build the mask in order to manufacture their, their chips. Once the IP is released and the mask is built, the design house will not have any control on them. However, a dishonest foundry can utilize this information and the facilities to reproduce the design with negligible cost. This is known as the IP overbuilding. Can we use digital watermarking techniques to protect a design, designer's right in this case? The answer is no. Watermark protects the authorship of an intellectual property. In IC overbuilding, the foundry just reproduce more copies of the IP than required. And then sells the extra copies to make profit. The foundry will not attempt to claim the authorship of the IP. How about digital fingerprint? Fingerprint enables the trace of intellectual properties back to the dishonest IP user who illegally distributed the IP. When the overbuilt ICs carry a fingerprint, the user who has this fingerprint will also become the victim of IC overbuilding. This is because this innocent user will be, now be considered as the source of these extra copies. How integrated circuits metering or hardware metering solves this problem then. Let's first see how meters work in our daily life. Why don't we talk about utility meters, like water meter or electricity meter? The meters are installed and maintained by the utility providers to monitor the users. However, in the case of the IC overbuilding, the foundry is the provider of the ICs. And the design house who receive these ICs will be the user. So what we need in, in our case is actually a reverse metering. Where the user wants to monitor the provider. The basic concept behind IC metering is to enable a unique tag to each copy of the IC and make sure that the tag is under the control of the design house, not the foundry. Over the years, many different types of tags have been proposed and used for hardware metering. They can be categorized based on various criterias. First, when the tag can only be used for cheap identification, it is called a passive metering. The tag in active metering can also do a lot of other functionalities, such as enable the chip, disable the chip, or control the chip. Active metering methods can be further classified as internal controlled or external controlled based on whether the control is part of the design or not. Intrinsic metering does not need help from additional hardware components, or the modification of the design. However, extrinsic metering methods do. Depending whether the tag interacts with the chip's functionality or not, we have non-functional metering and functional metering. Finally, some tags can be reproduced and some cannot. We call the latter unclonable tags, tags. Serial number is perhaps the most popular and one of the earliest of ways for device tagging. A serial number can be physically indented on the device or stored permanently in the memory. This image shows a Trusted Platform Module in storage on a motherboard. What we see here is, it has a couple of serial numbers. For example here, and here. These tags are passive, they are extrinsic because they do need additional, like this piece of paper or trying to be physically indented on the, on the device. And they are non-functional because they have nothing to do with the functionality of the chip, and most important, they are reproducible. You can use another tag or piece of paper to over, to cover this. Or you can change the numbers here. And it, it is the fact that this text can be reproduced make them unsuitable to countermeasure foundry overbuilding. The ICID tag was proposed around 2007. It is based on the silicon manufacturer variation. Because these variations occur during the chip fabrication process, and it is generally believed that they are random and uncontrollable. Therefore, ICID is considered as an unclonable tag, and thus can be used for anti-overbuilding. Depending whether the ID requires additional hardware components or not, IC Identification, or ICID, can be, can be either intrinsic or extrinsic. Let's first see an example of an intrinsic unclonable ICID based on leakage current. Consider a small subcircuit with four two-input NAND gate, G1, G2, G3 and G4, with five input signals, x1, x2, x3, x4, and x5. So here is the leakage of our ideal two-input NAND gate and the different input combinations. However, due to fabric, fabrication variation, the leakage on the NAND2 gates will almost for sure be different from these ideal values. For example, let's consider two ICs both have this two, have the structure of four two-input NAND gates. Their total leakage under four different input vectors are listed here in this table, and we see a dramatic difference between their leakage values. This leakage-based attack is intrinsic because it does not require any extra hardware. It is also unclonable because it is based on fabrication variations. It is will be very hard for any foundries to reproduce this manufactured variations. Now we show a functional passive tagging message. Recall that in the graph vertex coloring problem, we want to assign each node a color such that any pair of adjacent nodes will receive different colors. In this case, the IP is a solution to the graph coloring problem. Consider this graph and a coloring scheme, or an IP. We observe that node H, for example, can also be colored with red or yellow, because it has only two neighbors and they are both colored, colored with green. And similarly, we observe that F can also receive a color, which is brown. And finally, node E can also be colored by green instead of yellow. So, therefore, we can create 12 different tags by giving different colors to these three modes, H, E, and F. This is a functional tag, because the tag, which has the colors for node H, E, and F, is part of the solution or part of the functionality of the IP. Next, we see active integrated circuit metering methods. Most of the existing active metering methods follow the following steps. First, the design house will modify the design specification, most likely in the early design stage, to insert a lock. Then complete the design and ask the foundry to fabricate that design. The foundry will fabricate, and then, maybe, overbuild the chips. Due to manufacturer variations, each chip with each IC, will have a unique and unclonable identifier that can be used to authenticate the chip. In the active IC metering scheme, the design house can use this unique ID to actively meter or monitor the IC. For example, by enabling, disabling, locking, or unlocking the ICs. Here is an example of an internal active IC metering approach. The design house introduces additional flip-flops to build what is called a boosted finite state machine. Notice that each added flip-flop will double the number of states in the original finite state machine. Therefore, when we power up the chip and use the path data to select a random power up state. Most likely this state does not belong to any of the original final state machine. But for the chip to function properly, it has to start from certain initial state. The design house will provide a chip with power up states specific input sequence to direct the random power up state to the initial state, such that the chip can work properly. Without this correct input sequence, the, the, the IC will not be, it will be useless. This active IC metering approach uses internal finite state machine to control chips, to, to control the monitoring of chip. The additional flip-flops make it extr extrinsic. The use of PUF ensures that it is unclonable and thus can be used to countermeasure chip overbuilding attack. Finally, we show an external active IC metering approach. In this approach, the design house will add control signals and logical units such as exclusive or gate to non-critical parts of the design. Unless all the control signals receive the proper values, the chip or the fabricated ICs will be locked. The design house will then provide an external key to unlock each of the ICs based on some asymmetric cryptographic primitives, for example, the public key infrastructure. In this case, we see this is active metering scheme. Because it does involve the interaction between the, the design house and each fabricated ICs. It is an external method because the signal comes from the external value provided by design house. It is extrinsic because we do introduce additional control signals and logical gates. And finally, it is also unclonable, which means that it can also be used to countermeasure circuit overbuilding.