Arnaud Lefray
email: arnaud.lefray@ens-lyon.fr

Eddy Caron
email: eddy.caron@ens-lyon.fr

Jonathan Rouzaud-Cornabas
email: jonathan.rouzaud-cornabas@inria.fr

Christian Toinard
email: christian.toinard@insa-cvl.fr

Microarchitecture-aware Virtual Machine Placement Under Information Leakage Constraints

Keywords: Security, Cloud, Virtual Machine Placement, Isolation, Microarchitecture, Covert channels

One of the major concerns when moving to Clouds is data confidentiality. Nevertheless, more and more applications are outsourced to a public or private Cloud. In general, the usage of virtualization is acknowledged as an isolation mechanism between applications running on shared resources. But, as previously shown, virtualization does not ensure data security. Indeed, the isolation can be broken due to covert channels existing in both the software and the hardware (e.g., improperly virtualized caches). Furthermore, even if a perfect control mechanism could be design, it would not protect against covert channels as they bypass control mechanism using legal means.

In this paper, we first describe how these attacks are working. Next, after presenting the existing mitigation mechanisms, we show that a good solution is to take into account security while allocating resources (i.e., when placing the VMs). Furthermore, depending on which resources are shared, we demonstrate that the achievable bitrate of these attacks can change dramatically. We propose a new metric to quantify them and use it as an acceptable risk for isolation properties. Then, we show how to use them when allocating resources and the importance of a finegrained resource allocation mechanism. Finally, we demonstrate that a security-oblivious placement algorithm breaks a fair amount of properties but taking into account the isolation impacts the acceptance rate (i.e., the percentage of successfully placed VMs).

I. INTRODUCTION

Security is one of the biggest concern for the massive adoption of Clouds [START_REF] Jaeger | Outlook: Cloudy with a Chance of Security Challenges and Improvements[END_REF]. Indeed, multitenancy and shared resources facilitate attacks and thefts by altering the level of isolation between tenants, processes or Virtual Machines (VMs). While virtualization could be seen as an isolation mechanism between tenants, it is not the case [START_REF] Ristenpart | you, get off of my cloud: exploring information leakage in third-party compute clouds[END_REF]. Accordingly, it is required to have another control mechanism to enforce the isolation. Furthermore, the security of a system is as strong as the weakest link. And, even with a perfect information flow (or access) control mechanism at the system level (e.g., Hypervisor/Operating system), information can be silently leaked out (or accessed) by exploiting (unwillingly) unsecure design or implementation; this is called covert channels. The literature exhibits multiple covert channels attacks that have been successfully conducted in Cloud environments [START_REF] Ristenpart | you, get off of my cloud: exploring information leakage in third-party compute clouds[END_REF], [START_REF] Wu | Whispers in the hyper-space: high-speed covert channel attacks in the cloud[END_REF], [START_REF] Xu | An exploration of l2 cache covert channels in virtualized environments[END_REF] (e.g., EC2) thanks to the shared hardware components between an attacker and a victim. Previous works opt for different approaches to tackle this issue: detection of attacks, fine-grained tracking of resources usage and placement algorithms. Placement algorithms under collocation/anti-collocation constraints specify if 2 VMs can share the same Physical Machine (PM) or not. Accordingly, they do not take into account any scenarios where sharing resources is reasonable when measuring information leakage.

In this paper, we propose a new resource allocation mechanism under information leakage constraints. Our mechanism takes into account microarchitectural components as they are one of the main reasons of covert channels. Moreover, it allows to have a more fine-grained allocation and thus reduces the quantity of resources wasted due to security constraints. But first, we need a way to present the quantity of information that can be leaked between 2 applications. Our allocation algorithm can be based on any covert-channel metric but due to the lack of proper metric, we propose a new information leakage metric that can be easily used by a tenant and is both application and hardware independent. This metric quantifies information leakage through microarchitectural covert channels based on the achievable bitrate between 2 applications. Using this metric, a tenant can express its isolation properties and specify the acceptable leakage that fits his security needs. For example, banks, governments and medical establishments usually require more secure setups than research institutes running experiments. Using the application model (a set of VMs) and our metric, we propose our new resource allocation mechanism. Furthermore, we present how we have tackled the specificity of NUMA (Non-Uniform Memory Access) allocation policies to encompass both traditional and modern architectures, and proposed a model for our algorithm.

The paper is organized as follows. Section II motivates our work by presenting related works on covert channel metrics and security-aware placement algorithms. We explain our new information leakage metric in Section III. Section IV details our placement algorithm including our NUMA allocation model. In section V, after presenting our evaluation environment and scenarios, we evaluate our security-aware algorithm against a security-oblivious one. Section VI concludes this paper and presents our future work.

II. BACKGROUND

In this section, we present the background and motivation of our work. First, we do a quick introduction of microarchitecture of multi-core processors and of the security and isolation issues in Clouds. Then we explain how to break isolation and the mitigation techniques against these attacks. Finally, we present existing metrics that quantify the quality of isolation.

A. Microarchitectural components

Since the last few years, the complexity of physical machines' hardware topology has increased dramatically [START_REF] Broquedis | hwloc: A Generic Framework for Managing Hardware Affinities in HPC Applications[END_REF]. The number of cores, shared caches, and memory nodes have completely changed the microarchitecture of computers. With the increasing number of cores, scalability becomes a major issue. Modern processors use non-uniform interconnects to address it. This technology is named Non-Uniform Memory Access (NUMA) architectures. For example, Figure 1 shows the inner architectural components of 3 modern platforms. As NUMA architectures impacts the memory hierarchy model, a traditional x86 architecture can be viewed as a single NUMA with local accesses. Therefore, we encompass most legacy and modern systems by considering the NUMA model.

B. Security and Isolation in Clouds

Security is a major issue in Clouds [START_REF] Jaeger | Outlook: Cloudy with a Chance of Security Challenges and Improvements[END_REF], in particular public Clouds. Ristenpart et al. [START_REF] Ristenpart | you, get off of my cloud: exploring information leakage in third-party compute clouds[END_REF] discuss multiple approaches to exploit this co-residency in Clouds such as Cross-VM performance degradation, Denial of Service (DoS) attacks or stealing cryptographic keys, thus demonstrating the reality of security threats. They have shown the feasibility of collocating their VMs on the same physical machine as business targets in EC2. From this work, it is clear that virtualization is far from being sufficient to have a secure Cloud.

The major problem of virtualization is a weak isolation. In security, isolation is defined as the composition of the confidentiality and integrity properties where:

• Confidentiality is the absence of unauthorized disclosure of information.

• Integrity is the absence of unauthorized system alteration.

As a result, isolation is the absence of unauthorized disclosure and alteration of information.

In this paper, we focus on the isolation problem of VMs sharing the same hardware and hypervisor. Furthermore, we will not consider performance interference. Indeed, it does not allow information modification or leak even if it is due to improper isolation [START_REF] Varadarajan | Resource-Freeing Attacks: Improve your Cloud Performance (At your Neighbor's Expense)[END_REF].

C. Micro-Architectural Timing Covert channels

Cloud providers can provide a large range of security mechanisms to prevent unauthorized information flows. But, despite all the effort, there is still a potential risk of data leakage in the Cloud, that is covert channels.

A covert channel is an attack which bypasses the control mechanism using legal means to leak information to unauthorized neighbors. A covert channel breaks the confidentiality property and thus, the isolation property. Therefore, even a perfect control mechanism is useless against covert channels.

Covert channels should not be confused with side channels. A covert channel exists when 2 cooperative entities, let say Trojan and Spy, use a common protocol to communicate or exfiltrate information. For a side channel, only one process, the Spy, collects unwillingly disclosed information. Because the leaking process can be considered as an unintentional Trojan, we argue that side channels are special cases of covert channels. Recent exploits (e.g., Heartblead, Ghost) have shown the easiness of remotly uploading and executing a malicious code.

Covert channels are categorized in covert storage channels and covert timing channels.

A covert storage channel exploits a standard data channel to encodes secret information. This problem has been described in 1983 by G. Simmons [START_REF] Simmons | The prisoners' problem and the subliminal channel[END_REF] as the prisoner's problem. This attack is popular for network protocols, for example by using the reserved or unused bits of a frame to convey information. As covert-storage channels are not due to hardware components but software design, we will focus mainly on covert timing channels.

A covert timing channel exploits access timings of shared resources. In his work [START_REF]Cache missing for fun and profit[END_REF], C. Percival took advantage of cache hit and miss to convey "0" and "1" respectively. With collocated VMs sharing multiple resources (hardware and system), the Cloud is an environment conducive for such exploits. Building a covert timing channel in a public commercial Cloud (e.g., EC2) has been proven feasible [START_REF] Ristenpart | you, get off of my cloud: exploring information leakage in third-party compute clouds[END_REF], [START_REF] Wu | Whispers in the hyper-space: high-speed covert channel attacks in the cloud[END_REF], [START_REF] Xu | An exploration of l2 cache covert channels in virtualized environments[END_REF]. A reliable bandwidth of just a hundred bits per second is enough to silently extract hundreds of 1024-bytes private keys, or tens of thousands of credit cards in a day. The DoD guideline [START_REF] Tcsec | Trusted Computer System Evaluation Criteria[END_REF] (TCSEC / Orange Book) characterizes a covert channel by its bitrate and error rate. It suggests that covert channels exceeding a threshold of 0.1 bit per second should be audited and be of concern to security if it performs over 1 bit per second.

In a Cloud environment, covert timing channels can be conducted using several hardware or system components. In Table I, we draw a summary of previous Cloud covert timing channels works. For the same component, reported bitrates can differ up to 6 orders of magnitude (e.g., 0.2 bps and 190.4 kbps for L2 cache covert channel) depending on the experimental environment (i.e., setup column). This gap cannot be explained by hardware differences alone (e.g., CPU clock speed, cache size). How the attack is implemented also has a major impact on the bitrate.

D. Mitigation techniques

Covert channels in multitenant environments pose a real threat with bitrates largely over the 1 bit per second standard threshold. A covert channel is by definition a reliable data channel, therefore reducing the bandwidth, preventing the channel from being reliable (i.e., increasing the error rate) or removing the channel are the basic ideas for mitigation techniques.

We discuss below the mitigation possibilities given 3 perspectives: the tenant, the Cloud provider and the hardware manufacturer.

1) Tenant:

