Systems and methods for implementing an encrypted search index

• US 10,025,951 B2
• Filed: 11/04/2016
• Issued: 07/17/2018
• 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:
  US15/344,353
• Publication Number:
  US 20170053134A1
• Time in Patent Office: 620 Days
• Field of Search: 713165, 726 2, 707694, 707706, 707711, 707737
• 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

An encrypted search index is disclosed. For instance, an exemplary system may include a search index stored on disk with customer information stored therein, the search index files having 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; a file input/output (IO) layer to encrypt the customer information being written into the individual search index file and to decrypt the customer information being read from the individual search index file; and a query interface to execute the operation against the customer information stored in the memory in its decrypted form.

Claims

1. A system comprising:

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

disk storage of the system having a search index stored thereupon comprised of a plurality of individual search index files, the search index having customer information stored therein;

wherein at least one of the individual search index files constitutes a term dictionary or a term index type file having an 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 information and non-customer data organized into sub-blocks, wherein sub-blocks having customer information therein do not contain non-customer data and wherein sub-blocks having non-customer data therein do not contain customer information;

a query interface, to execute via the processor and memory of the system, wherein the query interface is to receive an incoming search query;

a file input/output (TO) layer to encrypt the customer information being written into the individual search index file and to decrypt the customer information being read from the individual search index file based on the incoming search query without requiring decryption or encryption of the individual search index file in its entirety; and

the query interface to execute the incoming search query and return outgoing search results including at least a portion of the customer information in decrypted form.

2. The system of claim 1, further comprising:

the memory to receive the customer information in its decrypted form from file IO layer during the process of receiving and processing the incoming search query against the search index, the incoming search query 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 customer information given an encryption key and Initialization Vector (IV), wherein the search processing components interacting with the file IO layer will receive decrypted customer information from the individual search index file when given a correct encryption key and IV and continue processing the incoming search query 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 implements a software implemented interface layer to encrypt and decrypt the customer 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 incoming search query is an update operation including at least a write operation of new or updated customer information into the individual search index file of the search index;

wherein the memory receives the customer 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 customer information in the memory in its decrypted state including at least performing the write operation of the new or updated customer information in the memory; and

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

6. The system of claim 1:

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

wherein the memory receives the customer 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 customer information in the memory in its decrypted state; and

wherein the file TO layer takes no further action on the customer 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 customer 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 information 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 1, wherein every sub-block of the search index stores exclusively non-customer data or customer information and wherein no sub-block stores both customer data and non-customer data within a same sub-block so as to reduce vulnerability of the customer information to frequency based attacks and to negate reconstruction of the customer information from the search index.

12. The system of claim 1, wherein the customer information includes one or more of:

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

13. The system of claim 1, further comprising a multi-tenant database system operating within a host organization to store the customer information;

wherein the host organization hosts the query interface; and

wherein the multi-tenant database system is to execute the incoming search query against the search index of the system and is to return the outgoing search results including at least a portion of the customer information via the query interface hosted by the host organization.

14. The system of claim 13:

wherein the host organization provides cloud computing services to 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 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 the cloud computing services provided by the host organization.

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

storing a search index on disk storage within the system, the search index comprised of a plurality of individual search index files, the search index having customer information stored therein;

wherein at least one of the individual search index files constitutes a term dictionary or a term index type file having an 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;

storing, via the search index on disk storage, both customer information and non-customer data organized into sub-blocks, wherein sub-blocks having customer information therein do not contain non-customer data and wherein sub-blocks having non-customer data therein do not contain customer information;

receiving an incoming search query via a query interface;

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 based on the incoming search query without requiring decryption or encryption of the individual search index file in its entirety; and

executing, via the query interface, the incoming search query and return outgoing search results including at least a portion of the customer information in decrypted form.

16. The computer-implemented method of claim 15, wherein every sub-block of the search index stores exclusively non-customer data or customer information and wherein no sub-block stores both customer data and non-customer data within a same sub-block so as to reduce vulnerability of the customer information to frequency based attacks and to negate reconstruction of the customer information from the search index.

17. The computer-implemented method of claim 15:

wherein the system comprises a multi-tenant database system operating within a host organization to store the customer information;

wherein the host organization provides cloud computing services to a plurality of separate and distinct customer organizations which utilize the multi-tenant database system and wherein the host organization hosts the query interface; and

wherein the multi-tenant database system is to execute the incoming search query against the search index of the system and is to return the outgoing search results including at least a portion of the customer information via the query interface hosted by the host organization.

18. 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 storage within the system, the search index comprised of a plurality of individual search index files, the search index having customer information stored therein;

wherein at least one of the individual search index files constitutes a term dictionary or a term index type file having an 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;

storing, via the search index on disk storage, both customer information and non-customer data organized into sub-blocks, wherein sub-blocks having customer information therein do not contain non-customer data and wherein sub-blocks having non-customer data therein do not contain customer information;

receiving an incoming search query via a query interface;

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 based on the incoming search query without requiring decryption or encryption of the individual search index file in its entirety; and

executing, via the query interface, the incoming search query and return outgoing search results including at least a portion of the customer information in decrypted form.

19. The non-transitory computer readable storage media of claim 18, wherein every sub-block of the search index stores exclusively non-customer data or customer information and wherein no sub-block stores both customer data and non-customer data within a same sub-block so as to reduce vulnerability of the customer information to frequency based attacks and to negate reconstruction of the customer information from the search index.

20. The non-transitory computer readable storage media of claim 18:

wherein the system comprises a multi-tenant database system operating within a host organization to store the customer information;

wherein the host organization provides cloud computing services to a plurality of separate and distinct customer organizations which utilize the multi-tenant database system and wherein the host organization hosts the query interface; and

wherein the multi-tenant database system is to execute the incoming search query against the search index of the system and is to return the outgoing search results including at least a portion of the customer information via the query interface hosted by the host organization.