CN105303123A - Blocking confusion based dynamic data privacy protection system and method - Google Patents

Abstract

The invention discloses a blocking confusion based dynamic data privacy protection system and method. Newly inserted and modified data is cached through a trusted third party, and the data is grouped and stored when conditions are met; the privacy security of deleted data and residual data in a delete operation is ensured by keeping key fragmentations; and the reduction of storage resource consumption and the optimization of the application performance are realized by falsification of a data recycling mechanism. Experiments prove that the proposed dynamic data privacy protection mechanism is higher in feasibility and practicability.

Description

A dynamic data privacy protection system and method based on block obfuscation

technical field

The invention relates to a dynamic data privacy protection system and method based on block obfuscation.

Background technique

With the rapid development of cloud computing, SaaS applications with multi-tenant characteristics are adopted by more and more enterprises and service providers due to their low-cost, scale-effective business operation model and single-instance, on-demand software delivery features. .

In SaaS applications, on the one hand, tenants meet their own business needs through on-demand leasing and personalized customization, while saving high costs for infrastructure and subsequent upgrades, maintenance, and management. On the other hand, by signing a service level agreement (service level agreement, SLA) with the SaaS service provider, the service quality of the application is guaranteed, and the interests of both the tenant and the service provider are maintained.

However, with the widespread promotion and use of SaaS applications, the security of tenant private data in the cloud has also received more and more attention. In multi-tenant applications, in order to meet the needs of tenants for business operations on data, tenants' sensitive data usually needs to be stored and processed in plain text on non-fully trusted service providers, so that the tenant's private data is separated from the tenant's direct control, which may be maliciously leaked by the service provider. For example, driven by profit, a service provider may resell the product pricing information and customer relationship of a company that leases its application to its competitors, resulting in damage to the company's economic interests.

Aiming at the problem of tenant privacy leakage faced by SaaS applications, [1 ZhangKun, LiQingzhong, ShiYuliang. Research on DataCombinationPrivacyPreservationMechanismforSaaS[J]. Research on Combined Privacy Protection Mechanism [J]. Journal of Computer Science, 2010, 33(11): 2044-2054)] proposed a data combination privacy protection mechanism based on block obfuscation: firstly, the combined privacy Segment attributes into different blocks and confuse the relationship between different blocks; then, aiming at the privacy leakage problem caused by unbalanced data distribution in blocks, a balancing mechanism based on fake data is proposed, by adding fake data to make each block The block distribution is balanced; finally, the reconstruction mechanism of obfuscated data is constructed by interacting with a trusted third party to ensure the availability of tenants' private data.

