Yuan Zhao
email: yzhao@is.ac.cn

Jingqiang Lin

Wuqiong Pan
email: wqpan@is.ac.cn

Cong Xue

Fangyu Zheng
email: fyzheng@is.ac.cn

Ziqiang Ma

RegRSA: Using Registers as Buffers to Resist Memory Disclosure Attacks

Keywords: Memory Disclosure Attack, Register, RSA, Montgomery Multiplication

Memory disclosure attacks, such as cold-boot attacks and DMA attacks, allow attackers to access all memory contents, therefore introduce great threats to plaintext sensitive data in memory. Register-based and cache-based schemes have been used to implement RSA securely, at the expense of decreased performance. In this paper, we propose another concept named register buffer, which makes use of all available registers as secure data buffer, no matter scalar registers or vector registers. The plaintext sensitive data only appear in register buffer. Based on this concept, we finish a security implementation of 2048-bit RSA called RegRSA, to defeat against memory disclosure attacks. The 1024-bit Montgomery multiplication in RegRSA runs entirely in register buffer, by performing computations using scalar instructions and registers, maintaining intermediate variables in vector registers. Due to the size limitation of register buffer, several variables out of Montgomery multiplications are spilled into memory. Re-gRSA encrypts these variables with AES before saving in memory. Furthermore, RegRSA employs a windowing method and the CRT speed-up to accelerate R-SA, and minimizes the data exchange between registers and memory to reduce the workload of AES encryption/decryption. The evaluation on Intel Haswell i7-4770R shows that, the performance of RegRSA achieves a factor of 0.74 compared to the regular RSA implementation in OpenSSL and is much greater than PRIME, the existing register-based scheme for 2048-bit RSA. Moreover, RegR-SA allows multiple instances to run on a multi-core CPU simultaneously, which makes it more practical for the real-world applications.

Introduction

RSA [START_REF] Rivest | A method for obtaining digital signatures and public-key cryptosystems[END_REF] is the most prevalent asymmetric cryptographic algorithm. Although this algorithm is considered computationally secure, the RSA implementations face various security threats. Memory disclosure attacks, such as cold-boot attacks [START_REF] Halderman | Lest we remember: cold-boot attacks on encryption keys[END_REF] and DMA attacks [START_REF] Wetzels | Hidden in snow, revealed in thaw: Cold boot attacks revisited[END_REF], allow attackers to obtain all memory contents, which makes plaintext private keys in memory unsafe. Besides, the sensitive data used or produced during RSA private-key operations, which can be used to derive the private key, should not appear in memory in plaintext. These sensitive data shall be stored in some secure storage when they participate in the private-key computations.

Registers and L1 caches in CPUs dedicated to one core, become the required secure storage because they are exclusive to the thread currently running on this CPU core under certain controls [START_REF] Garmany | PRIME: private RSA infrastructure for memory-less encryption[END_REF][START_REF] Guan | Copker: Computing with private keys without ram[END_REF]. L1 caches are much larger than registers and programmes can be coded in high-level languages. But malicious binaries running on one CPU core could exploit the last-level cache (LLC) to flush a L1 cache line of other cores to memory with the hardware cache coherence mechanism. The existing cachebased scheme [START_REF] Guan | Copker: Computing with private keys without ram[END_REF] forces all other cores that share LLC, into the no-fill cache mode during the cryptographic computations, and sharply reduces the memory access performance of these cores. Moreover, it does not support multiple instances on the cores that shares LLC. The advantage of register-based scheme is that registers are unaffected by other cores, which builds the possibility of executing multiple instances on a multicore CPU simultaneously. However, the challenge is that registers might be not enough for the asymmetric cryptographic implementation, which requires (sensitive) data to be swapped between registers and memory frequently (results in frequent symmetric encryptions before being written into memory and decryptions after being loaded into registers). So the key point of register-based schemes is to implement the most frequent function entirely in registers as far as possible.

In order to implement an efficient register-based RSA system against memory disclosure attacks, we should choose an implementation method of RSA which has advantages both on speed and storage consuming. Redundant representation [START_REF] Gueron | Software implementation of modular exponentiation, using advanced vector instructions architectures[END_REF] is the major method for vector-instruction implementations, which achieves high speed but demands much more storage space. PRIME [START_REF] Garmany | PRIME: private RSA infrastructure for memory-less encryption[END_REF] adopts redundant representation method. In order to finish register-based RSA implementation, PRIME has to abandon CRT method and its performance is greatly degraded. Another vector approach [START_REF] Bos | Montgomery multiplication using vector instructions[END_REF] adopts 2-way single instructions to implement Montgomery multiplication, which consumes less storage than redundant representation method. But the authors in [START_REF] Bos | Montgomery multiplication using vector instructions[END_REF] point out that its speed is lower than 64-bit scalar implementation. So the register-based scheme adopting 64-bit scalar instructions is our mainly concerned.

Contributions

In this paper, we propose an 2048-bit RSA implementation named RegRSA, resistant to memory disclosure attacks. Our basic idea is to keep all plaintext sensitive data only in registers when being used in RSA private-key computations. The performance of RegRSA is close to the implementation in OpenSSL and it allows multiple instances to run on a multi-core CPU simultaneously. Our major contributions are described as follows:

• We propose a concept named register buffer that makes use of all available registers as secure data buffer. We also summarize the available registers in newer CPUs and the instructions used to move data between different kinds of registers. We present several improvements on using AES-NI [START_REF] Gueron | Intel Advanced Encryption Standard (AES) New Instructions Set[END_REF] to reduce the cost of AES key expansion for each data block.

Related Work

Cold-boot attacks and DMA attacks have been explored to access sensitive data in memory. The first attack exploiting the remanence effect of RAM was reported in [START_REF] Anderson | Tamper resistance -a cautionary note[END_REF]. In 2008, the work in [START_REF] Halderman | Lest we remember: cold-boot attacks on encryption keys[END_REF] presented an cold-boot attack which recovered cryptographic keys by freezing the RAM chips. The study in [START_REF] Wetzels | Hidden in snow, revealed in thaw: Cold boot attacks revisited[END_REF] provided an overview of cold-boot attacks and the proposed counter-measures. DMA attacks are launched from peripherals through high-speed peripheral ports like PCI [START_REF] Carrier | A hardware-based memory acquisition procedure for digital investigations[END_REF] and Firewire [START_REF] Böck | Firewire-based physical security attacks on windows 7, efs and bitlocker[END_REF]. TRESOR-HUNT [START_REF] Blass | TRESOR-HUNT: attacking CPU-bound encryption[END_REF] presented an advanced DMA attack to get the AES key in privileged registers by compromising the integrity of OS kernel. In order to resist memory disclosure attacks, register-based and cache-based schemes are proposed. The register-based schemes employ registers as the secure storage, such as AESSE [START_REF] Müller | AESSE: a cold-boot resistant implementation of AES[END_REF], Amnesia [START_REF] Simmons | Security through amnesia: a software-based solution to the cold boot attack on disk encryption[END_REF] and TRESOR [START_REF] Müller | TRESOR Runs Encryption Securely Outside RAM[END_REF] which keep AES keys in registers and computed AES using registers only. PRIME [START_REF] Garmany | PRIME: private RSA infrastructure for memory-less encryption[END_REF] is the first register-based scheme for 2048-bit RSA private-key operations, but its performance is greatly degraded. The study in [START_REF] Yang | Protecting elliptic curve cryptography against memory disclosure attacks[END_REF] proposed an elliptic curve cryptography implementation using CPU registers. On the other hand, the cache-based schemes employ caches to store sensitive data. FrozenCache [START_REF] Pabel | Frozen cache[END_REF] exploited CPU caches to store keys outside RAM. Copker [START_REF] Guan | Copker: Computing with private keys without ram[END_REF] proposed a method to perform RSA private-key operations within CPU caches. Existing RSA implementations against memory disclosure attacks including PRIME and Copker, cannot support simultaneous multiple instances on multi-core CPUs well. Mimosa [START_REF] Guan | Protecting private keys against memory disclosure attacks using hardware transactional memory[END_REF] is the first work to protect sensitive data using hardware transactional memory, which essentially stores data in caches; but it requires special CPU hardware features.

Outline

The rest of this paper is organized as follows. Section 2 introduces the available registers in CPU. Sections 3 and 4 describe the design and the implementation of RegRSA. In Section 5, we evaluate RegRSA in terms of security and performance. We conclude this paper in Section 6.

Available Registers in Commodity CPUs

Registers are classified into user-accessible registers and special internal registers. Useraccessible registers can be read or written by CPU instructions, while internal registers cannot be accessible by instructions. On Intel CPUs, the most commonly-used x86 platform, instructions include scalar instructions and vector instructions. Firstly, scalar integer instructions operate on scalar registers, also called general purpose registers (GPRs); and scalar floating-point instructions operate on floating-point registers. Secondly, Intel vector instruction sets include MMX [START_REF] Dulong | Complete Guide to MMX Technology[END_REF], SSE [START_REF]Intel. Intel 64 and ia-32 architectures software developer's manual[END_REF] and AVX [START_REF] Lomont | Introduction to intel advanced vector extensions[END_REF]. The registers for MMX are called MM registers, which are physically the same registers with floating-point registers. The registers for SSE are called XMM registers, and the registers for AVX are the extensions of XMM registers called YMM registers. XMM registers are the low 128-bit of YMM registers. A 64-bit CPU has more registers and every scalar register is double size. Users on 64-bit OS can manipulate these greatersize registers. For example, on an Intel Haswell CPU, there are sixteen 64-bit GPRs, eight 64-bit MM registers and sixteen 256-bit YMM registers. The total space of these registers is 704-byte. Besides, there are four 64-bit debug registers (DRs) available if the operating system prohibits debugged applications access these registers [START_REF] Müller | TRESOR Runs Encryption Securely Outside RAM[END_REF].

Table 1. Instructions used to move data between different kinds of registers

