计算机科学技术学报 ›› 2021,Vol. 36 ›› Issue (5): 1022-1036.doi: 10.1007/s11390-021-1253-8

所属专题： Computer Architecture and Systems

• • 上一篇    下一篇

一种用于安全分支预测器的新颖概率饱和计数器设计

Lu-Tan Zhao1,2, Rui Hou1,2,*, Senior Member, CCF, Kai Wang3, Yu-Lan Su1,2, Pei-Nan Li1,2 and Dan Meng1,2, Senior Member, CCF   

  1. 1 State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences Beijing 100093, China;
    2 School of Cyber Security, University of Chinese Academy of Sciences, Beijing 100093, China;
    3 Department of Computer Science and Technology, Harbin Institute of Technology, Harbin 150001, China
  • 收稿日期:2020-12-31 修回日期:2021-08-29 出版日期:2021-09-30 发布日期:2021-09-30
  • 作者简介:Lu-Tan Zhao received his B.E. degree in electronic information science and technology from Henan Polytechnic University, Zhengzhou, in 2014, and his M.E. degree in circuits and systems from University of Electronic Science and Technology of China, Chengdu, in 2017. He is a Ph.D. candidate at the State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences, Beijing. His current research interests include computer architecture and hardware security.
  • 基金资助:
    This work was supported by the Strategic Priority Research Program of Chinese Academy of Sciences under Grant No. XDC02010200 and the National Natural Science Foundation of China under Grant No. 62125208.

A Novel Probabilistic Saturating Counter Design for Secure Branch Predictor

Lu-Tan Zhao1,2, Rui Hou1,2,*, Senior Member, CCF, Kai Wang3, Yu-Lan Su1,2, Pei-Nan Li1,2 and Dan Meng1,2, Senior Member, CCF        

  1. 1 State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences Beijing 100093, China;
    2 School of Cyber Security, University of Chinese Academy of Sciences, Beijing 100093, China;
    3 Department of Computer Science and Technology, Harbin Institute of Technology, Harbin 150001, China
  • Received:2020-12-31 Revised:2021-08-29 Online:2021-09-30 Published:2021-09-30
  • About author:Lu-Tan Zhao received his B.E. degree in electronic information science and technology from Henan Polytechnic University, Zhengzhou, in 2014, and his M.E. degree in circuits and systems from University of Electronic Science and Technology of China, Chengdu, in 2017. He is a Ph.D. candidate at the State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences, Beijing. His current research interests include computer architecture and hardware security.
  • Supported by:
    This work was supported by the Strategic Priority Research Program of Chinese Academy of Sciences under Grant No. XDC02010200 and the National Natural Science Foundation of China under Grant No. 62125208.

PDF (PC)

15

补充材料

1

1、研究背景（context）：分支预测器有效提升指令并行性，是处理器性能优化方案中不可或缺的设计之一。饱和计数器是实现分支预测器的基本模块。以前的研究主要关注饱和计数器的性能和其硬件成本，忽略了其安全性。然而，近来的研究表明分支预测器侧信道攻击能够利用饱和状态计数器中状态的改变，获得敏感信息，威胁几乎所有的商用高性能处理器。这一严重的安全威胁表明探索有效防御机制的迫切性。
2、目的（Objective）：本文从饱和计数器模块切入，探索一种安全、轻量的硬件防御机制，通过改变饱和计数器确定性的更新策略，有效缓解分支预测器中的侧信道攻击。
3、方法（Method）：通过针对分支预测器的攻击深入分析，本文发现分支预测器侧信道存在的根源在于饱和计数器状态会随着程序行为确定性的更新。攻击者能够利用状态改变感知受害者的执行逻辑。为消除这个安全隐患，本文进一步提出了一个概率更新的机制，通过混淆状态改变与程序行为间的映射关系，该机制可以有效降低攻击者的观测成功率。通过引入随机化干扰感知攻击的过程有效缓解分支预测器漏洞。
4、结果（Result&Findings）：概率更新机制带来的平均性能损失小于2.4%，硬件代价几乎可以忽略不计。攻击的成功率随着更新概率的降低而降低，当更新概率为63%，攻击连续偷取32位密钥的成功率将低于百万分之一。
5、结论（Conclusions）：本文提出了一种新颖的概率饱和计数器设计方案，变传统的确定性状态转移模式为概率状态转移模式，仅需对原更新逻辑做微小改动，即可大大降低攻击者感知分支方向预测器的能力。

