Comprehensive software protection system

• US 5,123,045 A
• Filed: 02/07/1990
• Issued: 06/16/1992
• Est. Priority Date: 08/18/1989
• Status: Expired due to Fees

• Current Assignee: Massachusetts Institute of Technology
• Original Assignee: Massachusetts Institute of Technology
• Inventors: Ostrovsky, Rafail, Goldreich, Oded
• Primary Examiner(s): Swann, Tod
• Application Number:
  US07/476,814
• Time in Patent Office: 860 Days
• Field of Search: 380/3, 380/4, 380/46, 364/246.6, 364/255.1, 364/255.8, 364/949.81, 364/961, 364/961.2, 364/969
• US Class Current: 713/190
• CPC Class Codes: G06F 12/1408 by using cryptography for digital transmission H04L9/00
• CPC Class Codes: G06F 21/123 by using dedicated hardware, e.g. dongles, smart cards, cryptographic processors, global positioning systems [GPS] devices
• CPC Class Codes: G06F 21/79 in semiconductor storage media, e.g. directly-addressable memories

Abstract

An efficient software protection scheme is presented in which a data processing system provides comprehensive software protection using hardware and software measures. Specifically, it provides protection of the pattern of access to memory during execution of a program and also provides protection of the data stored in memory. The protection scheme is secure in the sense that it behaves like a black box which reveals no information other than the I/O behavior and running time. Thus, not only the values stored in the general purpose memory are hidden, but also the sequence in which memory location are accessed during execution is hidden. This comprehensive scope of protection is achieved by an extremely efficient scheme. In particular, if the running time of the original program it T, the running time of the protected program is only slower by some factor of (logT)^C where C is a small constant.

Claims

1. In a data processing system, a method for efficiently protecting an access pattern of an executing program to a plurality of unprotected addressable locations using a physically protected resource comprising the steps of:

a) permuting an order in which values are stored in the unprotected addressable locations prior to beginning execution of the program;

b) partially permuting an order in which values are stored in subsets of the unprotected addressable locations at various times during execution of the program, the partial permuting step including transferring values from one subset of the unprotected addressable locations to another subset of the unprotected addressable locations; and

c) accessing the values at the unprotected addressable locations in light of the order imposed by the permuting step and the partial permuting step wherein access is achieved in a pattern independent of the original access pattern.

2. A method as recited in claim 1 wherein the number of unprotected addressable locations may be dynamically altered during execution of the program.

3. A method as recited in claim 1 wherein the permuting step and partial permuting step are performed using a pseudo-random function having a seed stored in the physically protected resource.

4. A method as recited in claim 1 wherein the frequency at which the partial permuting occurs during execution of the program for a subset of unprotected addressable locations depends on how many values are in the subset of unprotected addressable locations.

5. A method as recited in claim 1 wherein each subset of unprotected addressable locations is unique and does not share elements with other subsets.

6. A method as recited in claim 1 wherein there are log N order of magnitude subsets of unprotected addressable locations where N is the total number of unprotected addressable locations.

7. A method as recited in claim 6 wherein each subset has a unique level i associated with it that is designated by an integer in the range from 1 to log N.

8. A method as recited in claim 7 further comprising moving the values stored in subset of level i to a subset of level i+1 every K^i-1 steps where K is a constant.

9. A method as recited in claim 8 wherein moving further comprises partially permuting the subset of level i+1.

10. A method as recited in claim 1 further comprising the step of encrypting all values before storing them in the unprotected addressable locations.

11. A method as recited in claim 1 wherein the unprotected addressable locations comprise random access memory locations.

12. A method as recited in claim 1 wherein the unprotected addressable locations comprise entries in a distributed data base.

13. A method as recited in claim 1 wherein the unprotected addressable locations comprise a compound data structure.

14. A method as recited in claim 1 wherein each subset of unprotected addressable locations comprises a hash table.

15. In a data processing system, a method of hiding from an observer a pattern of access to memory by a program, comprising the steps of:

a) storing the program and the data the program uses, comprised of a plurality of virtual memory locations specified by virtual addresses, in a highest level buffer of a set of buffers held in the memory wherein a physical address of a physical memory location in which a virtual memory location is stored is specified by a pseudo-random function of its virtual address;

b) accessing each buffer whenever a memory access is sought;

c) when a virtual memory location in a buffer is located by the program, moving contents of the location to a lowest level buffer; and

d) when a buffer is full, moving its contents to a next higher priority buffer and pseudo-randomly rearranging the sequence in which the virtual memory locations are held in the next higher priority buffer.