GPR MM XMM YMM DR GPR MOV MOV VMOV/PINR/VPINR - MOV MM MOV MOV MOVQ2DQ - - XMM VMOV/PEXTR/VPEXTR MOVDQ2Q MOVDQA/VMOVDQA VINSERTI128 - YMM - - VEXTRACTI128 VMOVDQA - DR MOV - - - -
Scalar registers, MM registers and YMM registers can be used as secure storage for sensitive computations. The data in different kinds of registers may be exchanged frequently. Table 1 summarizes the instructions used to move data between different kinds of registers. Note that, scalar registers and XMM registers can exchange data with most other registers, so they could be the hub of data exchange or keep the most commonly used data. Specifically, instructions PINR and VPINR insert a 64-bit data item from a scalar register to the particular location in a XMM register. The difference between PINR and VPINR is that, PINR is a legacy instruction that keeps the high 128-bit of the destination YMM register unchanged, but with performance penalty. VPINR is an new AVX instruction which will clear the high 128-bit of destination YMM register with no performance penalty.

System Design

In this section, we present the design goals of RegRSA. Then, we propose the concept of register buffer and describe the architecture of RegRSA on top of register buffer.

Design Goals

The target of this work is to design a secure and efficient 2048-bit RSA implementation as follows. Security Goal. All the sensitive data including cryptographic keys (AES keys and RSA private keys) and intermediate variables does not appear in the memory in the form of plaintext, against cold-boot attacks [START_REF] Halderman | Lest we remember: cold-boot attacks on encryption keys[END_REF] and other memory disclosure attacks. Performance Goal. The speed of RegRSA should be close to regular implementations, e.g., OpenSSL. Multiple optimization techniques are expected to be exploited in RegR-SA, such as Montgomery multiplication [START_REF] Montgomery | Modular multiplication without trial division[END_REF], the windowing method [START_REF] Koc | High-speed RSA implementation[END_REF] for modular exponentiation, and the CRT speed-up [START_REF] Koc | High-speed RSA implementation[END_REF]. Assumptions. First, the OS kernel is trustworthy, which means an attacker can not tamper the OS kernel to launch attacks such as TRESOR-HUNT [START_REF] Blass | TRESOR-HUNT: attacking CPU-bound encryption[END_REF]. Second, the system initialization before any user-space process is safe for users to input a password to derive an AES key in privileged debug registers [START_REF] Müller | TRESOR Runs Encryption Securely Outside RAM[END_REF]. Finally, the register features are available in hardware and software platform, that is, CPUs and the OS are 64-bit, and necessary instruction extensions including AVX, AES-NI and MULX are ready.

Register Buffer

Existing register-based schemes [START_REF] Garmany | PRIME: private RSA infrastructure for memory-less encryption[END_REF][START_REF] Müller | TRESOR Runs Encryption Securely Outside RAM[END_REF][START_REF] Yang | Protecting elliptic curve cryptography against memory disclosure attacks[END_REF] have investigated the usage of registers for storing sensitive data, but only focused on some registers (not all available registers). The high-speed implementations of cryptographic algorithms have explored the cooperation of different kinds of instructions and registers to accelerate cryptograph computing, but such implementations do not systematically consider the security of keys. In this paper, we propose a concept named register buffer, which makes use of all available registers as secure data buffer, no matter scalar registers or vector registers.

As the registers are used to provide operands and accept results for certain instructions, register buffer requires the comprehensive cooperation of different kinds of instructions and registers for efficient computing and secure storage. As described in Figure 1, register buffer is divided into two sets of registers: computation-reg and storage-reg. Computation-reg is a set of registers which provides inputs and receives results for ongoing instructions. Storage-reg is a set of registers for maintaining data unused in the current period. The registers are ready to be converted between computation-reg and storage-reg depending on which kind of instructions are being executed. Data are plaintext in register buffer. When data have to be stored in memory (RAM or caches), they are encrypted with AES. In brief, register buffer deems that all available registers are secure storage resources which should be fully utilized for efficiency and security.

RegRSA Architecture

From an implementation point of view, RegRSA is divided into three levels: (1) the modular multiplication level, (2) the modular exponentiation level and (3) the RSA level. The high level calls the lower level by sending parameters and receiving results. The architecture and the data transfer between registers and main memory are depicted in Figure 2. In the modular multiplication level, we design and implement an all-register 1024bit Montgomery multiplication which computes Montgomery multiplication by using scalar instructions and registers, maintaining parameters in vector registers. In the modular exponentiation level, we apply the windowing method for 1024-bit Montgomery exponentiation. We compute, encrypt and save precomputed table in the kernel heap, and then load the precomputed values depending on the exponents and decrypt the values. Based on the CRT method, we implement 2048-bit RSA by performing two 1024-bit Montgomery exponentiations. The encrypted Montgomery exponents are loaded from memory and the results of Montgomery exponentiations are encrypted and swapped between registers and the kernel stack. In all levels, all the sensitive data in RAM are encrypted with AES and the AES key is in debug registers. Note that, the major computations, Montgomery multiplication, do not need to exchange data between register and memory, so the performance degradation from data encryption/decryption and exchange is not significant.

1024-bit

Implementation

In this section, we describe the detailed implementation of RegRSA: in particular, the assembly codes of RegRSA to gain the complete control of registers, and the integration of RegRSA into Linux kernel because such implementation must run in kernel mode otherwise task switching may dump registers into RAM. [START_REF] Koc | Analyzing and comparing montgomery multiplication algorithms[END_REF] is an interleaved Montgomery multiplication method with three 1024-bit inputs A, B, M and one 64-bit input µ (-M -1 mod 2 64 ). As depicted in Figure 3, we employ scalar registers and scalar instructions to perform Montgomery multiplication, while keeping three 1024-bit inputs in YMM registers, 64-bit input in a scalar register and saving the 64-bit intermediate variables q j (q j = S j × µ mod 2 64 ) in MM registers. We make full use of 704-byte register buffer to finish the first all-register 1024-bit Montgomery multiplication implementation.

Montgomery Multiplication Implementation

1024-bit Montgomery multiplication [22] performs the computation

S = A × B × R -1 (mod M), R = 2 1024 , 0 A, B < M < R. Coarsely Integrated Operand Scanning (CIOS)

A[0] A[2] A[4] A[6] × B[j] M[0] M[2] M[4] M[6] × qj A[1] A[3] A[5] A[7] × B[j] M[1] M[3] M[5] M[7] × qj

A[0] B[j] q j Sj Sj+1 A M B q j GPR YMM MM A[7] M[0] M[7] ... ...

Fig. 3. First part of our 1024-bit Montgomery multiplication implementation

According to 64-bit Linux call convention, registers RBX, RBP, RSP, R12, R13, R14, R15 must be protected, we push these registers except RSP into stack. Since the left fifteen 64-bit scalar registers are not enough for computing the whole 1024-bit Montgomery multiplication in one time, we split Montgomery multiplication into four parts. The first part performs

A[0 ∼ 7] × B[0 ∼ 7] + M[0 ∼ 7] × (q 0 ∼ q 7 ), the second part performs A[8 ∼ 15] × B[0 ∼ 7] + M[8 ∼ 15] × (q 0 ∼ q 7 ), the third part performs A[0 ∼ 7] × B[8 ∼ 15] + M[0 ∼ 7] × (q 8 ∼ q 15 ) and the fourth part is A[8 ∼ 15] × B[8 ∼ 15] + M[8 ∼ 15] × (q 8 ∼ q 15
). The j-th round computation of the first part is depicted in Figure 3. Instruction MULX [START_REF]Intel. Intel 64 and ia-32 architectures software developer's manual[END_REF] is used to perform 64-bit scalar multiplication. The summation variable S occupies nine scalar registers and is updated in every round, and q j in MM registers is moved back when needed. Eight MM registers are enough for storing q 0 ∼ q 7 or q 8 ∼ q 15 for eight rounds. Besides, the final subtraction in Montgomery multiplication is always performed, whether or not S is no less than M, to eliminate the timing side-channel [START_REF] Brumley | Remote timing attacks are practical[END_REF].

Montgomery Exponentiation Implementation

We use the fixed windowing method [START_REF] Koc | High-speed RSA implementation[END_REF] to speed up Montgomery exponentiation. The size of window is 6-bit (64 entries). For CRT-enabled RSA, two different moduli are needed; i.e., for the private-key parameters p and q, two tables of C p k and C q k (k = 0, • • • , 63) which share a memory space. At the beginning of Montgomery exponentiation, we prepare precomputed table: compute and encrypt C p 2 ∼ C p 63 (or C q 2 ∼ C q 63 ), save them into kernel memory. C p 0 , C p 1 (or C q 0 , C q 1 ) are also encrypted and saved in the precomputed table for the const time of table lookup. Then we get the precomputed value from the precomputed table to YMM registers depending on the exponent, and decrypt them using 128-bit AES. Since the maximum size of kernel stack is 8KB which still has to save struct thread_info at the stack bottom, 6-bit precomputed table which needs 8KB memory cannot be saved in kernel stack. So we use system function kmalloc to allocate 8KB memory on the kernel heap for precomputed table before beginning RegRSA, and use function kfree to free memory after finishing Re-gRSA. We load all entries of the precomputed table in sequence when we need certain precomputed values.

AES-NI instruction extension [START_REF] Gueron | Intel Advanced Encryption Standard (AES) New Instructions Set[END_REF] is used to implement AES encryption/decryption and key expansion by hardware. In this study, we present several improvements on using AES-NI. First, AES-128 and AES-256 only need one 128-bit temporary register in the key expansion. Second, we derive the round keys from the last round to the first round which is very useful for AES decryption. Third, we perform on-the-fly bulk AES encryption/decryption which uses one round key to process multiple 128-bit data blocks and then the next round key, which sharply reduces the cost of key expansions for each data block.

RSA Implementation