关键词: 分支预测器, 侧信道攻击, 饱和计数器

Abstract: In a modern processor, branch prediction is crucial in effectively exploiting the instruction-level parallelism for high-performance execution. However, recently exposed vulnerabilities reveal the urgency to improve the security of branch predictors. The vital cause of the branch predictor vulnerabilities is that the update strategy of the saturating counter is deterministic. As a fundamental building block in a modern branch predictor, previous studies have paid too much attention to the performance and hardware cost and ignored the security of saturating counter. This leaves attackers with the opportunities to perform side-channel attacks on the branch predictor. This paper focuses on the saturating counter to explore a secure and lightweight design to mitigate branch predictor side-channel attacks. Instead of applying the isolation mechanism to branch predictor resources, we propose a novel probabilistic saturating counter design to confuse the attacker's perception of the victim's behaviour. It changes the conventional deterministic state transition function to a probabilistic state transition function. When a branch is committed, the conventional saturating counter needs to be updated about whether the prediction results are correct or not. While for the probabilistic saturating counter, the branch predictor determines whether the update is performed based on the update probability. The probabilistic saturating counter dramatically reduces the ability of the attacker to spy the saturating counter's state. Our analyses using a cycle-accurate simulator suggest that the proposed mechanism incurs 2.4% performance overhead and hardware cost while providing strong protection.

Key words: branch predictor, side-channel attack, saturating counter