Work [2ShiY, JiangZ, ZhangK.Policy-BasedCustomizedPrivacyPreservingMechanismforSaaSApplications[C]//GridandPervasiveComputing.BerlinHeidelberg:Springer,2013:491-500, (Policy-BasedCustomizedPrivacyPreservingMechanismforSaaSApplications)] and work[3ShaoY,ShiY, LiH.ANovelCloudDataFragmentationCluster-basedPrivacyPreservingMechanism[J].InternationalJournalofGrid&DistributedComputing, 2014,7(4):21-32, (a new cluster-based cloud data fragmentation privacy protection mechanism)] on this basis, respectively from different aspects Complements and optimizations. Work [2ShiY, JiangZ, ZhangK.Policy-BasedCustomizedPrivacyPreservingMechanismforSaaSApplications[C]//GridandPervasiveComputing.BerlinHeidelberg:Springer,2013:491-500, (Policy-BasedCustomizedPrivacyPreservingMechanismforSaaSApplications)]Tenant-based personalized privacy protection and transaction processing requirements, a policy-based personalized privacy protection mechanism is proposed. Work[3ShaoY, ShiY, LiH.ANovelCloudDataFragmentationCluster-basedPrivacyPreservingMechanism[J].InternationalJournalofGrid&DistributedComputing,2014,7(4):21-32, (a new cluster-based privacy protection mechanism for cloud data fragmentation)] Attributes are clustered, attributes with high correlations are divided into the same block as much as possible, and application performance is improved by reducing the number of connections between blocks.

However, in the cloud computing environment, with the continuous operation of multi-tenant applications, tenants' business operations such as adding, deleting, and modifying data will lead to continuous changes in the underlying data storage, and the distribution of each block will also change accordingly. When the data distribution is no longer uniform, the relationship between shards will face the risk of being leaked with a high probability. On the other hand, if the attacker can obtain the operation logs and data snapshots of each block in a local time, the private information contained in this part of the data can still be deduced through comparative analysis. This requires that the privacy protection mechanism adopted must be able to adapt to this change to ensure that the privacy protection needs of tenants are continuously met.

For privacy protection, data encryption and data obfuscation are currently two relatively mature solutions. However, the encrypted data often loses its operability, so improving the retrieval speed and processing efficiency of ciphertext is a research hotspot in encryption privacy protection. Literature [4Q.Liu, G.Wang, J.Wu.AnEfficientPrivacyPreservingKeywordSearchSchemeinCloudComputing[C]//inProceedingofthe2009InternationalConferenceonComputationalScienceandEngineering.Piscataway, NJ:IEEE,2009:715-720, (An Efficient Privacy-Preserving Keyword Search Scheme for Cloud Computing)] The characteristics of cloud computing are analyzed, and a keyword retrieval mode for privacy protection in the cloud is proposed. It supports service providers to participate in part of the decryption work to reduce the burden on the client, and at the same time implements keyword retrieval on encrypted data to protect Tenant data privacy and user query privacy. Literature [5C.Gentry.Fullyhomomorphic encryption using ideallattices[C]//inProceedingsofthe41stannualACMsymposiumonTheoryofcomputing.Bethesda:ACM,2009:169-178, (Fully homomorphic encryption technology based on ideal lattice)] uses the mathematical object of "ideallattice" to construct privacy Homomorphic (privacyhomomorphism) algorithm enables people to fully manipulate encrypted data. Encryption methods have a great impact on data processing performance, and researchers propose other methods to prevent privacy leaks. Literature [6RaymondChi-WingWong, LiJ, AdaWai-CheeFu, WangK. (α, k)-anonymity: An enhanced k-anonymity model for privacy-preserving data publishing [C] // Proceeding of the ACMSIGKDD International Conference on Knowledge Discovery and Data Mining. NewYork: ACM, 2006: 754-759, (an improved -Anonymized privacy-preserving data release model)] proposed (α,k)-anonymity principle, which ensures that the data table meets the k-anonymization principle, and requires records related to any sensitive attribute value in each equivalence class The percentage of α is not as high as α, so as to avoid attackers using consistency attack and background knowledge attack to confirm the connection between sensitive data and personal identity. The literature [7MachanavajjhalaA, KiferD, GehrkeJ, et al.l-diversity: Privacybeyondk-anonymity[J].ACMTransactionsonKnowledgeDiscoveryfromData(TKDD), 2007,1(1)] proposes the principle of l-diversity, which requires that the sensitive attributes of each equivalence class have at least l different values, so that the attacker can at most confirm the sensitive information of an individual with the probability of 1/l. The literature [8CirianiV, DiVimercatiSDC, ForestiS, et al. Fragmentation and encryption to enforce privacy in data storage [C]//Computer Security–ESORICS2007. Berlin Heidelberg: Springer, 2007: 171-186, (data storage privacy protection based on information decomposition and data encryption)] effectively combines information decomposition and Data encryption, proposes to use the concept of privacy constraints to achieve information decomposition, and proposes the concept of privacy constraints to describe the combination of data attributes that need to be protected by encryption and data attributes that will leak privacy at the same time. According to these privacy constraints, after information decomposition, A block pattern that meets the requirements is obtained, wherein the association relationship between each data block is saved in the client. Literature [9 OuyangJia, YinJian, LiuShaopeng, et al. An Effective Differential Privacy Transaction Data Publication Strategy [J]. Journal of Computer Research and Development, 2014, 51 (10): 2195-2205 (in Chinese) [J].Computer Research and Development, 2014,51(10):2195-2205)] Aiming at the lack of data security and utility published by transactional database privacy protection, an effective transactional data release strategy that satisfies differential privacy constraints is proposed TDPS, this strategy is based on itemset I, constructs a complete tree Trie of transaction database D, and then adds noise that meets the split privacy constraints to the complete tree based on compressed sensing technology to obtain a noisy Trie tree, and finally mines frequent itemsets from this tree tasks, data privacy is well protected. However, these studies mainly focus on privacy protection issues in the field of data publishing, and rarely involve the addition, deletion, and modification of private data.

For the privacy protection of dynamic data, many different methods have been proposed one after another, but these methods mainly solve the privacy protection of dynamic data in data publishing and data mining, and are not suitable for privacy protection in SaaS applications. .

J.Byun et al. were the first to discuss continuous growth in the literature [10ByunJW, SohnY, BertinoE, etal. The privacy protection of the data set has been studied accordingly. The idea is that new records must meet two restrictions to be inserted: one is that the number of records to be inserted cannot be less than a certain number, and the other is that the record set to be inserted must meet l- If the requirements of the diversity technology are not met, it cannot be inserted. This method has the problem that the data update is not timely and the update of the data is limited to the operation of inserting. Similarly, literature [11PeiJ, XuJ, WangZ, etal.Maintainingk-anonymityagainstincrementalupdates[C]//ScientificandStatisticalDatabaseManagement, 2007.SSBDM'07.19thInternationalConferenceon.Piscataway, NJ: IEEE, 2007:5-5] and literature [12ByunJW, LiT, BertinoE ,etal.Privacy-preservingincrementaldatadissemination[J].JournalofComputerSecurity,2009,17(1):43-68, (Maintenance of k-anonymization principle for insertion operation)]The method proposed in is only for privacy protection of data for insertion operation , and in SaaS applications, tenants need to frequently insert, delete, and modify data, so these methods are not suitable for SaaS applications. Literature [13XiaoX,TaoY.M-invariance:towardsprivacypreservingre-publicationofdynamicdatasets[C]//Proceedingofthe2007ACMSIGMODinternationalconferenceonManagementofdata.NewYork:ACM,2007:689-700, (M-invariance: privacy protection for dynamic dataset publishing process)] proposed m- The core idea of the invariance anonymity mechanism is that in any snapshot of the data set, a specified data record can only be placed in a shard with a fixed set of privacy attributes. value-dependent attacks. Literature[14HeY,BarmanS,NaughtonJF.Preventingequivalenceattacksinupdated,anonymizeddata[C]//DataEngineering(ICDE),2011IEEE27thInternationalConferenceon.Piscataway,NJ:IEEE,2011:529-540, (protection against equivalence attacks in anonymous data publishing)] Aiming at the problem of value equivalence attack in data publishing, in the literature [13XiaoX,TaoY. Based on the privacy protection of the dataset publishing process)], a graph-based anonymity algorithm is proposed using the "minimum cut" algorithm, which protects both value-related attacks and value-equivalent attacks. Literature [15NergizAE, CliftonC, MalluhiQM.Updatingoutsourcedanatomizedprivatedatabases[C]//Proceedingofthe16thInternationalConferenceonExtendingDatabaseTechnology.NewYork:ACM,2013:179-190, (Privacy protection of dynamically changing outsourced databases)] Aiming at the privacy protection of dynamically changing outsourced databases, in the data On the basis of decomposition, it is proposed to encrypt and store the data recently inserted and modified by the user in the outsourced database, save the encryption key on the client, and only delete part of the data containing identification information when deleting data. This method requires the client to save Encryption keys need to clearly distinguish identification information from sensitive information, and frequent encryption and decryption operations are required in business operations. In SaaS applications, tenants do not need to store any information or have any computing power, and tenants need to be able to personalize privacy requirements, and the specified privacy constraints often cannot clearly distinguish between identification information and sensitive information, so literature [15NergizAE, CliftonC, MalluhiQM.Updatingoutsourcedanatomizedprivatedatabases[C]//Proceedingofthe16thInternationalConferenceonExtendingDatabaseTechnology.NewYork:ACM,2013:179-190, (Privacy Protection of Dynamically Changing Outsourced Databases)] The privacy protection method in is not completely suitable for the dynamic privacy protection of SaaS applications.

Although the various methods proposed above have well dealt with various dynamic privacy protection problems in data publishing and data mining, due to the completely different characteristics of SaaS applications and data publishing, the above methods cannot be fully adapted to SaaS applications. . Work [1 Zhang Kun, Li Qingzhong, Shi Yuliang. Research on Data Combination Privacy Preservation Mechanism for SaaS [J]. Chinese Journal of Computers, 2010, 33 (11): 2044-2054 (in Chinese) (Zhang Kun, Li Qingzhong, Shi Yuliang. Research on Data Combination Privacy Preservation Mechanism for SaaS Applications [J]. Journal of Computer Science, 2010, 33(11):2044-2054)] Aiming at SaaS applications, a block-based privacy protection mechanism is proposed, which decomposes the combined privacy in tenant data into different data blocks according to the privacy constraints proposed by tenants , and hide the association between the shards, realize the SaaS data privacy protection in the plaintext state, ensure the continuous balance of data distribution in each block by inserting forged data, and prevent the service operator from leaking the tenant's data combination Privacy, but this document does not mention how to protect private data when tenants insert, delete, and modify data, and there is a danger of leaking data block associations.

With the rapid development of information technology, the collection, storage and analysis of data has become more convenient and faster, and the technical means have become more advanced and perfect. In real life, due to the imperfection of enterprise management and authority distribution, it often occurs in cloud computing services that service providers or database administrators (in this invention, the relevant personnel who maliciously disclose the privacy of tenants are collectively referred to as attackers) use various technical means to maliciously Obtain user data and its change records, and disclose user privacy after analysis. Although the tenant data has hidden the relationship between different shards through block obfuscation before being stored in the cloud, the attacker can still analyze the uneven distribution of each block after the data change or the data change log and the corresponding local data. Data snapshots are analyzed to obtain private information of some tenants. The following will use the example shown in Figure 1 to work [1 ZhangKun, Li Qingzhong, Shi Yuliang. Research on Data Combination Privacy Preservation Mechanism for SaaS [J]. Chinese Journal of Computers, 2010, 33 (11): 2044-2054 (in Chinese) (Zhang Kun, Li Qingzhong, Shi Yuliang. Research on Combined Privacy Protection Mechanism[J].Journal of Computer Science,2010,33(11):2044-2054)]Analyze the threat of privacy leakage and other deficiencies that the proposed privacy protection mechanism faces when tenants conduct business operations.

The Snapshot (T1) in Figure 1 is based on the work before the business operation [1 ZhangKun, Li Qingzhong, Shi Yuliang. Research on Data Combination Privacy Preservation Mechanism for SaaS [J]. Research on the data combination privacy protection mechanism of SaaS application[J].Journal of Computer Science,2010,33(11):2044-2054)] The proposed method divides the logical view of tenant data into blocks to obtain the physical storage mode of data objects, Snapshot (T2) is the physical storage mode of the data object obtained after the Snapshot (T1) is inserted, deleted and modified once respectively. Table 1 is the tenant's business operation log on the database during this period obtained through a certain tool or technology.

1) Leaking tenant privacy through operation logs and data snapshots

After the attacker obtains the data change log (Table 1) and the data snapshots Snapshot(T1) and Snapshot(T2) before and after the change, through the log, it can be found that three blocks are inserted and deleted at the same time. By comparing the Snapshot(T1) And Snapshot(T2), it can be inferred that the process deletes a piece of data about Bob and Bob suffers from the disease Measles, and adds a piece of data about Greg and Greg suffers from the disease Flu. Since the value of one slice is modified in Chunk2 and Chunk3 at the same time, it can be inferred that the disease information of the 43-year-old patient with the original zip code of 62000 has been changed from Measles to Flu and his zip code has also changed.

2) Inhomogeneous block data leads to leakage of tenant privacy

Assuming that the SLA agreement signed by the tenant stipulates that the attacker can only associate the fragmented data in different blocks with a probability of 1/3 at most. From the distribution of disease information in Snapshot (T1), it can be seen that when the data is updated Currently, there are three types of disease value information in the block: Cancer, Measles, and Flu, and the probability of occurrence of each value does not exceed 1/3, which meets the privacy protection level requirements specified by the tenant, that is, from other blocks Taking any shard, the maximum correct rate of accurately associating it with the corresponding disease information does not exceed 1/3. In the updated data distribution Snapshot (T2), there are only two disease values: Cancer and Flu, and the probability of Flu has increased to 2/3. If the attacker guesses that the disease a patient suffers from is Flu, then its correct rate will rise to 2/3. Obviously, the data distribution at this time has destroyed the privacy protection requirements proposed by the tenants.

Table 1 Database business operation log

3) The problem of spurious data surge caused by block equalization