We utilize the CRT method and our 1024-bit Montgomery exponentiation implementation to finish 2048-bit RSA private-key operations. The input parameters are copied from the user space memory to the kernel space memory, including the CRT parameters p, C p , d p , q, C q , d q , q -1 mod p, and Montgomery parameters R 2 mod p, R 2 mod q, -p -1 mod 2 r , -q -1 mod 2 r . The parameters d p , d q , q -1 mod p, R 2 mod p, R 2 mod q, -p -1 mod 2 r , -q -1 mod 2 r are constant for each private key, while C p = C mod p and C q = C mod q which need to be computed on the fly for each ciphertext C. All the above parameters are encrypted with AES when they are stored in memory. As described in Algorithm 1, the CRT speed-up requires two 1024-bit Montgomery exponentiations for 2048-bit RSA. As register buffer is not enough to hold the result of one Montgomery exponentiation while performing another, we keep the intermediate variables encrypted in memory.

Algorithm 1 Implementation of 2048-bit RSA Private-key Operation

Input: The CRT parameters p, C p , d p , q, C q , d q , q -1 mod p, and Montgomery parameters R 2 mod p, R 2 mod q, -p -1 mod 2 r , -q -1 mod 2 r Output: Plaintext M.

1: Load parameters p, C p , d p , R 2 mod p, -p -1 mod 2 r from RAM to registers and decrypt them with AES 2: M p ← C p dp mod p 3: Encrypt M p with AES and save it in RAM 4: Load parameters q, C q , d q , R 2 mod q, -q -1 mod 2 r from RAM to registers and decrypt them with AES 5: M q ← C q dq mod q 6: Encrypt M q with AES and save it in RAM 7: Load M p , M q , q, q -1 mod p, R 2 mod p, -p -1 mod 2 r from RAM to registers and decrypt them with AES 8: M ← M q + [(M p -M q ) × (q -1 mod p) mod p] × q 9: return M

Integration in Linux Kernel

We integrate RegRSA into Linux kernel to ensure no data in registers would leak into main memory. Char module. We integrate RegRSA into a char module and compile this module into Linux kernel. The module provides an interface for user space with the system call ioctl. The user processes can use the interface to send the inputs to RegRSA and receive the results. In kernel space, RegRSA can access privileged debug registers for AES keys (and all other registers). Atomicity. Before the execution of RegRSA, kernel preemption is suspended by calling preempt_disable and interrupts are disabled by calling local_irq_save. So data in registers will not be written into main memory by context switch during the RegRSA computations. Finally, kernel preemption is restored by calling preempt_enable and interrupts are enabled by calling local_irq_restore. As non-maskable interrupts (NMIs) cannot be disabled by software settings, we adopt the solution in Copker [START_REF] Guan | Copker: Computing with private keys without ram[END_REF].

We modify NMI handlers to clear registers with sensitive data, including scalar registers, MM registers and YMM registers.

AES Key

AES key is securely produced and maintains safety after OS initialization. AES key derivation. By utilizing an existing technique in TRESOR [START_REF] Müller | TRESOR Runs Encryption Securely Outside RAM[END_REF], we have patched the linux kernel to let user input a password before any userland process startup. We assume the password is strong enough to defeat against brute-force attacks. Moreover, the user can update AES keys by changing the password after a while. AES key protection. Also like in TRESOR [START_REF] Müller | TRESOR Runs Encryption Securely Outside RAM[END_REF], AES key is stored in debug registers which cannot be accessed from user space. System functions ptrace_set_debugreg and trace_get_debugreg are patched to ensure the user process cannot set four debug registers dr0 to dr3 or get their values.

Evaluation

In this section, we conduct security analysis on RegRSA, evaluate its performance and the impact of RegRSA. In the end, we discuss some further considerations. The system is evaluated on this platform: Intel Haswell i7-4770R CPU, 8GB memory and OS is Ubuntu 14.04 64-bit. We turn off Turbo Boost of Intel Haswell i7-4770R for stable frequency 3.2GHz, in the performance experiments.

Security Analysis

Memory Disclosure Attacks. First, we explore the security for the situation of only one RegRSA running instance on CPU. The input parameters are all sensitive data, including CRT parameters and Montgomery parameters, which are encrypted with AES before passing from user space to kernel space. AES key is in privileged debug registers, no user process could read or write these registers. Due to the atomic execution of RegRSA, no data in registers will leak into main memory by task switch. In the Montgomery multiplication level, all the intermediate variables are produced and kept in registers. In the Montgomery exponentiation level, the precomputed table is encrypted before stored in RAM, and the precomputed values are decrypted in XMM registers. In the RSA level, the results of Montgomery exponentiation are encrypted before stored in memory and decrypted after reading into registers. All the data in registers are eliminated before leaving the atomic region. In a word, all the sensitive data in main memory are encrypted, and the plaintext sensitive data appear in registers only.

Also, we have done experimental evaluation on RegRSA. We used Kdump to dump kernel memory while RegRSA was performing RSA private-key operations. We searched AES keys and RSA private keys in the captured image and found no matching strings.

When there are multiple instances of RegRSA on several CPU cores, no matter how many requests received from user space, only one RegRSA instance is running on a single CPU core in a moment due to the atomic execution. As each RegRSA instance owns its own variables in kernel stack and heap, RegRSA can execute multiple instances on different CPU cores which will not interfere with each other.

Cache-based Timing Side-Channels. RegRSA is resistant to cache-based timing side channel attacks [START_REF] Bernstein | Cache-timing attacks on AES[END_REF][START_REF] Bonneau | Cache-collision timing attacks against AES[END_REF][START_REF] Brumley | Remote timing attacks are practical[END_REF]. We employ the fixed windowing method in Montgomery exponentiation and the final subtraction in Montgomery multiplication is always performed, so there is no branch in the execution flow. Thus, there is no timing side channels in RegRSA based on instruction paths. When we perform the table-lookup in Montgomery exponentiation, we load the precomputed table as a whole. This makes attackers could not learn which entry RegRSA accesses and deduce the exponents. Therefore, there is no timing side channels attacks based on data access.

Performance

Comparison with OpenSSL. We launch different numbers of threads in user space to send RSA private-key operation requests to RegRSA. Because of simultaneous multithreading (SMT), eight threads make RegRSA occupy the CPU fully. RegRSA is compared with OpenSSL version 1.0.1f, in different concurrent levels. The numbers of RSA private-key operations per second and the ratios of the performances between RegRSA and OpenSSL are given in Table 2. As the number of threads increases, the performance becomes better, either for Re-gRSA or OpenSSL. RegRSA achieves at least a factor of 0.74 compared to the speed of OpenSSL. The efficiency degradation of 26% is acceptable, to defeat against memory disclosure attacks.

Comparison with PRIME. We expect to compare RegRSA with PRIME [START_REF] Garmany | PRIME: private RSA infrastructure for memory-less encryption[END_REF] on the same platform. Because we do not have the source code of PRIME, the comparison with PRIME is conducted through OpenSSL -we assume the OpenSSL in [START_REF] Garmany | PRIME: private RSA infrastructure for memory-less encryption[END_REF] is identical with that in this paper (version 1.0.1f). Table 3 presents the speed ratio of PRIME and RegRSA to OpenSSL, respectively. So we can see that the efficiency of RegRSA is far beyond PRIME; moreover, RegRSA can execute 8 instances on quad-core CPUs simultaneously.

Impact on Concurrent Tasks

As RegRSA disables kernel preemption and interrupts during its running, the stable of the operating system and the performance of other applications may be effected. We initiate eight user threads to continuously send RSA private-key operation requests. The results are presented in Table 4. There is no significant difference between the situations of RegRSA, mock RegRSA and OpenSSL. So disabling kernel preemption and interrupts in RegRSA does not cause obvious negative effects.

Discussions

SMT. SMT on Intel CPUs also known as Hyper-Threading (HT), which is used to improve the efficiency of processing units in CPUs. HT provides two hardware threads on each core. Each thread has a separate set of registers that can be used for RegRSA. So RegRSA can run at most eight instances on a quad-core HT CPU simultaneously. Two threads on one CPU core will facilitate instruction pipelining which improves performance of RegRSA slightly; see Table 2 for details.

Full Memory Encryption. The aim of full memory encryption is to provide confidentiality of the entire software stack outside the CPU [START_REF] Henson | Memory encryption: a survey of existing techniques[END_REF]; therefore, memory disclosure attacks are defeated. However, existing memory encryption suffer significant performance degradation [START_REF] Henson | Beyond full disk encryption: protection on security-enhanced commodity processors[END_REF].

Other CPUs. If a CPU possesses multiple registers including scalar registers, MM registers and YMM registers, and supports AES-NI instruction set and MULX instruction, it may be a suitable platform for RegRSA. So besides Intel CPUs, other CPUs like AMD can also be considered. For example, AMD Carrizo CPUs also support AVX2, MULX and AES-NI, it can be a potential candidate.

Conclusion

We propose a concept named register buffer that makes use of all available registers as secure data buffer, and design and implement 2048-bit RSA named RegRSA. In RegR-SA, all the sensitive data appeared in main memory are encrypted, and the plaintext data are protected in registers to defeat against memory disclosure attacks. The evaluation on Intel Haswell i7-4770R showed that, the performance of RegRSA achieves at least a factor of 0.74 compared to the RSA implementation of OpenSSL. Moreover, RegRSA supports multiple instances on multi-core CPUs simultaneously, which makes RegRSA more practical for the real-world applications against memory disclosure attacks. We will explore to use two sets of registers of Hyper-Threading for one RSA computation instance in the future.

Fig. 1 .

 1 Fig. 1. Register buffer

•

  We make full use of 704-byte register buffer in Intel Haswell CPU to implement an 1024-bit Montgomery multiplication running entirely in register buffer, by performing computations using scalar instructions and registers, maintaining intermediate variables in vector registers. • We use a fixed windowing method to speed up Montgomery exponentiation, and finish a CRT-enabled 2048-bit RSA implementation. The precomputed table and intermediate variables are encrypted and stored in OS kernel heap or stack.

