Systems and methods for implementing an encrypted search index

• US 9,501,661 B2
• Filed: 06/30/2014
• Issued: 11/22/2016
• Est. Priority Date: 06/10/2014
• Status: Active Grant

• Current Assignee: Salesforce.com, Inc.
• Original Assignee: Salesforce.com, Inc.
• Inventors: Kumar, Mukul Raj, Peddada, Prasad
• Primary Examiner(s): MOORTHY, ARAVIND K
• Application Number:
  US14/320,135
• Publication Number:
  US 20150356314A1
• Time in Patent Office: 876 Days
• Field of Search: 713/165, 726/2, 707/694, 707/706, 707/711, 707/737
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2228 Indexing structures
• CPC Class Codes: G06F 16/2272 Management thereof
• CPC Class Codes: G06F 16/2455 Query execution
• CPC Class Codes: G06F 16/355 Class or cluster creation or modification
• CPC Class Codes: G06F 16/93 Document management systems
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06F 21/6209 to a single file or object, e.g. in a secure envelope, encrypted and accessed using a key, or with access control rules appended to the object itself
• CPC Class Codes: G06F 21/6218 to a system of files or objects, e.g. local or distributed file system or database
• CPC Class Codes: G06F 21/6227 where protection concerns the structure of data, e.g. records, types, queries
• CPC Class Codes: G06F 21/6245 Protecting personal data, e.g. for financial or medical purposes
• CPC Class Codes: G06F 21/6254 by anonymising data, e.g. decorrelating personal data from the owner's identification
• CPC Class Codes: G06F 2221/2107 File encryption
• CPC Class Codes: H04L 63/08 for authentication of entities cryptographic mechanisms or cryptographic arrangements for entity authentication H04L9/32

Abstract

A search index stored within the system having a plurality of individual search index files having information stored therein. At least one of the individual search index files constitutes a term dictionary or a term index type file having internal structure that allows a portion of the individual search index file to be updated, encrypted, and/or decrypted without affecting the internal structure of the individual search index file. A file input/output (IO) layer encrypts the information being written into the individual search index file and to decrypt the information being read from the individual search index file. The file TO layer encrypts and decrypts only a portion of the individual search index file in reply to an operation without requiring decryption or encryption of the individual search index file in its entirety. A query interface executes the operation against the information stored in the memory in its decrypted form.

Claims

1. A system to execute within a host organization, wherein the system comprises:

a processor and a memory to execute instructions at the system;

a search index stored on disk within the system comprised of a plurality of individual search index files, each of the individual search index files being accessible as a random access file, the search index having information stored therein, wherein at least one of the individual search index files constitutes a term dictionary or a term index type file having internal structure which allows a portion of the individual search index file to be updated, encrypted, and/or decrypted without affecting the internal structure of the individual search index file;

wherein the search index stores both customer data and non-customer data organized into sub-blocks, wherein sub-blocks having customer data therein do not contain non-customer data and wherein sub-blocks having non-customer data therein do not contain customer data;

a file input/output (TO) layer to encrypt the information being written into the individual search index file and to decrypt the information being read from the individual search index file, wherein the file IO layer encrypts and decrypts only a portion of the individual search index file in reply to an operation without requiring decryption or encryption of the individual search index file in its entirety; and

a query interface to execute the operation against the information stored in the memory in its decrypted form.

2. The system of claim 1, further comprising:

the memory to receive the information in its decrypted form from file IO layer during the process of receiving and processing the operation against the search index, the operation affecting at least the individual search index file amongst the plurality of individual search index files which make up the search index.

3. The system of claim 1, further comprising:

the file IO layer to encrypt and decrypt the information given an encryption key and Initialization Vector (IV), wherein the search processing components interacting with the file IO layer will receive decrypted customer data from the individual search index file when given a correct encryption key and IV and continue processing the operation and creating search results without any further knowledge of what or how encryption occurs within the disk'"'"'s file system.