The tenant has limited possibilities against covert channels. HomeAlone [START_REF] Zhang | HomeAlone: Coresidency detection in the cloud via side-channel analysis[END_REF] is a detection approach to detect unusual L2 cache usage without relying on hardware support nor hypervisor modification. But HomeAlone's oracle is not perfect and the Spy can try to evade the detection. Moreover, according to Wu et al. [START_REF] Wu | Whispers in the hyper-space: high-speed covert channel attacks in the cloud[END_REF], for memory bus covert timing channels, this approach would be subject to high performance overhead and high false positive rate due to non-determinism and higher access latencies. To sum up, a detection approach at the tenant level cannot be generalized and do not apply to yet to discover covert timing channels.

2) Cloud provider: On the other side, the Cloud provider has more latitude to mitigate covert channels. He can use detection techniques at the hypervisor level with lower overhead. Moreover, he can modify the scheduling policy to implement cache partitioning or page coloring to isolate cache/memory accesses [START_REF] Raj | Resource management for isolation enhanced cloud services[END_REF], [START_REF] Taesoo | System-Level Protection Against Cache-based Side Channel Attacks in the Cloud[END_REF] at the cost of performance. Others existing preventive approaches are dedicated instances or collocation/anti-collocation placement. In this case, the isolation properties can be modelized as collocation and anticollocation constraints [START_REF] Caron | Improving users' isolation in iaas: Virtual machine placement with security constraints[END_REF], [START_REF] Jayasinghe | Improving Performance and Availability of Services Hosted on IaaS Clouds with Structural Constraint-aware Virtual Machine Placement[END_REF]. Nevertheless, they require to express the list of tenants with whom each VM is allowed to share resources (or not). Moreover such measures are costly for the tenant as he pays extra charges for dedicated physical machines as these approaches use coarse grain resource allocation model.

On modern public Clouds such as Amazon EC2 and Microsoft Azure, hardware multithreading called simultaneous multithreading (SMT) is disabled as cache-based covert channels attacks are easy to build. For example, L1 caches that are dedicated to one core are the easiest way to create covert channels [START_REF]Cache missing for fun and profit[END_REF] between VMs. The NoHype concept [START_REF] Keller | NoHype: Virtualized Cloud Infrastructure without the Virtualization[END_REF] consists in removing the virtualization layer while retaining the key features enabled by virtualization. They limit covert channel by enabling one VM per core but as we have shown, other covert channels exist within the microarchitecture components.

3) Hardware manufacturer: A covert channel is based on a faulty implementation. Thus, the hardware design is the initial reason of most covert channels. The solution would be to integrate security concerns when designing hardware components. Needless to say, it will not fix the issues on hardware already in production. Nevertheless, hardware design is out of the scope of this paper. 4) Summary: Because of the lack of near-future improvement in hardware design and the specificity of detection techniques, we propose a covert channel aware placement solution. Outsourced applications do not have the same level of criticality. For example, a private individual's web site is less threatened by covert channels than a banking or government application. Therefore, we consider the tenant to be responsible for specifying an acceptable information leakage risk and then, the Cloud provider has automated procedures to decide whether or not the tenant's VM should share L1/L2/L3 caches, memory bus, etc. with other VMs. Such solution can be applied to any Cloud and easily enriched with newly discovered covert channel attacks. The placement algorithm has to use a general metric to deduce a value from a given placement/hardware configuration and compare it with the tenant's risk requirement. The following part discusses existing metrics and devises a new metric to tackle practicability issues.

E. Covert channel aware metric

Due to the recentness of Cloud (and virtualization) covert channels works, the literature is quite poor in covert channel metric propositions. Published in 2012 and after, the reference works are the metrics proposed by Demme J. et al. [START_REF] Demme | Sidechannel vulnerability factor: A metric for measuring information leakage[END_REF] and Zhang T. et al. [START_REF] Zhang | Side channel vulnerability metrics: The promise and the pitfalls[END_REF] with respectively the Side channel Vulnerability Factor (SVF) and the Cache Side channel Vulnerability (CSV). Firstly, both metrics are design for side channels and not covert channels, but because side channels and covert channels are intrinsically related, theses metrics cannot be discard based on this sole argument to motive our new information leakage metric. SVF and CSV are float values between 0 and 1 reflecting the degree of information leakage an observer can see from an execution. They correlate the oracle execution traces with the leaked execution traces viewed by another process in terms of cache accesses, cpu loads, etc. The approach is thus hardware-independent but the obtained value is applicationspecific. Indeed, the evaluation is based on the execution of a cryptographic library and it is hard to deduce if a given value would be roughly the same for an arbitrary application.

One problematic is to allow a tenant to specify a value as an acceptable risk. Because SVF and CSV are correlation factors, they can be easily used for comparison but except for limit values (0 and 1) it is quite a challenge to give a practical meaning to an intermediate value (e.g., 0.467), even for a knowledgable tenant. Therefore, both SVF and CSV are unspecifiable in practice, and thus we must come up with an alternative covert channel aware metric presented thereafter.

III. INFORMATION LEAKAGE METRIC : A MICRO-ARCHITECTURAL SECURITY METRIC

We have shown in Section II that both SVF and CSV metrics are not satisfying. Because the DoD guideline [START_REF] Tcsec | Trusted Computer System Evaluation Criteria[END_REF] (TCSEC / Orange Book) indicates that a covert channel (characterized by its bitrate and error rate) over 1 bit per second (bps) should be of concern to security, we use it as a reference value for our metric.

Therefore, we define the Information Leakage Metric as follows :

Definition 1 (Information Leakage Metric): Ratio between the covert channel theoretical bitrate in a noiseless environment and the reference value (1 bps).

Unlike SVF and CSV, our metric characterizes the worst case scenario. In a security context, such scenario corresponds to the maximal bitrate a covert channel can theoretically achieve. Thus, to compute this value, we consider a noiseless environment and a parallel setup (the Trojan and the Spy run on distinct cores). Because our Information Leakage approach is based on a core characteristic (i.e., the bitrate), a value exists for any timing covert channel though it can be complex to compute it.

In the following, we exemplify the approach with a cachebased timing covert channel.

A. Cache-based Timing Covert channels bitrate in Virtualized Environment

In this subsection, we detail how a cache-based timing covert channels works using Percival et al. technique [START_REF]Cache missing for fun and profit[END_REF].

The idea is to time the latency of accessing memory addresses. We distinguish two cases, that is, if the accessed data are already in the cache, then the latency is small; else it must be retrieved from the main memory, then the latency is larger. As illustrated in Figure 2, the Spy accesses twice a set of cache lines (by accessing memory addresses mapped to it). When the data is in the cache, the latency is under a threshold and so the Spy reads bit "0", otherwise it reads bit "1". Its data are now in the cache.