Table 2 .

 2 Comparison with OpenSSL

	# of Concurrent Threads	1	4	8
	RegRSA	637	2537	2638
	OpenSSL	858	3308	3571
	RegRSA / OpenSSL	0.74	0.77	0.74

Table 3 .

 3 Comparison with PRIMEThrough a period of observation, we see that the operating system works properly without disruptions, and the response of OS is normal as well. Then we use the SysBench benchmark to evaluate the performance impact on concurrent tasks. We run the CPU test of SysBench and execute the test in four situations. The first is no computing-intensive tasks performing during the test. The second is same as OS stable test with running eight user threads to send requests to RegRSA. The third is to start eight threads to perform a "mock" RegRSA in user space. This mock RegRSA does not disable kernel preemption and interrupts, and use a fixed value as the AES key -other configurations are the same as those of RegRSA. The fourth is to perform OpenSSL speed test for 2048-bit RSA private-key operations in eight threads. Test parameters of SysBench are 8 threads, 10,000 requests and prime numbers up to 20000. The test score is the average time for each request.

		Latency (ms)	Speed Ratio
	PRIME	21.0	-
	OpenSSL [10]	1.8	-
	PRIME / OpenSSL [10]	-	0.086
	RegRSA / OpenSSL 1.0.1f	-	0.74

Table 4 .

 4 Impact on other applications

		Idle	RegRSA	Mock RegRSA	OpenSSL
			kernel space	user space
	SysBench (ms)	2.83	5.94	5.87	5.98

This work was partially supported by National 973 Program under award No. 2014CB340603 and No. 2013CB338001, and Strategy Pilot Project of Chinese Academy of Sciences under award No. XDA06010702. Corresponding author.


Changhai Ou

Zhu Wang

Degang Sun
email: sundegang@iie.ac.cn

Xinping Zhou
email: zhouxinping@iie.ac.cn

Juan Ai
email: aijuan@iie.ac.cn

Uncertain? No, It's Very Certain!

Keywords: guessing entropy, CPA, guessing entropy enhanced CPA, GE-CPA, side channel, DP A contest v1

de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Standaert et al. proposed two evaluation methods success rate and guessing entropy to evaluate the efficiency of side channel attacks [START_REF] Standaert | A unified framework for the analysis of side-channel key recovery attacks[END_REF]. Souissi et al. detailed that, on one hand, the first-order success rate denoted the probability that, given a pool of traces, the attack's best guess was the correct key; On the other hand, the guessing entropy measured the position of the correct key in a list of key hypotheses ranked by a kind of side channel attack [START_REF] Souissi | First principal components analysis: a new side channel distinguisher[END_REF]. A. Venelli expressed guessing entropy as the average position of the correct hypothesis in the sorted hypothesis vector of an attack [START_REF] Venelli | Efficient entropy estimation for mutual information analysis using bsplines[END_REF]. The positions of wrong keys are not taken into consideration.

In short, as well as the concept of entropy firstly proposed by Shannon [START_REF] Shannon | A mathematical theory of communication[END_REF], which denotes the uncertainty of information, guessing entropy is also used to denote the uncertainty of information. The higher the guessing entropy, the greater uncertainty of the key.

Related Works

There are three main types of applications of the guessing entropy:

Firstly, as well as success rate in [START_REF] Standaert | Partition vs. comparison sidechannel distinguishers: An empirical evaluation of statistical tests for univariate side-channel attacks against two unprotected cmos devices[END_REF][START_REF] Rivain | On the exact success rate of side channel analysis in the gaussian model[END_REF][START_REF] Veyrat-Charvillon | An optimal key enumeration algorithm and its application to side-channel attacks[END_REF][START_REF] Lomné | How to estimate the success rate of higher-order side-channel attacks[END_REF], guessing entropy is used to evaluate the efficiency of side channel attacks. In other words, guessing entropy is used to evaluate the uncertainty of key [START_REF] Nassar | Rsm: a small and fast countermeasure for aes, secure against 1st and 2nd-order zero-offset scas[END_REF][START_REF] Fei | A statistical model for dpa with novel algorithmic confusion analysis[END_REF][START_REF] Luo | Algorithmic collision analysis for evaluating cryptographic systems and side-channel attacks[END_REF].

Secondly, as well as entropy, guessing entropy is also used to evaluate the uncertainty of information. The information here is not limited to the key. For example, Michael Backes and Boris Köpf proposed a novel approach for quantifying a system's resistance to unknown message side channel attacks using guessing entropy [START_REF] Backes | Formally bounding the side-channel leakage in unknownmessage attacks[END_REF].

Thirdly, guessing entropy is used to improve the efficiency of side channel attacks. Nassar et al. proposed an empirical approach named Rank Corrector (RC) aiming at enhancing most side channel attacks [START_REF] Nassar | rank correction: A new sidechannel approach for secret key recovery[END_REF]. The main principle of RC is to detect and discard the false keys hypotheses when analyzing the ranking evolution. With the increase number of power traces, the correct key will reach the first position. Martin et al. constructed an extremely efficient algorithm that accurately computing the rank of a (known) key in the list of all keys [START_REF] Mather | Multi-target dpa attacks: Pushing dpa beyond the limits of a desktop computer[END_REF]. This approach is tweaked and can be also utilised to enumerate the most likely keys in a parallel fashion.

However, the above improvements only consider that guessing entropy changes with the number of power traces used in each repetition. They don't consider the relationship between the repetitions and guessing entropy. So, very different from [START_REF] Mather | Multi-target dpa attacks: Pushing dpa beyond the limits of a desktop computer[END_REF], we make use of the information leaking from the guessing entropy to recover the key rather than only a kind of evaluation in this paper. Our scheme significantly improves the efficiency of CPA.

Our Contributions

It is difficult to recover the key using in cryptographic device with a probability of about 1.00 under the condition that the number of power traces is very small and the success rate is very low. To solve the problem, we propose guessing entropy enhanced CPA (GE-CPA) in this paper. Its feasibility is proved in theory and experiment. Experiments on an AT89S52 single chip and the Side Channel Attack Standard Evaluation Board (SASEBO) show that, our scheme can effectively recover the key with a probability of about 1.00 even under the condition that the success rate of traditional CPA is only about 5% to 8%. Thus, the problem is well solved.

Organization

This paper is organized as follows. The concept of guessing entropy in side channel attack is given in Section 2. In Section 3, we introduce our guessing entropy enhanced CPA (GE-CPA). Then, in Section 4, experiments on AES algorithm implemented on an AT89S52 single chip and power trace set secmatv1 on DES algorithm implemented on the side channel attack standard evaluation board (SASEBO) from the website DP A contest V 1 [START_REF]Dpa contest[END_REF] are performed to compare our GE-CPA with traditional CPA. Finally, we conclude this paper in Section 5.

Guessing entropy

Similar to Shannon entropy, guessing entropy (GE) [START_REF] Standaert | A unified framework for the analysis of side-channel key recovery attacks[END_REF] in side channel attacks also denotes the uncertainty of information. Guessing entropy is defined as the key position in side channel attack. For example, the attacker performs C-PA on AES and gets 256 correlation coefficients corresponding to guessing key from 0 to 255. Then, the correlation coefficients are sorted in descending order. The bit length of key corresponding to the same intermediate value is 8. For each 2 8 possible key in each experiment, if the guessing entropy of guessing key k

′ 0 ≤ k ′ ≤ 2 8
-1 is in the position ν, the the guessing entropy is equal to ν.

The guessing entropy, which represents the uncertainly of the key used in cryptographic device, is widely used to evaluate the efficiency of side channel attacks.

Guessing entropies enhanced CPA

In this section ,we will introduce the statistical characteristics of guessing entropy. Then, we introduce the way to determine the correct key from guessing entropy enhanced CPA (GE-CPA). The attack flow and the special success rate of our GE-CPA are also given in this section.

3.1

The Statistical Characteristic of Guessing Entropy

We have shown the guessing entropy defined by Standaert et al [START_REF] Standaert | A unified framework for the analysis of side-channel key recovery attacks[END_REF] in Section 2. The location i of the correct key s is returned for each experiment. In this paper, We assume that all keys are likely to be the correct one. However, the correct key is the most superior one of all possible keys. Thus, different to [START_REF] Standaert | A unified framework for the analysis of side-channel key recovery attacks[END_REF], in order to select the optimal key, we calculate guessing entropies for all possible keys. Each guessing key returns a guessing entropy for each repetition. We sort the guessing entropies in descending order and assign different scores according to their positions in the guessing vector. For example, small guessing entropies are given higher scores. Suppose that the bit length of key corresponding to the same intermediate value is ξ. For each of 2 ξ possible keys in each repetition, if the guessing entropy of guessing key k

′ 0 ≤ k ′ ≤ 2 ξ -1 is ν, then we define the score of guessing entropy of k ′ as W k ′ = 2 ξ + 1 -ν. (1)

Determine The Correct Key from Guessing Entropies

Standaert et al. also defined the first order success rate in [START_REF] Standaert | A unified framework for the analysis of side-channel key recovery attacks[END_REF]. A guessing key is returned in each experiment. If this key is the correct one, then we say that the attack experiment satisfies the first order success. Similar to their definition, we define a successful CPA [START_REF] Brier | Correlation power analysis with a leakage model[END_REF] if the correct key s satisfies

s = argmax k {W k } . (2)
Actually, the equation ( 2) is usually satisfied when the guessing entropy of the correct key is close to 1. That's to say, if the number of power traces used in our experiment is n, then the probability

lim n→∞ P r[s = argmax k {W k }] = 1. (3)
For each successful repetition, the score of guessing entropy of the correct key is greater than these of wrong guessing keys. So, guessing entropy can be used to distinguish the correct key from the wrong ones. This is why guessing entropy can also contribute to the key recovery.

Let n denote the number of power traces used in each repetition. We define a function of scores of guessing entropies corresponding to guessing key k