In Figure 1, after the business operation is completed, the shards in Chunk3 have only two values: Cancer and Flu, and the value of Flu accounts for 2/3. At this time, to make it meet the privacy protection level requirement 1/3 specified by the tenant, the number of shards in Chunk3 needs to reach at least 12, that is, at least 6 pieces of fake data need to be inserted into Chunk3 for balance. At this time, the ratio of forged data to the total data volume will reach 1/2. In the cloud computing environment, with the sharp increase of user data volume, a high proportion of forged data will not only waste a lot of storage space, but also lead to A drastic drop in application performance. On the other hand, work [1 ZhangKun, Li Qingzhong, Shi Yuliang. Research on Data Combination Privacy Preservation Mechanism for SaaS [J]. Chinese Journal of Computers, 2010, 33(11): 2044-2054 (in Chinese) [J].Journal of Computer Science,2010,33(11):2044-2054)] The proposed balance strategy is achieved by continuously inserting fake fragments. As the application continues to run, the fake data in the system will always increase, while When the amount of data is large, if you want to achieve data balance by deleting fake data, you will need to pay a huge computational cost.

From the above example analysis, we can see that if the tenant's business operations are directly applied to the cloud data, not only will the private information of the tenant being operated this time be directly leaked, but also other private data in the table will be caused due to the data distribution in the block. Inhomogeneity causes leakage. In addition, an unreasonable balance mechanism will also cause the system to pay a large storage consumption and performance cost due to the high proportion of forged data.

Contents of the invention

The purpose of the present invention is to solve the above problems, and to provide a dynamic data privacy protection system and method based on block obfuscation, which caches the latest data inserted and modified by tenants in a trusted third party, and when the block conditions are met, then The data is divided into blocks and stored in the storage layer after being balanced in groups; for deletion operations, the data in key blocks and low-weight blocks are kept from being deleted, preventing attackers from reconstructing tenant privacy through data manipulation behavior; using The counterfeit data recovery mechanism recovers redundant counterfeit data in the storage layer, reduces the proportion of counterfeit data in the total data volume, effectively supports tenants’ business operations, and ensures the security of tenants’ private information during dynamic data changes.

In order to achieve the above object, the present invention adopts the following technical solutions:

A dynamic data privacy protection system based on block obfuscation, including:

The application layer is responsible for managing the application components for tenants to lease and customize, receives the data service processing requests submitted by the tenants and forwards the requests to the privacy protection layer for processing; the application layer can deploy a variety of different application components, each application Components can deploy multiple instances for load balancing;

The privacy protection layer is the core part of the dynamic data privacy protection framework, responsible for receiving and processing data business processing requests transferred from the application layer, and returning the processing results to the application layer; data business processing requests include data insertion requests and data deletion requests , data query request or data modification request;

The storage layer is responsible for storing tenant data and is the final executor of all data processing operations; the storage layer deploys multiple database instances, and the database instances use the same or different databases for deployment;

A trusted third party is responsible for managing the tenant's personalized privacy protection policy, and is also responsible for managing the latest inserted or modified data. It can identify the identity of the data tenant and prevent attackers from maliciously accessing the privacy protection policy and temporary data. and steal.

For data insertion requests, the newly inserted data is packaged and temporarily stored in a trusted third party;

For the data deletion request, the non-key block and the corresponding slice in the high-weight block are deleted in the storage layer; the non-key module refers to a block that does not contain key attributes;

For data query requests, the reconstruction module of the privacy protection layer will return the reconstruction results of the original data;

For data modification requests, the corresponding original data in the storage layer is deleted first, and then the modified data is packaged and temporarily stored in a trusted third party.

The privacy protection layer includes: update processing module, block processing module, balance module, reconstruction module and forged data recovery module;

The update processing module is responsible for receiving the business operation request delivered by the application layer, then analyzing the operation request type, performing different operation processes according to the operation request type, and returning the operation result to the application layer after the operation is completed; The type of operation request includes: insert, delete, modify and query; the update processing module also receives the data of the reconstruction module; the update processing module also stores the operation result in the storage layer; the update processing module also stores the authentication information in the authentication module; Store the temporary data in the temporary data management module;

The block processing module is responsible for performing vertical block on the new group generated by the temporary data management module; when a new group is delivered to the block processing module, it sends a request to the privacy policy management module to obtain the corresponding data block strategy, according to The block strategy divides the data vertically and stores the block data in the storage layer;

The equalization module obtains the data distribution state of each block from the block processing module, generates forged data satisfying α, β, and γ balance, and performs α, β, and γ balance on each block; the data distribution state refers to all The frequency of fragmentation values;

The forged data recovery module is responsible for periodically checking the grouping status, and judging whether the forged data of the grouping needs to be recovered according to the proportion of valid data in each grouping; for the grouping that needs to recover the forged data, transfer the remaining valid data in the grouping Go to the temporary data management module for cache processing, and then delete all the data grouped in each block;

The reconstructed block connects the original private data before the block according to the query, deletion or modification conditions submitted by the tenant in the business operation, and returns the global ID corresponding to the original data; the reconstructed module reads from the storage layer Take the block data, then reconstruct the block data, and feed back the reconstructed result to the update processing module.

The trusted third party includes: a privacy policy management module, an authentication module and a temporary data management module.

The authentication module is responsible for receiving the identity authentication information of the tenant, identifying the identity of the tenant, and preventing malicious attackers from accessing the corresponding privacy protection policy and temporary data according to the identification result, while allowing legitimate tenants to access the corresponding privacy protection policy and temporary data ;

The privacy policy management module is responsible for storing and accessing the tenant's personalized privacy protection policy, and transferring the corresponding tenant's privacy protection policy to the block processing module according to the tenant ID.

The temporary data management module is responsible for temporarily storing the newly inserted or modified data of the tenant, and horizontally grouping the temporary data according to the grouping conditions, and passing the grouped data to the block processing module after generating new groups. The grouping condition includes the size of the grouping and the distribution of data in the grouping;

A dynamic data privacy protection method based on block obfuscation, which caches newly inserted and modified data through a trusted third party, and groups and stores data when conditions are met; guarantees deletion by retaining key shards The privacy and security of deleted data and remaining data during operation; the reduction of storage resource consumption and the optimization of application performance are achieved through forged data recovery algorithms.

A dynamic data privacy protection method based on block obfuscation, comprising the following steps:

Step (1): The application component of the application layer is responsible for receiving the business operation submitted by the tenant, and forwarding the operation to the update processing module of the privacy protection layer;

Step (2): The update processing module analyzes the operation type, if it is an insert operation, then proceed to step (3), otherwise, execute step (7);

Step (3): The update processing module submits the tenant's identity information to the authentication module of the trusted third party for identification, and allows the tenant to access the temporary data management module after passing the authentication;

Step (4): The temporary data management module caches the newly inserted data in the form of plain text, and periodically checks whether the cached data meets the grouping conditions. If so, calls the group generation and block algorithm to generate a new group and uploads it to the block Processing module; if not reached, no processing will be done;

Step (5): If a new packet is uploaded to the block processing module, the block processing module requests the block policy of the corresponding tenant from the privacy policy management module of the trusted third party, and vertically divides the packet data according to the block policy. piece;

Step (6): The equalization module generates forged data according to the data distribution of each block, so that the data distribution of each block satisfies α, β and γ balance, and then stores the block data in the storage layer; the block data Including forged data and private data stored by users;

Step (7): The reconstruction module reconstructs the private data through the private data reconstruction algorithm, and judges whether it is a modification operation. If so, the original data is modified and assembled into new data, and then the original data is deleted, and the step ( 3), otherwise go to step (8);

Step (8): Determine whether to delete the operation, and if so, execute the data deletion algorithm to delete the corresponding fragments in the non-critical blocks and high-weight blocks of the storage layer. After the deletion is successful, call the forged data recovery algorithm through the forged data recovery module Check whether there is grouped forged data that needs to be recycled; otherwise, it is determined as a query operation, and step (9) is performed;

Step (9): Filter the query results according to the global identifier and query conditions calculated by the reconstruction module, and return the results to the tenant.

The insertion operation inserts the newly inserted data into the temporary update table after adding a global ID and a time stamp for temporary storage, and when the amount of data in the temporary update table is greater than a set threshold, call the grouping generation and block algorithm to the temporary update table The data is grouped horizontally, and the data is divided into blocks and balanced in units of horizontal groups, and finally stored in the storage layer.

When performing deletion processing, for the same group of incompatible blocks, keep the deleted data in key blocks and low-weight shards.

The data deletion algorithm is as follows:

Input: Data Object Physical View DOPV, Temporary Update Table U, Privacy Blocking Policy PPS, Delete Condition RC

Step (1-1): Delete the data conforming to RC from U;