16. A method as recited in claim 15 wherein the step of moving contents of a location in a buffer to a next level buffer comprises moving the contents to a location specified by a pseudo-random function of a virtual address of the contents.

17. A method as recited in claim 15 wherein the set of buffers comprises a set of hash tables.

18. In a data processing system a method of protecting a virtual address pattern of a program to a memory from an observer such that a physical address pattern of access of the program to the memory exhibited during execution of the program reveals no information about the virtual address pattern of the program to the memory, comprising the steps of:

a) storing the program and the data, said program and data being comprised of a plurality of virtual memory locations specified by virtual addresses, in a level N buffer of a set of N buffers held in the memory, each buffer comprised of X^L buckets where L is the level of the buffer and X is the number of buckets in a level 1 buffer, and for each virtual memory location, a physical address of a bucket comprised of physical memory locations in a buffer in which it is stored is specified by a pseudo-random function of its virtual address;

b) scanning at least one bucket in each buffer when seeking a virtual memory location required for execution;

c) moving the contents of a virtual memory location of a bucket in a buffer required for execution when it is found to a bucket in the level 1 buffer; and

d) periodically during program execution, moving contents of a level L buffer to a level L+1 buffer such that each memory location is stored at an address in the level L+1 buffer that is a pseudo-random function of a virtual address.

19. A method as recited in claim 18 wherein the buffers are hash tables.

20. A method as recited in claim 18 wherein the pseudo-random functions are hash functions.

21. In a data processing system, a method of hiding a pattern of access by a program, comprising the steps of:

a) storing the program and data the program uses, said program and data being comprised of a plurality of virtual memory locations having virtual addresses, in a highest level hash table of a set of hash tables that are organized into levels from lowest to highest, each hash table comprised of a plurality of buckets of physical memory locations and having a unique seed associated with it for a pseudo-random hash function;

b) executing the program;

c) scanning at least one bucket in each buffer when seeking a virtual memory location needed by the program for execution;

d) moving contents of a bucket where virtual memory location required by the program for execution has been found to the lowest level hash table; and

e) at fixed time intervals, moving contents of a hash table to a next highest level hash table such that each virtual memory location previously held in the hash table is stored at a bucket in the next highest hash table whose address is determined by the pseudo-random function.

22. A method as recited in claim 21 further comprising the step of storing the seeds for the pseudo-random hash function in memory.

23. In a data processing system, having a memory comprised of a plurality of buffers wherein each buffer is assigned a level designated by an integer value and each buffer is comprised of a plurality of buckets of physical memory locations, a method of accessing memory locations when executing a program so as to not reveal a virtual address access pattern, comprising the steps of:

a) calculating a bucket address using a pseudo-random function of a virtual address of a virtual memory location sought to be accessed;

b) examining memory contents at the bucket address to determine if the virtual memory location sought is held there;

c) if the virtual memory location is not held there, calculating another bucket address for a next buffer using a pseudo-random function of the virtual address of the virtual memory location sought to be accessed;

d) examining memory contents at the bucket address of the next buffer to determine if the virtual memory location sought is there; and

e) if the virtual memory location is there, acting on the virtual memory location as dictated by the program and if it is not there, repeating steps c through d until the virtual memory location is found.

24. A method as recited in claim 23 wherein calculating a bucket address comprises determining a value of a pseudo-random hash function of the virtual address.

25. A method as recited in claim 23 further comprising the step of moving contents of a buffer to a next level buffer and rehashing the next level buffer.

26. A method as recited in claim 23 further comprising the step of copying contents of a bucket into a lowest level buffer if the virtual memory location is found.

27. A method as recited in claim 23 wherein all bucket addresses are calculated using a same pseudo-random function but with different seeds for each buffer.

28. A method as recited in claim 23 further comprising the step of performing false accesses to all buffers yet to be examined if the virtual memory location is found in the buffer so that it is not apparent to an observer which buffer holds the virtual memory location.

29. In a data processing system having a memory and physically protected CPU, a method of preventing an adversary from replacing contents of a physical memory location with contents from another physical memory location during execution of a program comprising the steps of:

a) storing a seed for a pseudo-random function in a memory;

b) storing in each memory location a data value, a virtual address and a value of a pseudo-random function of the data value, wherein a seed of the pseudo-random function is the seed stored in the physically protected memory space;

c) checking using the CPU after each memory access to the memory locations in the memory whether a proper pseudo-random function value was stored in the accessed memory location; and

d) if an improper pseudo-random function value was stored, terminating execution of the program.

30. In a data processing system having a memory, a method of preventing an adversary from replacing contents of a physical memory location with a previously held contents of said physical memory location during executing of a program, comprising the steps of:

