基于异或的隐私保护码优化研究

doi:10.11896/j.issn.1002-137X.2017.06.006

摘要/Abstract

摘要： 随着存储系统的发展,为了满足当前高速增长的信息数据量对存储的需求,云存储行业迅速兴起。然而,单云存储面临着数据保密性、安全性、可用性和厂商锁定的风险。基于异或的非系统纠删码-隐私保护码(PPC)可以用来构造具有隐私保护能力的多云存储系统,从而在很大程度上解决上述问题。主要针对PPC编码算法进行优化,以提高编码运行性能。通过设计搜索PPC的最优调度来减少编码过程中的异或次数。由于PPC的编码/解码计算可以表示为生成矩阵(0/1矩阵)和数据向量的乘法,直观上计算量与生成矩阵中1的数目成正比,因此通过对计算次序的优化调度可以获得更好的性能。首先, 设计并实现搜索PPC最优调度次序的算法,利用此算法寻找计算性能最优者,可优化具有隐私保护能力的多云存储系统的性能。其次,在基于最优调度次序的编码算法的基础上,利用AVX2技术的SIMD并行优化来提高编码过程中的每次异或的性能。实验表明,基于最优调度的编码性能提高了34.8%,进行SIMD并行优化后进一步提高了107.1%。

关键词: 隐私保护码,编码优化,SIMD优化,数据安全,纠删码,非系统码

Abstract: With the development of storage systems,the rapid rise of cloud storage has met the storing problem of highly increased data quantity.However,now the single cloud storage is facing the risks of data confidentiality,security,availability and vendor lock-in.To solve the above problems,we can construct the multi-cloud storage system with the private protecting ability through using privacy protecting code(PPC),which is an erasure code based on the XOR ope-ration.This paper mainly analyzed the optimization coding algorithm on the PPC to improve the performance of encoding operations.First,we designed an algorithm to search the optimal XOR scheduling sequence to reduce the XOR times in encoding.Because the encoding/decoding calculation of the PPC can be expressed as the multiplication of generator matrix (0/1 matrix) and data vectors,it can be observed visually that the computation is proportional to the number of 1 of the generator matrix.And based on the optimal scheduling order,we can get better performance.The searching result can be used to construct the multi-cloud storage system.Second,we can use the AVX2 technique of SIMD parallel optimization to improve the encoding performance based on the optimization schedule.Through the experiment,the performance of encoding based on the optimization schedule improves by 34.8%,and after being further optimized by SIMD technique,the performance improves 107.1%.

Key words: PPC,Encoding optimization,SIMD optimization,Data security,Erasure codes,Non-systematic codes

金星彤,李鹏,王刚,刘晓光,李忠伟. 基于异或的隐私保护码优化研究[J]. 计算机科学, 2017, 44(6): 36-42. https://doi.org/10.11896/j.issn.1002-137X.2017.06.006

JIN Xing-tong, LI Peng, WANG Gang, LIU Xiao-guang and LI Zhong-wei. Optimizing Small XOR-based Non-systematic Erasure Codes[J]. Computer Science, 2017, 44(6): 36-42. https://doi.org/10.11896/j.issn.1002-137X.2017.06.006

参考文献

[1] ZHOU A Y.Data intensive computing-challenges of data mana-gement techniques[J].Communications of CCF,2009,5(7):50-53.
[2] Google Drive [EB/OL].[2016-07-09].https://en.wikipedia.org/wiki/Google_Drive.
[3] Dropbox (service) [EB/OL].[2016-07-09].https://en.wikipedia.org/wiki/Dropbox_(service).
[4] Amazon Simple Storage Service(S3) [EB/0L].[2016-07-09].https://aws.amazon.com/ s3.
[5] Microsoft Azure[EB/OL].[2016-07-09].https://en.wikipe-dia.org/wiki/Microsoft_Azure.
[6] A survey called “Data Breach Investigations Report” in 2015 by Verizon[EB/OL].[2016-07-09].http://www.freebuf.com/news/64183.html.
[7] BESSANI A,CORREIA M,QUARESMA B,et al.DepSky:dependable and secure storage in a cloud-of-clouds[J].ACM Transactions on Storage (TOS),2013,9(4):12.
[8] ABU-LIBDEH H,PRINCEHOUSE L,WEATHERSPOON H.RACS:a case for cloud storage diversity[C]∥Proceedings of the 1st ACM Symposium on Cloud Computing.ACM,2010:229-240.
[9] BOWERS K D,JUELS A,OPREA A.HAIL:a high-availability and integrity layer for cloud storage[C]∥Proceedings of the 16th ACM Conference on Computer and Communications Secu-rity.ACM,2009:187-198.
[10] SHEN L,FENG S,SUN J,et al.CloudS:A Multi-cloud Storage System with Multi-level Security[C]∥International Conference on Algorithms and Architectures for Parallel Processing.Sprin-ger International Publishing,2015:703-716.
[11] MENON J,BRUCK J,BRADY J,et al.EVENODD:An Efficient Scheme for Tolerating Double Disk Failures in RAID Architectures[J].IEEE Transactions on Computers,1995,4(2):192-202.
[12] CORBETT P,ENGLISH B,GOEL A,et al.Row-diagonal parity for double disk failure correction[C]∥Proceedings of the 3rd USENIX Symposium on File and Storage Technologies (FAST’04).2004:1-14.
[13] XU L,BRUCK J.X-Code:MDS Array Codes with Optimal Encoding[J].IEEE Transactions on Information Theory,1999,45(1):272-276.
[14] CHAO J,HONG J,DAN F,et al.P-Code:A new RAID-6 code with optimal properties[C]∥23rd International Conference on Supercomputing.New York,June 2009.
[15] HUANG C,XU L.STAR:An Efficient Coding Scheme for Correcting Triple Storage Node Failures[J].IEEE Transactions on Computers,2007,7(7):889-901.
[16] LIN S,WANG G,STONES D S,et al.T-Code:3-Erasure Longest Lowest-Density MDS Codes[J].IEEE Journal on Selected Areas in Communications,2010,8(2):289-296.
[17] AUTHORS U.WEAVER codes:highly fault tolerant erasurecodes for storage systems[C]∥ Fast 05 Conference on File & Storage Technologies,2005:16.
[18] PLANK J S,SCHUMAN C D,ROBISON B D.Heuristics foroptimizing matrix-based erasure codes for fault-tolerant storage systems[J].IEEE/IFIP International Conference on Dependable Systems & Networks Annual,2012,2(12):1-12.
[19] SIMD[EB/OL].[2016-07-09].https://en.wikipedia.org/w/in-dex.php?title=SIMD&oldid=726575429.
[20] PLANK J S.A tutorial on Reed-Solomon coding for fault-tole-rance in RAID-like systems[J].Softw.,Pract.Exper.,1997,7(9):995-1012.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed