Intellectual property metering(11)

Abstract. We have developed the first hardware and software (intellectual property) metering scheme that enables reliable low overhead proofs for the number of manufactured parts and copied programs. The key idea is to make each design slightly different d

examples for the case n =1000. For instance, after checking 50 products and not finding any duplicates, the designer believes that there does not exist another copy of 1000 chips with a 46.64% confidence. With the same result, the probability that the foundry makes 10000 instead of 1000 is less than 33% (1-67.37%). The designer’s confidence goes up quickly as more tests are conducted. After 100 successful tests, the designer will be 92.62% convinced of the foundry’s honesty.

One implication of Theorem 5.1 is the “Birthday Paradox” problem: among 24 peo-ple, with probability larger than one half, there will be two who share the same birthday,assuming all birth dates are equally distributed over the days in the year.

Theorem 5.1 not only gives formula on the designer’s confidence about foundry’s honesty, it also answers problem P3. As we mentioned, 1-Prob[n,k,l] measures the foundry’s honesty and it increases as l increases. For a designer to gain a desired level of

confidence α, we need to find the smallest l such that . Unfortu-nately, there is no exact closed form for formula (1), however, the solution can be always

found numerically and there exist good approximation formulas when n is large [14].

We assume that k is equally distributed and derive Theorem 5.2 which answers prob-lem P4 immediately.

Theorem 5.2. The probability that the first unauthorized is found at the l +1st test is

(3)

Corollary 5.3. The expected number of tests to find the first unauthorized is

(4)

Corollary 5.4. If the first failure occurs at l , then the expectation for k is

(5)

6 Global Design Flow

In this section, we address how to create many different copies of the systems that have the same functionality.1 We illustrate our approach using two problem instances that are

heavily used in the VLSI CAD, namely: graph coloring, and boolean satisfiability.

Table 1: Designer’s confidence after l consecutive successful tests l k=2 k=3 k=4 k=5 k=1010

2.24% 2.97%

3.33% 3.55% 3.98%20 9.15% 12.00% 13.38% 1

4.20% 1

5.82%50 4

6.64% 56.62% 60.87% 63.21% 6

7.47%75 76.34% 85.25% 8

8.33% 8

9.86% 92.33%100

92.62%

96.84%

97.73%

98.39%

99.02%

1.

1Prob n k l ,,[]α≥()–Pr n k l 1+,,[]Prob n k l ,,[]l l 1+()k 1–()

⋅⋅N l

–------------------------------------------⋅=l Pr n k l ,,[]⋅l 1

=n k 1–()1

+∑

k 1

=∞∑

k Pr n k l ,,[]⋅k 1

=∞∑