Intellectual property metering(10)

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

the main flow of the program when a special function is invoked from command or highly unlikely data input. Our preferred mode is to use don’t care conditions in the control flow of the program to enter the ID module. Program obfuscation can be used to protect the module isolation and altering against attacks. The module may have either dynamic data structures as information carrier or can just create a particular output sequence.

In addition to mechanism differences, there two other key differences between the schemes discussed in [8] and the one just proposed. The first is that our goal is different:instead of watermarking, we want only creation of distinct copies. This condition makes not only the software mutation task easier, but also induces low size and/or performance overhead. The second difference is even more important. Our primary technical goal is to enable rapid ID authentication for a software component/product. Therefore, the idea is to create versions that rapidly create different IDs that can be verified against database of produced copies. Note that our technique can be used, with straightforward modification,also for software watermarking. The final alternative to software metering which we dis-cuss is conceptually most complex, but also potentially most rewarding. The idea is to alter software in such a way that each output produces by different version of the software which differs from each other. This can be easily achieved by postprocessing the final out-put within the software. More interestingly, it can be demonstrated that in many cases one can systematically alter software in such a way that the functionality is essentially pre-served. Typical example include word processing, large scale optimization and computer-aided design packages.

5 Detection: Mathematical Model and Results

In this section, we will address problems P3 and P4 proposed in Section 3. Suppose the design house asks the foundry to fabricate n copies and N Š n is the number that the foundry really makes. P3 asks the expected number of tests to find a duplicate if N > n or the number of tests to convince designer that N = n . P4 requires an estimation of N once the first unauthorized is found. We take the dishonest foundry’s best strategy in that he

makes duplicates for each original copy. It is proven that for a fixed , the dishonest foundry has the best chance to survive in this equiprobable case.

Theorem 5.1. Draw l from objects which consist of k copies of n distinct ones,

the probability that there is no duplicate, denoted by Prob[n,k,l], is

(1)

which has an upper bound

(2)

where .

Prob[n,k,l] is the probability that there are no unauthorized parts found after l random tests (without replacement), provided that there are k copies for each of the n originals. It decreases as k increases, since when the population (N ) grows, it becomes more difficult to find duplicates; it also decreases as l , the number of tests, increases.

The quantity 1-Prob[n,k,l] is the confidence that the designer can achieve from l con-secutive successful tests. Success means that no duplicate is found. Table 1 shows some k 1–N k n ⋅=N k n ⋅=1k 1–N 1–------------–12k 1–()N 2–-------------------–…1l 1–()k 1–()N l 1–()–-------------------------------–⋅1p n --–12p ⋅n ---------–…1l 1–()p ⋅n ----------------------–⋅p 11k ⁄–=