Journal of Computer Science and Technology ›› 2021, Vol. 36 ›› Issue (5): 1022-1036.doi: 10.1007/s11390-021-1253-8

Special Issue: Computer Architecture and Systems

• Special Section of APPT 2021 (Part 1) • Previous Articles     Next Articles

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.

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. Evaluating and Improving Linear Regression Based Profiling: On the Selection of Its Regularization [J]. Journal of Computer Science and Technology, 2020, 35(5): 1175-1197.
[2] Cheol Hong Kim, Sung Woo Chung, and Chu Shik Jhon. A Power-Aware Branch Predictor by Accessing the BTB Selectively [J]. , 2005, 20(5): 607-614 .
[3] FAN DongRui , YANG HongBo , GAO GuangRong and ZHAO RongCai . Evaluation and Choice of Various Branch Predictors for Low-Power Embedded Processor [J]. , 2003, 18(6): 0-0.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[1] Zhou Di;. A Recovery Technique for Distributed Communicating Process Systems[J]. , 1986, 1(2): 34 -43 .
[2] Chen Shihua;. On the Structure of Finite Automata of Which M Is an(Weak)Inverse with Delay τ[J]. , 1986, 1(2): 54 -59 .
[3] Li Wanxue;. Almost Optimal Dynamic 2-3 Trees[J]. , 1986, 1(2): 60 -71 .
[4] Wang Jianchao; Wei Daozheng;. An Effective Test Generation Algorithm for Combinational Circuits[J]. , 1986, 1(4): 1 -16 .
[5] Chen Zhaoxiong; Gao Qingshi;. A Substitution Based Model for the Implementation of PROLOG——The Design and Implementation of LPROLOG[J]. , 1986, 1(4): 17 -26 .
[6] Huang Heyan;. A Parallel Implementation Model of HPARLOG[J]. , 1986, 1(4): 27 -38 .
[7] Zheng Guoliang; Li Hui;. The Design and Implementation of the Syntax-Directed Editor Generator(SEG)[J]. , 1986, 1(4): 39 -48 .
[8] Huang Xuedong; Cai Lianhong; Fang Ditang; Chi Bianjin; Zhou Li; Jiang Li;. A Computer System for Chinese Character Speech Input[J]. , 1986, 1(4): 75 -83 .
[9] Xu Xiaoshu;. Simplification of Multivalued Sequential SULM Network by Using Cascade Decomposition[J]. , 1986, 1(4): 84 -95 .
[10] Tang Tonggao; Zhao Zhaokeng;. Stack Method in Program Semantics[J]. , 1987, 2(1): 51 -63 .

ISSN 1000-9000(Print)

         1860-4749(Online)
CN 11-2296/TP

Home
Editorial Board
Author Guidelines
Subscription
Journal of Computer Science and Technology
Institute of Computing Technology, Chinese Academy of Sciences
P.O. Box 2704, Beijing 100190 P.R. China
Tel.:86-10-62610746
E-mail: jcst@ict.ac.cn
 
  Copyright ©2015 JCST, All Rights Reserved