Step (1-2): Obtain all block numbers except key blocks and low-weight blocks, and store them in the array chunk;

Step (1-3): According to the privacy data reconstruction algorithm, obtain the global identifier resultSet of the original data that meets the conditions of RC in DOPV;

Steps (1-4): foreachinresultSetdo

fori=0tochunk.length-1do

Calculate the DSID whose id is in chunk[i] and delete its corresponding fragment in chunk[i];

The fake data recovery algorithm is:

When the proportion of the remaining data in a horizontal grouping is less than the set lower limit value T _remain , insert the remaining data into the temporary update table U, and delete all the data in the grouping, after grouping the data in the table U Store again. The algorithm process is described as follows:

Input: group information table group_info, remaining data ratio threshold T _remain

Step (2-1): foreachgidinggroup_infodo

Step (2-2): ifremain/tal<T _remain

Step (2-3): call the privacy data reconstruction algorithm to obtain the set resultSet of the global ID corresponding to the remaining data in the group gid;

Step (2-4): foreachinresultSet

Step (2-5): Insert the original data corresponding to the id into U;

Step (2-6): Call the data deletion algorithm to delete all data of the group gid from the storage layer

Algorithm 3. Packet Generation and Blocking Algorithm

Input: temporary data table U, minimum group size N, minimum block entropy _H1 and minimum conditional entropy _H2

Output: group g

Step (3-1): Create an empty group g (the element in g is the unique identifier of the record in U);

Step (3-2): sort the values of the key attributes in table U according to their frequency of occurrence from small to large;

Step (3-3): whileeg.length<Ndo

According to the sorting results in step (3-2): select key attribute values in turn, and add the data ID containing this value to g;

Step (3-4): Select data t in turn from the remaining data in table U, if the entropy value of each corresponding block is not less than H1 after adding it to g, then add t.ID to g;

Step (3-5): call the block strategy to block the data in g;

Step (3-6): Construct fake data according to H1 and H2 to balance each block;

Step (3-7): storing each block data into the storage layer;

Step (3-8): return;

Algorithm 4. Privacy data reconstruction algorithm

Input: data object physical view DOPV, privacy block policy PPS, reconstruction condition RC

Output: original data global ID set resultSet

Step (4-1): Divide and reconstruct condition RC according to PPS;

Step (4-2): fori=1tokdo

Step (4-3): Query the DSID matching rc _i on the block Chunk _i , and put its corresponding global ID into the set IDSet _i

Step (4-4): Intersect all IDSets to get

Step (4-5): filter the global ID corresponding to the forged data in the resultSet;

Step (4-6): Store RC and resultSet in cache;

Steps (4-7): returnresultSet.

Beneficial effects of the present invention:

1 The present invention proposes a dynamic data privacy protection mechanism based on block obfuscation, which processes tenant business operations in units of horizontal grouping, caches newly inserted and modified data through a trusted third party, and stores the data when conditions are met. Carry out grouping and upload to the storage layer for storage; by retaining key fragments to ensure the privacy and security of deleted data and remaining data in the deletion operation; finally, a fake data recovery mechanism is proposed, which reduces the consumption of storage resources and optimizes application performance . At the end of the paper, the experimental verification and performance evaluation are carried out. The experimental results show that the mechanism can effectively protect the privacy of tenants in the process of business processing, and also has good processing performance.

2 In order to deal with the privacy leakage and block balance problems caused by multi-tenants’ business operations on data in SaaS applications, the present invention proposes to horizontally group data first, and perform privacy protection on tenant data in units of finer-grained horizontal grouping. Protection, and the introduction of block information entropy to evaluate the equilibrium state of the block, by ensuring the security of each level of grouping in the tenant business operation, to achieve the protection of the overall privacy data. The impact of forged data on application performance is reduced by taking into account the group balance state during horizontal grouping and subsequent group merging and recovery of forged data.

Description of drawings

Figure 1 is a schematic diagram of data change;

Fig. 2 is a schematic structural diagram of the system of the present invention;

Fig. 3 is a schematic diagram of changes in business operations as the amount of data increases;

Figure 4 is a schematic diagram of business operation overhead under different methods;

Figure 5 is a schematic diagram of the change in the proportion of forged data over time;

Figure 6 is a schematic diagram of the change of the proportion of forged data with the size of the group;

Fig. 7 is a flow chart of the method of the present invention.

detailed description

The present invention will be further described below in conjunction with the accompanying drawings and embodiments.

1 Dynamic Data Privacy Protection Framework

Aiming at the privacy leakage problem and other deficiencies faced by tenants in the business operation process, the present invention proposes a dynamic data privacy protection framework (Fig. 2) and a dynamic data privacy protection method (Fig. 7) based on block obfuscation. The model consists of four parts: application layer, privacy protection layer, storage layer and trusted third party. The application layer is responsible for managing the applications leased by tenants and responding to tenants' business requests. The privacy protection layer is responsible for processing the business requests submitted by the tenants and protecting the privacy of the tenants during the processing according to the privacy protection requirements customized by the tenants. The storage layer is responsible for storing the tenant data after block processing. The trusted third party is responsible for managing the latest updated data of the tenant and the tenant's privacy protection policy, and prevents attackers from unauthorized access to the data and privacy protection policy through the identity authentication mechanism.

In the framework shown in Figure 2, after the application layer receives the service request from the tenant, it forwards the request to the update processing module for processing through step 1; Which operations, and send the corresponding operation instructions through ②; the temporary data management module is responsible for grouping the latest updated data, and will notify the block processing module after the grouping is completed; the block processing module calls the block from the trusted third party through ③ The strategy divides the temporary data group into blocks. After the block is completed, the block is balanced by ④ and the result is stored in the storage layer ⑤; the fake data recovery module ⑥ monitors the remaining data of each group in the storage layer and recycles it regularly Redundant falsified data.

2 Realization of dynamic data privacy protection mechanism

The previous example analyzes the privacy leakage and block balance problems caused by tenant business operations during the continuous operation of SaaS applications, and proposes a dynamic data privacy protection framework based on block confusion to address these problems. Based on the previous section, this section will introduce the relevant concepts and specific implementation of the framework in detail, and will use specific formulas and theorems to prove that the disclosure of tenant privacy can be effectively prevented when the framework is used for business operations on data. Here are some relevant definitions first:

2.1 Related definitions

Definition 1. Horizontal grouping G, a horizontal grouping is represented as a subset of the tenant data logical view T, and the tenant data logical view T is represented as And any two different horizontal groups Gi and Gj do not overlap, that is, G _i ∩G _j = φ (1≤i<j≤m).

Definition 2. Privacy partitioning strategy PPS, divides the attribute set Attrs={A ₁ ,A ₂ ,...,A _n } of the logical view T into several different subsets according to the privacy constraints proposed by the tenants, that is, Attrs=∪ subAttrs(i)(i=1,2,...,k), where k is the number of blocks, so that each subset does not violate the privacy constraints, and any two attribute subsets do not overlap each other, that is, subAttrs(i)∩subAttrs(j)=φ(1≦i<j≦k).

Definition 3. Block information entropy H(X), given a data block X, the value range of the block in the block is {v ₁ ,v ₂ ,...,v _n }, each corresponding The probability of value occurrence is {p(v ₁ ),p(v ₂ ),...,p(v _n )}, then the information entropy of the block is:

$\mathrm{<span\; class="notranslate">\; h</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; x</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; =</span><span\; class="notranslate">\; -</span>\underset{\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 1</span>}}{\overset{\mathrm{<span\; class="notranslate">\; no</span>}}{<span\; class="notranslate">\; \&Sigma;</span>}}\mathrm{<span\; class="notranslate">\; p</span>}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; v</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}}<span\; class="notranslate">\; )</span>{\mathrm{<span\; class="notranslate">\; log</span>}}_{\mathrm{<span\; class="notranslate">\; b</span>}}\mathrm{<span\; class="notranslate">\; p</span>}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; v</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; ,</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; )</span>$

Where b represents the base used in logarithms, usually 2, and the unit of corresponding entropy is bit. The more uniform the value of each fragment in the data block, the greater its information entropy. When the probability of occurrence of each fragment value is equal, the information entropy of the block reaches the maximum value. Conversely, when there is only one fragment Its entropy value is at least 0 when it appears.

Definition 4. Fragmentation depends on p(x/y), which is represented by conditional probability, where x represents a certain value of attribute X in block A, and y represents a certain value of attribute Y in block B. At this time Say that the shard with X value x in block A depends on the shard with Y value y in block B with probability p(x/y).

