Tamper resistant software encoding and analysis
The present invention relates generally to computer software, and more specifically, to a method and system of making computer software resistant to tampering and reverse-engineering. Tampering refers to changing computer software in a manner that is against the wishes of the original author, and is distinct from obscurity techniques which do not change the underlieing data or control flow of a program. Broadly speaking, the method of the invention is to analyse the effectiveness of various encoding techniques by measuring the number of possible decodings corresponding to a given encoded world. This analysis gave rise to a number of new data flow encoding techniques including alternative mixed encoding (a combination of linear and residue number encoding), and multinomial encoding.
1. An improved method of increasing the tamper-resistance and obscurity of computer software code comprising the steps of:
a) compiling unencoded original computer code into a data-flow-oriented form intermediate code;
b) selecting an encoding technique for a code fragment from said intermediate code;
c) determining a calculable measure of resistance for said encoding technique; and
d) in the event said measure of resistance satisfies a predetermined security requirement, applying said encoding technique to said code fragment to produce an encoded code fragment;
whereby said measure of resistance is an accurate measure of the size of the search space which an attacker must search when attempting to decode said encoded code fragment, thereby providing a measure of the workload faced by said attacker to achieve such decoding for improving security; and
wherein said step c) comprises:
calculating the number of possible candidate code fragments that correspond to said encoding technique for the linear encoding of a sum: R w ≧K n+1 /A, where:
R w is the number of possible candidate code fragments;
K is the range of variable in the system;
n is the number of encoded variables which are summed together in the linear encoding; and
A is the range of variables of a 1 , . . . , a n .
2. An improved method of increasing the tamper-resistance and obscurity of computer software code comprising the steps of:
a) compiling unencoded original computer code into a data-flow-oriented form intermediate code;
b) selecting an encoding technique for a code fragment from said intermediate code;
c) determining a calculable measure of resistance for said encoding technique; and
d) in the event said measure of resistance satisfies a predetermined security requirement, applying said encoding technique to said code fragment to produce an encoded code fragment;
whereby said measure of resistance is an accurate measure of the size of the search space which an attacker must search when attempting to decode said encoded code fragment, thereby providing a measure of the workload faced by said attacker to achieve such decoding for improving security; and
wherein step c) comprises:
calculating the number of possible candidate code fragments that correspond to said encoding technique for the linear encoding of a product: Rw equal to the product of the numbers of divisors of the integers x′-b 1 and y′-b 2 where:
Rw is the number of possible candidate code fragments;
x′=a 1 *x+b 1 ; and
y′=a 2 *y+b 2 .
3. An improved method of increasing the tamper-resistance and obscurity of computer software code comprising the steps of:
a) compiling unencoded original computer code into a data-flow-oriented form intermediate code;
b) selecting an encoding technique for a code fragment from said intermediate code;
c) determining a calculable measure of resistance for said encoding technique; and
d) in the event said measure of resistance satisfies a predetermined security requirement, applying said encoding technique to said code fragment to produce an encoded code fragment;
whereby said measure of resistance is an accurate measure of the size of the search space which an attacker must search when attempting to decode said encoded code fragment, thereby providing a measure of the workload faced by said attacker to achieve such decoding for improving security; and
wherein step c) comprises:
calculating the number of possible candidate code fragments that correspond to said encoding technique for a residue encoding: R w ≧S(p, k), where:
Rw is the number of possible candidate code fragments;
p=p 1 . . . p k ; and
S (x, k) is the number of different representations of integer x as a product of k mutually coprime numbers.
4. An improved method of increasing the tamper-resistance and obscurity of computer software code comprising the steps of:
a) compiling unencoded original computer code into a data-flow-oriented form intermediate code;
b) selecting an encoding technique for a code fragment from said intermediate code;
c) determining a calculable measure of resistance for said encoding technique; and
d) in the event said measure of resistance satisfies a predetermined security requirement, applying said encoding technique to said code fragment to produce an encoded code fragment;
whereby said measure of resistance is an accurate measure of the size of the search space which an attacker must search when attempting to decode said encoded code fragment, thereby providing a measure of the workload faced by said attacker to achieve such decoding for improving security; and
wherein step c) comprises:
calculating the number of possible candidate code fragments that correspond to said encoding technique for the residue encoding of a sum: R w ≧(n!+2 2n −1) * p 2 , where:
R w is the number of possible candidate code fragments;
p=p 1 ·p 2 . . . p n ; and
n is the number of elements that are being summed together.
5. An improved method of increasing the tamper-resistance and obscurity of computer software code comprising the steps of:
a) compiling unencoded original computer code into a data-flow-oriented form intermediate code;
b) selecting an encoding technique for a code fragment from said intermediate code;
c) determining a calculable measure of resistance for said encoding technique; and
d) in the event said measure of resistance satisfies a predetermined security requirement, applying said encoding technique to said code fragment to produce an encoded code fragment;
whereby said measure of resistance is an accurate measure of the size of the search space which an attacker must search when attempting to decode said encoded code fragment, thereby providing a measure of the workload faced by said attacker to achieve such decoding for improving security; and
wherein step c) comprises:
calculating the number of possible candidate code fragments that correspond to said encoding technique for the residue encoding of a product: R w ≧φ T (p), where:
Rw is the number of possible candidate code fragments;
p=p 1 ·p 2 . . . p n ;
φ(N) is the Euler function which is the number of positive integers coprime with (positive integer) N and less then N; and
T
=
∑
i
=
1
t
a
i
.
6. An improved method of increasing the tamper-resistance and obscurity of computer software code comprising the steps of:
a) compiling unencoded original computer code into a data-flow-oriented form intermediate code;
b) selecting an encoding technique for a code fragment from said intermediate code;
c) determining a calculable measure of resistance for said encoding technique; and
d) in the event said measure of resistance satisfies a predetermined security requirement, applying said encoding technique to said code fragment to produce an encoded code fragment;
whereby said measure of resistance is an accurate measure of the size of the search space which an attacker must search when attempting to decode said encoded code fragment, thereby providing a measure of the workload faced by said attacker to achieve such decoding for improving security; and
wherein step c) comprises:
calculating the number of possible candidate code fragments that correspond to said encoding technique for encoding using polynomials of several variables:
R w ≧φS; (p), where:
R w is the number of possible candidate code fragments;
p=p 1 ·p 2 . . . p n ;
φ(N) is the Euler function which is the number of positive integers coprime with (positive integer) N and less than N; and
S
=
∑
i
=
1
N
m
i
-
N
,
m i is the number of independent variables in the ith summand, and N is the number of summands.
7. An improved method of increasing the tamper-resistance and obscurity of computer software code comprising the steps of:
a) compiling unencoded original computer code into a data-flow-oriented form intermediate code;
b) selecting an encoding technique for a code fragment from said intermediate code;
c) determining a calculable measure of resistance for said encoding techniques;
d) in the event said measure of resistance satisfies a predetermined security requirement;
e) applying said encoding technique to said code fragment to produce an encoded code fragment; and
f) repeating steps b) through e) to produce multiple encoded code fragments;
whereby said measure of resistance is an accurate measure of the size of the search space which an attacker must search when attempting to decode the particular encoded code fragment, thereby providing a measure of the workload faced by said attacker to achieve such decoding for improving security; and
wherein step c) comprises:
calculating the number of possible candidate code fragments that correspond to said encoding techniques for the linear encoding of a sum: Rw≧K n+1 /A, where:
Rw is the number of possible candidate code fragments;
K is the range of variable in the system;
n is the number of encoded variables which are summed together in the linear encoding; and
A is the range of variables of a 1 , . . . , a n .
8. An improved method of increasing the tamper-resistance and obscurity of computer software code comprising the steps of:
a) compiling unencoded original computer code into a data-flow-oriented form intermediate code;
b) selecting an encoding technique for a code fragment from said intermediate code;
c) determining a calculable measure of resistance for said encoding techniques;
d) in the event said measure of resistance satisfies a predetermined security requirement;
e) applying said encoding technique to said code fragment to produce an encoded code fragment; and
f) repeating steps b) through e) to produce multiple encoded code fragments;
whereby said measure of resistance is an accurate measure of the size of the search space which an attacker must search when attempting to decode the particular encoded code fragment, thereby providing a measure of the workload faced by said attacker to achieve such decoding for improving security; and
wherein step c) comprises:
calculating the number of possible candidate code fragments that correspond to said encoding technique for the linear encoding of a product: R w equal to the product of the numbers of divisors of the integers x′-b 1 and y′-b 2 where:
R w is the number of possible candidate code fragments;
x′=a 1 * x+b 1 ; and
y′=a 2 * y+b 2 .
9. An improved method of increasing the tamper-resistance and obscurity of computer software code comprising the steps of:
a) compiling unencoded original computer code into a data-flow-oriented form intermediate code;
b) selecting an encoding technique for a code fragment from said intermediate code;
c) determining a calculable measure of resistance for said encoding techniques;
d) in the event said measure of resistance satisfies a predetermined security requirement;
e) applying said encoding technique to said code fragment to produce an encoded code fragment; and
f) repeating steps b) through e) to produce multiple encoded code fragments;
whereby said measure of resistance is an accurate measure of the size of the search space which an attacker must search when attempting to decode the particular encoded code fragment, thereby providing a measure of the workload faced by said attacker to achieve such decoding for improving security; and
wherein step c) comprises:
calculating the number of possible candidate code fragments that correspond to said encoding technique for a residue encoding:
R w ≧S(p, k),
where:
R w is the number of possible candidate code fragments;
p=p1 . . . pk; and
S (x, k) is the number of different representations of integer x as a product of k mutually coprime numbers.
10. An improved method of increasing the tamper-resistance and obscurity of computer software code comprising the steps of:
a) compiling unencoded original computer code into a data-flow-oriented form intermediate code;
b) selecting an encoding technique for a code fragment from said intermediate code;
c) determining a calculable measure of resistance for said encoding techniques;
d) in the event said measure of resistance satisfies a predetermined security requirement;
e) applying said encoding technique to said code fragment to produce an encoded code fragment; and
f) repeating steps b) through e) to produce multiple encoded code fragments;
whereby said measure of resistance is an accurate measure of the size of the search space which an attacker must search when attempting to decode the particular encoded code fragment, thereby providing a measure of the workload faced by said attacker to achieve such decoding for improving security; and
wherein step c) comprises:
calculating the number of possible candidate code fragments that correspond to said encoding technique for the residue encoding of a sum:
R w ≧(n!+2 2n −1) * p 2 , where:
R w is the number of possible candidate code fragments;
p=p 1 ·p 2 . . . p n ; and
n is the number of elements that are being summed together.
11. An improved method of increasing the tamper-resistance and obscurity of computer software code comprising the steps of:
a) compiling unencoded original computer code into a data-flow-oriented form intermediate code;
b) selecting an encoding technique for a code fragment from said intermediate code;
c) determining a calculable measure of resistance for said encoding techniques;
d) in the event said measure of resistance satisfies a predetermined security requirement;
e) applying said encoding technique to said code fragment to produce an encoded code fragment; and
f) repeating steps b) through e) to produce multiple encoded code fragments;
whereby said measure of resistance is an accurate measure of the size of the search space which an attacker must search when attempting to decode the particular encoded code fragment, thereby providing a measure of the workload faced by said attacker to achieve such decoding for improving security; and
wherein step c) comprises:
calculating the number of possible candidate code fragments that correspond to said encoding technique for the residue encoding of a product:
R w ≧φ T ;(p),
where:
R w is the number of possible candidate code fragments;
p=p 1 ·p 2 . . . p n ,
φ(N) is the Euler function which is the number of positive integers coprime with (positive integer) N and less then N; and
T
=
∑
i
=
1
t
α
i
.
12. An improved method of increasing the tamper-resistance and obscurity of computer software code comprising the steps of:
a) compiling unencoded original computer code into a data-flow-oriented form intermediate code;
b) selecting an encoding technique for a code fragment from said intermediate code;
c) determining a calculable measure of resistance for said encoding techniques;
d) in the event said measure of resistance satisfies a predetermined security requirement;
e) applying said encoding technique to said code fragment to produce an encoded code fragment; and
f) repeating steps b) through e) to produce multiple encoded code fragments;
whereby said measure of resistance is an accurate measure of the size of the search space which an attacker must search when attempting to decode the particular encoded code fragment, thereby providing a measure of the workload faced by said attacker to achieve such decoding for improving security; and
wherein step c) comprises:
calculating the number of possible candidate code fragments that correspond to said encoding technique for encoding using polynomials of several variables.
R w ≧φ S ; (p) where:
R w is the number of possible candidate code fragments;
p=p 1 ·p 2 . . . p n ;
φ(N) is the Euler function which is the number of positive integers coprime with (positive integer) N and less than N; and
S
=
∑
i
=
1
N
m
i
-
N
,
m i is the number of independent variables in the ith summand, and N is the number of summands.