Compiler Optimizations to Reduce Security Overhead Tao Zhang Xiaotong Zhuang Santosh Pande College of Computing Georgia Institute of Technology Atlanta, GA, 30332-0280 {zhangtao, xt2000, santosh}@cc.gatech.edu Abstract In this work, we present several compiler optimizations to reduce the overhead due to software protection. We first propose an aggressive rematerialization algorithm which attempts to maximally realize non-trusted values from other trusted values thereby avoiding the security cost for those non-trusted values. We further propose a compiler technique to utilize the secure storage in our machine model efficiently. To optimize the security cost on data that has to be stored in non-trusted storage, we propose a data grouping technique. Security operations can be performed over the group of data instead of over each piece separately. We show an interesting application of the data grouping technique to reduce the security cost. We test the effectiveness of our optimizations on a recently proposed software protection scheme that involves large overhead. Our results show that the above optimizations are effective and reduce the security overhead significantly.1. Introduction Software security implies several important properties including confidentiality, integrity and recoverability. To enforce these properties, large overhead is introduced due to additional security operations in the software code. Thus there are hardware mechanisms such as in [18][19] introduced to provide the root of security as well as performance enhancements. However, large overhead still exists and those hardware solutions involve extensive changes to existing hardware. Recently, Zhang et al. [2] proposed a software solution based on secret sharing [1] with only minimum hardware support to achieve software data confidentiality, integrity and recoverability at the same time. Due to the lack of extensive hardware support, the performance degradation can reach up to 90% when all application data is protected. The overhead will be even higher when higher security levels are applied. In general, software security poses a great challenge to performance. In all software protection schemes, there is a security boundary. Data inside the security boundary can be trusted but data outside the security boundary must be protected from attacks. For schemes based on cryptographic mechanisms, to protect the confidentiality of the data, expensive encryption operations have to be performed every time the data is evicted outside the security boundary. The cost is in terms of tens of cycles even with crypto hardware support and can be up to hundreds of cycles if done in software. Similarly, to protect the integrity of the data, expensive hashing operations have to be performed every time the data is evicted outside the security boundary. The cost is similar to the encryption cost. Moreover, checksums generated during the hashing take memory space and increase memory cost. The secret sharing based scheme [2] has to pay similar cost to protect confidentiality and integrity, although based on a different mechanism. Besides confidentiality and integrity, recoverability (although largely ignored previously) is an equally important security property, especially for critical software providing critical services. To provide recoverability, redundancy has to be introduced, which tends to lead to significant performance and memory cost. Compiler has been playing a critical role in performance optimizations. In our work, we are interested in what a compiler can do to the performance challenge brought by software security. We assume a general machine model which requires only minimum hardware support and modifications to currently dominant micro-architectures. In our machine model, we assume that process contexts including registers are protected and trusted. We also assume that there is a software controlled secure storage inside the processor chip. Besides process contexts and the secure storage, all other components are considered non-Proceedings of the International Symposium on Code Generation and Optimization (CGO’06) 0-7695-2499-0/06 $20.00 © 2006 IEEEtrusted. We believe this is a realistic machine model in the near future, as explained in the next section. Based on the machine model, we present several compiler optimizations to reduce the overhead due to software protection. The overhead of software protection schemes is mainly due to the computation and memory cost of providing confidentiality, integrity and recoverability for non-trusted memory resident values. We first propose an aggressive rematerialization algorithm which attempts to maximally realize non-trusted values from other trusted values thereby avoiding the security cost for them. We further propose a compiler technique to utilize the secure storage efficiently. Data stored in the secure storage is trusted thus the security cost is avoided. To optimize the security cost on data that has to be stored in non-trusted storage, we propose a data grouping technique. Security operations can be performed over the group of data instead of over each piece separately. We show an interesting application of the data grouping technique to reduce security cost. The rest of the paper is organized as follows. Section 2 gives our machine model. Section 3 elaborates our compiler optimizations. Section 4 evaluates the effectiveness of the optimizations. Section 5 discusses related work. Finally section 6 concludes the paper. 2. Machine Model In this section, we clarify our machine model to facilitate the understanding of the optimizations proposed in this work. The goal of our machine model is to introduce minimum hardware support for security. We have two major assumptions in our machine model. We assume that process contexts including registers can be trusted. We also assume that there is a software controlled secure storage inside the processor chip. Note that such a software-controlled storage, like a scratch pad, is much cheaper than a hardware-controlled cache. All other components including the caches and the external memory are considered non-trusted. From the above assumptions, any data residing in the caches and the external memory is considered non-secure and has to be protected against attacks. On the other hand, data residing in registers and the secure storage is considered to be secure and does not need to be protected. The above assumptions can