In practical applications, the concept of shard dependency is ubiquitous, such as the relationship between the salary level of employees and their positions in a company. Assuming that the salary level of ordinary employees in a company is generally 3000-5000, and the salary level of department managers is 5000-8000, but about 15% of the salary range of 5000-8000 is ordinary employees with outstanding performance, and there are also 5% of the salary range of 3000-5000. % are department managers with poor performance. At this time, if a certain salary level is given as 6500, we can infer that it is a department manager with a probability of 85%, that is, the shard with a salary of 6500 has a probability of 85 Depends on the shard whose position is "Department Manager". At this point, even if the two blocks containing salary and position attributes are balanced, the shards can still be associated with a high probability.

In order to describe the degree of data balance when attributes in different blocks have dependencies, the present invention introduces the concept of conditional entropy between blocks:

Definition 5. Inter-block conditional entropy H(Y/X), which means that under the premise of knowing the value of random variable X, how much information entropy of random variable Y is left, which is used to measure the random variable under the condition of known random variable X Uncertainty in variable Y. Expressed as,

$\begin{array}{c}\mathrm{<span\; class="notranslate">\; h</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; Y</span>}<span\; class="notranslate">\; /</span>\mathrm{<span\; class="notranslate">\; x</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; =</span>\underset{\mathrm{<span\; class="notranslate">\; x</span>}<span\; class="notranslate">\; \&Element;</span>\mathrm{<span\; class="notranslate">\; x</span>}}{<span\; class="notranslate">\; \&Sigma;</span>}\mathrm{<span\; class="notranslate">\; p</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; x</span>}<span\; class="notranslate">\; )</span>\mathrm{<span\; class="notranslate">\; h</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; Y</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; x</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; x</span>}<span\; class="notranslate">\; )</span>\\ <span\; class="notranslate">\; =</span><span\; class="notranslate">\; -</span>\underset{\mathrm{<span\; class="notranslate">\; x</span>}<span\; class="notranslate">\; \&Element;</span>\mathrm{<span\; class="notranslate">\; x</span>}}{<span\; class="notranslate">\; \&Sigma;</span>}\mathrm{<span\; class="notranslate">\; p</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; x</span>}<span\; class="notranslate">\; )</span>\underset{\mathrm{<span\; class="notranslate">\; the\; y</span>}<span\; class="notranslate">\; \&Element;</span>\mathrm{<span\; class="notranslate">\; Y</span>}}{<span\; class="notranslate">\; \&Sigma;</span>}\mathrm{<span\; class="notranslate">\; p</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; the\; y</span>}<span\; class="notranslate">\; /</span>\mathrm{<span\; class="notranslate">\; x</span>}<span\; class="notranslate">\; )</span>\mathrm{<span\; class="notranslate">\; log</span>}\mathrm{<span\; class="notranslate">\; p</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; the\; y</span>}<span\; class="notranslate">\; /</span>\mathrm{<span\; class="notranslate">\; x</span>}<span\; class="notranslate">\; )</span>\\ <span\; class="notranslate">\; =</span><span\; class="notranslate">\; -</span>\underset{\mathrm{<span\; class="notranslate">\; x</span>}<span\; class="notranslate">\; \&Element;</span>\mathrm{<span\; class="notranslate">\; x</span>}}{<span\; class="notranslate">\; \&Sigma;</span>}\underset{\mathrm{<span\; class="notranslate">\; the\; y</span>}<span\; class="notranslate">\; \&Element;</span>\mathrm{<span\; class="notranslate">\; Y</span>}}{<span\; class="notranslate">\; \&Sigma;</span>}\mathrm{<span\; class="notranslate">\; p</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; x</span>}<span\; class="notranslate">\; /</span>\mathrm{<span\; class="notranslate">\; the\; y</span>}<span\; class="notranslate">\; )</span>\mathrm{<span\; class="notranslate">\; log</span>}\mathrm{<span\; class="notranslate">\; p</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; the\; y</span>}<span\; class="notranslate">\; /</span>\mathrm{<span\; class="notranslate">\; x</span>}<span\; class="notranslate">\; )</span>\\ <span\; class="notranslate">\; =</span><span\; class="notranslate">\; -</span>\underset{\mathrm{<span\; class="notranslate">\; x</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; the\; y</span>}}{<span\; class="notranslate">\; \&Sigma;</span>}\mathrm{<span\; class="notranslate">\; p</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; x</span>}<span\; class="notranslate">\; /</span>\mathrm{<span\; class="notranslate">\; the\; y</span>}<span\; class="notranslate">\; )</span>\mathrm{<span\; class="notranslate">\; log</span>}\mathrm{<span\; class="notranslate">\; p</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; the\; y</span>}<span\; class="notranslate">\; /</span>\mathrm{<span\; class="notranslate">\; x</span>}<span\; class="notranslate">\; )</span>\end{array}<span\; class="notranslate">\; ,</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 2</span>}<span\; class="notranslate">\; )</span>$

It can be proved by formula (2) that when the value of Y is completely determined by X, H(Y/X) takes the minimum value of 0, conversely, if and only when X and Y are mutually independent variables, H(Y/X) Take the maximum value.

Definition 6. Temporary update table U, which is set in a trusted third party and used to store the latest updated data of tenants, in the form of (ID,A ₁ ,A ₂ ,...,A _n ,Date), where ID It is the globally unique identifier of the record, which is used to generate the DSID of each shard when it is divided into blocks. The Date field is a timestamp, which is used to identify the time when the piece of data was inserted or modified.

2.2 The specific implementation of dynamic data privacy protection

In the work [1] and [2], in order to prevent the tenant's privacy protection policy from being obtained maliciously by the attacker, a trusted third party is proposed to manage the privacy protection policy, and the attacker's malicious request is blocked through the authentication mechanism. The present invention adds a temporary data management module on the basis of a trusted third party, which is mainly responsible for temporarily storing the latest updated data of tenants, and after generating horizontal groups, vertically divides the horizontal groups into blocks and stores them in the storage layer. The identity authentication mechanism of a trusted third party prevents temporary data from being maliciously obtained, so that temporary data can be safely stored in plain text, and the response time when tenants request data is guaranteed.

2.2.1 Insert data

Let tenant _i submit an insert request at time t ₁ :

INSERTINTOTVALUES(a ₁ ,a ₂ ,...,a _n )①

According to the analysis in Section 2, if the data is directly written into each block of the cloud database, the same number of records will be added to each block at the same time. This part of the tenant's privacy faces a great risk of leakage.

Therefore, this mechanism converts the request ① into the following request:

INSERTINTOUVALUES(id,a ₁ ,a ₂ ,...,a _n ,t ₁ )②

Request ② to add the global ID and timestamp t ₁ to the newly inserted data and insert them into the temporary table U for temporary storage. When the amount of data in table U is greater than the set threshold N, call the grouping generation algorithm 3 to horizontally group the data in table U , and divide and balance the data in units of horizontal groupings, and finally store them in the storage layer. Since the operation of table U occurs in a trusted third party, although the group relationship is exposed to the attacker when the data is stored in the storage layer, each block in the group has been balanced, so the entire group is still safe, and the entire insertion The process is also reliable.

2.2.2 Delete data

For the data in the temporary update table U, the deletion operation occurs in a trusted third party, and the corresponding data can be directly deleted. Corresponding to the data in each block of the storage layer, performing the deletion operation at the same time will cause privacy leakage. Therefore, the present invention proposes to retain the data in some blocks when deleting data. For this reason, the following concepts are firstly introduced:

Definition 7. The key attribute KA refers to the highly sensitive attribute in the privacy constraint, which is specified by the tenant in the privacy protection requirement. For example, in the incompatible constraint {Owner, Age, Zip, Disease}, the patient is more sensitive to the Disease attribute. When the patient’s identity information is leaked, he still hopes that his disease information can be protected, so the block containing the Disease attribute is guaranteed safety is more important.

Definition 8. Key block KC, the present invention refers to a block containing key attributes as a key block.

Definition 9. Low-weight block LWC refers to the block with the lowest frequency except the key block in the process of business processing, and the amount of data in this block will not have a great impact on the efficiency of business processing.

Definition 10. Incompatible block MEC, the present invention refers to all blocks involved in the same incompatible privacy constraint as a group of incompatible blocks (Chunk1, Chunk2 and Chunk3 in Figure 1 are a group of incompatible tolerant block), when the privacy requirement contains multiple incompatible constraints, there will be multiple sets of incompatible blocks in the corresponding block results.