′ on η repetitions (Exp 1 , Exp 2 , • • • , Exp γ ) as ψ γ, n, k ′ = f W Exp1 k ′ , W Exp2 k ′ , • • • , W Expγ k ′ . (4)
Actually, ψ can be any function of the scores of guessing entropies, such as multiplication, addition, etc. In this paper, we only use a very simple function

ψ γ, n, k ′ = 1 η η i=1 W Expi k ′ . ( 5
)
The limit of function ψ is equal to 2 ξ if the guessing key k ′ is correct. However, if the guessing key is incorrect, the limit of ψ is equal to 2 ξ +1 2 . That's to say, for each repetition i (1 ≤ i ≤ η), the following formula 6 is satisfied.

lim γ→∞ ψ (γ, n, s) > lim γ→∞ ψ (γ, n, δ) δ ∈ 0, 1, • • • , 2 ξ -1 \ {s} . (6)
Formula ( 6) indicates that when the number of power traces we use in each experiment is large enough, the average score of guessing entropies lim γ→∞ ψ (γ, n, s) of correct key s will be the maximum with a limitation of 2 ξ . The limits of scores of guessing entropies of other wrong guessing keys are 2 ξ +1 2 . That is why the correct key falls in the location of largest score. So as to meet the definition of the first order success rate in [START_REF] Standaert | A unified framework for the analysis of side-channel key recovery attacks[END_REF]. Thus, the feasibility of GE-CPA is well explained in theory.

Attack Flow

In the above subsection 3.2, we show how to recover the key from GE-CPA. Suppose that we randomly encrypt m plaintexts and acquire m power traces. The number of repetitions C is set to 0, the array W 0 • • • 2 ξ -1 saves the scores of guessing entropies for all possible keys from 0 to 2 ξ -1, and k indicates the number of power traces added in each repetition. The steps to recover the key using GE-CPA are as follows:

Step 1: The attacker randomly selects n(n << m) power traces and the corresponding n plaintexts. He then sets the number of repetitions C = C + 1.

Step 2: For each guessing key, he calculates the assumed power consumption using power model(i.e. Hamming distance model). Then, he calculates the correlation coefficients between the assumed power consumption and the power traces. All correlation coefficients are returned, which is different from traditional CPA.

Step 3: The attacker sorts the correlation coefficients, determines the score of guessing entropy for each possible key key i . Then, he adds them to the array of scores of guessing entropies W . Actually, Other functions like multiplication can also be used.

Step 4: The attacker sorts the array W , determines the score of guessing entropy for each key. If the score of guessing entropy of the correct key is still not the maximum in W , then, n = n + k. Otherwise, he goes to step 1.

The greater the score of guessing entropy of the correct key, the higher certainty the key is. The correct key can be recovered with a probability of 1.00 when the score of guessing entropy corresponding to the correct key is equal to 256.

Success Rate in Guessing Entropy Enhanced CPA

The relationship between different repetitions and guessing entropies has not been taken into consideration in traditional side channel attacks. They just judge whether an experiment is successful. Therefore, in the statistics, the success rate will be close to a fixed value (i.e. 0.50), which not grows with the increase number of repetitions. In our GE-CPA, we consider the relationship between repetitions and guessing entropies. When the number of power traces used in each repetition is sufficient to make the score of guessing entropy corresponding to the correct key larger than those of wrong keys, the success rate grows with the increase number of repetitions. Finally, the success rate of GE-CPA is close to 1. Thus, the success rate of GE-CPA is very different from that of traditional side channel attacks.

Actually, the number of power traces in each repetition is far from infinity. The score of guessing entropy of the correct key is just close to a fixed value larger than 2 ξ +1 2 rather than 2 ξ after many repetitions if the number of power traces we use in each repetition is relatively small. That is to say, the score of guessing entropy corresponding to the correct key will be larger than other ones corresponding to wrong guessing keys. In this case, the correct key can also be distinguished from the wrong ones.

Suppose that we randomly select τ power traces from a total number of N and repeat this operation γ times. The average score of guessing entropy of the correct key is µ µ >

Then, the success rate φ of our GE-CPA is

φ = lim γ→∞ T γ,C τ N suc T γ,C τ N suc + T γ,C τ N unsuc = 1 (8)
Actually, the variable γ doesn't need to be infinity, the greater the variable γ is, the closer to µ the average score of guessing entropy of the correct key will be.

The score of guessing entropy of the correct key is obviously larger than those of wrong keys after many repetitions. γ is less than 30 when only a small number of power traces with success rate ranging from 5% to 8% are used. Failure will not happen if more repetitions are done. This also demonstrates the high efficiency of our GE-CPA.

Experimental Results

Experiments on AT89S52 single chip

Our first experiment is performed on an AT89S52 single chip. The clock frequency of this chip is 12 M Hz. The minimum instructions takes 12 clock cycles for execution. We utilize a T ektronix DP O 7254 oscilloscope, and the sampling rate is set to 1GS/s. The output of S-box in the first round of AES encryption is chosen as the attack point. We test the instruction 'M OV CA, @A + DP T R', which treats the value of register A as the offset and treats the address DP T R of S-box as the base address, then looks up table S-box and writes the result back to register A (as shown in Fig. 1). We randomly encrypt 4000 plaintexts and acquire 4000 power traces. Each power trace contains 5000 time samples. We calculate the correlation coefficients between each time sample and Hamming weights of the outputs of S-box. We randomly choose 150 power traces and the corresponding success rate is 93%. We randomly choose power traces from a total number of 150 and repeat this operation for 200 times to calculate the success rate and guessing entropy (as shown in Fig. 2). The success rate ranges from 1% to 61% when 10 ∼ 110 are used. The corresponding guessing entropies range from 115.9 to 1.35 (as shown in Fig. 2(b)). When 40, 60, 80 and 100 power traces are used, the success rates reach 3%, 7.6%, 11% and 16.5%. The corresponding guessing entropies reach 29.5, 12.5, 5.1 and 2.2 respectively.

The experimental results of our GE-CPA are shown in Fig. 3. The key even can be recovered after only 10 repetitions when 40 power traces with a success rate of 5.5% are used. This also indicates that our GE-CPA can significantly improve the efficiency of CPA. The average score of guessing entropy of the correct key is close to 226.5, which is stably larger than these corresponding to wrong keys. When more power traces are used in each repetition, the guessing entropy corresponding to correct key decreases, leading to the increase of the corresponding score of guessing entropy. The guessing entropies are 29.5, 12.5, 5.1 and 2.2 when 40, 60, 80 and 100 power traces are used respectively. With more repetitions, the average score of guessing entropy corresponding to the correct key are close to 226.5, 243.5, 250.9 and 253.8 respectively. Other scores of guessing entropies corresponding to wrong keys are relatively smaller.

The experimental results will be better if a small number of power traces are randomly selected from a large power trace set in each repetition. However, this paper tries to solve the problem that how to recover the key with a probability of about 1.00 under the condition that the number of power traces is small, and success rates is low. So, we only consider to use a small number of power traces in our experiment. For example, we use 150 power traces in total in this experiment. If we randomly select 150 power traces from a total number of 4000 to perform CPA, the success rate is equal to 0.93, which is less than 1.00.

Experiments on SASEBO

Our second experiment is on DES algorithm implemented on the side channel attack standard evaluation board (SASEBO). We use the power trace set of DP A contest v1 provided on the website of DP A contest [START_REF]Dpa contest[END_REF]. 5000 power traces of power trace set secmatv1 are downloaded. We attack the first S-box with 6 bits input and 4 bits output in the last round of the DES algorithm (as shown in Fig. 4). We use the 14000 th ∼ 16000 th time samples in our experiments. We randomly select 200 power traces from a total number of 5000 and repeat the operation 200 times. The first order success rate is about 80%. Then, we randomly select power traces from a total number of 200 to perform CPA. The success rates range from 1% to 39% when 10 ∼ 140 power traces are used (as shown in Fig. 5(a)). The corresponding guessing entropies range from 33.6 to 6.13 (as shown in Fig. 5(b)). When 40, 60, 80 and 100 power traces are used, the success rates reach 3%, 7.6%, 11% and 16.5% (as shown in Fig. 5(a)). The corresponding guessing entropies are 25.56, 19.4, 16.1 and 10.8 respectively (as shown in Fig. 5(b)).

When more power traces are used, the guessing entropy corresponding to the correct key decreases, leading to the increase of the corresponding score (as shown in Fig. 6). The score of guessing entropy corresponding to the correct key becomes the largest one after 5 repetitions when average 60,100 and 120 power traces are used.

However, in order to obtain a stable success rate, the experiments with average 60 power traces have better results than that with 80 power traces. This also indicates, the guessing entropies of the initial several experiments are very important, which may affect the starting position of success. The score of guessing entropy of the correct key will be greater if more power traces are used after a few repetitions. However, this doesn't mean the difference of the scores of guessing entropies between the correct key and wrong keys is better. Because of the limited number of repetitions, less power traces used in each repetition may get greater difference.

When 80 power traces are randomly selected, the score of guessing entropy of the correct key becomes stable in different repetitions (as shown in Fig. 7). Sometimes, the experiment has a good beginning (as shown in Fig. 7(a)), the score of guessing entropy of the correct key becomes the maximum after 1 ∼ 6 repetitions. However, it gradually reduce after 7 repetitions. The change is stable after 26 repetitions. The score of guessing entropy of the correct key is sometimes small at the beginning of our experiments. However, it becomes the maximum after many repetitions (as shown in Fig. 7(b)). Regardless of the beginning, the correct key can finally be distinguished from the wrong ones.