Similarly, to transmit bit "1", the Trojan accesses the same set of cache lines (by accessing its own memory addresses mapped to it) i.e., he flushes the Spy's data off the cache. To transmit bit "0", the Trojan lets the cache in the same state by doing nothing.

A set-associative cache is divided in sets of cache lines. As shown in Figure 3, a memory address can be splitted into {TAG, SET, OFFSET} bits where OFFSET is the offset in the cache line, SET the set number and TAG the stored value to compare addresses. In a w-way set-associative cache, w addresses mapped to the same cache line can be stored at the same time, generally based on a LRU replacement policy.

As a result, w addresses must be accessed to fully flush one w-way cache line.

Furthermore, virtual to physical address translation rises the problem of addressing uncertainty. Nonetheless, in modern operating systems, the memory space is divided in 4 KB pages and the translation mechanism maps a virtual page to a physical page. Thus, as illustrated in Figure 3, the last 12 bits of a memory address remain identical after the translation, leaving unknownsets possible cache sets for one virtual memory address where :

unknownsets = nbsets × linesize pagesize (1)
Therefore, to evict a Spy's cache line, the Trojan accesses at least minlines addresses where:

minlines = w × unknownsets (2)
Given the total cache size is ttsize = w × nbsets × linesize, to read or transmit a single bit the trojan accesses at least:

minlines = ttsize pagesize (3)
Finally, we suppose the same probability to transmit bit "0" or bit "1" i.e., P (0) = P (1) = 1/2. Thus, the final time to read or write a bit is:

(latency cached + latency f lushed ) 2 × ttsize pagesize (4)

B. Discussion

Previous works on covert timing channels are mainly based on experimental results. To our knowledge, our paper is the first attempt to generalize the computation of cache-based covert timing channel bitrate. For this generalization, we consider the time between writing and reading to be null whereas experimental approaches must implement a synchronization mechanism. Indeed, there is a vast range of possibilities for this synchronization between the Trojan and the Spy, and choosing one would alter the quality of our metric. Moreover, this synchronization can be achieved independently from the attack itself. For example, in side channels works, the question is to detect when a cache activity corresponds to a cryptographic computation. If the victim is a web server, a simple solution is to trigger it by accessing a SSL-encrypted web page.

Secondly, our information leakage metric can only be based on known covert timing channel attacks, thus it encompasses neither unknown existing attacks nor yet-to-discover attack schemes. However, this metric does not rely on execution traces and as so, it applies to any application and, if properly adapted, any hardware. For example, atomic memory operations are improperly emulated in x86 virtualized environment [START_REF] Wu | Whispers in the hyper-space: high-speed covert channel attacks in the cloud[END_REF]. These atomic operations have been implemented with a big system lock (a lock that freezes all other activities of the system) to keep the memory consistent. Consequently, a memory contention generated by one VM can be seen by another one running on the same physical machine. By observing a contention or its absence, the Trojan and the Spy can transmit respectively bit "1" or "0".

IV. INFORMATION LEAKAGE AWARE PLACEMENT

This paper focuses on the placement of VMs with information leakage constraints specified as isolation properties. What we want to demonstrate is the effectiveness of our approach to ensure isolation and what to consider when doing placementbased security i.e., how to enhance state of the art algorithms to take into account these constraints. In this section we present how isolation properties are satisfied (i.e., enforced) during the placement routine. Moreover, we describe the problem of NUMA allocation and show how we tackle this issue. Finally, we prove the NP-completeness of our placement problem.

A. Isolation Properties Satisfaction

A placement is the association between a VM and a configuration. We define a configuration as a set of NUMAs and cores. By instantiated VMs, we denote the VMs placed on a physical machine (on a set of NUMAs and cores).

A candidate VM's configuration is valid if both following conditions are met: 1) All properties of the candidate VM are satisfied regarding instantiated VMs. 2) All properties of instantiated VMs are satisfied regarding the candidate VM.

An isolation property of a first VM vm 1 is satisfied regarding a second VM vm 2 if one of the 2 following conditions is met:

1) vm 2 is allowed to transfer information with vm 1 2) the information leakage between their configurations is lower than the one specified by the property (as an acceptable risk).

These 2 requirements on top of the hardware ones must be fulfilled to find a suitable configuration. Furthermore, to be able to ensure that all the VMs are respecting their isolation properties (and the ones of the others) during their whole lifetime, it is important to use CPU pinning i.e., to statically associate VMs with cores. Indeed, by not doing so (i.e., if we let a VM changes core during its lifetime or randomly selects one at startup), one of the isolation property could be broken and so the security of the application running inside it as the configuration of the VM would have changed.

Accordingly, our security-aware algorithm must test all configurations for a VM on the physical machines and place it as soon as a configuration is valid. Moreover the placement routine must update the available resources of the platform. Actually, this update is more complex than it seems due to the way NUMA allocation works. In the following part, we present the NUMA allocation problem and the solution we propose.

B. The NUMA allocation problem

We must consider real-world microarchitectural allocation schemes to counter real-world microarchitectural attacks (covert channels). Therefore, our proposal is to have a finegrained control over which (microarchitectural) component is shared amongst multiple VMs to mitigate potential covert channels. With libvirt1 , in addition to the selection of specific cores, we can choose a set of NUMA nodes and one of the 3 available memory allocation policies:

• interleave that allocates memory on a given set of NUMA nodes in a round-robin fashion but falls back to other nodes if the allocation is not possible. In the worst case, any NUMA node can be allocated.

• strict that only allocates memory on a given set of NUMA nodes (or it fails).

• preferred that allocates memory on a given preferred node but falls back to other nodes if the allocation is not possible. In the worst case, any NUMA node can be allocated.

We use the strict policy to have a fine-grained control over memory allocation as we have for CPU cores.

Figure 4 illustrates how the strict NUMA allocation works. We consider a physical machine composed of 2 NUMA nodes with 2 Gb memory and 2 cores each. A first VM (1 core, 1 Gb memory) is bound to the core c 1 and the closest NUMA node (i.e., the memory banks are directly connected to the core), N uma 1 . A second VM requiring 3 cores is bound to c 2 , c 3 , c 4 which are spread on the 2 NUMA nodes. If this VM requires 2 Gb memory, allocating memory from N uma 2 is enough. But if 3 Gb memory are required, both N uma 1 and N uma 2 are chosen.

In terms of microarchitectural attacks, the information leakage between the 2 VMs is simply the bandwidth leakage between their bound cores and NUMAs. Figure 5 illustrates our proposal to deal with the memory segmentation. The first VM (3 cores and 3 Gb of memory) is bound on both N uma 1 and N uma 2 because it requires more than 2 Gb. The problem is that there is no indication on how much memory will be left on N uma 1 and N uma 2 , a total of 1 Gb memory being free though. As a result, the second VM requiring 1 core and 1 Gb memory is also bound to N uma 1 and N uma 2 . Our solution is to virtually consider the merging of N uma 1 and N uma 2 , that is N uma 1,2 which has a total memory of 4 Gb, 1 Gb being free after the placement of the first VM.

Then, in terms of microarchitectural attacks, the information leakage between the 2 VMs is the bandwidth leakage between {c 1 , c 2 , c 3 , N uma 1 , N uma 2 } and {c 4 , N uma 1 , N uma 2 }. Our NUMA allocation procedure works as follows. Upon a new memory allocation request, we select a set of NUMAs numas in the list of available NUMAs such as there is enough memory to allocate. If numas contains more than 1 NUMA, we merge them and create a new virtual NUMA n new , set n new available memory properly, and finally we replace numas from the list available NUMAs with n new . Otherwise (numas is a singleton), we just update numas available memory.

In the desallocation procedure, we delete a virtual NUMA if and only if there is no more VM allocated on it. When it is the case, we put the merged NUMAs back in the list of available NUMAs.

Our security-aware allocation is not rendering the placement problem less complex. Indeed, VM placement (and any placement problem) is know to be NP-hard and can be abstracted as bin-packing problem. In the next subsection, we prove that our extension actually increase the complexity of solving the placement problem.

C. Complexity of our allocation problem

Let an infinity of cores with the VM deployment capacity C. Let a list of virtual machine {vm 1,1 , vm 1,2 , . . . , vm n,n }. We can split this set of virtual machines, in different sub-set: {vm 1,1 , vm 1,2 , . . . , vm 1,n } with a size c n , {vm 2,1 , vm 2,2 } with a size c 2 , and so on. We want pack objects of different volumes (here a sub-set of VMs) into a finite number of bins (here cores) each of volume C in a way that minimizes the number of bins (/cores) used.

