Obfuscating Transformations on Data Array Content and Addresses

Abstract

In a first computer (digital) data obfuscation process, data which is conventionally arranged in a data structure called an array (e.g., a table) and conventionally stored in computer or computer device memory is obfuscated (masked) by logically or mathematically combining the data, entry-by-entry, with a masking value which is computed as a logical or mathematical function of the entry itself or its index in the array, modulo a security value. The complementary unmasking value is a pointer to the entry's address in the table modulo the security value. In a second computer (digital) data obfuscation process, the addresses (location designations) in memory of a data array are themselves obfuscated (masked) by partitioning the array into blocks of entries and shuffling the order of the data entries in each block by a predetermined algorithm, resulting in a shuffled array also differing from the original array in terms of its size (the total number of entries).

1 - 27 . (canceled) 
     
     
         28 . A machine-implemented method of recovering original data from an obfuscated array of data, the method comprising:
 identifying an address of a particular entry of the obfuscated array in a physical memory, wherein the particular entry was obfuscated according to a first function;   computing a security parameter that depends on a primary memory address of the obfuscated array, wherein the primary address is a physical address of the first entry of the array;   computing an unmasking value by using a second function that takes as an input the identified address of the particular entry modulo the computed security parameter; and   computing an unobfuscated value of the selected entry by using an inverse of the first function that takes as input the particular entry of the obfuscated array and the unmasking value.   
     
     
         29 . The method of  claim 28 , wherein the second function is one of an affine, logical, and arithmetic function, wherein the first function is respectively affine, logical, or arithmetic. 
     
     
         30 . The method of  claim 28 , wherein the computation of the security parameter is based on a page number of the primary memory address. 
     
     
         31 . The method of  claim 28 , wherein the primary address modulo the security parameter equals a predetermined constant value. 
     
     
         32 . The method of  claim 28 , wherein computing an unobfuscated value comprises identifying the first function based on the address of the particular entry of the obfuscated array. 
     
     
         33 . The method of  claim 28 , wherein the second function is an invertible function. 
     
     
         34 . A non-transitory machine readable medium storing a program which when executed by at least one processing unit recovers original data from an obfuscated array of data, the program comprising sets of instructions for:
 identifying an address of a particular entry of the obfuscated array in a physical memory, wherein the particular entry was obfuscated according to a first function;   computing a security parameter that depends on a primary memory address of the obfuscated array, wherein the primary address is a physical address of the first entry of the array;   computing an unmasking value by using a second function that takes as an input the identified address of the particular entry modulo the computed security parameter; and   computing an unobfuscated value of the selected entry by using an inverse of the first function that takes as input the particular entry of the obfuscated array and the unmasking value.   
     
     
         35 . The non-transitory machine readable medium of  claim 34 , wherein the second function is one of an affine, logical, and arithmetic function, wherein the first function is respectively affine, logical, or arithmetic. 
     
     
         36 . The non-transitory machine readable medium of  claim 34 , wherein the computation of the security parameter is based on a page number of the primary memory address. 
     
     
         37 . The non-transitory machine readable medium of  claim 34 , wherein the primary address modulo the security parameter equals a predetermined constant value. 
     
     
         38 . The non-transitory machine readable medium of  claim 34 , wherein the set of instructions for computing an unobfuscated value comprises a set of instructions for identifying the first function based on the address of the particular entry of the obfuscated array. 
     
     
         39 . The non-transitory machine readable medium of  claim 34 , wherein the second function is an invertible function. 
     
     
         40 . A method of obfuscating the storage of an array of data in memory, the method comprising:
 identifying a security parameter;   allocating a portion of memory for an obfuscated array comprising a first set of entries for storing a second set of entries of a data array, wherein the second set of entries are in a particular order, a number of entries in the first set of entries is greater than a number of entries in the second set of entries, and the number of entries in the first set modulo the security parameter equals 0;   partitioning the portion of memory into a plurality of blocks, wherein each block comprises a subset of the first set of entries and is for storing a corresponding subset of the second set of entries; and   for each block, storing the corresponding entries of the data array in the block in a different order than the particular order of the entries in the data array.   
     
     
         41 . The method of  claim 40 , wherein the different order is determined according to an ordering function. 
     
     
         42 . The method of  claim 41  further comprising determining the ordering function from one of the addresses. 
     
     
         43 . The method of  claim 40 , wherein one or more entries in the obfuscated array do not correspond to any entry in the data array. 
     
     
         44 . The method of  claim 43 , wherein the one or more entries that do not correspond are in a last block of the plurality of blocks. 
     
     
         45 . The method of  claim 40 , wherein the number of entries in the first set of entries is equal to a number of entries in the second set of entries plus a result of a negative of the number of entries in the second set of entries modulo the security parameter. 
     
     
         46 . The method of  claim 40  further comprising determining the security parameter from one of the addresses. 
     
     
         47 . The method of  claim 40  further comprising constructing a constant table used for incrementing an obfuscated address by adding to the obfuscated address a value from the constant table, the value being found in the constant table as a function of the obfuscated address modulo the security parameter.