4. The system of claim 1, wherein the file IO layer is a software implemented interface layer to encrypt and decrypt the information from at least the individual search index file of the search index at the IO level by interacting directly with and being bound uniquely to one or more of the plurality of individual search index files within the search index.

5. The system of claim 1:

wherein the operation is an update operation including at least a write operation of new or updated information into the individual search index file of the search index;

wherein the memory receives the information in its decrypted state via the file IO layer after receipt and during processing of the update operation as part of creating a return result responsive to the update operation;

wherein the query interface executes the update operation against the information in the memory in its decrypted state including at least performing the write operation of the new or updated information in the memory; and

wherein the file IO layer encrypts the information in the memory having at least the update or the addition thereto and writes the encrypted information back into the individual search index file of the search index.

6. The system of claim 1:

wherein the operation includes a read-only search query operation of the information previously stored in the individual search index file of the search index;

wherein the memory receives the information in its decrypted state via the file IO layer after receipt and during processing of the read-only search query operation as part of creating a return result responsive to the read-only search query operation;

wherein the query interface executes the read-only search query operation against the information in the memory in its decrypted state; and

wherein the file IO layer takes no further action on the information in the memory in its decrypted state subsequent to execution of the read-only search query operation.

7. The system of claim 6:

wherein the read-only search query operation comprises one of an exact term search or a wild card search, and wherein the exact term search or the wild card search is performed by the query interface against the information in its decrypted state in the memory.

8. The system of claim 1, wherein the search index is an Apache Lucene compatible type index to which random access is made to sub-portions of individual search index files within the search index and to which updates to the sub-portions of the individual search index files within the search index are made without affecting an internal structure of any individual search index file being accessed or updated within the search index.

9. The system of claim 1, wherein the at least one of the individual search index files comprises a plurality of terms delineated by internal structure of the search index, each term corresponding to at least a value for the term and a field within which the term is maintained.

10. The system of claim 9, wherein the individual search index file is divided into blocks and further wherein the blocks are divided into sub-blocks within which the customer data of the individual search index file and the non-customer data of the search index do not share any same sub-block.

11. The system of claim 10:

wherein the file TO layer encrypts all terms of the individual search index file as a single contiguous block including the customer data at rest as stored on disk within the individual search index file to reduce vulnerability of the customer data to frequency based attacks and/or reconstruction of the customer data from the search index.

12. The system of claim 9, wherein each term is marked with term information and a term suffix in accordance with an Apache Lucene compatible type index.

13. The system of claim 1, wherein the information comprises sensitive customer data having at least one of the following represented therein:

customer name, customer telephone number, customer email address, customer mailing address, customer salary data, customer financial data, customer heath records data, customer order history, customer preference data, customer payment information, and/or customer calendar data.

14. The system of claim 1:

wherein the individual search index file and storage of the information within the search index is implemented via the plurality of individual search index files as stored on disk within the system which are selectively retrieved and/or updated during the process of adding index documents or executing operations including search queries, add operations, delete operations, and update operations; and

wherein the query interface is operable to submit queries, including the operation, against the search index.

15. The system of claim 14:

wherein the database comprises a multi-tenant database system implemented by the host organization to store customer data and search index metadata on behalf of a plurality of separate and distinct customer organizations which utilize the multi-tenant database system; and

wherein each of the plurality of separate and distinct customer organizations which utilize the multi-tenant database system constitutes an entity selected from the group consisting of;

a separate and distinct remote organization, an organizational group within the host organization, a business partner of the host organization, or a customer organization that subscribes to cloud computing services provided by the host organization.

16. The system of claim 1:

wherein the customer data and the non-customer data do not share any same sub-block and divided into the sub-blocks accordingly; and

wherein access to the non-customer data cannot be directly associated with any specifically encrypted term from the term dictionary or the term index type file due to all terms of the term dictionary or the term index type file being encrypted as a single contiguous block.