It is worth noting that we use a total number of 200 power traces to compare the difference of guessing entropies between the correct key and wrong keys. Actually, when 60 power traces are used in each repetition, our GE-CPA can recover the key (As shown in Fig. 6). Some power traces may be repeatedly selected if the total number of power traces is small and the number of repetitions is large. The effectiveness may be a little worse than randomly selecting power traces from a large power trace set. In addition, the quality of this power trace set may affect the experimental results. However, the experimental results are almost the same if we randomly select 60 power traces from a total number of 120 or 200. Komano et al. proposed built-in determined sub-key correlation power analysis, 65 power traces are used to recover the key. Which is more efficiency than our GE-CPA [START_REF] Komano | Bs-cpa: Built-in determined subkey correlation power analysis[END_REF]. We also simply compare the efficiency of our guessing entropy ehanced CPA (GE-CPA) with other enhanced side CPA attacks shown on the web site of DPA contest v1 [START_REF]Dpa contest[END_REF]. Hideo used 107 power traces by using his advanced BS-CPA. Yongdae used 119 power traces by using his "CPA with chosen order". Daisuke used 120 power traces by using his "Dual round attack by BS-CPA using improved power model". The efficiency of those attacks are similar to our GE-CPA. Benedikt used 329 power traces by using the difference of means on the last round of DES. Victor used 322 power traces by using his "CPA on the 16th round of the DES selecting the good temporal window". Other attacks using more power traces are not deteiledly introduced here. Our GE-CPA is more efficiency than these attacks.

Conclusion

As a common evaluation to evaluate the effectiveness of side channel attacks, guessing entropy is used to measure the uncertainty of the key. In this paper, we analyze the statistical characteristics of guessing entropy and propose GE-CPA. Experiments on AES algorithm implemented on an AT89S52 single chip and power trace set secmatv1 of DES algorithm implemented on the side channel attack standard evaluation board (SASEBO) from the website DP A contest v1 show that our scheme can efficiently recover key. Our scheme can significantly improve the effectiveness of CPA.

Actually, CPA is just a common type of side channel analysis. Guessing entropy can enhance many other types of side channel analysis like DPA and template attack, etc. This also indicates the practicability of our scheme.

2 ξ +1 2 .

 2 The limits of scores of guessing entropies corresponding to the wrong guessing keys are 2 ξ +1 2 when γ → ∞. Let T

Fig. 1 .

 1 Fig. 1. The output of S-box in the first round of AES algorithm.

Fig. 2 .

 2 Fig. 2. Success rate (a) and guessing entropy (b) of CPA on AT89S52.

Fig. 3 .

 3 Fig. 3. Score of guessing entropy for each key in different repetitions when 60, 80, 100 and 120 power traces are used in each repetition.

Fig. 4 .

 4 Fig. 4. DES algorithm. (a) shows a round of DES, and (b) shows the S-box of DES.

Fig. 5 .

 5 Fig. 5. Success rate (a) and Guessing entropy (b) of CPA on SASEBO.

Fig. 6 .

 6 Fig.6. Scores of guessing entropies for each key in different repetitions when 60, 80, 100 and 120 power traces are used in each repetition.

Fig. 7 .

 7 Fig. 7. Scores of guessing entropies for each key in different repetitions when 80 power traces are randomly selected in each repetition.

Acknowledgment. This research is supported by the Nation Natural Science Foundation of China (No.61372062). The authors would like to thank Prof Kerry-Lynn Thomson from Nelson Mandela Metropolitan University and the anonymous referees of IFIP SEC 2016 for the suggestions to improve this paper.


Yu-Yang Hong

Yu-Ping Wang

Jie Yin
email: yinjie@mail.tsinghua.edu.cn

NativeProtector: Protecting Android Applications by Isolating and Intercepting Third-Party Native Libraries

Keywords: Android security, Native libraries, Process isolation, Call interception

An increasing number of Android developers are incorporating third-party native libraries in their applications for code reuse, CPU-intensive tasks and other purposes. However current Android security mechanism can not regulate the native code in applications well. Many approaches have been proposed to enforce security of Android applications, but few of them involve security of the native libraries in Android applications. In this paper, we propose NativeProtector, a system that regulates the third-party native libraries in Android applications. The standalone Android application is separated into two components: the server app and the client app where server app contains the native libraries for providing services from the native libraries while the client app contains the rest parts of the original app. The client app binds to the server app at the launching time, and all native function calls are replaced with interprocess calls to the server app. NativeProtector also generates the stub libraries intercept system calls in server app and enforce security of the native libraries in server app. We have implemented a prototype of NativeProtector. Our evaluation shows that NativeProtector can successfully detect and block the attempts of performing dangerous operations by the third-party native libraries in Android applications. The performance overhead introduced by NativeProtector is acceptable.

Introduction

Android dominated the smartphone market with a share of 82.8% in the second quarter of 2015 [6]. This trend is benefited from the great increase of third-party Android applications, because they can be easily downloaded and installed. However, numbers of malicious applications also occur to leak user private information and perform dangerous operations. Therefore, preventing privacy leaks and enabling fine-grained control in Android applications are necessary.

Many approaches have been proposed to protect the security of Android applications, but they often focus on Java code, because Android applications are often written in Java language. In fact, Android also provides JNI (Java Native Interface) for calling native libraries in applications, and many developers tend to use third-party native libraries to reuse existing code or perform CPU-intensive tasks (such as image filtering and video encoding). However, the security of these third-party native libraries is often omitted [START_REF] Shekhar | Separating Smartphone Advertising from Applications[END_REF]. In the Android system, these native libraries can access the entire process address space and share all the permissions which the user grants to the whole applications, and they are also uncovered by Java security mechanism. Thus, malicious native libraries are very dangerous for Android security.

To the best of our knowledge, only a few existing approaches focus on the security of native libraries in Android. NativeGuard [START_REF] Sun | NativeGuard: Protecting android applications from third-party native libraries[END_REF] is a typical framework which uses process isolation to sandbox native libraries of applications. It has two main advantages. Firstly, NativeGuard separates native libraries to another standalone application, so native libraries can not fully access the entire application address space, and the interaction between native libraries and Java code is fulfilled via Android Inter-Process Communication (IPC) mechanism. Secondly, the generated native-library application is no longer granted permissions, so dangerous operations can not be performed.

However, NativeGuard still has some limitations. Firstly, because no permissions are granted to the native-library application, the benign native libraries crash when they need necessary permissions. Secondly, NativeGuard lacks finegrained control of the native libraries to manager their behaviors.

To ensure the security of native libraries in Android, we propose a practical approach named NativeProtector. On one hand, inspired by NativeGuard, we use the process isolation to prevent the native libraries from accessing the entire application address space and limit the permissions of native libraries. On the other hand, we perform fine-grained control of native libraries by instrumenting the third-party native libraries and intercepting native-library calls to access private data and perform dangerous system calls. In detail, the third-party native libraries are separated as a standalone application, so the access of native libraries to Java code is restricted by fine-grained access control. By combining isolation and interception, we can ensure the security of native libraries without crashing benign native libraries. Meanwhile, NativeProtector is very easy to deploy. It can run as a common application without the root privilege because NativeProtector statically instruments the target application. Hence, no modification is required for the Android framework.

The main contributions of this paper are following:

-By combining isolation and interception, we have proposed a practical approach named NativeProtector, to protect Android applications from malicious third-party native libraries. -We have built a prototype of NativeProtector to separate an application to the native-library application and Java code, and instrument the native libraries to perform fine-grained access control. -We have evaluated NativeProtector on real-world and manually crafted applications. The experimental results show that NativeProtector is effective for security and compatible for many applications, and the performance overhead is also acceptable.

The rest of this paper is organized as follows: Section 2 provides some background information on Android security and JNI, we also talk about dynamic loading and linking in Android. In Section 3 we describe the threat model of Na-tiveProtector and defenses provided by NativeProtector. Section 4 goes through details about NativeProtector's implementation. In Section 5 we evaluate effectiveness, compatibility and overhead of NativeProtector . Related work is shown in section 6. Section 7 gives the conclusion of this paper.

Background

In this section, we first briefly give an overview of Android security, and then introduce some important concepts in Android to help to better understand NativeProtector.

Android Security Overview

Android OS is an open-source software stack for mobile devices consisting of a Linux kernel, Android application framework and system applications. In Android, each application runs in a separate sandboxed environment that isolates data and code from other applications which is guaranteed by Linux kernel's process isolation. One application can not access to another application's address space and private data. Inspired by this mechanism, the third-party native libraries can be separated as another application to ensure that they can not access to the entire application's address space or private data.

Java Native Interface

Similar to the desktop Java program, Android provides the Java Native Interface (JNI) to define a framework for Java code and native code to call each other. Commonly, developers use native libraries in their applications for code reuse, CPU-intensive task or application hardening. Android provides Native Develop Kit (NDK) [START_REF]Android NDK[END_REF] to allow developers to implement parts of applications in native languages like C and C++. NDK compiles native source code files into shared libraries which can be loaded dynamically under the request of the application's java code. When a native function is invoked, it will be passed a special data structure of type JNIEnv, which allows the native code to interact with the java code [START_REF] Siefers | Robusta:Taming the native beast of the JVM[END_REF]. For instance, the native code can use JNIEnv->FindClass("Sample") to locate the Java class "Sample" and call its functions. Inspired by this mechanism, these key JNI related functions can be interposed to intercept the access to private data and dangerous function calls based on predefined policies.

Dynamic Loading and Linking

Android adopts its own dynamic loader and linker for native libraries. Unlike the desktop Linux operating system, Android's loader do not take the lazy Binding policy, which means the loader will recursively resolve all the external functions when the application is loading into the memory. But the PLT/GOT [START_REF] Plt | the key to code sharing and dynamic libraries[END_REF] structure is still used for dynamic linking. In particular, for an ELF file which has some external functions, its call sites to an external function is actually jump instruction to a stub function in the Procedure Linkage Table (PLT). This stub function performs a memory load on a entry in the Global Offset Table (GOT) to retrieve the real target address of this function call. When a native library is loaded, the loader resolves all external functions and fills them in the GOT entries.

System Design

In this section, we first give the threat model of NativeProtector, and then we explain how can we prevent the damage from the third-party native libraries and the defenses provided by NativeProtector.

Threat Model