We use the binary code to describe the solution and indicate if a VM is on a core or not. Variable x ij is egal to 1 if the VM i is deployed on the core j, and 0 otherwise. Boolean variable y j is egal to 1 if the core is used, 0 otherwise. We try to minimize the number of core used.

min n j=1 y j (5)
This problem is known as the NP-hard problem called the Bin Packing Problem (BPP). Nevertheless, in our case we have additional constraints due to the security rules. We can consider these constraints like conflicts. The Bin-Packing Problem with Conflicts is called BPPC. It consists in determining the minimal number of identically bins (/cores) needed to store a set of items (VMs) with height is less than the capacity of bins (/cores), where some of this items are incompatible with each other (isolation rules), therefore cannot be packed together in the same bin (/core). The BPPC is a variation of the classical one dimensional BPP which is a combinatorial problem and known also to be NP-hard [START_REF] Coffman | Approximation algorithms for np-hard problems. chapter Approximation Algorithms for Bin Packing: A Survey[END_REF], [START_REF] Maiza | Heuristics for solving the bin-packing problem with conflicts[END_REF]. Finally, our problem is even harder as we do not have 1 dimension (core) but 2 (memory and core). To keep the proof of concept simple, we rely on a first-fit heuristic to solve this BPPC problem.

V. EVALUATION

In this section, we evaluate our security-aware framework on a 3-tier use case using the information leakage metric previously introduced. A 3-tier application delivers a service (most of the time, a website) that is composed of 3 main parts: a frontend server (e.g., Apache), an application server (e.g., Tomcat) and a database (e.g., MySQL). In this section, we consider a 3-tier application composed of 1 frontend VM, 2 application VMs and 1 database VM. Each of these VMs requires 1 core. Firstly, we present our testbed platform. Then, we detail the scenarios we use in our evaluation. Finally, we demonstrate that a security-oblivious placement algorithm breaks a fair amount of isolation properties but taking them into account impacts the acceptance rate (i.e., the percentage of successfully placed submissions).

A. Testbed platform

We consider an heterogeneous platform of a hundred physical machines. We define 2 types of existing physical machines, namely Taurus and Genepi from the Grid'5000 experimental platform [START_REF] Balouek | Adding virtualization capabilities to the Grid'5000 testbed[END_REF]. In order to compute the cache-based timing covert channel bandwidth, we use the hwloc [START_REF] Broquedis | hwloc: A Generic Framework for Managing Hardware Affinities in HPC Applications[END_REF] tool to obtain Taurus and Genepi hardware topology.

We observe that Taurus has a shared L3 cache of 15 MB and Genepi has a shared L2 cache of 6144 KB. Then we compute the cache latencies using lat mem rd from the lmbench [START_REF] Mcvoy | lmbench: Portable tools for performance analysis[END_REF] benchmarks suite presented in Figure 6.

From Taurus latency measures, we can identify 4 steps, that is 1.43ns from 1 B to 32 KB (L1 cache), 4.3ns from 32 KB to 256 KB (L2 cache), 17.0ns from 256 KB to 15 MB (L3 cache). Taurus RAM latency is 108ns on local NUMA and 184.5ns on remote NUMA.

From Genepi latency measures, we can identify 3 steps, that is 1.2ns from 1 B to 32 KB (L1 cache), 6.3ns from 32 KB to 6144 KB (L2 cache), and 130.0ns above (RAM). Identically, Genepi L2 cache-based timing covert channel can transmit one bit in 0.5 × (6.3ns + 130ns) × 6144KB/4KB = 104.7µs i.e., 9.551 Kbps bitrate.

B. Scenarios

For our placement evaluation, we define 4 security levels, namely Strong, Medium, Weak and None; their corresponding bitrates are given in Table II. As we want to observe the impact of bitrates on the placement (i.e., acceptance rate), these levels are based on our platform microarchitecture (i.e., Taurus and Genepi). Determining which levels are relevant to security requires a thorough study, and thus this question is out of the scope of this paper. Considering our platform, a VM with a Strong isolation property cannot share any cache with any other VM. Similarly, a VM with a Medium Isolation can only share Taurus's L3 if memory is allocated on a remote NUMA. Either a local or a remote allocation is possible with a Weak Isolation. Finally, only the None security level allows VMs to share Genepi's L2 cache. It is reasonable to admit that a tenant considers other tenant's VMs as a bigger threat than its own VMs. Therefore, we define a two-fold policy where internal refers to the security level between the 4 VMs of an application, and external refers to the security level with other VMs in the Cloud.

C. Placement Results

Our objective is to analyze (1) the risk, in terms of unsatisfied security rules, of a security-agnostic algorithm as implemented in current Cloud platforms, and (2) the acceptance rate with our security-aware algorithm which guarantee the satisfaction of all rules.

In this evaluation, we consider all internal/external security level combinations with the internal level always weaker (or equal) than the external one.

We simulate a platform that is composed of 50 Genepi physical machines and 50 Taurus physical machines for a total of 1000 cores. We evaluate the submission of 250 3tier applications requiring a total of 1,000 cores (i.e., 4 VMs × 250 apps.) to saturate the platform.

We evaluate 2 First-Fit algorithms:

• security-agnostic (sec-agnostic FF). It does not try to verify any security rules and so will always have a 100% acceptance rate.

• security-aware (sec-aware FF). It must satisfy all rules and so will always have 0% of unsatisfied rules.

The results presented in Table III show that not considering security (i.e., sec-agnostic FF) exposes a non-negligible number of instantiated applications to covert channels attacks. Even with light constraints like Medium/None some VMs are still insecure (15% of unsatisfied rules) whereas sec-aware FF is able to place 100% of the submissions.

On the other hand, strict security policies come at great expenses. For example the Strong/Strong scenario can only achieve 30% acceptance rate. A future work will be to budget an application according to its security constraints. These first results gives us an overlook of the trade-offs induced by security levels. Due to our simulation setup (platform and submissions), all acceptance rates obtained with sec-aware FF are optimal. It would not be the case for heterogeneous inputs though. The proof is quite simple. In short, with the Medium and Weak levels, 100% of Taurus cores can be allocated if using a remote NUMA, that is 12 cores. For Genepi physical machines, the Medium/Weak levels only allow one core per L2 to be allocated out of 2. As a result, only half of the cores can be allocated on Genepi physical machines i.e., 4 cores. We obtain (12 cores + 4 cores) × 50 physical machines = 800 cores for 1000 available cores, and thus the 80% acceptance rate obtained with a First Fit is optimal for Medium and Weak levels. The proof is similar for other levels, and thus the design of other security-aware algorithms would be relevant only for a more heterogeneous setup where First Fit is not optimal. As we want to focus on a proof-of-concept in this paper, the study of other algorithms is part of our future work.

VI. CONCLUSION

Even with perfect information flow control mechanisms, virtualized environments are still sensitive to silent information leakage, that is covert channels, due to shared hardware ressources. This paper proposes a fine-grained placement based on the tenant's isolation properties to tackle this issue. The tenant submits an application i.e., a set of VMs, and he defines foreach VM the acceptable risk in isolation properties, with respect to other VMs. Due to the lack of usable covert channel metric to qualify an acceptable risk, this paper proposes a new information leakage metric and demonstrates how to compute it with the example of a cache-based timing covert channel. As covert channels exploit microarchitecture flaws, we integrate the specificity of NUMA allocation schemes in our placement algorithm. Furthermore, this paper outlines the riskfactor of traditional placement algorithms while demonstrating the feasability of taking into account information leakage constraints.

This work is a proof-of-concept for placement-based security. This paper covers VM isolation constraints on microarchitectural components. A next step will be to apply our approach to networking. Combining computing and networking resources, designing efficient provisioning algorithms for arbitrary Cloud applications is part of our future work. Independently, an open issue is how to define what is an acceptable risk for real-world tenant's specifications. Finally, we have shown the trade-off between infrastructure consolidation and security requirements. A perspective is to propose a model for the Cloud provider to charge these security requirements.

Fig. 1 .

 1 Fig. 1. Interconnection of processors (P), memory (M) and I/O chipsets in some modern architectures: (a) and (b) 2 Intel Westmere-EP processors; (c) 4 Intel Nehalem-EX processors.

Fig. 2 .

 2 Fig. 2. Cached-based timing covert channel transmitting "10".

Fig. 3 .

 3 Fig. 3. Memory address cache line and page mapping.

Fig. 4 .

 4 Fig.[START_REF] Coffman | Approximation algorithms for np-hard problems. chapter Approximation Algorithms for Bin Packing: A Survey[END_REF]. Strict memory allocation policy for 2 VMs (1 core then 3 cores).1 The API for managing the virtualization layer on Linux: http://libvirt.org/

