Rule Processing Optimization Technologies on the Sunway Many-Core Processor

Zhang Zhendong; Wang Tong; Liu Peng

doi:10.7544/issn1000-1239.202220656

Journal of Computer Research and Development > 2024 > 61(1): 66-85. > DOI: 10.7544/issn1000-1239.202220656

Zhang Zhendong, Wang Tong, Liu Peng. Rule Processing Optimization Technologies on the Sunway Many-Core Processor[J]. Journal of Computer Research and Development, 2024, 61(1): 66-85. DOI: 10.7544/issn1000-1239.202220656

Citation:

PDF (2912 KB)

Rule Processing Optimization Technologies on the Sunway Many-Core Processor

Zhang Zhendong^{1, 2,},
Wang Tong^{1, 2},
Liu Peng^{1, 2, 3, ,}

1.
College of Information Science and Electronic Engineering, Zhejiang University, Hangzhou 310027
2.
Research Center for Intelligent Supercomputing, Zhejiang Lab, Hangzhou 311100
3.
State Key Laboratory of Mathematical Engineering and Advanced Computing, Wuxi, Jiangsu 214125

Funds: This work was supported by the Open Project Program of the State Key Laboratory of Mathematical Engineering and Advanced Computing (2020A11, 2017A07) and the Key Research Project of Zhejiang Lab (2021PB0AC02).

More Information

Author Bio:
Zhang Zhendong: born in 1996. PhD. His main research interests include computer architecture, domain-specific accelerator, and high-performance computing

Wang Tong: born in 1998. Master. Her main research interests include computer architecture, compiler optimization, and AI software and hardware co-design

Liu Peng: born in 1970. PhD, professor. His main research interests include computer architecture, parallel computer architecture, VLSI design, and hardware security
Received Date: July 23, 2022
Revised Date: May 14, 2023
Available Online: November 27, 2023

Graphical Abstract

Abstract

Abstract

High-performance password recovery system is one of the important application scenarios of the Sunway many-core processor. Many popular password recovery systems and tools adopt rule processing as a mainstream password generation method due to its relatively high hit rate compared with the dictionary/mask based password generation methods. However, current researches lack optimization for the rule processing algorithm on the Sunway processor, which makes the rule-based password generation speed become the bottleneck of the password recovery systems. By analyzing the parallelism of the rule processing algorithm at different levels, we propose several optimization techniques for the rule processing on the Sunway processor. For the thread-level optimizations, we explore the optimal scheme to parallelize the rule processing algorithm, which includes the optimal task mapping technique, the optimal local data memory allocation technique, the load balancing technique, and the variable-length rule storage technique. For the data-level optimizations, we analyze the computing patterns of the rule functions and leverage the Sunway SIMD instructions to vectorize the rule functions and reduce the execution time. The experimental results based on the SW26010 processor show that the proposed optimization techniques effectively eliminate the performance bottleneck of rule processing and the rule-based password recovery speed is increased by 30 to 101 times.
- Sunway many-core processor,
- password recovery,
- rule processing,
- heterogeneous computing,
- SIMD

FullText(HTML)

References (21)

References