[1] Sinharoy B, Van Norstrand J A, Eickemeyer R J et al. IBM POWER8 processor core microarchitecture. IBM Journal of Research and Development, 2015, 59(1):Article No. 2. DOI:10.1147/JRD.2014.2376112.
[2] Suggs D, Subramony M, Bouvier D. The AMD "Zen 2" processor. IEEE Micro, 2020, 40(2):45-52. DOI:10.110-9/MM.2020.2974217.
[3] Grayson B, Rupley J, Zuraski G Z et al. Evolution of the Samsung Exynos CPU microarchitecture. In Proc. the 47th ACM/IEEE Annual International Symposium on Computer Architecture, May 30-June 3, 2020, pp.40-51. DOI:10.1109/ISCA45697.2020.00015.
[4] Evtyushkin D, Riley R, Abu-Ghazaleh N C, Ponomarev D. BranchScope:A new side-channel attack on directional branch predictor. In Proc. the 23rd International Conference on Architectural Support for Programming Languages and Operating Systems, March 2018, pp.693-707. DOI:10.1145/3173162.3173204.
[5] Lee S, Shih M W, Gera P et al. Inferring fine-grained control flow inside SGX enclaves with branch shadowing. In Proc. the 26th USENIX Security Symposium, August 2017, pp.557-574.
[6] Acii?mez O, Ko? ? K, Seifert J P. Predicting secret keys via branch prediction. In Proc. the 7th Cryptographers' Track at the RSA Conference on Topics in Cryptology, February 2007, pp.225-242. DOI:10.1007/1196766815.
[7] Acii?mez O, Ko? ? K, Seifert J P. On the power of simple branch prediction analysis. In Proc. the 2nd ACM Symposium on Information, Computer and Communications Security, March 2007, pp.312-320. DOI:10.1145/122-9285.1266999.
[8] Huo T, Meng X, Wang W et al. Bluethunder:A 2-level directional predictor based side-channel attack against SGX. IACR Transactions on Cryptographic Hardware and Embedded Systems, 2019, 2020(1):321-347. DOI:10.46586/tches.v2020.i1.321-347.
[9] Evtyushkin D, Ponomarev D, Abu-Ghazaleh N. Understanding and mitigating covert channels through branch predictors. ACM Transactions on Architecture and Code Optimization, 2016, 13(1):Article No. 10. DOI:10.114-5/2870636.
[10] Bhattacharya S, Mukhopadhyay D. Fault attack revealing secret keys of exponentiation algorithms from branch prediction misses. IACR Cryptol. ePrint Arch, 2014, 2014:Article No. 790.
[11] Vougioukas I, Nikoleris N, Sandberg A et al. BRB:Mitigating branch predictor side-channels. In Proc. the 2019 IEEE International Symposium on High Performance Computer Architecture, February 2019, pp.466-477, DOI:10.1109/HPCA.2019.00058.
[12] Lee L, Ishii Y, Abu-Sunwoo D. Securing branch predictors with two-level encryption. ACM Transactions on Architecture and Code Optimization, 2020, 17(3):Article No. 21. DOI:10.1145/3404189.
[13] Zhao L, Li P, Hou R et al. A lightweight isolation mechanism for secure branch predictors. arXiv:2005.08183, 2020. https://arxiv.org/abs/2005.08183, May 2021.
[14] McFarling S. Combining branch predictors. Technical Report, Digital Western Research Laboratory, 1993. https://www.hpl.hp.com/techreports/Compaq-DEC/WRL-TN-36.pdf, May 2021.
[15] Lee C, Chen I K, Mudge T N. The bi-mode branch predictor. In Proc. the 30th Annual International Symposium on Microarchitecture, Dec. 1997, pp.4-13. DOI:10.1109/MICRO.1997.645792.
[16] Kessler R E. The Alpha 21264 microprocessor. IEEE Micro, 1999, 19(2):24-36. DOI:10.1109/40.755465.
[17] Jimenez D A, Lin C. Dynamic branch prediction with perceptrons. In Proc. the 7th HPCA International Symposium on High-Performance Computer Architecture, Jan. 2001, pp.197-206. DOI:10.1109/HPCA.2001.903263.
[18] Tarjan D, Skadron K. Merging path and gshare indexing in perceptron branch prediction. ACM Transactions on Architecture and Code Optimization, 2005, 2(3):280-300. DOI:10.1145/1089008.1089011.
[19] Seznec A. TAGE-SC-L branch predictors again. In Proc. the 5th JILP Workshop on Computer Architecture Competitions (JWAC-5):Championship Branch Prediction (CBP-5), June 2016.
[20] Seznec A. A 256 Kbits L-TAGE branch predictor. In Proc. the 2nd JILP Workshop on Computer Architecture Competitions (JWAC-2):Championship Branch Prediction (CBP-2), Dec. 2006.
[21] Seznec A. A new case for the TAGE branch predictor. In Proc. the 44th Annual IEEE/ACM International Symposium on Microarchitecture, Dec. 2011, pp.117-127. DOI:10.1145/2155620.2155635.
[22] Kocher P, Horn J, Fogh A et al. Spectre attacks:Exploiting speculative execution. In Proc. the 2019 IEEE Symposium on Security and Privacy, May 2019, pp.1-19, DOI:10.1109/SP.2019.00002.
[23] Chen G, Chen S, Xiao Y et al. SgxPectre:Stealing intel secrets from SGX enclaves via speculative execution. In Proc. the 2019 IEEE European Symposium on Security and Privacy, June 2019, pp.142-157. DOI:10.1109/EuroSP.2019.00020.
[24] Evtyushkin D, Ponomarev D, Abu-Ghazaleh N. Jump over ASLR:Attacking branch predictors to bypass ASLR. In Proc. the 49th Annual IEEE/ACM International Symposium on Microarchitecture, October 2016, Article No. 40.
[25] Ahn Y J, Hwang D Y, Lee Y S et al. Saturating counter design for meta predictor in hybrid branch prediction. In Proc. the 8th WSEAS International Conference on Circuits, Systems, Electronics, Control & Signal Processing, December 2009, pp.217-221.
[26] Lee J K F, Smith A J. Branch prediction strategies and branch target buffer design. Computer, 1984, 17(1):6-22. DOI:10.1109/MC.1984.1658927.
[27] Sherwood T, Calder B. Automated design of finite state machine predictors for customized processors. In Proc. the 28th Annual International Symposium on Computer Architecture, June 30-July 4, 2001, pp.86-97. DOI:10.1145/379240.379254.
[28] Seznec A, Michaud P. A case for (partially) TAgged GEometric history length predictors. Journal of Instruction Level Parallelism, 2006, 8:Article No. 1.
[29] Sherwood T, Calder B. Loop termination prediction. In Proc. the 3rd International Symposium on High Performance Computing, October 2000, pp.73-87. DOI:10.1007/3-540-39999-28.
[30] Bulck J V, Piessens F, Strackx R. SGX-Step:A practical attack framework for precise enclave execution control. In Proc. the 2nd Workshop on System Software for Trusted Execution, October 2017, Article No. 4. DOI:10.1145/3152701.3152706.
[31] Zhang T, Koltermann K, Evtyushkin D. Exploring branch predictors for constructing transient execution trojans. In Proc. the 25th International Conference on Architectural Support for Programming Languages and Operating Systems, March 2020, pp.667-682. DOI:10.1145/3373-376.3378526.
[32] Elkhouly R, El-Mahdy A, Elmasry A. 2-Bit branch predictor modeling using Markov model. Procedia Computer Science, 2015, pp.650-653. DOI:10.1016/j.procs.2016.05.115.
[33] Zhang Y, Juels A, Oprea A, Reiter M K. HomeAlone:Coresidency detection in the cloud via side-channel analysis. In Proc. the 2011 IEEE Symposium on Security and Privacy, May 2011, pp.313-328. DOI:10.1109/SP.2011.31.
[34] Crane S, Homescu A, Brunthaler S et al. Thwarting cache side-channel attacks through dynamic software diversity. In Proc. the 22nd Annual Network and Distributed System Security Symposium, February 2015. DOI:10.14722/ndss.2015.23264.
[35] Sabbagh M, Fei Y, Wahl T et al. SCADET:A sidechannel attack detection tool for tracking Prime+Probe. In Proc. the 2018 IEEE/ACM International Conference on Computer-Aided Design, Nov. 2018, pp.1-8. DOI:10.1145/3240765.3240844.
[36] Binkert N, Beckmann B, Black G et al. The gem5 simulator. ACM SIGARCH Computer Architecture News, 2011, 39(2):1-7. DOI:10.1145/2024716.2024718.
[37] Bucek J, Lange K D, Von Kistowski J. SPEC CPU2017:Next-generation compute benchmark. In Proc. the Companion of the 2018 ACM/SPEC International Conference on Performance Engineering, April 2018, pp.41-42. DOI:10.1145/3185768.3185771.
[38] Li S, Ahn J H, Strong R D et al. McPAT:An integrated power, area, and timing modeling framework for multicore and manycore architectures. In Proc. the 42nd Annual IEEE/ACM International Symposium on Microarchitecture, December 2009, pp.469-480. DOI:10.1145/1669-112.1669172.
[39] Agosta G, Breveglieri L, Pelosi G et al. Countermeasures against branch target buffer attacks. In Proc. the Workshop on Fault Diagnosis and Tolerance in Cryptography, Sept. 2007, pp.75-79. DOI:10.1109/FDTC.2007.10.
[40] Yan M, Choi J, Skarlatos D et al. InvisiSpec:Making speculative execution invisible in the cache hierarchy. In Proc. the 51st Annual IEEE/ACM International Symposium on Microarchitecture, Oct. 2018, pp.428-441. DOI:10.1109/MICRO.2018.00042.
[41] Li P, Zhao L, Hou R et al. Conditional speculation:An effective approach to safeguard out-of-order execution against spectre attacks. In Proc. the 2019 IEEE International Symposium on High Performance Computer Architecture, Feb. 2019, pp.264-276. DOI:10.1109/HPCA.2019.00043.
[42] Yu J, Yan M, Khyzha A et al. Speculative taint tracking (STT):A comprehensive protection for speculatively accessed data. In Proc. the 52nd Annual IEEE/ACM International Symposium on Microarchitecture, October 2019, pp.954-968. DOI:10.1145/3352460.3358274.
[43] Hu W M. Lattice scheduling and covert channels. In Proc. the 1992 IEEE Computer Society Symposium on Research in Security and Privacy, May 1992, pp.52-61. DOI:10.1109/RISP.1992.213271.
[44] Pasricha S, Veidenbaum A. Improving branch prediction accuracy in embedded processors in the presence of context switches. In Proc. the 21st International Conference on Computer Design, Oct. 2003, pp.526-531. DOI:10.1109/ICCD.2003.1240950.
[45] Dhodapkar A S, Smith J E. Saving and restoring implementation contexts with co-designed virtual machines. In Proc. Workshop on Complexity-Effective Design, June 2001.
[46] Ramsay M, Feucht C, Lipasti M H. Exploring efficient SMT branch predictor design. http://citeseerx.ist.psu.edu/viewdoc/citations;jsessionid=156C5BEB0B1C452690D-8A3BBE301116F?doi=10.1.1.79.5793, Sept. 2021.
[47] Qureshi M K. CEASER:Mitigating conflict-based cache attacks via encrypted-address and remapping. In Proc. the 51st Annual IEEE/ACM International Symposium on Microarchitecture, Oct. 2018, pp.775-787. DOI:10.1109/MICRO.2018.00068.
[48] Purnal A, Giner L, Gruss D et al. Systematic analysis of randomization-based protected cache architectures. In Proc. the 42nd IEEE Symposium on Security and Privacy, May 2021, pp.987-1002. DOI:10.1109/SP40001.2021.00011.
[49] Bodduna R, Ganesan V, SLPSK P et al. Brutus:Refuting the security claims of the cache timing randomization countermeasure proposed in CEASER. IEEE Computer Architecture Letters, 2020, 19(1):9-12. DOI:10.1109/LCA.2020.2964212.
[1] Xiang-Jun Lu, Chi Zhang, Da-Wu Gu, Jun-Rong Liu, Qian Peng, Hai-Feng Zhang. 对基于线性回归建模方法的分析与改进：正则化选择[J]. 计算机科学技术学报, 2020, 35(5): 1175-1197.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
[1] 周笛;. A Recovery Technique for Distributed Communicating Process Systems[J]. , 1986, 1(2): 34 -43 .
[2] 陈世华;. On the Structure of Finite Automata of Which M Is an(Weak)Inverse with Delay τ[J]. , 1986, 1(2): 54 -59 .
[3] 李万学;. Almost Optimal Dynamic 2-3 Trees[J]. , 1986, 1(2): 60 -71 .
[4] 王建潮; 魏道政;. An Effective Test Generation Algorithm for Combinational Circuits[J]. , 1986, 1(4): 1 -16 .
[5] 陈肇雄; 高庆狮;. A Substitution Based Model for the Implementation of PROLOG——The Design and Implementation of LPROLOG[J]. , 1986, 1(4): 17 -26 .
[6] 黄河燕;. A Parallel Implementation Model of HPARLOG[J]. , 1986, 1(4): 27 -38 .
[7] 郑国梁; 李辉;. The Design and Implementation of the Syntax-Directed Editor Generator(SEG)[J]. , 1986, 1(4): 39 -48 .
[8] 黄学东; 蔡莲红; 方棣棠; 迟边进; 周立; 蒋力;. A Computer System for Chinese Character Speech Input[J]. , 1986, 1(4): 75 -83 .
[9] 许小曙;. Simplification of Multivalued Sequential SULM Network by Using Cascade Decomposition[J]. , 1986, 1(4): 84 -95 .
[10] 唐同诰; 招兆铿;. Stack Method in Program Semantics[J]. , 1987, 2(1): 51 -63 .
版权所有 © 《计算机科学技术学报》编辑部
本系统由北京玛格泰克科技发展有限公司设计开发 技术支持：support@magtech.com.cn
总访问量：