Granted Patent B2

US 9,646,161 · App. 14/581,390 · Granted May 9, 2017

Inventors: Saghar Estehghari (La Tronche, FR); Nicolas Guerin (Notre-Dame-de-Mésage, FR)

Assignee: Xerox Corporation

G06F21/602G06F17/30595H04L9/0822H04L9/0825H04L9/0863H04L9/0866H04L9/3226H04L63/045H04L63/083H04L63/0807H04L63/0853

Abstract

Claims (32)

1. A computer-implemented method of fingerprinting a relational database associated with a computer memory with a unique identifier associated with a user of the relational database, the relational database configured to include a plurality of rows associated with a plurality of tuples, a plurality of attribute columns associated with each row, a plurality of unique primary keys wherein each primary key is associated with a unique row, and a plurality of attributes wherein each attribute is associated with a tuple and a respective attribute column, the method comprising:

a) generating a fingerprint bit string including a data user identification code and a secret key (k) unknown to the user and unique to the relational database; and

b) embedding the fingerprint bit string in the relational database by modifying a plurality of pseudorandomly selected attribute values in a plurality of respective rows, the pseudorandomly selected attribute values associated with one or more columns determined by an originator of the relational database to be tolerant of modifications,

wherein a pseudorandom function S(x) is used to determine a row, to determine an attribute to modify within the row and to determine a bit string index associated with a sequence of rows to embed the fingerprint bit string, the pseudorandom function S(y) seeded with one of the primary keys associated with the row and the primary key associated with the row concatenated with the secret key;

wherein the plurality of attributes include a plurality of data types, and the plurality of pseudorandomly selected attribute values are modified to embed the fingerprint bit based on one of a plurality of processes, where each process is associated with one distinct data type associated with the attribute; and

wherein the data types include one or more of a Float, Double, and Decimal, and the Float, Double and Decimal type attribute values are initially represented using normalized scientific notation of the attribute value of the form α* 10 b , where 1<|α|<10, and subsequently the least significant bit associated with α is modified.

2. The computer-implemented method of fingerprinting a relational database according to claim 1 , wherein the fingerprint bit string is the hash of the data user identification code and the secret key.

3. The computer-implemented method of fingerprinting a relational database according to claim 1 , wherein the length of the fingerprint bit string is at least 128bits and the length of the secret key is at least 64 bits.

4. A system for fingerprinting a relational database associated with a computer memory with a unique identifier associated with a user of the relational database, the relational database configured to include a plurality of rows associated with a plurality of tuples, a plurality of attribute columns associated with each row, a plurality of unique primary keys wherein each primary key is associated with a unique row, and a plurality of attributes wherein each attribute is associated with a tuple and a respective attribute column, the system comprising:

a fingerprinting component configured to generate a fingerprint bit string including a data user identification code and a secret key (k) unknown to the user and unique to the relational database; and

an embedding component configured to embed the fingerprint bit string in the relational database by modifying a plurality of pseudorandomly selected attribute values in a plurality of respective rows, the pseudorandomly selected attribute values associated with one or more columns determined by an originator of the relational database to be tolerant of modifications,

wherein a pseudorandom function S(x) is used to determine a row, to determine an attribute to modify within the row and to determine a bit string index associated with a sequence of rows to embed the fingerprint bit string, the pseudorandom function S(y) seeded with one of the primary keys associated with the row and the primary key associated with the row concatenated with the secret key;

wherein the plurality of attributes include a plurality of data types, and the plurality of pseudorandomly selected attribute values are modified to embed the fingerprint bit based on one of a plurality of processes, where each process is associated with one distinct data type associated with the attribute; and

wherein the data types include one or more of a Float, Double, and Decimal, and the Float, Double and Decimal type attribute values are initially represented using normalized scientific notation of the attribute value of the form α* 10 b , where 1<|α|<10, and subsequently the least significant bit associated with α is modified.