There are three main advantages for using native libraries or native code in Android applications: a) porting applications between platforms; b) reusing existing libraries or providing libraries for reuse; c) increasing performance in certain cases, particularly for CPU-intensive applications like pixel rendering, image filtering and games. For these advantages, many Android developers tend to incorporate native libraries in their applications. But these native libraries are always developed by the third party, so they can be malicious. Note that a carefully designed Android application may have security check on passing sensitive data to native library. However, the developers usually trust the native libraries and fail to perform such checks.

Similar to existing solutions [START_REF] Sun | NativeGuard: Protecting android applications from third-party native libraries[END_REF], we assume an adversary model that the third-party native libraries in the applications are not trustworthy, but some native libraries are essential to the functionalities of the applications. We need to ensure the applications with third-party native libraries work as normally as possible when restricting the third-party native libraries' unprivileged operations such as accessing to the private data In this paper, the developer is trustworthy so that the Java code of the applications is trustworthy. As there are many approaches of enforcing the security of Java code in Android applications [START_REF] Enck | TaintDroid: an information-flow tracking system for realtime privacy monitoring on smartphones[END_REF][START_REF] Nauman | Apex: extending android permission model and enforcement with user-defined runtime constraints[END_REF][START_REF] Zhang | Vetting undesirable behaviors in android apps with permission use analysis[END_REF][START_REF] Zhao | TrustDroid: Preventing the use of SmartPhones for information leaking in corporate networks through the used of static analysis taint tracking[END_REF], it's reasonable that the Java code can be regulated well even though it involving some malicious code.

Defenses Provided

As shown in Fig. 1, NativeProtector separates the original app to two standalone apps. One of them consists of Java bytecode and the resources of the original The other consists of the third-party native libraries implemented as an Android service [START_REF]Android Service[END_REF]. The Java one acts as the client, and the native one acts as the server. These two apps communicate with each other via Android IPC. In this way, the security of native libraries is controlled by Android's existing process isolation security mechanisms, which means the third-party native libraries can not access to the entire application address space. To support arbitrary applications, where source code is not always available, we craft the application separation process in bytecode instead of source code.

To control the third-party native libraries' access to private data and dangerous operations, NativeProtector inserts hooking libraries into the server app which contains the third-party libraries. These hooking libraries intercept the interactions between the third-party native libraries and the system to enforce various security policies. To control the third-party native libraries' access to private data and dangerous operations by JNI calls, we also intercept the JNI calls called by the native code to enforce security policies.

Use case: For each app to be installed, NativeProtector separates it into two standalone apps. They are both installed on the user's cellphone and the server app is installed as an Android service. When the client app is launched, it starts the server app and binds to the service of the server app. When the client app needs to call the functions in the native libraries, the client app will interact with the server app through IPC.

Implementation

We have implemented a prototype of NativeProtector in Java and C programming languages.

Apk Repackaging

Each Android application is distributed as a package file format which is named APK (Android Application Package). An APK file contains a manifest file named AndroidManifest.xml, the application's code in form of dex bytecode, XML resources like activity layouts, other resources such as images, and the native libraries which are standalone Linux shared object files (.so). To support arbitrary applications, all we worked is on the APK file.

An APK file is actually a ZIP compression package, which can be easily decompressed with decompression tools. Because the Android SDK puts all the application's compiled bytecode in a single file called classes.dex, and the XML files are also compressed, we can not edit the bytecode or XML files directly to add our protection code. We need to take the original APK files, disassemble it to a collection of individual classes and XML files, add NativeProtector's code in them, and then reassemble all the things back to new APK files.

To perform this task we choose apktool [START_REF]Apktool[END_REF], a tool for Android applications reverse engineering which can decode resources to nearly original form and rebuild them after making some modifications. In NativeProtector apktool is taken in the repackaging process. We first take apktool to disassemble the APK file to manifest file and resources, the native libraries, and the application's bytecode which is in the smali format. Then we use these files to generate the client app source files and server app source files. Meanwhile, we insert our stub libraries into the server app source files to intercept the private data access and dangerous operation for enforcing security policies. Finally, we use apktool to reassemble the client app and server app to APK files, and install them on the user's phone.

Native Libraries Isolation