When performing deletion processing, for the same group of incompatible blocks, keep the fragments of the deleted data in the key blocks and low-weight blocks. Structure, can not break the privacy constraints, to ensure the privacy of tenants. The process of deletion algorithm is described as follows:

Algorithm 1. Data deletion algorithm

Input: Data Object Physical View DOPV, Temporary Update Table U, Privacy Blocking Policy PPS, Delete Condition RC

①Delete RC-compliant data from U;

② Obtain all block numbers except key blocks and low-weight blocks, and store them in the array chunk;

③According to Algorithm 4, obtain the global identifier resultSet of the original data that meets the conditions of RC in DOPV;

④foreachinresultSetdo

fori=0tochunk.length-1do

Calculate the DSID whose id is in chunk[i] and delete its corresponding fragment in chunk[i];

Two auxiliary theorems are proposed below to prove that Algorithm 1 will not cause privacy leakage during the deletion operation:

Theorem 1. For an incompatible block group, keep the data of a certain block unchanged, and only delete the data in the remaining blocks each time the data is deleted, then the information entropy of each block after the data is deleted is greater than or equal to the data deleted The information entropy of each previous block.

Proof: Assuming that an incompatible block group contains two blocks C1 and C2, only the block of C2 is deleted when the deletion request is executed. Since the data distribution of the C1 block is always the same, the information entropy of the C1 block is also constant. For block C2, suppose the data distribution before deleting the block is {p(v ₁ ),p(v ₂ ),...,p(v _n )}, according to the meaning of maximum entropy, in the known partial knowledge Under the premise, the most reasonable inference about the unknown part is the most random inference that conforms to the known knowledge, so we can always find a data filling method so that the data distribution after supplementation is {p ₁ (v ₁ ),p ₁ (v ₂ ),...,p ₁ (v _n )}, and have:

$<span\; class="notranslate">\; -</span>{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 1</span>}}^{\mathrm{<span\; class="notranslate">\; no</span>}}\mathrm{<span\; class="notranslate">\; p</span>}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; v</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}}<span\; class="notranslate">\; )</span>{\mathrm{<span\; class="notranslate">\; log</span>}}_{\mathrm{<span\; class="notranslate">\; b</span>}}\mathrm{<span\; class="notranslate">\; p</span>}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; v</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; \&le;</span><span\; class="notranslate">\; -</span>{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 1</span>}}^{\mathrm{<span\; class="notranslate">\; no</span>}}{\mathrm{<span\; class="notranslate">\; p</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; v</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}}<span\; class="notranslate">\; )</span>{\mathrm{<span\; class="notranslate">\; log</span>}}_{\mathrm{<span\; class="notranslate">\; b</span>}}{\mathrm{<span\; class="notranslate">\; p</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; v</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}}<span\; class="notranslate">\; )</span>$

That is, the current entropy value of the C2 block speculated by the attacker can only be greater than or equal to its initial entropy value, that is, on the premise that there is no background knowledge of the data distribution in the block, the attacker can only use the C2 block to be as evenly distributed as possible. Take the guesswork out of privacy.

Theorem 2. For an incompatible block group, keep the data of a certain block unchanged, and only delete the data in the remaining blocks each time the data is deleted, then the conditional entropy of each block after the data is deleted is greater than or equal to the data deleted Conditional entropy of each block before.

Proof: Suppose that events X and Y represent the value-taking events from blocks C1 and C2 respectively. In the present invention, we only care about the information entropy required for guessing Y=y _j given X=x _i or guessing X given Y=y _j = the information entropy required by x _i , so it is only necessary to prove that H(Y|X=x) and H(X|Y=y) do not decrease. Depend on

$\mathrm{<span\; class="notranslate">\; h</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; x</span>}<span\; class="notranslate">\; /</span>\mathrm{<span\; class="notranslate">\; Y</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; the\; y</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; =</span>\underset{\mathrm{<span\; class="notranslate">\; x</span>}<span\; class="notranslate">\; \&Element;</span>\mathrm{<span\; class="notranslate">\; x</span>}}{<span\; class="notranslate">\; \&Sigma;</span>}\mathrm{<span\; class="notranslate">\; p</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; x</span>}<span\; class="notranslate">\; /</span>\mathrm{<span\; class="notranslate">\; the\; y</span>}<span\; class="notranslate">\; )</span>\mathrm{<span\; class="notranslate">\; log</span>}\mathrm{<span\; class="notranslate">\; p</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; x</span>}<span\; class="notranslate">\; /</span>\mathrm{<span\; class="notranslate">\; the\; y</span>}<span\; class="notranslate">\; )</span>$

The value of X remains unchanged, and P(x│y) remains unchanged when x and y are given, so H(X|Y=y) maintains the initial size. And for H(Y|X=x),

$\mathrm{<span\; class="notranslate">\; h</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; Y</span>}<span\; class="notranslate">\; /</span>\mathrm{<span\; class="notranslate">\; x</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; x</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; =</span>\underset{\mathrm{<span\; class="notranslate">\; the\; y</span>}<span\; class="notranslate">\; \&Element;</span>\mathrm{<span\; class="notranslate">\; Y</span>}}{<span\; class="notranslate">\; \&Sigma;</span>}\mathrm{<span\; class="notranslate">\; p</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; the\; y</span>}<span\; class="notranslate">\; /</span>\mathrm{<span\; class="notranslate">\; x</span>}<span\; class="notranslate">\; )</span>\mathrm{<span\; class="notranslate">\; log</span>}\mathrm{<span\; class="notranslate">\; p</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; the\; y</span>}<span\; class="notranslate">\; /</span>\mathrm{<span\; class="notranslate">\; x</span>}<span\; class="notranslate">\; )</span>$

After deleting the fragment in C2, the number of values of Y may be reduced, but without background knowledge, the attacker can only think that Y can take other values than the remaining values, that is, the number of values of Y can only be greater than or equal to the initial number such that H(Y|X=x) is greater than or equal to its initial value.

Auxiliary theorems 1 and 2 show that when only some fragments are deleted, the entropy value of each block and the conditional entropy value between blocks can always be kept unchanged, so the entropy value will not decrease during the deletion process. Leaking tenant privacy.

With the continuous operation of SaaS applications, such a situation may gradually appear in cloud databases, that is, after multiple deletions and modifications of data in a horizontal group, only one or a few small pieces of data remain. privacy security, it is necessary to fully retain the data of key blocks and low-weight blocks, as well as forged data during data balancing. When the number of is increasing, a larger proportion of forged data will also have a greater impact on query efficiency.

Therefore, when the present invention is designing an algorithm, a forged data recovery mechanism is added. When the proportion of the remaining data in a horizontal grouping is less than the set lower limit value T _remain , the remaining data is inserted into the temporary update table U, and the Delete all the data in the group, and store the data in table U again after grouping. The algorithm process is described as follows:

Algorithm 2. Forged data recovery

Input: group information table group_info, remaining data ratio threshold T _remain

①foreachgidinggroup_infodo

②ifremain/tatal<T _remain

③ Call Algorithm 4 to obtain the set resultSet of the global ID corresponding to the remaining data in the group gid;

④foreachinresultSet

⑤ Insert the original data corresponding to id into U;

⑥ Call Algorithm 1 to delete all data of the group gid from the storage layer

2.2.3 Modify data

For the data in the temporary update table U, the modification operation occurs in a trusted third party, and the corresponding data can be directly modified. Corresponding to the data in each sub-block of the storage layer, since performing modification operations on each sub-block at the same time will cause privacy leakage, the processing method of the present invention is to directly insert the modified data into the temporary update table U for storage, and At the same time, the original data is deleted from each block of the storage layer. In Section 4.2.2, it is proved that the deletion process of deletion algorithm 1 is safe, and the insertion operation occurs in a trusted third party, so the whole modification process is safe.

2.2.4 Packet Generation and Data Blocking

Algorithm 3. Packet Generation and Blocking Algorithm

Input: temporary data table U, minimum group size N, minimum block entropy _H1 and minimum conditional entropy _H2

Output: group g

① Create an empty group g (the element in g is the unique identifier recorded in U);

②Sort the values of the key attributes in table U according to their frequency of occurrence from small to large;

③while eg. length<Ndo

According to the sorting results in ②, select key attribute values in turn, and add the data ID containing this value to g;

④ Select data t from the remaining data in table U in turn, if the entropy value of each corresponding block is not less than H1 after adding it to g, then add t.ID to g;

⑤ Call the block strategy to block the data in g;

⑥ Construct fake data according to H1 and H2 to balance each block;

⑦ Store each block data in the storage layer;

⑧ return;