5. The system for fingerprinting a relational database according to claim 4 , wherein the fingerprint bit string is the hash of the data user identification code and the secret key.

6. The system for fingerprinting a relational database according to claim 4 , wherein the length of the fingerprint bit string is at least 128 bits and the length of the secret key is at least 64 bits.

7. A computer-implemented method of fingerprinting a relational database associated with a computer memory with a unique identifier associated with a user of the relational database, the relational database configured to include a plurality of rows associated with a plurality of tuples, a plurality of attribute columns associated with each row, a plurality of unique primary keys wherein each primary key is associated with a unique row, and a plurality of attributes wherein each attribute is associated with a tuple and a respective attribute column, the method comprising:

a) generating a fingerprint bit string including a data user identification code and a secret key (k) unknown to the user and unique to the relational database; and

b) embedding the fingerprint bit string in the relational database by modifying a plurality of pseudorandomly selected attribute values in a plurality of respective rows, the pseudorandomly selected attribute values associated with one or more columns determined by an originator of the relational database to be tolerant of modifications,

wherein a pseudorandom function S(x) is used to determine a row, to determine an attribute to modify within the row and to determine a bit string index associated with a sequence of rows to embed the fingerprint bit string, the pseudorandom function S(v) seeded with one of the primary keys associated with the row and the primary key associated with the row concatenated with the secret key;

wherein the plurality of attributes include a plurality of data types, and the plurality of pseudorandomly selected attribute values are modified to embed the fingerprint bit based on one of a plurality of processes, where each process is associated with one distinct data type associated with the attribute; and

wherein the data types include geographical data and the geographical data types are represented as a set of attributes including a latitude value including a decimal portion and longitude value including a decimal portion, wherein one of the latitude value or longitude value is modified by counting the number of digits in the decimal portion and if it includes less than 6 digits, the decimal portion is expanded as follows:

if the count is less than or equal to 3, concatenate 6−(count+2) zeros and a random number between 11 and 20 to an end of the value,

otherwise, concatenate 6−(count +1) zeros and a random number between 1 and 10 to the end of the value.

8. A system for fingerprinting a relational database associated with a computer memory with a unique identifier associated with a user of the relational database, the relational database configured to include a plurality of rows associated with a plurality of tuples, a plurality of attribute columns associated with each row, a plurality of unique primary keys wherein each primary key is associated with a unique row, and a plurality of attributes wherein each attribute is associated with a tuple and a respective attribute column, the system comprising:

a fingerprinting component configured to generate a fingerprint bit string including a data user identification code and a secret key (k) unknown to the user and unique to the relational database; and

an embedding component configured to embed the fingerprint bit string in the relational database by modifying a plurality of pseudorandomly selected attribute values in a plurality of respective rows, the pseudorandomly selected attribute values associated with one or more columns determined by an originator of the relational database to be tolerant of modifications,

wherein a pseudorandom function S(x) is used to determine a row, to determine an attribute to modify within the row and to determine a bit string index associated with a sequence of rows to embed the fingerprint bit string, the pseudorandom function S(y) seeded with one of the primary keys associated with the row and the primary key associated with the row concatenated with the secret key;

wherein the plurality of attributes include a plurality of data types, and the plurality of pseudorandomly selected attribute values are modified to embed the fingerprint bit based on one of a plurality of processes, where each process is associated with one distinct data type associated with the attribute; and

wherein the data types include geographical data and the geographical data types are represented as a set of attributes including a latitude value including a decimal portion and longitude value including a decimal portion, wherein one of the latitude value or longitude value is modified by counting the number of digits in the decimal portion and if it includes less than 6 digits, the decimal portion is expanded as follows:

if the count is less than or equal to 3, concatenate 6−(count +2) zeros and a random number between 11 and 20 to an end of the value,

otherwise, concatenate 6−(count +1) zeros and a random number between 1 and 10 to the end of the value.

Assignments (10)

Continuity (1)