Fig. 5 .

 5 Fig. 5. Strict memory allocation policy for 2 VMs (3 cores then 1 core).

Fig. 6 .

 6 Fig. 6. Taurus (with NUMAs) and Genepi memory read latencies. Finally, using Equation 4, Taurus L3 cache-based timing covert channel can transmit one bit in 0.5 × (17ns + 108ns) × 15M B/4KB = 240.0µs i.e., 4.167 Kbps bitrate on local NUMA, and 0.5 × (17ns + 184.5ns) × 15M B/4KB = 386.9µs i.e., 2.585 Kbps bitrate on remote NUMA.

TABLE I .

 I

		COVERT-TIMING CHANNELS SUMMARY FOR CLOUD
		ENVIRONMENTS
	Paper	Component	Bitrate	Setup
	[12]	L1	3.2 Mbps	Lab
		L2	800 kbps	Lab
	[19]	SMT/FU	500 kbps	Lab
		Speculation	200 kbps	Lab
	[22]	L2	262.47 bps	Lab
		L2	3.75 bps	EC2
	[21]	Memory bus	746.8 bps	Lab
		Memory bus	107.9 bps	EC2
		L2	190.4 kbps	Lab
	[11]	CPU	0.49 bps	Lab
	[20]	Xen Shared-Mem	174.98 bps	Lab
	[14]	Memory bus	0.006 bps	EC2
		Hard disk	0.0005 bps	EC2
		L2	0.2 bps	EC2

TABLE II

 II

	.	SECURITY LEVEL AND ASSOCIATED BITRATES
	Security Level	bitrate (B)
	Strong		B < 2.585Kbps
	Medium	2.585Kbps ≤ B < 4.167Kbps
	Weak		4.167Kbps ≤ B < 9.717Kbps
	None		B > 9.717Kbps

TABLE III

 III

		.	FIRSTFIT PLACEMENT RESULTS
	Scenario	sec-agnostic FF	sec-aware FF
	External	Internal	(% of unsatisfied rules)	(acceptance rate in %)
	Strong	Strong	100	30
	Strong	Medium	65	60
	Strong	Weak	50	60
	Strong	None	30	80
	Medium	Medium	50	80
	Medium	Weak	35	80
	Medium	None	15	100
	Weak	Weak	20	80
	Weak	None	0	100
	None	None	0	100

The API for managing the virtualization layer on Linux: http://libvirt.org/

ACKNOWLEDGMENT

This work was done thanks to the financial support of the Celtic+ project SEED4C (Eureka Celtic+ CPP2011/2-6).


Eddy Caron

Jonathan Rouzaud-Cornabas

Improving users' isolation in IaaS: Virtual Machine Placement with Security Constraints

Keywords: Security, Isolation, Hierarchical VM Placement, Covert-channel, Cloud Computing, IaaS

Nowadays virtualization is used as the sole mechanism to isolate different users on Cloud platforms. We will show that due to improper virtualization of microarchitectural components, data leak and modification can occur on public Clouds. Furthermore, using the same vector, it is possible to induce performance interferences, i.e. noisy neighbors. Using this approach, a VM can slow down and steal resources from concurrent VMs. We propose placement heuristics that take into account isolation requirements. We modify three classical heuristics to take into account these requirements. Furthermore, we propose four new heuristics that take into account the hierarchy of the Cloud platforms and the isolation requirements. Finally, we evaluate these heuristics and compare them with the modified classical ones. We show that our heuristics are performing at least as good as classical ones but are scaling better and are faster by a few order of magnitude than the classical ones.

I. INTRODUCTION

Virtualization is now widely used in modern data centers. Thank to mature software stacks and the widespread availability of platforms all over the world, the Cloud is now available for many applications of different kinds. Security and performance are the main goal users want to achieve when porting applications over IaaS or PaaS platforms. Security has been proven to be sometimes difficult to obtain [START_REF] Ristenpart | Get Off of My Cloud: Exploring Information Leakage in Third-Party Compute Clouds[END_REF] and several issues have been raised in public Clouds and public domain virtualization software stacks. Several different kinds of attacks and security issues can be observed that may lower the impact of Clouds. On the performance side, the expectations are higher than what can be actually obtained on today's public Clouds. Shared Physical Machines lead to performance degradation that are not appropriate for high performance applications. Isolation is then a critical issue both for security and performance concerns.

In this paper, we present the limitation of using virtualization technology as the sole approach to isolate workloads and users within a Cloud. In highly secured environments, strong isolation is done by unshared resources environment for two tasks with different security clearance. It is still the strongest defense against covert-channels (and other attacks). But this approach eliminates most of the current public and private Clouds but also the way how virtualization is used. With the widespread usage of virtualization, the need of strong isolation in such environment becomes critical. First, in Section II, we present the micro-architecture of modern computer. We also present the virtualization limitations and how they can be exploited to attack security and privacy in the Clouds. Moreover, we show that the same issue exists for performance. In Section III, we introduce a set of VM placement heuristics that take into account the security requirements. Furthermore, we propose a set of optimization for these heuristics to improve performance and consolidation. In the Section IV, we present our evaluation methodology and explain our results. Finally, in the Section V, we conclude and present our future work.

II. MICRO-ARCHITECTURE: WHERE VIRTUALIZATION FAILED

Since the last few years, the complexity of physical machines' hardware topology has increased dramatically [START_REF] Broquedis | hwloc: A Generic Framework for Managing Hardware Affinities in HPC Applications[END_REF]. The number of cores, shared caches, and memory nodes have completely changed the microarchitecture of computers. From a simple CPU architecture during the Pentium era, we have now access to complex multi-core, multi-level caches that can be specific to a core, shared between some or all. Symmetric Multithreaded Processors (SMP) brings another level of hierarchy. SMP is a mean to share the resources of a core between multiple logical processors.

With the increasing number of cores, scalability becomes a major issue. To address it, modern proces-sors use non-uniform interconnects 1 . This technology is named a Non-Uniform Memory Access (NUMA) architecture. But memory is not the only resources to be accessed through these non-uniform interconnects, Input/Ouput Devices accesses are done in a similar manner (Non-Uniform Input/Output Access -NUIOA). In this type of architecture, some cores have faster access than others to some I/O devices and memory banks [START_REF] Goglin | Dodging Non-Uniform I/O Access in Hierarchical Collective Operations for Multicore Clusters[END_REF]. For example, Figure 1 shows the inner architectural components of five modern platforms. As one can see, depending on whether the data is stored in a directly connected memory bank or in a remote one, the access to it will need to passthrough one (or more) CPU. The same is true for the I/O devices. Accordingly, the placement of tasks on CPU and their related data on memory banks is critical to exploit performance on these modern architecture. The inner-topology of computer has a large impact on performance depending where the different process of an application are placed. For example, the DMA throughput can decrease by up to 42% when accessing a GPU from a distant NUMA node. Thus, exporting the topology to the VM is critical. Virtualized NUMA (vNUMA) is already available [START_REF] Ali | Performance Evaluation of HPC Benchmarks on VMware's ESXi Server[END_REF]. But there is not a one-to-one mapping between virtual and physical NUMA. Indeed, some physical NUMA can be shared through two vNUMA by VMs and two NUMA can be aggregated into one vNUMA. Accordingly, performance optimization can be buried by the vNUMA not really providing the same kind of hardware connections it 1 HyperTransport for AMD and QPI for Intel.

exposes.

A. Covert-Channel

Contrary to the memory and CPU, the microarchitectural component are not properly virtualized in modern platform. Therefore, the sharing of microarchitectural components can be used as covert channels to leak information between concurrent VMs. In [START_REF] Xu | An Exploration of L2 Cache Covert Channels in Virtualized Environments[END_REF], authors present new work on the creation of covert channels of communication between virtual machines through the L2 cache processors. Their goal is to quantify the rate of leakage through this channel. In previous work [START_REF] Ristenpart | Get Off of My Cloud: Exploring Information Leakage in Third-Party Compute Clouds[END_REF], three channels were studied: memory (0.006bps), disk (0.0005bps), and L2 cache (0.2bps). The purpose of [START_REF] Xu | An Exploration of L2 Cache Covert Channels in Virtualized Environments[END_REF] is to see if they can optimize the speed. In experimental testbeds, they were able to reach a rate of 223.71bps and between 1.27bps and 10.46bps on Amazon EC2. Other studies of covert channels within Clouds have been made in [START_REF] Okamura | Load-Based Covert Channels Between Xen Virtual Machines[END_REF], [START_REF] Zhang | Home-Alone: Co-residency Detection in the Cloud via Side-Channel Analysis[END_REF].