17. A computer-implemented method to execute within a host organization having at least a processor and a memory therein, wherein the computer-implemented method comprises:

storing a search index on disk within the host organization, the search index comprised of a plurality of individual search index files, each of the individual search index files being accessible as a random access file, the search index and having information stored therein, wherein at least one of the individual search index files constitutes a term dictionary or a term index type file having internal structure which allows a portion of the individual search index file to be updated, encrypted, and/or decrypted without affecting the internal structure of the individual search index file;

wherein the search index stores both customer data and non-customer data organized into sub-blocks, wherein sub-blocks having customer data therein do not contain non-customer data and wherein sub-blocks having non-customer data therein do not contain customer data;

encrypting the information being written into the search index via a file input/output (TO) layer and decrypting the customer information being read from the search index via the file IO layer, wherein the file IO layer encrypts and decrypts only a portion of the search index in reply to an operation without requiring decryption or encryption of the individual search index file in its entirety; and

executing, via a query interface, the operation against the information stored in the memory in its decrypted form.

18. The computer-implemented method of claim 17, further comprising:

receiving the information in its decrypted state into the memory from the file IO layer in advance of executing the operation against the information in the memory.

19. The computer-implemented method of claim 17:

wherein the individual search index file comprises a plurality of terms delineated by internal structure of the individual search index file, each term corresponding to at least a value for the term and a field within which the term is maintained; and

wherein the method further comprises;

dividing the individual search index file into blocks, and

dividing the blocks into sub-blocks within which the customer data of the individual search index file and the non-customer data of the individual search index file do not share any same sub-block.

20. The computer-implemented method of claim 17:

wherein the host organization implements the method via computing architecture of the host organization including at least the processor and the memory;

wherein a user interface operates at a user client device remote from the host organization and communicatively interfaces with the host organization via a public Internet;

wherein the operation is received at the user interface of the user client device and communicated to the host organization via the public Internet; and

wherein the host organization operates as a cloud based service provider to the user client device.

21. The computer-implemented method of claim 17, wherein the host organization provides a multi-tenant database system which implements the search index executing via computing architecture of the host organization, the multi-tenant database system having elements of hardware and software that are shared by a plurality of separate and distinct customer organizations, each of the separate and distinct customer organizations being remotely located from the host organization.

22. Non-transitory computer readable storage media having instructions stored thereon that, when executed by a processor of a system, the instructions cause the system to perform operations comprising:

storing a search index on disk within the host organization, the search index comprised of a plurality of individual search index files, each of the individual search index files being accessible as a random access file, the search index having information stored therein, wherein at least one of the individual search index files constitutes a term dictionary or a term index type file having internal structure which allows a portion of the individual search index file to be updated, encrypted, and/or decrypted without affecting the internal structure of the individual search index file;

wherein the search index stores both customer data and non-customer data organized into sub-blocks, wherein sub-blocks having customer data therein do not contain non-customer data and wherein sub-blocks having non-customer data therein do not contain customer data;

encrypting the information being written into the search index via a file input/output (TO) layer and decrypting the customer information being read from the search index via the file IO layer, wherein the file IO layer encrypts and decrypts only a portion of the search index in reply to an operation without requiring decryption or encryption of the individual search index file in its entirety; and

executing, via a query interface, the operation against the information stored in the memory in its decrypted form.

23. The non-transitory computer readable storage media of claim 22, wherein the instructions cause the system to perform operations further comprising:

receiving the information in its decrypted state into the memory via the file IO layer after receipt and during processing of the operation as part of creating a return result responsive to the operation.

24. The non-transitory computer readable storage media of claim 22:

wherein the individual search index file comprises a plurality of terms delineated by internal structure of the individual search index file, each term corresponding to at least a value for the term and a field within which the term is maintained; and

wherein the instructions cause the system to perform operations further comprising;

dividing the individual search index file into blocks, and

dividing the blocks into sub-blocks within which the customer data of the individual search index file and the non-customer data of the individual search index file do not share any same sub-block.