a) storing a seed for a pseudo-random function in a memory space accessible by the physically protected CPU, said CPU and memory space being inaccessible to the adversary;

b) incrementing a counter each time the memory is shuffled;

c) storing in each memory location a data value, a counter value corresponding to the counter'"'"'s current value, and a value of the data value, a pseudo-random function wherein the pseudo-random function is a function of the data value, and a seed for the pseudo-random function is stored in the physically protected memory space;

d) checking for each memory access to the memory locations in the memory whether a proper counter value was stored in the accessed memory location; and

e) if an improper counter value was stored, terminating execution of the program.

31. A method as recited in claim 30 further comprising the step of encrypting the data values before storing them in the memory locations.

32. In a data processing system, a memory for protecting a program from adversaries, comprising:

a) a lowest level buffer comprised of X buckets of memory;

b) a highest level buffer comprised of X^N buckets of memory wherein N is a total number of buffers;

c) N-2 buffers each having a unique level between the lowest level and the highest level and each having X^L buckets where L is a level of the buffer;

wherein address spaces of the buffers pseudo-randomly map from virtual addresses of the program and data that the program uses, and virtual memory locations of the program and the data are stored in the buffers in accordance with the pseudo-random mappings.

33. A memory as recited in claim 32 wherein the buckets have multiple memory locations.

34. A memory as recited in claim 33 wherein the buckets have a constant number of memory location K, where 2K is an infeasible calculation.

35. A memory as recited in claim 32 wherein the buffers are comprised of hash tables.

36. A memory as recited in claim 32 wherein the pseudo-random mapping of the virtual addresses of the program to the address spaces of the buffers is performed by a hash function.

37. A memory as recited in claim 36 wherein a unique seed is associated with each level buffer and the seed is used by a pseudo-random function to implement the pseudo-random mapping.

38. In a data processing system, a method for efficiently protecting an access pattern of an executing program to a plurality of unprotected addressable locations using a physically protected resource comprising the steps of:

a) permuting an order in which values are stored in the unprotected addressable locations prior to beginning execution of the program;

b) partially permuting an order in which values are stored in subsets of the unprotected addressable locations at various times during execution of the program, the frequency at which the partial permuting occurs during execution of the program for a subset of unprotected addressable locations depending on how many values are in the subset of unprotected addressable locations; and

c) accessing the values at the unprotected addressable locations in light of the order imposed by the permuting step and the partial permuting step wherein access is achieved in a pattern independent of the original access pattern.

39. In a data processing system, a method for efficiently protecting an access pattern of an executing program to a plurality of unprotected addressable locations using a physically protected resource comprising the steps of:

a) permuting an order in which values are stored in the unprotected addressable locations prior to beginning execution of the program;

b) partially permuting an order in which values are stored in subsets of the unprotected addressable locations at various times during execution of the program, each subset of unprotected addressable locations being unique and not sharing elements with other subsets; and

c) accessing the values at the unprotected addressable locations in light of the order imposed by the permuting step and the partial permuting step wherein access is achieved in a pattern independent of the original access pattern.

40. In a data processing system, a method for efficiently protecting an access pattern of an executing program to a plurality of unprotected addressable locations using a physically protected resource comprising the steps of:

a) permuting an order in which values are stored in the unprotected addressable locations prior to beginning execution of the program;

b) partially permuting an order in which values are stored in subsets of the unprotected addressable locations at various times during execution of the program, there being log N order of magnitude subsets of unprotected addressable locations where N is the total number of unprotected addressable locations; and

c) accessing the values at the unprotected addressable locations in light of the order imposed by the permuting step and the partial permuting step wherein access is achieved in a pattern independent of the original access pattern.

41. A method as recited in claim 40 wherein each subset has a unique level i associated with it that is designated by an integer in the range from 1 to N.

42. A method as recited in claim 41 further comprising moving the values stored in subset of level i to a subset of level i+1 every K^i-1 steps where K is a constant.

43. A method as recited in claim 42 wherein moving further comprises partially permuting the subset of level i+1.

44. In a data processing system, a method for efficiently protecting an access pattern of an executing program to a plurality of unprotected addressable locations using a physically protected resource comprising the steps of:

a) permuting an order in which values are stored in the unprotected addressable locations prior to beginning execution of the program;

b) partially permuting an order in which values are stored in subsets of the unprotected addressable locations at various times during execution of the program, each subset of unprotected addressable locations comprising a hash table; and

c) accessing the values at the unprotected addressable locations in light of the order imposed by the permuting step and the partial permuting step wherein access is achieved in a pattern independent of the original access pattern.