In [START_REF] Wu | Whispers in the Hyperspace: High-speed Covert Channel Attacks in the Cloud[END_REF], authors present a new inter-VMs attack in the Cloud. Unlike previous works, they do not use the L2 cache CPU but the memory bus. This new channel allows them not to be limited to a set of cores sharing a cache but they can reach the entire physical machine. To do this, they observe the memory bus contention as covert channel. They are able to create a covert channel with a bandwidth of 746.8 bps (+/-10.1) and between 343.5 bps (+/-66.1) and 107.9 bps (+/-39.9) on Amazon EC2. This improvement is at least a factor of 10 with approaches via the L2 cache.

B. Noisy Neighbors: Performance Interference

Virtualization is also used in Cloud Computing to provide performance isolation between multiple tenants. With a perfect performance isolation, no performance interference between two VMs must exist. Thus, noisy VM will have no impact on the performance of other VMs. Hypervisors implement resources allocation algorithms that fairly shares resources between different VMs. But these algorithms focus only on CPU time and memory capacity and do not take into account other resources [START_REF] Barham | Xen and the Art of Virtualization[END_REF]. Furthermore, current hardware virtualization does not provide mechanisms to limit microarchitectural components usage.

With the lack of strong isolation and in particular on micro-architectural components, the performance of a VM can suffer from interference coming from another one running on the same hardware. In [START_REF] Varadarajan | Resource-Freeing Attacks: Improve your Cloud Performance (At your Neighbor's Expense)[END_REF], authors show that the performance loss can be up to 80% on a cache-sensitive benchmark because of the behavior of a collocated VM. But others works have shown the same type of performance loss can be achieved by attacking shared memory [START_REF] Moscibroda | Memory Performance Attacks: Denial of Memory Service in Multi-Core Systems[END_REF] and [START_REF] Barker | Empirical Evaluation of Latency-Sensitive Application Performance in the Cloud[END_REF]. Other works have studied the strong performance interference in Cloud Computing platforms [START_REF] Pu | Understanding Performance Interference of I/O Workload in Virtualized Cloud Environments[END_REF], [START_REF] Wang | The Impact of Virtualization on Network Performance of Amazon EC2 Data Center[END_REF], [START_REF] Schad | Runtime Measurements in the Cloud: Observing, Analyzing, and Reducing Variance[END_REF]. As one can expect, all the shared resources (compute, storage and network) in Clouds are affected by interference issues.

The effectiveness of such interference could lead to a new class of attacks called Resource-Freeing Attacks (RFA) in [START_REF] Varadarajan | Resource-Freeing Attacks: Improve your Cloud Performance (At your Neighbor's Expense)[END_REF]. "A resource-freeing attack leverages these observations of contention to improve a VM's performance by forcing a competing VM to saturate some bottleneck resources". The purpose of such attack would be to create interference that leads a VM to starve due to its inability to access specific micro-architectural components and thus freeing other resources. Accordingly, the VM that launches the attack could used these resources to boost its performance. Authors of [START_REF] Varadarajan | Resource-Freeing Attacks: Improve your Cloud Performance (At your Neighbor's Expense)[END_REF] have shown they can gain a performance boost of up to 60% in lab and 13% on Amazon EC2.

C. Detection of Covert-Channel

Amazon provides a service that dedicates physical machines to an user: dedicated instances. But this service comes with a high price. [START_REF] Zhang | Home-Alone: Co-residency Detection in the Cloud via Side-Channel Analysis[END_REF] propose to continuously monitor memory access latencies and generates alarms when anomalies are detected. But memory probing incurs high performance overhead. Moreover, their approach has a high false positive rate.

VALID [START_REF] Bleikertz | VALID: A Virtualization Assurance Language for Isolation and Deployment[END_REF] is a specific language for security assurance. The goal is to verify the respect of security properties i.e. to detect violations of them. The language can express security goals such as isolation and generally express security properties based on information flow. Their approach is limited to detect isolation faults in network and is not able to do it for micro-architectures.

D. Improving Isolation within a Physical Machine

As we have presented in Section II-A, it is possible to create covert channels between VMs by using the lack of proper virtualization of micro-architectural components.

In [START_REF] Raj | Resource management for isolation enhanced cloud services[END_REF], authors propose to improve the isolation of virtual machines while minimizing the loss of consolidation. The approach consists in offering better refinement within this isolation. They propose two algorithms: cache hierarchy aware core assignment and page coloring based cache partitioning. It limits the risk of breaking the isolation between virtual machines without having to use multiple physical machines. But their approach introduces a very large overhead that renders it inapplicable on real world Cloud platforms.

In [START_REF] Taesoo | System-Level Protection Against Cache-based Side Channel Attacks in the Cloud[END_REF], authors propose a protection that allows the hypervisor to counter attacks on CPU caches. Their approach has an overhead equivalent to 3 % loss of memory and cache. In addition, it brings an overhead of 5.9 to 7.2 % in terms of computation. Other works around software mechanisms to increase performance isolation exist for other resources: disk [START_REF] Gulati | mClock: Handling Throughput Variability for Hypervisor IO Scheduling[END_REF], memory bandwidth [START_REF] Verghese | Performance Isolation: Sharing and Isolation in Shared-Memory Multiprocessors[END_REF], and network [START_REF] Shieh | Seawall: Performance Isolation for Cloud Datacenter Networks[END_REF].

The NoHype concept [START_REF] Keller | NoHype: Virtualized Cloud Infrastructure without the Virtualization[END_REF], [START_REF] Szefer | Eliminating the Hypervisor Attack Surface for a More Secure Cloud[END_REF] consists in removing the virtualization layer while retaining the key features enabled by virtualization. They limit covert-channel by enabling one VM per core but as we have show, other covert-channels exist within the micro-architecture components. Moreover, they are not able to do fair sharing on I/O and memory bus. Thus the performance isolation between VMs with NoHype remains weak.

E. Discussions

As we have shown in this section, the microarchitecture of modern platforms is evolving very fast. From a single CPU processor few years ago, we have now access to massively parallel platforms with complex hierarchy of micro-architectural components.

The current trend of security in Clouds is to use virtualization as the sole mechanism to enforce security and performance isolation between users and their VMs. But the lack of proper isolation of microarchitectural components lead to the ability of creating covert-channels between these VMs. It has been shown that it is possible to use these covert-channels to extract sensitive information such as cryptographic keys. But the security isolation is only one fold of a two folds issue. Performance isolation is also critical for Clouds. Indeed, if a VM is not able to efficiently use its available resources due to a noisy neighbor, it can lead to availability issue. As we have shown, a VM can applied such noisy neighbor behavior to slowdown a collocated VM. That leads the collocated VM to release resources and the VM who launches the attacks is able to extract more performance from the Cloud.

Motivation: As we have shown depending of the micro-architectural components shared between VMs, it is more or less effective to create covert-channels. The same is true for performance isolation. The sharing (or not) of micro-architectural components brings to complex security and performance trade-offs. Providing the tenant with the ability to specify the level of sharing his VMs can accept for micro-architectural components would give the ability to the user to configure the quality of isolation for each of his VMs. In the rest of the paper, we propose an approach to provide adaptable isolation. We show how it can be ported to any resource management system at node level (hypervisor) and at Cloud level.

To help guide the placement of virtual machines, the main approach is to use constraints which reflect the goals expressed by the user and the entity that operates the infrastructure. By expressing the placement problem as Constraint Satisfaction Problems (CSP), it is possible to use a solver to resolve it. Constraints can represent different goals such as energy saving [START_REF] Van | Autonomic Virtual Resource Management for Service Hosting Platforms[END_REF]. But solving large problems is time consuming thus using a decentralized and hierarchical approach can decrease the computation of a solution [START_REF] Feller | Snooze: A Scalable, Fault-Tolerant and Distributed Consolidation Manager for Large-Scale Clusters[END_REF], [START_REF] Feller | Energy-Aware Ant Colony Based Workload Placement in Clouds[END_REF]. The principle of using a linear program or a linear system to solve the problem of placement of virtual machines in the Cloud with constraints has been studied numerous times as in [START_REF] Simarro | Dynamic Placement of Virtual Machines for Cost Optimization in Multi-Cloud Environments[END_REF], [START_REF] Tordsson | Cloud Brokering Mechanisms for Optimized Placement of Virtual Machines Across Multiple Providers[END_REF]. The constraints can modelize numerous goals such as performance and availability [START_REF] Jayasinghe | Improving Performance and Availability of Services Hosted on IaaS Clouds with Structural Constraint-aware Virtual Machine Placement[END_REF]. These goals are then translate into collocation and anti-collocation constraints. As for the CSP approach, linear program approaches do not scale. To improve the performance of VM placement algorithm, hierarchical representation allows to reduce the search space [START_REF] Jayasinghe | Improving Performance and Availability of Services Hosted on IaaS Clouds with Structural Constraint-aware Virtual Machine Placement[END_REF]. Avoiding cache and processor resource contention through scheduling algorithms is a well studied approach [START_REF] Bhadauria | An Approach to Resource-Aware Co-Scheduling for CMPs[END_REF], [START_REF] Merkel | Resource-Conscious Scheduling for Energy Efficiency on Multicore Processors[END_REF], [START_REF] Zhuravlev | Addressing Shared Resource Contention in Multicore Processors via Scheduling[END_REF]. At the cluster level, numerous works have also been done [START_REF] Li | Feedback Dynamic Algorithms for Preemptable Job Scheduling in Cloud Systems[END_REF], [START_REF] Srikantaiah | Energy Aware Consolidation for Cloud Computing[END_REF]. The purpose of these approaches is to increase performance isolation between processes.

The current issue is to have efficient and scalable algorithms that are able to work at the scale of multidatacenters Cloud infrastructure. CSP or linear program approaches do not scale well. Indeed, placing VMs on Clouds can be formalized as a multi-dimensional bin-packing. Therefore, the complexity of solving such problem is NP-Complete. Heuristics allow to have almost optimal solutions with a reduced complexity. In this paper, we propose to use such heuristics. They are able to take into account isolation requirements while placing VMs on a multi-datacenter Clouds or any infrastructures described through the distributed system model.

A. User Isolation Requirement

The purpose of the user isolation requirement is to enforce isolation between users.

The requirement has a scope where it applies i.e. a level in the hierarchy of the distributed systems. For example, if the requirement's scope is PM, it will apply to all the level below the PM e.g. NUMA and socket and at the PM level. We differentiate 3 types of isolation requirement: alone, friends and enemies. With alone requirement, the user specifies that only his VMs can shared the resources at a given level (and all the above ones). With friends one, the user specifies a list of users allowed to share resources with him. And with ennemies, the user specifies a list of users that must never share resources with him.

To verify these requirements, we introduce two functions. The first one checks if a node and the VMs already allocated on it respects the user's requirements. Furthermore, the functions also verifies if all the nodes above the checked node also verifies the user's requirements. The second one verifies if a new VM respects the user's requirements of all VMs already allocated on a given PM.

B. Heuristics

In this section, we will first present two optimizations than can used by all VM placement heuristics. Then, we present heuristics that do not take into account the hierarchy in the section. We present a first fit heuristic that takes into account the hierarchy. Finally, we present best fit heuristics that take into account the hierarchy.

1) Optimizations: A function, Check Capacity, is used by the heuristics to verify that a node of the distributed system has enough resources for a VM. To avoid to search in a branch of the hierarchy if no node within it contains enough resources to start a VM, we introduce the optimization betterF it. Indeed, a level in the hierarchy can have enough free aggregated resources of a specific capacity but these resources are shared between PMs. For example, a cluster can have 20 free CPU cores but with only a maximal block of 4 available on a PM. Thus, without betterF it, the algorithm will try to find a PM that can host the VM that requests 8 CPU cores but will failed as none contains enough resources. With betterF it, the algorithm will know that there is no block of CPU cores larger than 4 and thus it can avoid to iterate through all the PMs of the cluster. Therefore, betterF it avoids to search in branch where there is no solution.

Except for the FirstFit heuristics, all the VM placement heuristics presented here return a list of PMs. Thus, we need to sort this list to select the PM that is the best to start the VM. All the PMs returned by the VM placement heuristics fit the capacity and isolation requirements, the sorting algorithm does not change anything about it. But the sorting algorithm helps to improve the quality of placement by selecting the best fitting PMs in a list of fitting PMs. Moreover, the same heuristic can be used to sort all the nodes in the hierarchy and not only the PMs. Indeed, in some heuristics, we need to sort a list of nodes at other level e.g. clusters within the hierarchy. We use two different sorting heuristics. sortBestF it applies best fit i.e. it places at the beginning of the list the nodes that have just enough resources for the VM. It helps to improve the consolidation of the nodes while respecting the resources and isolation requirements. sortBestF itAppsAf f inity is more advanced version that takes into account already placed VMs. In addition of best fit, it puts at the beginning of the list the nodes where VMs from the same application are already running. Then the nodes that has a father, i.e. a node at a higher level in the hierarchy, where VMs from the same application are running. And recursively, it does so for every upper levels. For example, it will put at first two PMs where VMs from the same application are already running and will sort one from the other one by applying the best fit heuristic. Then, it will put the PMs that belong to a cluster where VMs from the same application are running and applies best fit heuristic between them. Therefore, it helps to consolidate the application by placing the VMs belonging to an application close to another. Thus, it helps to minimize the latency between VMs of an application. Moreover, by grouping the VMs of an application on a sub-part of the hierarchy, it helps to improve the number of allocated VMs by avoiding to spread an application in the hierarchy. Indeed, if an application is spread in the distributed system and required an isolation requirement with a scope at the upper level of the hierarchy, it can lock a large part of the distributed system for one application.

2) Heuristics not Hierarchy-Aware: In this paper, we present new heuristics that take into account the hierarchy of distributed systems such as cloud. But, we want to compare our heuristics with ones that do not take into account hierarchy. Even if they do not take into account the hierarchy, they respect the capacity and isolation requirements. The F irstF it heuristic takes the list of all the PMs on the distributed system. It iterates trough it until it finds a node that fits the capacity and isolation requirements. The issue with F irstF it is that it always iterates on a fixed list of PMs. To improve it, F irstF itShuf f le does a shuffle on the list of PMs before iterating on it. The BestF it heuristic takes the list of all the PMs on the distributed systems. It returns a list that contains all fitting PMs. This list can then be sorted using one of the sorting algorithms presented previously.