In Algorithm 3, grouping is based on key attributes, and the grouping results first ensure that the key blocks are as balanced as possible. The second line of the algorithm first sorts the key attributes according to their frequency of occurrence, and the third line selects the key attributes with a small frequency of occurrence and adds their corresponding data to the group, so that the key attributes in the group can have more values , the distribution is more uniform. The fourth line of the algorithm adopts the idea of greed, and selects the data in turn from the remaining blocks to try. When adding it to g, the entropy value of each block is not less than H1, then it is accepted to add g; lines 5-7 of the algorithm generate After grouping g, call the block strategy to block the group, and use the balancing method in [1] to balance each block.

2.2.5 Privacy data reconstruction

After the privacy data is divided and obfuscated, its data availability is also lost. In the cloud computing environment, tenants need to frequently access, delete and modify the original data. Therefore, how to quickly reconstruct private data has become a key issue in SaaS application privacy protection.

When partitioning private data, a unique shard identifier (DSID) will be generated for each shard based on the global ID of the original data, which is mainly used to reconstruct the original data and filter forged data. Algorithm 4 is an original data reconstruction algorithm based on a trusted third party. The input is the data object physical view DOPV, the privacy partition policy PPS and the reconstruction condition RC, and the output is the global ID of the original record that meets the conditions. The block strategy divides the reconstruction condition RC into RC={rc ₁ ,rc ₂ ,...,rc _i ,...,rc _k }, where k is the number of blocks, rc _i is the weight of block Chunk _i Construction conditions; the second line of the algorithm queries the DSID that meets the condition rc _i on each block Chunk _i and converts it into a global ID and puts it into the set IDSet _i . The third line of the algorithm calculates the intersection of all IDSets to obtain the final match The original data global ID set resultSet of reconstruction condition RC; the fourth line of the algorithm filters the global ID corresponding to the forged data in the resultSet; the fifth line of the algorithm caches RC and resultSet in the cache to improve the execution efficiency of the same reconstruction request next time. The algorithm is described as follows:

Algorithm 4. Privacy data reconstruction algorithm

Input: data object physical view DOPV, privacy block policy PPS, reconstruction condition RC

Output: original data global ID set resultSet

① Divide the reconstruction condition RC according to the PPS;

②fori＝1tokdo

③ Query the DSID that matches rc _i on the block Chunk _i , and put its corresponding global ID into the set IDSet _i

④ Find the intersection of all IDSets to get

⑤ Filter the global ID corresponding to the forged data in the resultSet;

⑥ Store RC and resultSet in cache;

⑦return resultSet;

In the above algorithm, querying qualified DSIDs in each block is performed in parallel, and the query time is proportional to the size of the data. Assuming that all N is the maximum length of IDSet, if two-way merge is used for intersection, the time complexity is N ² *log2 ^k . Generally, the values of N that meet the conditions are not very large, so the time complexity is within an acceptable range.

3 Experimental evaluation

3.1 Experimental environment

For the experiment, the virtual machine applied from the laboratory cloud computing platform is used as a trusted third party, and its configuration is 8 cores, 16G memory and 500G hard disk. Use MongoDB3.0.0 to store tenant privacy protection policies, and use Mysql5.6.22 to store temporary update table data.

Use an Inspur blade server to simulate the deployment of multi-tenant applications, configured as a 12-core CPU (main frequency 3.10GHz), 32G memory, and a hard disk size of 2T. The storage layer also uses Mysql5.6.22 as the storage database, and the multi-tenant application uses java1.8 to write programs for simulation.

The data set is taken from the data in the basic information table of the medical registration of the insured person in the internal test data set of the social security project of the laboratory, and the data volume is about 3 million. A total of 20 attributes including surname (has been blurred), medical personnel category, gender, age, trust level, widow category, unit organization, medical account and other attributes were selected for the experiment. Incompatible privacy constraints are (surname, gender, age, organization).

3.2 Business processing overhead experiment

Fig. 3 is under the dynamic data privacy protection mechanism proposed by the present invention, the operation processing time of three different operations of adding, deleting and modifying under different data volumes, the horizontal axis is the data volume, and the vertical axis is the operation time (unit: ms).

It can be seen from Figure 3 that since the newly inserted data is always stored in the temporary table, while only a small amount of data is stored in table U and the amount of data is basically stable, the processing speed of inserted data is very fast, only about tens of milliseconds . For deletion and modification operations, since the updated data needs to be reconstructed first, the processing time is greatly increased, and it increases linearly with the increase of the data volume.

Fig. 4 compares the method proposed by the present invention with the other three methods in terms of service processing efficiency. Method A is not to protect privacy, method B is the dynamic privacy protection mechanism proposed by the present invention, adopts the block strategy in work [1], method C is the privacy protection mechanism proposed by work [1], method D is work [3] ] A privacy-preserving method after clustering data attributes. The amount of data is about two million. The number of attributes involved in each of the three types of business operations, query, insert, and modify, is divided into five levels: 2, 4, 6, 8, and 10. The experimental results use the processing time of all levels average of. As can be seen from the figure, the processing speed is the fastest when no privacy protection is performed, and although method B and method C query, delete and modify are all subject to the size of the data volume, due to the same data volume, the privacy protection proposed by the present invention The falsified data in the method is relatively reduced, so in general, the performance of method B is still improved compared with method C of work [1]. Method D is more efficient than method C because it clusters data attributes according to business operations, but it is still less efficient than method B due to the influence of forged data.

3.3 Forged data proportion experiment

Figure 5 compares the change of the proportion of forged data in methods B, C, and D over time when the minimum information entropy of the block is set to 3. It can be seen from the figure that when methods C and D are used, the proportion of forged data will gradually increase as the application runs, and the increase in the initial stage is relatively large. The distribution is not completely consistent with the overall distribution, and the data distribution is relatively uneven. When the amount of data gradually increases over time, the distribution is closer to the overall distribution. However, as the number of data operations continues to increase, more forged data needs to be added for further processing. balanced. In method B, as far as possible to select the data that makes the grouping data evenly distributed to form the grouping, supplemented by the recovery and processing of the forged data by the forged data recovery module, the proportion of forged data in the whole process is relatively stable.

Figure 6 compares the change of the proportion of forged data with the group size. When the group is small, due to the relatively small number of group values, the data distribution in the group is uneven, and more fake data needs to be added to balance. As the group size gradually increases, the number of fragment values gradually increases, and the distribution of fragments gradually becomes even. When the group size continues to increase, the data distribution within the group gradually approaches the overall distribution. Since the surname and age in the overall distribution are not uniformly distributed, the grouping tends to be uneven again, resulting in a rise in the proportion of forged data again.

From the comparison of the above several experiments, it can be seen that compared with the method C in the work [1], the privacy protection mechanism proposed by the present invention has higher operating efficiency, and with the continuous operation of the application, the proportion of forged data is lower and Always keep it steady.

For SaaS applications, the existing privacy protection mechanism lacks effective support for tenants' business operations, and it is difficult to guarantee the security of tenants' private information in the process of dynamic data changes. Aiming at the problem of privacy leakage caused by tenants' business operations and the high proportion of forged data in the SaaS mode, the present invention proposes a dynamic data privacy protection mechanism based on block obfuscation. This mechanism caches the latest data inserted and modified by tenants in a trusted third party. When the block conditions are met, the data is divided into blocks and balanced in groups and stored in the storage layer; for delete operations, key blocks and low The data in the weight block will not be deleted to prevent attackers from reconstructing the privacy of tenants through data manipulation behavior; finally, a fake data recovery mechanism is proposed to recover redundant fake data in the storage layer, reducing the proportion of fake data to the total data volume . Experimental results prove that the dynamic data privacy protection mechanism proposed by the present invention has a good optimization effect on application performance while ensuring the privacy of tenants. The next step will be to study the impact of different tenant data placement strategies on application performance during the dynamic data change process.

Although the specific implementation of the present invention has been described above in conjunction with the accompanying drawings, it does not limit the protection scope of the present invention. Those skilled in the art should understand that on the basis of the technical solution of the present invention, those skilled in the art do not need to pay creative work Various modifications or variations that can be made are still within the protection scope of the present invention.

Claims (10)

