In this course, we will study security and trust from the hardware perspective. Upon completing the course, students will understand the vulnerabilities in current digital system design flow and the physical attacks to these systems. They will learn that security starts from hardware design and be familiar with the tools and skills to build secure and trusted hardware.
Watermarking Examples
Loading...
From the course by University of Maryland, College Park
Hardware Security
317 ratings
From the lesson
Design Intellectual Property Protection
As a hardware designer or a company, you want to protect your design intellectual property (IP) from being misused (by users, competitors, silicon foundry, etc). We will cover how you can build such protection during the design process which can be used as an evidence to support law enforcement protection. You are expected to understand the basic digital logic design knowledge covered in week 1. We will use several NP-hard problems as examples to illustrate the concepts of IP protection. These problems (graph vertex coloring problem and graph partitioning problem) will be introduced in the lecture and you do not need to know the concept of NP-complete.
Meet the Instructors
Gang QuAssociate Professor
Electrical and Computer Engineering
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.
Explore our Catalog
Join for free and get personalized recommendations, updates and offers.
Coursera provides universal access to the world’s best education,
partnering with top universities and organizations to offer courses online.
© 2019 Coursera Inc. All rights reserved.