[1]	任必晋. 口令恢复在神威•太湖之光上的优化与实现 [D]. 郑州:郑州大学,2020 Ren Bijin. Implementation and optimization of password recovery on Sunway Taihu Light [D]. Zhengzhou: Zhengzhou University, 2020(in Chinese)
[2]	Fu Haohuan, Liao Junfeng, Yang Jinzhe, et al. The Sunway taihulight supercomputer: System and applications[J]. Science China Information Sciences, 2016, 59(7): 1−16
[3]	董本松,赵荣彩,张恒. 基于申威众核处理器的Office口令恢复技术[J]. 计算机技术与发展,2021,31(5):137−142 doi: 10.3969/j.issn.1673-629X.2021.05.024 Dong Bensong, Zhao Rongcai, Zhang Heng. Office password recovery technology based on Sunway many-core processor[J]. Journal of Computer Technology and Development, 2021, 31(5): 137−142(in Chinese) doi: 10.3969/j.issn.1673-629X.2021.05.024
[4]	Tatlı E S. Cracking more password hashes with patterns[J]. IEEE Transactions on Information Forensics and Security, 2015, 10(8): 1656−1665 doi: 10.1109/TIFS.2015.2422259
[5]	Hashcat. Hashcat: Advanced password recovery [EB/OL]. [2022-07-17].https://hashcat.net/hashcat/
[6]	Openwall. John the Ripper password cracker [EB/OL]. [2022-07-17]. http://www.openwall.com/john/
[7]	胡向东,柯希明,尹飞,等. 高性能众核处理器申威26010[J]. 计算机研究与发展,2021,58(6):1155−1165 doi: 10.7544/issn1000-1239.2021.20201041 Hu Xiangdong, Ke Ximing, Yin Fei, et al. Shenwei-26010: A high-performance many-core processor[J]. Journal of Computer Research and Development, 2021, 58(6): 1155−1165(in Chinese) doi: 10.7544/issn1000-1239.2021.20201041
[8]	Hashcat. Rule-based attack [EB/OL]. [2022-07-17].https://hashcat.net/wiki/doku.php?id=rule_based_attack
[9]	陈玥丹. 面向“神威·太湖之光”的异构并行算法设计与实现 [D]. 长沙:湖南大学,2020 Chen Yuedan. Design and implementation of heterogenous parallel algorithms on the Sunway Taihulight [D]. Changsha: Hunan University, 2020(in Chinese)
[10]	张恒,赵荣彩,董本松. 基于申威众核处理器的MD5解密算法优化[J]. 计算机与现代化,2022(2):13−18 doi: 10.3969/j.issn.1006-2475.2022.02.003 Zhang Heng, Zhao Rongcai, Dong Bensong. Optimization of MD5 decryption algorithm based on Sunway many-core processor[J]. Computer and Modernization, 2022(2): 13−18(in Chinese) doi: 10.3969/j.issn.1006-2475.2022.02.003
[11]	谢鑫君,罗顺,杨士华. 基于口令自生成的GPU暴力破解优化技术[J]. 信息安全与通信保密,2013(3):82−84 doi: 10.3969/j.issn.1009-8054.2013.03.032 Xie Xinjun, Luo Shun, Yang Shihua. An efficient improvement on gpu-hardware decryption through password’s self-manufacturing[J]. Information Security and Communications Privacy, 2013(3): 82−84(in Chinese) doi: 10.3969/j.issn.1009-8054.2013.03.032
[12]	董婉莹. 基于口令特征的高效字典生成方法研究 [D]. 郑州:郑州大学,2021 Dong Wanying. Research on efficient dictionary generation method based on password features [D]. Zhengzhou: Zhengzhou University, 2021(in Chinese)
[13]	Zhang Zhendong, Liu Peng, Wang Weidong, et al. RUPA: A high performance, energy efficient accelerator for rule-based password generation in heterogenous password recovery system [J]. IEEE Transactions on Computers, 2023, 72(4): 900−913
[14]	Weir M, Aggarwal S, Medeiros B, et al. Password cracking using probabilistic context-free grammars[C]//Proc of the 30th IEEE Symp on Security and Privacy. Piscataway, NJ: IEEE, 2009: 391−405
[15]	Marechal S. Automatic mangling rules generation [EB/OL]. [2022-12-30].https://www.openwall.com/presentations/Passwords12-Mangling-Rules-Generation/
[16]	Kacherginsky P. Password analysis and cracking kit [EB/OL]. [2022-12-30].https://github.com/iphelix/pack
[17]	Nam S, Jeon S, Moon J. Generating optimized guessing candidates toward better password cracking from multi-dictionaries using relativistic gan[J]. Applied Sciences, 2020, 10(20): 7306 doi: 10.3390/app10207306
[18]	Li Shunbin, Wang Zhiyu, Zhang Ruyun, et al. Mangling rules generation with density-based clustering for password guessing [J] IEEE Transactions on Dependable and Secure Computing, 2023, 20(5): 3588−3600
[19]	Ur B, Segreti S M, Bauer L, et al. Measuring real-world accuracies and biases in modeling password guessability[C]//Proc of the 24th USENIX Conf on Security Symp. Berkeley, CA: USENIX Association, 2015: 463−481
[20]	Lundberg T. Comparison of automated password guessing strategies [D]. Linköping: Linköping University, 2019
[21]	Amdahl G M. Validity of the single processor approach to achieving large scale computing capabilities[C]//Proc of the Spring Joint Computer Conf. New York: ACM, 1967: 483–485