1. A dynamic data privacy protection system based on block obfuscation, characterized in that it comprises: The application layer is responsible for managing the application components for tenants to lease and customize, receives the data service processing requests submitted by the tenants and forwards the requests to the privacy protection layer for processing; the application layer can deploy a variety of different application components, each application Components can deploy multiple instances for load balancing; The privacy protection layer is the core part of the dynamic data privacy protection framework, responsible for receiving and processing data business processing requests transferred from the application layer, and returning the processing results to the application layer; data business processing requests include data insertion requests and data deletion requests , data query request or data modification request; The storage layer is responsible for storing tenant data and is the final executor of all data processing operations; the storage layer deploys multiple database instances, and the database instances use the same or different databases for deployment; A trusted third party is responsible for managing the tenant's personalized privacy protection policy, and is also responsible for managing the latest inserted or modified data. It can identify the identity of the data tenant and prevent attackers from maliciously accessing the privacy protection policy and temporary data. and steal. 2. a kind of dynamic data privacy protection system based on block obfuscation as claimed in claim 1, is characterized in that, For data insertion requests, the newly inserted data is packaged and temporarily stored in a trusted third party; For the data deletion request, the non-key block and the corresponding slice in the high-weight block are deleted in the storage layer; the non-key module refers to a block that does not contain key attributes; For data query requests, the reconstruction module of the privacy protection layer will return the reconstruction results of the original data; For data modification requests, the corresponding original data in the storage layer is deleted first, and then the modified data is packaged and temporarily stored in a trusted third party. 3. A kind of dynamic data privacy protection system based on block obfuscation as claimed in claim 1, wherein the privacy protection layer comprises: an update processing module, a block processing module, an equalization module, a reconstruction module and forged data recovery module; The update processing module is responsible for receiving the business operation request delivered by the application layer, then analyzing the operation request type, performing different operation processes according to the operation request type, and returning the operation result to the application layer after the operation is completed; The type of operation request includes: insert, delete, modify and query; the update processing module also receives the data of the reconstruction module; the update processing module also stores the operation result in the storage layer; the update processing module also stores the authentication information in the authentication module; Store the temporary data in the temporary data management module; The block processing module is responsible for performing vertical block on the new group generated by the temporary data management module; when a new group is delivered to the block processing module, it sends a request to the privacy policy management module to obtain the corresponding data block strategy, according to The block strategy divides the data vertically and stores the block data in the storage layer; The equalization module obtains the data distribution state of each block from the block processing module, generates forged data satisfying α, β, and γ balance, and performs α, β, and γ balance on each block; the data distribution state refers to all The frequency of fragmentation values; The forged data recovery module is responsible for periodically checking the grouping status, and judging whether the forged data of the grouping needs to be recovered according to the proportion of valid data in each grouping; for the grouping that needs to recover the forged data, transfer the remaining valid data in the grouping Go to the temporary data management module for cache processing, and then delete all the data grouped in each block; The reconstructed block connects the original private data before the block according to the query, deletion or modification conditions submitted by the tenant in the business operation, and returns the global ID corresponding to the original data; the reconstructed module reads from the storage layer Take the block data, then reconstruct the block data, and feed back the reconstructed result to the update processing module. 4. a kind of dynamic data privacy protection system based on block obfuscation as claimed in claim 1, is characterized in that, The trusted third party includes: a privacy policy management module, an authentication module and a temporary data management module; The authentication module is responsible for receiving the identity authentication information of the tenant, identifying the identity of the tenant, and preventing malicious attackers from accessing the corresponding privacy protection policy and temporary data according to the identification result, while allowing legitimate tenants to access the corresponding privacy protection policy and temporary data ; The privacy policy management module is responsible for storing and accessing the tenant's personalized privacy protection policy, and transferring the corresponding tenant's privacy protection policy to the block processing module according to the tenant ID; The temporary data management module is responsible for temporarily storing the newly inserted or modified data of the tenant, and horizontally grouping the temporary data according to the grouping conditions, and passing the grouped data to the block processing module after generating new groups. 5. A dynamic data privacy protection method based on block obfuscation, which is characterized in that the method caches newly inserted and modified data through a trusted third party, and groups and stores the data when conditions are met; by retaining Key shards are used to ensure the privacy and security of deleted data and remaining data in the deletion operation; the reduction of storage resource consumption and the optimization of application performance are achieved through forged data recovery algorithms. 6. The method of claim 5, comprising the steps of: Step (1): The application component of the application layer is responsible for receiving the business operation submitted by the tenant, and forwarding the operation to the update processing module of the privacy protection layer; Step (2): The update processing module analyzes the operation type, if it is an insert operation, then proceed to step (3), otherwise, execute step (7); Step (3): The update processing module submits the tenant's identity information to the authentication module of the trusted third party for identification, and allows the tenant to access the temporary data management module after passing the authentication; Step (4): The temporary data management module caches the newly inserted data in the form of plain text, and periodically checks whether the cached data meets the grouping conditions. If so, calls the group generation and block algorithm to generate a new group and uploads it to the block Processing module; if not reached, no processing will be done; Step (5): If a new packet is uploaded to the block processing module, the block processing module requests the block policy of the corresponding tenant from the privacy policy management module of the trusted third party, and vertically divides the packet data according to the block policy. piece; Step (6): The equalization module generates forged data according to the data distribution of each block, so that the data distribution of each block satisfies α, β and γ balance, and then stores the block data in the storage layer; the block data Including forged data and private data stored by users; Step (7): The reconstruction module reconstructs the private data through the private data reconstruction algorithm, and judges whether it is a modification operation. If so, the original data is modified and assembled into new data, and then the original data is deleted, and the step ( 3), otherwise go to step (8); Step (8): Determine whether to delete the operation, and if so, execute the data deletion algorithm to delete the corresponding fragments in the non-critical blocks and high-weight blocks of the storage layer. After the deletion is successful, call the forged data recovery algorithm through the forged data recovery module Check whether there is grouped forged data that needs to be recycled; otherwise, it is determined as a query operation, and step (9) is performed; Step (9): Filter the query results according to the global identifier and query conditions calculated by the reconstruction module, and return the results to the tenant. 7. The method according to claim 6, wherein the data deletion algorithm is as follows: Input: Data Object Physical View DOPV, Temporary Update Table U, Privacy Blocking Policy PPS, Delete Condition RC Step (1-1): Delete the data conforming to RC from U; Step (1-2): Obtain all block numbers except key blocks and low-weight blocks, and store them in the array chunk; Step (1-3): According to the privacy data reconstruction algorithm, obtain the global identifier resultSet of the original data that meets the conditions of RC in DOPV; Steps (1-4): foreachinresultSetdo fori=0tochunk.length-1do Calculate the DSID whose id is in chunk[i] and delete its corresponding fragment in chunk[i]. 8. The method according to claim 6, characterized in that, the fake data recovery algorithm is: When the proportion of the remaining data in a horizontal grouping is less than the set lower limit value T _remain , insert the remaining data into the temporary update table U, and delete all the data in the grouping, after grouping the data in the table U Re-store; the algorithm process is described as follows: Input: group information table group_info, remaining data ratio threshold T _remain Step (2-1): foreachgidinggroup_infodo Step (2-2): ifremain/tal<T _remain Step (2-3): call the privacy data reconstruction algorithm to obtain the set resultSet of the global ID corresponding to the remaining data in the group gid; Step (2-4): foreachinresultSet Step (2-5): Insert the original data corresponding to the id into U; Step (2-6): Call the data deletion algorithm to delete all data of the group gid from the storage layer. 9. The method of claim 6, wherein the packet generation and block algorithm: Input: temporary data table U, minimum group size N, minimum block entropy _H1 and minimum conditional entropy _H2 Output: group g Step (3-1): Create an empty group g (the element in g is the unique identifier of the record in U); Step (3-2): sort the values of the key attributes in table U according to their frequency of occurrence from small to large; Step (3-3): whileeg.length<Ndo According to the sorting results in step (3-2): select key attribute values in turn, and add the data ID containing this value to g; Step (3-4): Select data t in turn from the remaining data in table U, if the entropy value of each corresponding block is not less than H1 after adding it to g, then add t.ID to g; Step (3-5): call the block strategy to block the data in g; Step (3-6): Construct fake data according to H1 and H2 to balance each block; Step (3-7): storing each block data into the storage layer; Step (3-8): return. 10. The method according to claim 6, wherein the privacy data reconstruction algorithm: Input: data object physical view DOPV, privacy block policy PPS, reconstruction condition RC Output: original data global ID set resultSet Step (4-1): Divide and reconstruct condition RC according to PPS; Step (4-2): fori=1tokdo Step (4-3): Query the DSID matching rc _i on the block Chunk _i , and put its corresponding global ID into the set IDSet _i Step (4-4): Intersect all IDSets to get Step (4-5): filter the global ID corresponding to the forged data in the resultSet; Step (4-6): Store RC and resultSet in cache; Steps (4-7): returnresultSet.