3) BestFit: HierarchicalAwareBestF it (HABF) takes into account the hierarchy. It applies one of the two sorting algorithms at each level of the hierarchy. First, it sorts using one of the two sorting algorithms all the root of the distributed systems and selects the best fitting one. Then it does the same with each child of the best fit node. Recursively, it reaches a subset of PMs, e.g. the PMs belonging to a cluster that fits the capacity and isolation requirements and returns this list. The list can be then sorted using one of the two sorting algorithms. All the best fit hierarchy-aware heuristics presented here including this one are based on a Breath First Search algorithm.

4) BestFit with Properties: Contrary to the previous one, HierarchicalAwareBestF itwP roperties (HABFP) starts to use best fit only when it reaches a level in the hierarchy that is equal to the higher level expressed by the isolation requirements. Thus, it will iterate through all the branches of the tree at the beginning. By doing so, the heuristic is able to choose the best fit node at a specific level in the hierarchy and is not limited to the children of the best fit node of each level. Unless the higher level expressed by isolation requirements is the higher level of the hierarchy, the heuristic will iterate through more nodes but it can find a best fit nodes that is behind a non best fit nodes. For example, an application specifies an isolation requirements at the cluster level. If using the first version of the best fit hierarchy-aware heuristic, it will select a cluster in best fit site. With this heuristic, it will iterate through all the sites and all the clusters belonging to each site. It will then select the best fit cluster.

5) BestFit Large: As we previously state, a best fit node can be behind a not best fit node at a upper level in the hierarchy. Thus, doing best fit at each level of the hierarchy can have bad effects by hiding some nodes. HierarchicalAwareBestF itLarge (HABFL) still applies a best fit hierarchy-aware heuristic but it iterates through all the valid nodes at each level. It will not iterate through part of the system that is not fitting capacity and isolation requirements. Thus, contrary to the non hierarchical-aware heuristics as presented in the Section III-B2, it does not have to iterate through all the PMs.

6) BestFit Large with Hierarchical Sorting:

HierarchicalAwareBestF itLargeSort (HABFLS) is a variant of HierarchicalAwareBestF itLarge. HierarchicalAwareBestF itLargeSort returns an already sorted list but this list is sorted differently than HABFL. The list is hierarchically sorted such as the first PM on the list are the ones that are the best fitting PMs with the best fitting ancestors. For example, first will be the sorted list of PMs of the best fitting cluster of the best fitting site. Then the best fitting node of the second best fitting cluster of the best fitting site, etc..

7) Summary:

We summarize the different heuristics in the table III-B7. For the heuristic complexity (without optimizations), we use the following formalism. In this case, the complexity is the worst case for finding (or not) a fitting node for a given VM, i.e. browsing all the nodes of the platform. A platform is composed of i hierarchical levels, with 1 the lower one, i.e. PM and i the higher one, e.g. region. At each level, the maximal number of nodes attached to a node of higher level is M N i . Accordingly, the maximal number of nodes N i at a level i is

N i = M N i × N i-1 .
The global number of nodes at any levels is N = ∀i, M N i × N i-1 . For the sake of simplicity, we use N P M to express the number of PMs. Accordingly,

N P M = M N O × N 1 .
For example, to model the EC2 platform2 , we use 5 hierarchical levels (region, zone, cluster, rack, PM) with M N i respectively equals to 7, 3, 5, 4 and 96. In this case, N P M = 40320. As one can see in the table III-B7, the theoretical complexity of hierarchy-aware heuristics is a little bit higher than the classical ones, i.e. an increasing of complexity of 1.4%. But, we will show in the Section IV that in practice, the hierarchicalaware heuristics are few orders of magnitude faster than classical ones.

8) Inside a Physical Machine: For the moment, the heuristic to select resources inside a PM is limited to select specific CPU core. It can be extended memory and other resources such as I/O devices. To select a set of cores inside the selected PM, we use the HierarchicalAwareBestF itwP roperties heuristic.

IV. EXPERIMENTATION

In this section, we will first present how we generate simulation scenario then how our simulation scenario are run. Then, we present our simulation results that compare the different heuristics we introduced in the previous section.

A. Scenario

In this section, we describe how we have generate our scenario. These scenario must be plausible with a bit of randomness. The users join and leave the platform based on some basic market rules. At the beginning, the platform has a few early adopters. Then, it gains momentum with an ever increasing number of users joining the platform. Finally, it has reach its limit of attractiveness and few new users are joining it. Accordingly, we approximate the number of users on the infrastructure using a poisson distribution. Furthermore, we use two types of models to simulate the elasticity of applications. The first one is called Uniform, it adds and removes VM (s) at each new application step of the simulation e.g. every hours by picking an amount to add/delete randomly. The second one is called AMR, it uses the elasticity model introduced in [START_REF] Klein | An RMS for Non-predictably Evolving Applications[END_REF].

We limit our experimentation to applications with only one isolation requirement. It is not a limitation of our algorithms but it is a good first evaluation of them. Indeed, we want to know the impact of isolation requirements on consolidation and on placement time thus combining different requirements will complexify the task. For each application, we randomly select an isolation type (and the related list of friends or ennemies users if needed) and a level at which it applies in the infrastructure.

On top of the isolation requirement, we need for each new application to generate the different parameter of an application (elasticity model, number of VMs at the beginning, isolation requirements). Then, we just need to launch the application i.e. schedule the VMs required at the beginning and launch the elasticity function. It runs continuously and based on the elastic model used, adds or removes VMs.

B. Results

We have generate 5 scenarios: 3 (scenario #1), 30 (#2) and 300 (#3) new users per day on a Cloud using the Grid'5000 platform and 3 (#4) and 30 (#5) new users per day on a Cloud using the EC2 platform. We run the 5 scenarios for for each of the 7 placement heuristics and the two options BetterFit (BF) and App-sAffinity (AF). NOBF and NOAF respectively indicat that we do not use BF and AF options.

1) Consolidation: We have compute four indicators for the consolidation: average CPU consolidation, average CPU consolidation per PM, average memory consolidation and average memory consolidation per host. For this metric, the higher is the better. They are computed by taking into account the PMs where VMs are placed. We compute the ratio of the amount of resources used against the total amount of resources on all the PMs for average CPU and memory consolidation. We do the same per PM and compute an average for average CPU and memory consolidation per PM. For reasons of space in this paper, we only display the global memory consolidation in the Figure 2 but the others are showing the same trend. As one can see, the impact of BF and AF optimizations is low especially for hierarchical heuristics. The same is true for all the other metrics. Accordingly, in the following figures, we will not show the value for each combination of optimizations but just the median of all combinations and the error bar.

As shown in the Figure 2, on the Grid'5000 platform, our hierarchical heuristics perform as good as classical one. Except for the case where 300 new users arrived each day, in this case, the classical BestFit heuristic is not able to run fast enough and the experimentation failed. On the EC2 platform, our hierarchical heuristics perform a lot better than the classical one. Indeed, they are able to take into account the hierarchy of the platform and improve the overall consolidation. Whereas, classical ones only see the platform as a long list of PMs. Accordingly, our heuristics scale better than classical ones on large scale and hierarchical platforms. Futhermore, all our hierarchical heuristics perform equally from a consolidation point of view.

2) Successfully added VMs: This metric highlights the number of VMs that have been successfully placed by each heuristics. For this metric, the higher is the better. As shown on the Figure 3, our heuristics perform a little bit better, on average, than classical one on Grid'5000 platforms. But on EC2 platforms, they are performing at least 2 times better than the classical ones. Accordingly, our heuristics permit to place between 2 and 4 times more VMs on the same platform than the classical ones. This is strongly link with the consolidation metrics as placing more VMs on a the same platform required to improve a better consolidation. 3) VM placement duration: In this section, we study the impact of the different heuristics and options on the duration of the VM placement. The lower is the better. The duration on the Figure 4 is displayed in nanoseconds. Except for the first experiment (3 users per day on the Grid'5000 platform), the value for the classical BestFit heuristic is not displayed because it is at least 100 times higher than the worst performing one and renders the figure unreadable if plotted. Contrary to the consolidation and successfully added VMs metrics, our hierarchical heuristics perform better even on the Grid'5000 platform. For example on the fifth experiment, our heuristics perform between 1,000 and 10,000 faster than the two classical FirstFit heuristics. Consequently, our heuristics are able to have at least the same consolidation and successfully added VMs than classical ones and being faster by at least two orders of magnitude. Finally, one can see than HABFP and HABFLS are slower than the two other ones. This is due to a larger space search in average. Indeed as previously explained, these two heuristics start to cut branch in the search space later than the two other.

4) Impact of requirements on placement duration: This section concludes the study of our experimentation. Here, we take a look on the impact of isolation requirements on the placement duration. We only study it for our heuristics as the other ones does not intrinsically take into account the isolation requirements. Futhermore, for a reason of space, we only show the results for a small subset of possible isolation requirements and for only one experiment (EC2 with 30 new users per day). We wanted to know if requiring a low (core) or high (datacenter) level of isolation or a different type of isolation (alone, friend, enemy) will have impact on the placement duration. As one can see on the Figure 5, the type of isolation is not strongly related to the placement duration. On the contrary, the level of isolation has an impact on the placement duration. The lower the level of isolation is the slower the placement duration time is. Indeed, with a high level of isolation, the heuristics are able to reduce the search space earlier than for the requirements that require low level of isolation. Finally, as in the previous section, HAFP and HABFLS are slower than the two other ones.

V. CONCLUSION

We have seen that a large range of possible and realworld attacks on Cloud platforms are due to improper isolation. We have shown that the existing method to improve isolation (from a data and performance points of view) are limited to only detecting them or induce a large overhead. Accordingly, we propose to enhance VM placement heuristics with isolation requirements.

We have introduce the concept of user's isolation requirements for hierarchical and distributed large scale platform. Then, we have explained how these requirements can be used inside VM placement heuristics. Furthermore, we have introduce 4 new heuristics that use the hierarchical nature of the platform.

From experiments, we show that our heuristics perform at least as good as classical ones. Furthermore, on large-scale platforms such as EC2, our heuristics are performing few orders of magnitude better than the classical ones. Finally, we highlight the correlation between VM placement duration and the level of isolation required by a VM.

In the future, we plan to take into account the possible correlation between consolidation and the amount of successfully placed VMs. We work on a improved application model with a larger scale of security requirements. We plan to extend our heuristics to support the whole scope of the requirements and applications expressed through it. Finally, we will extend our heuristics to allocate network resources as well.

Figure 1 .

 1 Figure 1. Interconnection of processors (P), memory (M) and I/O chipsets in some modern architectures [3]: (a) four AMD Istanbul processors; (b) four AMD Magny-Cours processors; (c) and (d) two Intel Westmere-EP processors; (e) four Intel Nehalem-EX processors.

Figure 2 .

 2 Figure 2. Memory consolidation per Host

Figure 3 .

 3 Figure 3. VM successfully added for each scenario

Figure 4 .Figure 5 .

 45 Figure 4. Average duration of placing a new VM

http://aws.amazon.com/ec2/