[1]	Cao Yiran, Zhu Youwen, He Xingyu, Zhang Yue. Utility-Optimized Local Differential Privacy Set-Valued Data Frequency Estimation Mechanism[J]. Journal of Computer Research and Development, 2022, 59(10): 2261-2274. DOI: 10.7544/issn1000-1239.20220504
[2]	Hong Jinxin, Wu Yingjie, Cai Jianping, Sun Lan. Differentially Private High-Dimensional Binary Data Publication via Attribute Segmentation[J]. Journal of Computer Research and Development, 2022, 59(1): 182-196. DOI: 10.7544/issn1000-1239.20200701
[3]	Wu Wanqing, Zhao Yongxin, Wang Qiao, Di Chaofan. A Safe Storage and Release Method of Trajectory Data Satisfying Differential Privacy[J]. Journal of Computer Research and Development, 2021, 58(11): 2430-2443. DOI: 10.7544/issn1000-1239.2021.20210589
[4]	Zhang Yuxuan, Wei Jianghong, Li Ji, Liu Wenfen, Hu Xuexian. Graph Degree Histogram Publication Method with Node-Differential Privacy[J]. Journal of Computer Research and Development, 2019, 56(3): 508-520. DOI: 10.7544/issn1000-1239.2019.20170886
[5]	Zhu Weijun, You Qingguang, Yang Weidong, Zhou Qinglei. Trajectory Privacy Preserving Based on Statistical Differential Privacy[J]. Journal of Computer Research and Development, 2017, 54(12): 2825-2832. DOI: 10.7544/issn1000-1239.2017.20160647
[6]	Wu Yingjie, Zhang Liqun, Kang Jian, Wang Yilei. An Algorithm for Differential Privacy Streaming Data Adaptive Publication[J]. Journal of Computer Research and Development, 2017, 54(12): 2805-2817. DOI: 10.7544/issn1000-1239.2017.20160555
[7]	Wang Liang, Wang Weiping, Meng Dan. Privacy Preserving Data Publishing via Weighted Bayesian Networks[J]. Journal of Computer Research and Development, 2016, 53(10): 2343-2353. DOI: 10.7544/issn1000-1239.2016.20160465
[8]	Lu Guoqing, Zhang Xiaojian, Ding Liping, Li Yanfeng, Liao Xin. Frequent Sequential Pattern Mining under Differential Privacy[J]. Journal of Computer Research and Development, 2015, 52(12): 2789-2801. DOI: 10.7544/issn1000-1239.2015.20140516
[9]	Ouyang Jia, Yin Jian, Liu Shaopeng, Liu Yubao. An Effective Differential Privacy Transaction Data Publication Strategy[J]. Journal of Computer Research and Development, 2014, 51(10): 2195-2205. DOI: 10.7544/issn1000-1239.2014.20130824
[10]	Ni Weiwei, Chen Geng, Chong Zhihong, Wu Yingjie. Privacy-Preserving Data Publication for Clustering[J]. Journal of Computer Research and Development, 2012, 49(5): 1095-1104.

Cited By

Cited by

Periodical cited type(5)

1.	张涵，于航，周继威，白云开，赵路坦. 面向隐私计算的可信执行环境综述. 计算机应用. 2025(02): 467-481 .
2.	付裕，林璟锵，冯登国. 虚拟化与密码技术应用:现状与未来. 密码学报(中英文). 2024(01): 3-21 .
3.	徐传康，李忠月，刘天宇，种统洪，杨发雪. 基于可信执行环境的汽车域控系统安全研究. 汽车实用技术. 2024(15): 18-25+73 .
4.	徐文嘉，岑孟杰，陈亮. 隐私保护下单细胞RNA测序数据细胞分类研究. 医学信息学杂志. 2024(10): 86-89 .
5.	孙钰，熊高剑，刘潇，李燕. 基于可信执行环境的安全推理研究进展. 信息网络安全. 2024(12): 1799-1818 .