NativeProtector isolates the native libraries to another application as an Android service. Actually, it generates several AIDL(Android Interface Definition Language [START_REF]Android Interface Definition Language (AIDL[END_REF]) interfaces and assistant smali code, and then modifies the launcher Activity and the JNI calls in the applications to achieve isolation. Fig. 2. shows the detailed process of the isolation of NativeProtector. Next, we illustrate some key points in the isolation process.

Generate Server Application After disassembling the original app's APK file by apktool, all smali files of the application are analyzed to record native function information. Then for each native function, NativeProtector creates a corresponding AIDL interface and an Android wrapper function in the server for communicating with the client. When the client calls the native function, there is an IPC call to the corresponding wrapper function with the same parameter, and the wrapper function invokes the native function through the AIDL interface. Finally, the native functions with AIDL interfaces and wrapper functions are reassembled into the server app using apktool . Generate Client Application After the server app is generated, we use the generated AIDL interfaces to craft the client app. We analyze all the smali files of the original app automatically to change the native function calls to corresponding AIDL calls. Then we use apktool to reassemble the Java bytecode of the orignal app which has been modified as above mentioned, the AIDL interfaces corresponding to the server app, and the other resource files of the original app to the client app as an APK file.

Modify the Launcher Activity To make the client app works normally we need to ensure that at the very beginning in the client app, the server app's service is bound to the client app and the client app can call the native functions normally. Launcher activity is the starting execution point of an Android application. A callback method of the activity named onCreate is automatically invoked by the system when the application is launched. So NativeProtector locates this callback method in the launcher activity, and inserts code to bind to the server app to ensure that the client app is launched together with the server app.

Native Libraries Interception

In the process of the native libraries isolation, NativeProtector instruments the native libraries for intercepting the private data access and dangerous operations. This interception is implemented as some hooking libraries which are packed in the server app, and we let the server app load the hooking libraries and perform the hooking operation for native libraries interception. NativeProtector also provides a policy manager employing various security policies to enforce security. Next we detail the native libraries interception process of NativeProtector.

Efficient Interception

The PLT/GOT structure is used for dynamic linking in Android. The call sites to external functions in Android native libraries are jump instructions to stub functions in PLT, and the stub functions then perform memory load on the entries in the GOT to retrieve the real address of these functions. We can exploit this mechanism to perform the required interposition. We scan every loaded native library and overwrite each GOT entry with pointer to our stub function. In this way, we can intercept the private data access and dangerous operations.

Policies As we are able to insert hooking libraries which can intercept the private data access and dangerous operations to monitor the third-party native libraries, we can introduce the various security policies in NativeProtector to enforce security. At present, we implement some typical security policies in Na-tiveProtector. In theory, NativeProtector can perform as a flexible framework to adopt many more useful security policies.

In NativeProtector, we monitor mainly three kinds of operations, including accessing private data, connecting to remote server and sending SMS (Simple Message Service) messages. We consider those operations, because they cover the two ends of path that may leak private data. The policies taken by Native-Protector to regulate the third-party native libraries in these three operations are described below:

-Private Data Policy This policy protects the user's private data such as IMEI, IMSI, phone number, location, stored SMS messages and contact list. These private data can be accessed from the system services provided by Android Framework APIs. These Android Framework APIs call a single call to the ioctl() function. NativeProtector intercepts the calls to ioctl(), and parses the data passed in the calls to determine which service is accessed.

Then we can know which private data is accessed by the native libraries and decide whether allow the private data access of the native libraries. -Network Policy Android uses connect() function for socket connection. All Internet connections in Android call this function eventually. NativeProtector can intercept this function to control the Internet access of the native libraries. We restrict the native libraries to connect to only a specific set of IP addresses and prevent the native libraries from connecting to malicious IP addresses. With these whitelist and blacklist policies, we can ensure the native libraries are regulated int network, and the normal use of the native libraries is not affected. The whitelist and blacklist can be managed by user, or be retrieved from a trusted server. -SMS Policy In Android framework, applications can not send SMS messages on their own. The applications must invoke RPCs to the SMS service through Binder. All the interactions with Binder call ioctl() function eventually. As we mentioned above, NativeProtector intercepts the calls to ioctl().

Thus we can get the destination number and the content of the SMS message to inform the users, and decide whether to allow this operation or not.

Meanwhile we can take a blacklist policy to prevent the native libraries from sending SMS messages to premium numbers. As NativeProtector only block sending SMS message to premium numbers, calling to those numbers is not blocked unless the phone call policy is adopted.

Evaluation

In this section, we evaluate the effectiveness, compatibility and performance of our prototype of NativeProtector. The experiments are performed on a Google Nexus 4 phone running Android 4.4.2.

Effectiveness

To show the effectiveness of NativeProtector, we have manually designed a demo app. This demo app contains a malicious but inseparable native library, which is used by the demo app for network connection. But this malicious native library gets the location information of the phone and send to a known malicious server. The demo app uses native system calls to perform this process instead of Java APIs. This demo app demonstrates that the third-party native libraries may make use of the permissions assigned to the applications and cause security violations. As for NativeGuard [START_REF] Sun | NativeGuard: Protecting android applications from third-party native libraries[END_REF], it simply separates the native libraries to another server app, and gives no permissions to the server app. This approach indeed restricts the third-party native libraries' access to all the application's process address which can change the execution of java code, but it also leads to the result that the third-party native libraries can not work any more. In this app, the native library can not connect to the network, even for the benign servers.

NativeProtector can improve the situation by combining separation and interception. For this demo app, NativeProtector separates the native library to the server app and generates hooking libraries to the server app. The server app has the permissions same as the original app, so the third-party native library can work well. But when the third-party native library accesses to the phone location (private data in the test), and when the third-party native library connects to the malicious IPs in the blacklist, the hooking libraries will intercept these dangerous function calls and block them. In this way, NativeProtector can help the app to use the third-party native libraries functionality and prevent applications from the malicious third-party native libraries.

Compatibility

To test the compatibility of our NativeProtector prototype, we have collected 20 popular apps from APKPure[4] store , a applications store which can ensure the applications download from it are the same as Google Play store. These applications are downloaded from the leaderboard of the hot free applications chart of the store in November 2015. NativeProtector successfully separates 15 of 20 applications. The five failed applications are due to the apktool. Two of them fail in the disassembling stage before NativeProtector's separation, and three of them fail in the assembling stage after NativeProtector's separation. Then we manually test the applications after separation by playing with the instrumented applications and using the functionalities of the instrumented applications. In the test, all the 15 applications processed by NativeProtector can work well. During the testing, we found that there are response delays in some applications. But on the whole, NativeProtector introduces acceptable overhead and does not affect the app's functionalities. Details about the evaluated applications are presented in Table 1.

Performance

For NativeProtector, a security framework which takes process isolation and system call interception, the runtime overhead depends greatly on the intensity of context switches and API invocations we intercepted (like connect()). In section 5.2, not mach delay is felt when testing in the real-world applications hardened by NativeProtector. To quantify the performance overhead, we talk about the NativeProtector's performance overhead in the extreme cases. We crafted two artificial application to represent the two extreme cases. One is testing the influence of the intensity of context switches on the NativeProtector's performance overhead, and the other is testing the NativeProtector's overhead affected by the API invocations we intercepted.

Firstly, we crafted an application which compresses a medium size file (about 5.6MB) stored on the phone with the popular Zlib library. The Java code of the application divides this file to small segments and passes one to Zlib which perform the compression. Then the Java code passes the next one to Zlib. When Zlib library is sandboxed by NativeProtector, the segments size has a great impact on the performance overhead, as small segment size means frequent context switches between Java and native code. Table 2 presents the overhead introduced by enabling NativeProtector in Zlib benchmark application that compresses the file with different segment size. All the performance time is the average over 5 tests. The results table illustrates that higher overhead comes up with smaller segments size. And the overhead can be 81.79% when the segments size is 1KB. But in the real world, few applications will perform context switches as frequently as this test. They utilize native libraries to perform CPU-intensive operations like image compression and conversion, without frequently making context switches. Thus NativeProtector brings acceptable overhead to the real-world applications. Secondly, we crafted an application which use native libraries to connect to a remote server and send a message. This application tries to connect the remote sever and send message ten times. After these operations are done, it logs the time consumed. We tested both the original application and the application hardened by NativeProtector for five times against the randomness. Table 3 shows the result of this test. We can see that NativeProtector introduces an overhead of 50% in this test, which we believe is acceptable as real-world applications will not invoke the APIs NativeProtector intercepted frequently.

In summary, the evaluation demonstrates that NativeProtector can enforce security on the native libraries in Android applications with acceptable overhead in most real-world applications where context switches between Java and native code are not frequent and the API invocations we intercepted are not frequently used. 6 Related Work

Android App Security

With the increasing popularity of Android and the increasing malware threats, many approaches to secure Android applications have been proposed. Some of them extend the Android framework to perform fine-grained control of Android applications at runtime [START_REF] Bugiel | Flexible and Fine-grained Mandatory Access Control on Android for Diverse Security and Privacy Policies[END_REF][START_REF] Conti | CRePE: Context-related policy enforcement for Android[END_REF][START_REF] Hornyack | These aren't the droids you're looking for: retrofitting android to protect data from imperious applications[END_REF][START_REF] Russello | Firedroid: hardening security in almost-stock android[END_REF][START_REF] Wang | DeepDroid: Dynamically Enforcing Enterprise Policy on Android Devices[END_REF][START_REF] Zhou | Taming information-stealing smartphone applications (on android)[END_REF]. AppFence [START_REF] Hornyack | These aren't the droids you're looking for: retrofitting android to protect data from imperious applications[END_REF] retrofits the Android operating system to return mock data of the sensitive resources to the imperious applications. CRePE [START_REF] Conti | CRePE: Context-related policy enforcement for Android[END_REF] allows both the user and authorized third parties to enforce fine-grained context-related polices. Deepdroid [START_REF] Wang | DeepDroid: Dynamically Enforcing Enterprise Policy on Android Devices[END_REF] intercepts Binder transactions and traces system calls to provide portability and fine-grained control.

The other approaches perform security enforcement at the application layer [START_REF] Backes | AppGuard-enforcing user requirements on android apps[END_REF][START_REF] Backes | Boxify: Full-fledged app sandboxing for stock Android[END_REF][START_REF] Davis | I-arm-droid: A rewriting framework for in-app reference monitors for android applications[END_REF][START_REF] Rasthofer | Droidforce: enforcing complex, data-centric, system-wide policies in android[END_REF][START_REF] Xu | Aurasium: Practical Policy Enforcement for Android Applications[END_REF][START_REF] Zhou | Hybrid User-level Sandboxing of Third-party Android Apps[END_REF]. Aurasium [START_REF] Xu | Aurasium: Practical Policy Enforcement for Android Applications[END_REF] uses native library interposing to enforce arbitrary policies at runtime. Appcage [START_REF] Zhou | Hybrid User-level Sandboxing of Third-party Android Apps[END_REF] hooks into the application's Dalvik virtual machine instance to sandbox the application's dex code and uses SFI (Software Fault Isolation) to sandbox the application's native code. Boxify [START_REF] Backes | Boxify: Full-fledged app sandboxing for stock Android[END_REF] combines the strong security guarantees of OS security extensions with the deployability of application layer solutions by building on isolated processes to restrict privileges of untrusted applications and introducing a novel application virtualization environment. NativeProtector takes the application layer approach. It can run in the user's phone and does not need to modify the Android framework, so it can be easly deployed.

Untruseted code Isolation

Android's UID-based sandboxing mechanism strictly isolates different applications in different processes. With this strong security boundary naturally supported by Android, many approaches have been proposed to isolate untrusted code in another process [START_REF] Jeon | Mr. Hide: finegrained permissions in android applications[END_REF][START_REF] Shekhar | Separating Smartphone Advertising from Applications[END_REF][START_REF] Sun | NativeGuard: Protecting android applications from third-party native libraries[END_REF][START_REF] Zhang | AFrame: isolating advertisements from mobile applications in Android[END_REF]. Dr. Android and Mr. Hide [START_REF] Jeon | Mr. Hide: finegrained permissions in android applications[END_REF] revokes all Android platform permissions from the untrusted applications and applies code rewriting techniques to replace well-known security-sensitive Android API calls in the monitored application with calls to the separate reference monitor application that acts as a proxy to the application framework. AdSplit [START_REF] Shekhar | Separating Smartphone Advertising from Applications[END_REF] and AFrame [START_REF] Zhang | AFrame: isolating advertisements from mobile applications in Android[END_REF] isolate the third-party advertising libraries which is the JAR format into separate processes. NativeGuard [START_REF] Sun | NativeGuard: Protecting android applications from third-party native libraries[END_REF] isolates native libraries into a non-privileged application. But the benign native libraries which need permission to perform legal task can not work any more, because it lacks the fine-grained access control of the native libraries. NativeProtector adopts the idea of isolation, and instruments the native libraries to take fine-grained access control of native libraries.

Conclusion

We have presented the design, implementation and the evaluation of NativeProtector, a system to regulate the third-party native libraries in Android applications. NativeProtector separates the native libraries and generated hooking libraries to another server app, and the rest part of the original app is generated as the client app. The client app binds to the server app at the launching time, and all native function calls are replaced with the IPCs to the server app. The hooking libraries intercept system calls in server app to enforce security of native libraries in the server app. We have implemented a prototype of NativeProtector. Our evaluation shows that NativeProtector can successfully regulate the third-party native libraries in Android applications and introduces acceptable overhead.

Fig. 1 .

 1 Fig. 1. System architecture of NativeProtector

Fig. 2 .

 2 Fig. 2. Isolation Process of NativeProtector

Table 1 .

 1 Apps used in Compatibility test ( * : failed by apktool )

	App	Size	Package name
	DuoLingGo	9 M com.duolingo
	ES File Browser *	5.9 M com.estrongs.android.pop
	Shadowsocks	3.7 M com.github.shadowsocks
	IMO	6.7 M com.imo.android.imoim
	Arrow Desktop	4.5 M com.microsoft.launcher
	Microsoft Outlook	18.1 M com.microsoft.office.outlook
	Snapseed	20.7 M com.niksoftware.snapseed
	Brightest LED Flashlight	5.1 M com.surpax.ledflashlight.panel
	Tiger VPN	5.8 M com.tigervpns.android
	Tumblr	21.1 M com.tumblr
	Twitter	21.7 M com.twitter.android
	HideMe VPN	5.8 M io.hideme.android
	OpenVPN Connect	2.3 M net.openvpn.openvpn
	New York Times *	1.2 M org.greatfire.nyt
	WiFi key *	6.3 M com.halo.wifikey.wifilocating
	Touch VPN	4.7 M com.northghost.touchvpn
	Firefox	40.1 M org.mozilla.firefox
	AliExpress Shopping App * 10 M com.alibaba.aliexpresshd
	Clean Master	16.6 M com.cleanmaster.mguard
	WiFi Toolbox *	7.7 M mobi.wifi.toolbox

Table 2 .

 2 Performance on Zlib benchmark application

	Segments Size Without NativeProtector With NativeProtector Overhead
	1KB	21905ms	39822ms	81.79%
	2KB	15093ms	23948ms	58.67%
	4KB	10585ms	15507ms	46.50%
	8KB	8993ms	11399ms	26.75%
	16KB	8494ms	9585ms	12.84%

Table 3 .

 3 Performance on API invocations

		First test Second test Third test Forth test Fifth test Average
	Without NP 608ms	543ms	512ms	438ms	619ms 544ms
	With NP	960ms	743ms	788ms	672ms	916ms 816ms
	Overhead			50%