Ivan Studnia
email: studnia@laas.fr

Eric Alata
email: ealata@laas.fr

Yves Deswarte
email: deswarte@laas.fr

Mohamed Kaâniche
email: kaaniche@laas.fr

Vincent Nicomette
email: nicomett@laas.fr

Survey of Security Problems in Cloud Computing Virtual Machines

Keywords: virtual machine, hypervisor, vulnerabilities, virtualization-based monitoring, isolation enforcement

Virtualization techniques are at the heart of Cloud Computing, and these techniques add their own vulnerabilities to those traditional in any connected computer system. This paper presents an overview of such vulnerabilities, as well as possible counter-measures to cope with them.

Introduction

Virtualization has become an attractive and widely used technology in today's computing. Indeed, the ability to share the resources of a single physical machine between several isolated virtual machines (VM) enabling a more optimized hardware utilization, as well as the easier management and migration of a virtual system compared to its physical counterpart, have given rise to new architectures and computing paradigms. In particular, virtualization is a key element in cloud computing.

However, adding another abstraction layer between hardware and software raises new security challenges. This paper gives an overview of some security problems related to the use of virtualization and shows that the widely used virtual machine managers cannot be considered fully secure. This observation, added to the ever growing popularity of virtualized architectures has led to an important number of studies aiming at enforcing security in virtual systems.

This paper presents first the virtualization principles, then discusses some vulnerabilities related to virtual systems before describing various attempts to address the security challenges raised by virtualization.

Context

Definition

In [START_REF] Popek | Formal requirements for virtualizable third generation architectures[END_REF], Popek and Goldberg define a virtual machine as "an efficient, isolated duplicate of a real machine". They also give three necessary conditions to reach this goal.

-Efficiency: Virtualization shall not induce a significant decrease in performance. Therefore, the greatest amount of instructions must not require an intervention from the virtual machine manager (VMM). -Resource control: The VMM must have a complete control over the virtualized resources.

-Equivalence: A program must behave the same way on a virtual machine as it would do on its physical counterpart.

However, this definition, given in 1974, does no longer cover the whole range of possibilities offered by virtualization. For example, it is now possible to emulate (parts of) systems which do not have a physical equivalent on the host machine. Therefore, new definitions have been established. We will use a definition given in [START_REF] Ramos | Security challenges with virtualization[END_REF]: "Virtualization is defined as a framework dividing the resources of the device from the execution environment, allowing environment plurality by using one or more techniques such as time-sharing, emulation, partitioning."

This definition allows us to include emulation or paravirtualization (cf. 2.3) into virtualization and therefore covers a broader range of currently used techniques.

Classification

Virtualization offers many possibilities, and according to the needs, various kinds of virtualization can be used:

-Process virtualization: virtualizing this layer consists in providing an interface between an application and the underlying system. This allows to create an application without concerning about the specificities of the OSes it will run on, as long as they possess the required virtualization layer. The Java Virtual Machine is an example of process virtualization. -Server virtualization: here, the virtualization is applied to the hardware. This will allow many OSes to run simultaneously on a physical machine. In this paper, we focus on server virtualization techniques.

Server virtualization

There are several ways of implementing server virtualization, either by interacting with the hardware, (nPar 4 for example), the OS (Linux-VServer 5 ) or through a hypervisor, that is to say a program dedicated to the management of virtual machines. Our study will focus on the latter 6 . These hypervisors are often categorized within two groups:

-Type 1: Type 1 managers are installed directly above the hardware and run with the highest level of privileges. Xen [START_REF] Barham | Xen and the art of virtualization[END_REF] and VMWare ESX [START_REF]VMWare ESX homepage[END_REF] are type 1 hypervisors. -Type 2: Type 2 managers are installed above an operating system, like any other program.

QEMU and VirtualBox are type 2 hypervisors. Furthermore, we can distinguish three major techniques of hypervisor based virtualization: full virtualization, paravirtualization and emulation.

Full virtualization

In this case, one or more unmodified operating systems (called "guests") are sharing hardware resources from the host system. The presence of the hypervisor is transparent from the guests viewpoint.

Paravirtualization The kernels of the guest systems are modified to make them able to communicate with the hypervisor below them via hypercalls. Hypercalls can be seen as equivalents to system calls of a non virtualized OS. Paravirtualization is historically the standard method of virtualization used by Xen.

Emulation Like full virtualization, emulation allows unmodified operating systems to run. However, in that case, the resources seen by the guest OS are completely simulated by software. This allows to execute an operating system compiled on an architecture different from the architecture of the host. This results in lower throughput than with the previously mentioned techniques. QEMU is an example of an emulator.

Hardware assisted virtualization

Leveraging hardware capabilities to support virtualization has been done for a long time (IBM System/370, 1972). However, hardware assisted virtualization was not implemented on x86 CPUs. This prevented Popek and Goldberg's conditions from being met because some privileged instructions were not correctly trapped. Therefore, the hypervisor had to perform extra tasks in order to address those lacks. This increased the overall complexity and impacted the performance. However, since 2006, Intel VT 7 and AMD-V 8 technologies implement such techniques. A new CPU state was introduced, orthogonal to privilege rings 0-3, called root mode on Intel chips and guest mode on AMD chips. This state is accessed whenever the hypervisor needs to take (resp. give back) the control over (to) a virtual machine. The guest OS can actually run in ring 0 but not in root mode. Furthermore, the handling of I/O memory virtualization allows to prevent DMA (Direct Memory Access) requests issued from a virtual machine to tamper with unauthorized zones of the host memory.

Although these various features were introduced to facilitate the work of the hypervisor, they can also be used to carry out new kinds of attacks. An example of such an attack is presented in 3.2.

Vulnerabilities and attacks

Virtualization technologies offer new economical and technical possibilities. However, the addition of a new layer of software introduces new security concerns. Garfinkel and Rosenblum give in [START_REF] Garfinkel | When virtual is harder than real: Security challenges in virtual machine based computing environments[END_REF] a list of challenges raised by virtualisation that are discussed hereafter.

Scaling. Virtualization enables quick and easy creation of new virtual machines. Therefore, security policies of a network (setup, updates. . . ) have to be flexible enough to handle a fast increase in the number of machines.

Transience. With virtualization, machines are often added to or removed from a network. This can hinder the attempts to stabilize it. For example, if a network gets infected by a worm, it will be harder to find precisely which machines were infected and clean them up when these machines exist only during brief periods of time on the network. Similarly, infected machines or still vulnerable ones can reappear after the infection was thought to be wiped out.

Software lifecycle. The ability to restore a virtual machine into a previous state raises many security concerns. Indeed, previously patched vulnerabilities (programs flaws, deactivated services, older passwords. . . ) may reappear. Moreover, restoring a virtual machine into a previous state can allow an attacker to replay some sequences, which renders obsolete any security protocol based on the state of the machine at a given time.

Diversity. In an organization where security policies are based on the homogeneity of the machines, virtualization increases the risk of having many versions of the same system at the same time on the network.

Mobility. A virtual machine is considered like any other file on a hard drive. It can be copied and moved to another disk or another host. This feature, cited as a benefit of virtualization, also adds security constraints because guaranteeing the security of a virtual machine becomes equivalent to guaranteeing the security of every host it has been on.

Identity. Usual methods used to identify machines (like MAC addresses) are not necessarily efficient with virtual machines. Moreover, mobility increases even more the difficulties to authenticate the owner of a virtual machine (as it can be copied or moved). Data lifetime. A hypervisor able to save the state of its VMs can counter the efforts made by a guest to delete sensitive data from its memory. Indeed, there may always be a backup version of the VM containing the data.

If many of these challenges can be addressed with good use policies (for cloud computing, examples can be found in [START_REF] Alliance | Security guidance for critical areas of focus in cloud computing v3.0[END_REF]), attackers may still exploit flaws in the system to perform their attacks. The rest of this section will focus on these malicious attempts to break into a virtualized system.

Vulnerabilities

Technically, virtualization has enabled the emergence of new attack scenarios. First, a virtual machine being the equivalent of a physical machine, an attacker willing to take control over it can use the same tools in both cases. On the other hand, the addition of a virtualization layer can give an attacker new ways of subverting its target. Indeed, as shown in figure 3, for a type 2 hypervisor, vulnerabilities in the virtualization layer may allow attacks to be performed from a virtual machine against another VM, the VMM or the host operating system. The picture would be similar for a type 1 hypervisor, except that there is no host OS underneath the hypervisor, so the corresponding attack surface is also removed. If there are any system management tools, these are also considered as a potential attack vector.

VMM

Attack examples

In this part, we will describe some typical examples of attacks targeting virtualized systems or using virtualization properties to corrupt a machine.

Detecting a virtualized environment. Virtualization technologies (except paravirtualization) are supposed to provide the guest OS with an identical duplicate of a real system. Actually, this is not completely true and it is therefore possible to detect whether there is a hypervisor running underneath the OS. Such techniques are useful for both attackers and defenders. On the one hand, an attacker can check if the targeted system is virtualized and acts accordingly. On the other hand, a user willing to check the integrity of his machine can check for the presence of a hypervisor installed against his will under his OS (cf 3.2). [START_REF] Ferrie | Attacks on more virtual machine emulators[END_REF] gives some generic examples of detection. First, a hypervisor can be detected by checking the execution time of some instructions because the processing of such instructions by the VMM requires more time than when the system is not virtualized. However, such comparisons are possible only if the measurements were previously done on an identical, known to be safe system. [START_REF] Ferrie | Attacks on more virtual machine emulators[END_REF] also describes a method based on the measurements of the time needed to access the Translation Lookaside Buffers (TLB): once those buffers have been filled with some known data, calling the CPUID instruction triggers the cleaning of at least one portion of the TLB if a hypervisor trapped it. Then, by comparing the access times to the TLB measured before and after calling CPUID, one can establish the presence of a hypervisor. One advantage of this approach is that it does not require preliminary baseline measurements.

Identifying the hypervisor. Ferrie describes in [START_REF] Ferrie | Attacks on more virtual machine emulators[END_REF] the processes he used to identify with precision which of six hypervisors (VMWare, VirtualPC, Parallels, Bochs, Hydra and QEMU) was used. To do so, he used specific instructions that are not handled by some hypervisors the same way as they are on a real system (this can lead to hypervisor-specific exceptions or, on the contrary, to the absence of exception whereas some would have been raised on a real system). Among the known applied examples of such methods, we can cite RedPill9 and ScoopyDoo 10 .

Once a VMM is correctly identified, an attacker can adapt his attack scenario to the vulnerabilities known as characteristic of this VMM. Such techniques also allow the creation of viruses targeting only the systems where a specific kind of hypervisor is running. It should be noted that some of these methods allow to detect and identify various popular hypervisors. However, in most cases they are legitimately installed on a machine, so it is understandable that they do not try to hide themselves.

Breach in the isolation. One of the main goals of a hypervisor is to ensure that the hosted virtual machines are isolated, which means that one guest system is not able to reach more resources than it has been granted, especially the memory used by the other guests or by the host system. However, bad configuration or design flaws within the VMM can allow an attacker to break out of the isolation. This can lead to:

-Denial of service: A virtual machine uses all the computing capacities of the real host, preventing the other VMs from running correctly. -System halt: A specifically crafted instruction causes the VM or the hypervisor to crash -VM escape: This category covers the situations where an attacker gains access to memory located outside the region allocated to the corrupted VM. The attacker can access the memory of other systems (guest or even host) and can read, write or execute its content. This can lead to a complete takeover of another VM, of the hypervisor or of the entire host system (for a type 2 hypervisor).

VM escape documented attacks targeting Xen, VMWare and Linux KVM are respectively described in [START_REF] Wojtczuk | Subverting the Xen hypervisor[END_REF], [START_REF] Kortchinsky | Cloudburst-a vmware guest to host escape story[END_REF] and [START_REF] Elhage | Virtunoid: Breaking out of KVM[END_REF]. In these three situations, an attacker was able to run some custom code with the highest privileges and therefore took over the whole system. This kind of attacks exploits some vulnerabilities in the source code or the design of the hypervisor. In [START_REF] Ormandy | An empirical study into the security exposure to hosts of hostile virtualized environments[END_REF], random sequences of code are sent (by fuzzing techniques) to several VMMs. For every tested hypervisor, some sequences have caused a system crash. This is often the first step to discover new exploitable vulenrabilities. Moreover, the amount of code shipped with every new version of a hypervisor seems to be increasing (cf. Table 1), which raises the probability of new vulnerabilities.

Accurate targeting of VMs in a cloud. In this paragraph, we will focus on the works done by Ristenpart et al. [START_REF] Ristenpart | Hey, you, get off of my cloud: exploring information leakage in third-party compute clouds[END_REF]. Their research work consists in identifying techniques to ensure a coresidence in a public cloud (Amazon EC2 in their experiments). This means that the authors are able to obtain a VM that is hosted on the same real host as another VM they want to attack. Thanks to this co-residence, they are able to monitor some activities of the targeted VM through a covert channel.

Let us note that, in these experiments, only "legitimate" tools were used and no modification of the targeted systems has been done.

The authors started by establishing a map of the cloud: they examined how the IPs were distributed according to the characteristics of the corresponding VMs (number of cores, storage capacity, . . . ). Then, they identified several techniques for checking the co-residence between an attacker's VM and his target, first through a network analysis (if the first node is the same, or if the IPs are within a certain range, they are co-resident), then by measuring the host activity. To do so, they compared the time required for reading a given portion of the memory before and during an intense activity imposed to the target (by sending multiple requests to the targeted server). Results of this experiment are shown in figure 4. The target is a web server to which multiple HTTP get requests were periodically sent. In the first two graphs, there is a clear distinction between the activity recorded during the HTTP gets and the "standard" activity ("No HTTP gets"): the two machines are co-resident. In the third graph, no distinction can be made: two machines are not resident on the same real host.

Once that co-residence is confirmed, an attacker can obtain more information about the target activities with a similar method (by monitoring the host activity without interacting with the target) or try to take over it by other means. Virtual Machine Based Rootkits. The previously described attacks were based on some characteristic features or design flaws of the VMMs. Virtual Machine Based Rootkits (VMBRs) are different. Here, the attacker uses some features of hardware-assisted virtualization of x86 processors (cf 2.4) in order to install a hypervisor underneath the targeted OS, putting it into a virtual machine. As the attacker totally controls the hypervisor, he can monitor the whole virtualized OS. Some VMBR implementations can virtualize the OS on the fly (BluePill [START_REF] Rutkowska | Subverting vista™ kernel for fun and profit[END_REF]), others can survive a reboot (SubVirt [START_REF] King | Subvirt: Implementing malware with virtual machines[END_REF]). Finally, J. Rutkowska [START_REF] Rutkowska | Bluepilling the xen hypervisor[END_REF] and her team were able to install BluePill under Xen after subverting it from one of its VM, therefore putting the hypervisor itself into a VM (nested virtualization).

Virtualization and security

As seen previously, virtualized systems have many advantages over their physical counterparts. However, they also have their own vulnerabilities (in addition to the "traditional" vulnerabilities inherited from physical systems). Although an important portion of the threats can be prevented by following some rules (for the administrator as well as the users), an attacker may still be able to reach his goal by exploiting some flaws. Many works are therefore published in order to improve the security of virtual environments. We will describe some of them hereafter, but this list is not comprehensive. Like [START_REF] Douglas | Secure virtualization and multicore platforms state-of-the-art report[END_REF], we split up these works in two categories: VM monitoring and isolation enforcement.

VM monitoring

The hypervisor having higher privileges than the virtualized operating systems, it can be used to monitor their activities "from the outside". This section describes applied examples of this idea.

Virtual machine introspection. Virtual machine introspection (VMI) techniques are based on the ability of the hypervisor to access VM-allocated memory space in order to analyze its content from outside. Data retrieval and analyses can be done directly within the hypervisor or from a dedicated VM (which is recommended because this will require less modifications in the hypervisor code). However, the VMM has basically no knowledge of the abstractions used by the guest OS and is therefore unable to understand the meaning of the retrieved memory zones. This is the semantic gap that VMI programs have to fill. There are many VMI implementations, from frameworks (like LibVMI 11 for Xen and KVM) to entire hypervisors, according to one's needs. [START_REF] Nance | Virtual machine introspection: Observation or interference? Security & Privacy[END_REF] classifies them according to three characteristics:

-Monitoring or interfering: is the system only watching and reporting any anomaly or can it counter attacks by itself ? -Semantic awareness: the amount of knowledge the system possesses about the guest OS. For example, Lares [START_REF] Payne | Lares: An architecture for secure active monitoring using virtualization[END_REF], using hooks located into the guest system, needs a strong knowledge of this system. On the other hand, Cloudsec [START_REF] Ibrahim | Cloudsec: A security monitoring appliance for virtual machines in the IaaS cloud model[END_REF] knows nothing about the guest OS and tries to fill the semantic gap according to the gathered information. -Event replay: the ability of the system to record the state of the monitored VM for further analyses.

Kernel protection. Virtualizing an OS puts it in a less privileged state, the hypervisor getting the highest privileges. The latter can then enforce security in the OS from outside.

SecVisor [START_REF] Seshadri | Secvisor: A tiny hypervisor to provide lifetime kernel code integrity for commodity oses[END_REF] is a hypervisor designed to ensure the integrity of an OS. It is a small VMM (less than 5000 lines of code) aimed at allowing only the execution of user approved code. The design of SecVisor had to fulfill three criteria:

1. A small amount of code in order to allow a formal checking or a manual audit. 2. A minimal exterior interface in order to reduce the attack surface. 3. The lowest possible amount of changes made into the monitored kernel in order to ease portability.

SecVisor does not prevent code from being added to the kernel, although it forbids its execution unless the code has been approved by the user. To do so, SecVisor relies on hardware features (cf. 2.4) such as hardware memory protection.

The Hytux prototype [START_REF] Lacombe | Enforcing kernel constraints by hardware-assisted virtualization[END_REF], developed at LAAS, is also a lightweight hypervisor that implements protection mechanisms in a more privileged mode than the Linux kernel. It is especially designed to counter kernel rootkits, malware that aims at corrupting the kernel of operating systems.

Rootkit detection. Similarly, Patagonix [START_REF] Litty | Hypervisor support for identifying covertly executing binaries[END_REF] is a hypervisor designed to detect rootkits hiding into the monitored OS, without relying on the OS capacities. To do so, the code of the virtualized OS is tagged as non executable, which triggers an action from the hypervisor the first time this code is executed of when it has been modified from the previous execution. Then, the code is identified by comparing it with a database of known binaries. Therefore, it becomes possible to detect modified binaries or programs trying to hide their presence to the OS. By using a database to deal with the semantic gap, Patagonix can theoretically monitor any OS as long as it possesses a sufficient database of its correct binaries.

Isolation enforcement

Some other studies focus on means to prevent a breach in the isolation property. Corrupting the hypervisor (by exploiting design flaws or other vulnerabilities) is a way to break this isolation. Again, various approaches are possible to deal with this problem.

Security modules. This category contains the modules developed to provide security features into a hypervisor. For example, Xen Security Modules [START_REF] Coker | Xen Security Modules (XSM). Xen Summit[END_REF] is a framework implementing new security rules into Xen that an administrator can include while compiling it.

Another example would be sVirt 12 , which uses Mandatory Access Control (MAC) to set a stronger isolation between the VMs in Linux-based virtualization solutions (such as KVM). sVirt assigns a distinct MCS (Multi Category Security) label to each VM but gives the same label to a VM process and its corresponding VM image. Therefore, a VM process will be allowed to read and modify only its corresponding image but any access from one VM process to another or to another image will be prevented. Thus, if one VM becomes compromised, it will not be able to access other VMs (images or processes) hosted on the same computer.

Protecting the VMM. As seen in section 4.1, a hypervisor can be used to monitor the virtualized systems it is hosting. However, as seen in 3.2, the hypervisor can in turn be targeted and modified by an attack. As the hypervisor possesses every privilege on its guest systems, it is crucial to preserve its integrity. However, while it is possible to ensure the integrity of a system during boot (we can for example cite the Trusted Computing Group13 which works on this topic), it is much harder to ensure runtime integrity. So, to ensure runtime integrity, one could think of installing a second hypervisor under the initial hypervisor dedicated to monitoring it, similarly to 4.1. However, one would have to guarantee that the most privileged hypervisor cannot in turn be corrupted. Several studies have therefore focused on using other means to ensure the integrity of the most privileged element.

First, HyperSentry [START_REF] Azab | HyperSentry: enabling stealthy incontext measurement of hypervisor integrity[END_REF] aims at providing a secure environment to tools willing to enforce the integrity of the most privileged element. For that purpose, it leverages both the SMM (System Management Mode) specificities to protect its code from the hypervisor and the Trusted Boot as defined by the TCG 14 to ensure the integrity of its code at startup. Moreover, through the use of communication channels uncontrolled by the hypervisor (like IPMI15 in [START_REF] Azab | HyperSentry: enabling stealthy incontext measurement of hypervisor integrity[END_REF]), an analysis can be executed without the hypervisor noticing it. Therefore, HyperSentry can access the state of a hypervisor at a given time without making it aware of the process, theoretically preventing it from tampering with the data before it is sent to the analysis tools.

Other works, like HyperSafe [START_REF] Wang | Hypersafe: A lightweight approach to provide lifetime hypervisor control-flow integrity[END_REF], try to protect the hypervisor from modifications through the strict enforcement of certain principles. HyperSafe patches an existing hypervisor to enforce two features (memory lockdown and restricted pointer indexing) aiming at guaranteeing control flow integrity. The objective is to make the hypervisor protect itself against unwanted modifications or executions of its code. HyperSafe has already been ported on Bitvisor and (not yet completely, according to [START_REF] Wang | Hypersafe: A lightweight approach to provide lifetime hypervisor control-flow integrity[END_REF]) on Xen.

However, if such tools allow to enhance the ability of a hypervisor to protect itself, using them implies increasing the amount of code running with high privileges (since it is part of the hypervisor). Thus, any design mistake present into these modules can become an entry point for new attacks. Such an example is detailled in [START_REF] Wojtczuk | Black Hat conference[END_REF], where an attack is made possible only if the FLASK module for XSM is installed, which is not the default configuration for Xen.

Protecting the VMs against their VMM. The purpose of CloudVisor [START_REF] Zhang | Cloudvisor: Retrofitting protection of virtual machines in multi-tenant cloud with nested virtualization[END_REF] is to ensure data confidentiality and integrity for the VM, even if some elements of the virtualization system (hypervisor, management VM, another guest VM) are compromised 16 . The idea is that data belonging to a VM but accessed by something else than this VM appears encrypted. To reach its goal, CloudVisor virtualizes the monitored hypervisor (realizing nested virtualization), therefore removing the latter from the most privileged zone while still giving it the illusion of the opposite. This means that the monitored VMM is now running in guest mode while CloudVisor is the only one in root mode. Any access, requested by the VMM, to some memory belonging to a VM is then trapped by Cloud-Visor. If the access is not requested by the owner of the requested page, CloudVisor encrypts its content. Such a concept seems particularly interesting within a cloud context, where multi-tenancy (unrelated users sharing the same physical resources) can be the norm and where privacy therefore represents one of the main concerns of cloud customers.

Microkernels. Microkernels result from the will to design an operating system kernel in another way: a feature shall be allowed in kernel space only if its removal (and execution in user space) prevents the system from working correctly. Everything else is designed as user space modules, communicating between themselves through IPC (Inter Process Communication). Figure 5 (source Wikipedia17 ) shows that with such a principle, there is much less code running in kernel space in a microkernel than in a so-called monolithic kernel (such as the Linux kernel). This makes a microkernel critical code easier to audit. Conceptually, since a privileged module deals with isolation and communication between the processes running above it, microkernels are close to hypervisors. However, only the formers have a claim on minimal size. Those similarities [START_REF] Heiser | Are virtual-machine monitors microkernels done right?[END_REF] allow some microkernels to work as virtual machine managers. Among these is L4 18 for which one implementation, called seL4, was formally proven to be secure [START_REF] Klein | sel4: Formal verification of an os kernel[END_REF]. This means that seL4 is theoretically flawless (unless a flaw is found in the proof system itself, or in the underlaying layers: memory protection, context switching, hardware management, etc.). Running such a microkernel with the highest level of privileges theoretically prevents their compromission. The use of microkernels, with their smaller amount of critical code, as a basis for virtualization can also help to counter the trend of the increasing code size into some hypervisors (example with Xen in Table 1).

Removing the VMM. NoHype [START_REF] Keller | Nohype: virtualized cloud infrastructure without the virtualization[END_REF] represents yet another case. The hypervisor being a potential attack surface between two virtual machines, one solution to remove this surface is to get rid of the hypervisor. This is made possible by using hardware assisted virtualization and putting several constraints on the conditions of virtualization: each virtual machine is linked to one unique processor core, the portion of memory allowed to it is fixed and managed by the hardware (see 2.4) and each (virtual) device is dedicated to only one VM. Figure 6 gives an overview of NoHype implementation. MMC stands for Multi-core Memory Controller. It is the device dedicated to managing the allocation of memory to each core. The system manager (on the left) also runs on one dedicated core, which is the only one allowed to send IPIs (Inter Processor Interrupts) to other cores, enabling the startup, shutdown or migration of a VM on them. For example, to start a VM, the system manager prepares the required resources and sends an IPI to the core on which the VM is supposed to run. This core runs a program responsible for configuring it (by mapping the allocated resources) then starts the VM image. The effective virtualization of the guest OS is realized by a tiny hypervisor, called core manager (the little grey squares on the schema). The system manager is then able to communicate exclusively with the core managers and only to trigger the migration or termination of a VM. However, due to its design, NoHype loses some features offered by more traditional virtual machine managers, such as the ability to share resources (devices, memory buffers) between several VMs.

Conclusion

Virtualization technologies can bring many interesting new features (optimized use of hardware resources, eased restauration, machine migration, . . . ), but they also introduce new means to perform attacks. These attacks may either be directed against virtualized systems or leverage some features related to virtualization in order to take over a system. Therefore, especially if a system is shared between many users, as is the case in cloud computing, strong security of virtual machines is crucial to protect their data and gain the customer's trust. We have presented various implementations dealing with those concerns on two main topics:

-Leveraging virtualization to secure a system located on top of a hypervisor.

-Securing the VMM. This also raised issues concerning the security of the most privileged element of a system.

The research on these topics is very active today, following a great diversity of possibilities, going from devising ways to secure popular systems like Xen, KVM or VMWare solutions, to creating new models such as the microkernel-based virtualization. However, even if these solutions are satisfying security-wise, one should still consider the possible issues of their large-scale deployment. Indeed, additional control procedures will cause a decrease in efficiency. One must therefore find the right balance between performance and security, according to their needs.

Fig. 1 .Fig. 2 .

 12 Fig. 1. Type 1 hypervisor

Fig. 3 .

 3 Fig. 3. (after figure 1 from [30]) Attack surfaces on virtual machines

3 Fig. 4 .

 34 Fig. 4. (Figure 5 from [23]) Establishing co-residence in a cloud through load measurements

Fig. 5 .

 5 Fig. 5. Overview of the differences between a monolithic kernel and a microkernel

Fig. 6 .

 6 Fig. 6. NoHype architecture (excerpt from [12])

Table 1 .

 1 Amount of lines of critical code into Xen, after[START_REF] Zhang | Cloudvisor: Retrofitting protection of virtual machines in multi-tenant cloud with nested virtualization[END_REF]

	VMM Dom0 Kernel Tools Total
	Xen 2.0 45K	4,136K	26K 4,207K
	Xen 3.0 121K	4,807K	143K 5,071K
	Xen 4.0 270K	7,560K	647K 8,477K

http://en.wikipedia.org/wiki/HP_nPar_%28Hard_Partitioning%29

http://linux-vserver.org/

We will use indifferently the terms "hypervisor" and "virtual machine manager" in this paper.

http://www.intel.com/technology/itj/2006/v10i3/1-hardware/6-vt-x-vt-i-solutions.htm

http://sites.amd.com/us/business/it-solutions/virtualization/Pages/virtualization.aspx

http://invisiblethings.org/papers/redpill.html

http://www.trapkit.de/research/vmm/scoopydoo/index.html

http://code.google.com/p/vmitools/

http://www.trustedcomputinggroup.org

http://www.trustedcomputinggroup.org/resources/trusted_boot

Intelligent Platform Management Interface : http://download.intel.com/design/servers/ipmi/ IPMIv2_0rev1_0.pdf

http://en.wikipedia.org/wiki/Microkernel

Acknowledgements

This research has been partially supported by the French ANR SOP project (ANR-11-INFR-0001), and by the French project Investissements d'Avenir SVC (Secure Virtual Cloud).


J Badie

S Bak

S T Serban

F Brémond

Recovering people tracking errors using enhanced covariance-based signatures

This paper presents a new approach for tracking multiple persons in a single camera. This approach focuses on recovering tracked individuals that have been lost and are detected again, after being miss-detected (e.g. occluded) or after leaving the scene and coming back. In order to correct tracking errors, a multi-cameras re-identification method is adapted, with a real-time constraint. The proposed approach uses a highly discriminative human signature based on covariance matrix, improved using background subtraction, and a people detection confidence. The problem of linking several tracklets belonging to the same individual is also handled as a ranking problem using a learned parameter. The objective is to create clusters of tracklets describing the same individual. The evaluation is performed on PETS2009 dataset showing promising results.

Introduction

Multiple persons tracking is an important and challenging task in video surveillance and one of its extensions is reidentification. The objective of re-identification consists in linking objects throughout a network of overlapping or nonoverlapping cameras. One of the other possible extensions is to track with the same ID individuals that reappear after a long occlusion or after reentering the scene. This extension can be called re-acquisition or global tracking.

Global tracking can perform two different roles depending on the time window where it is applied. On the first hand, it can be used to correct tracking errors such as changing IDs due to long-term occlusions in a short-term point of view. On the other hand, it can be used to to track people under the same ID even if they appear several times on the same scene, for example during a day (figure 1). The proposed approach tries to answer to both of the problems with the same framework.

Considering the problem of global tracking, it is relevant to use a descriptor which is independent not only from the person's posture, position or activity but also from the characteristics of the scene, such as changing background.

Therefore, appearance model based descriptors seem suited to identify people in video surveillance. Another constraint is that each tracklet (segment of trajectory) should be represented by a discriminative enough signature. This signature (representation of the appearance) helps to link several tracklets belonging to the same person.

In the state of the art, many different appearance-based descriptors with satisfying results already exist. A global tracking approach is described in [START_REF] Chau | Repairing People Trajectories based on Point Clustering[END_REF] to correct lost trajectories thanks to learned scene semantic information. In [START_REF] Wu | Detection and Tracking of Multiple, Partially Occluded Humans by Bayesian Combination of Edgelet based Part Detectors[END_REF], a tracking method based on body parts is proposed using edgelet features. In [START_REF] Kuo | Multi-target tracking by on-line learned discriminative appearance models[END_REF], Kuo et al. present a reliable descriptor and tracklet association method. However, in the majority of cases, two problems remains unsolved : the discrimination of the visual signatures (except in [START_REF] Kuo | Multi-target tracking by on-line learned discriminative appearance models[END_REF]) and the size of the time window where the algorithm can fuse two trajectories. To summarize, the state of the art has focused more on repairing trajectory interruptions due to short-term occlusions than checking if a person has left and reentered the scene.

Mean Riemannian Covariance Grid (MRCG) descriptor [START_REF] Bak | Multipleshot Human Re-Identification by Mean Riemannian Covariance Grid[END_REF] is used in the case of re-identification on overlapping or non-overlapping cameras promising results outperforming the state of the art. However, this approach has two main limitations. The first limitation is that background pixels are also used to compute tracklet signatures. The second one is that the results are given as a list of the best match for one tracklet and not as a definitive link between two tracklets. We propose to adapt this descriptor in a single camera in a real-time situation while overcoming the limitations.

This paper makes the following contributions:

• We propose to use Mean Riemannian Covariance Grid (MRCG) descriptor for short-term error recovering and for long-term re-acquisition by linking several tracklets belonging to the same person in a real-time situation (Section 2.3) on a mono-camera system.

• We enhance the quality and the reliability of the signature using an adaptive background subtraction and a people detection confidence (Section 2.1 and 2.2).

• and for creating clusters of tracklets using an adaptive parameter that can be learned in a real-time situation (Section 2.5).

The rest of the paper is organized as follows : Section 2 presents an overview of the proposed system, the features used to compute the tracklet signatures and how the tracklets are compared, linked and clustered. In Section 3, we discuss the results of the proposed method and compare them with the state of the art approaches. Section 4 concludes and presents some future works.

Proposed approach

The architecture of the proposed system is presented in Fig. 2. It is composed of the following steps : (1) object segmentation; (2) people detection; (3) short-term tracking; (4) global tracking. The global tracking gathers the outputs from all the previous algorithms and combine them to create the signature database of all non-noisy tracklets while the short-term tracker provides short but reliable tracklets in a small time window.

This architecture is flexible enough to adapt itself to any kind of short-term tracker. The global tracker postprocesses the results of the short-term tracker by computing the tracklets signatures and choose to link (or not) the trackets.

Foreground image

We use a segmentation method based on an Extended Gaussian Mixture Model (EGMM) [START_REF] Nghiem | Controlling Background Subtraction Algorithms for Robust Object Detection[END_REF]. This method consists in detecting foreground pixels which are post-processed to remove shadows and highlights and adding a controller to adapt the background subtraction to the current scene condition. This method constructs the background representa- The background subtraction images are used as a mask to compute the foreground images (Fig. 3) and is used as an input of the global tracker.

Segmentation

People detection confidence

In some cases, foreground images do not give a satisfying result, considering they will be used to compute a visual signature. For example, if on some frames, a person is partially or totally occluded, these frames should not be used to compute the person's visual signature. In order to handle this problem, the result of the segmentation are filtered by a specific people detection method.

For people detection, we propose to generate a value representing the confidence level of each detected object to measure the accuracy of the detection. In the proposed approach, we use a LBP-based method [START_REF] Corvee | Haar like and LBP based features for face, head and people detection in video sequences[END_REF] to obtain several detection candidates (Fig. 4a) for one person. A matching score S is associated to each candidate. By adding a Mean Shift clustering algorithm to successfully group the candidates, we obtain a single bounding box representing the detected object.

Each matching score S is generated using Adaboost with a learned database. In theory, the value of S can be between 0 and 1. However, only the best candidates (S > 0.5) are selected and used to compute the confidence. Considering the average matching score S a of all the N candidates and the best matching score S b of all the candidates, the confidence C is computed using the following formula :

C = 1 - 1 -(S a + S b )/2 N (1)
This equation combines the LBP scores for human detection giving a hightest priority to the best match. The higher the confidence, the more correct the person detection (Fig. 4). The drawback of the confidence is that it is not affected if more than one person is detected at the same place. As a consequence, it cannot be used to process occlusions between several individuals because it can only guarantee that at least one person is detected.

Signature computation

The short-term tracking algorithm is performed with a multi-feature tracker [START_REF] Chau | A multi-feature tracking algorithm enabling adaptation to context variations[END_REF] using 3D position, shape, dominant color and HOG descriptors. This tracker generates short but reliable tracklets. A tracklet is represented by a set of cropped images corresponding to the tracked regions. This set of images is used to compute MRCG signature. In the proposed approach, the short-term tracker is only consider as a tracking reference whose results need to be improved.

MRCG descriptor [START_REF] Bak | Multipleshot Human Re-Identification by Mean Riemannian Covariance Grid[END_REF] is used for re-identification in overlapping or non-overlapping cameras and shows very promising results. However, the reliability of the descriptor significantly depends on the quality of the input set of images. If the detection is not correct, the quality of the computed signature can significantly drop. In the original approach, the whole bounding box of the person is used to compute the signature (Fig. 5a). In our approach, we propose to combine background subtraction as a mask to keep only foreground pixels (Fig. 5b) and the people detection confidence to eliminate inaccurate detections with a confidence below a given threshold.

By filtering the images this way, we ensure that only significant pixels are used to compute the signature and we limit the number of noisy images. However, the quality of the signature is still limited by the quality of the background subtraction algorithm and the accuracy of the people detector.

Using MRCG descriptor online in single camera requires to save several images in every frames. We propose a method working as follows : we only consider non-noisy trackets (with at least 5 frames). When the tracklet is considered as finished by the short-term tracker, we compute its signature using the foreground images corresponding to a reliable enough detection (C superior to a predefined threshold). Considering the current signature, we compute its distance with all the previously computed signatures using the distance defined in [START_REF] Bak | Multipleshot Human Re-Identification by Mean Riemannian Covariance Grid[END_REF]. At any time, the global tracker has access to the current signatures and to the signatures that were lost.

Inspired by the method described in [START_REF] Kuo | Multi-target tracking by on-line learned discriminative appearance models[END_REF], distances (d) between all the combination of signatures are computed and arranged into two categories : possible links pl and impossible links il. Two tracklets are considered impossible to be linked if they are overlapping on at least one frame. For each category, we sort the links by increasing distance to obtain a tracklet similarity ranking.

Tracklets linking

The list of possible links P L = {pl k } N k=1 and the list of impossible links IL = {il k } M k=1 contains all the distances d between every 2-combination of trackets. Only the best possible links are used as candidates to be linked. To define these best possible links, we consider the highest rank of similarity between two tracklets that are impossible to link. This number is the smallest distance in the list of impossible links IL and is used as an initial threshold :

T 1 = d(il 1 ).
Considering this threshold, The list of possible links between tracklets is refined as follows :

P L ′ = {pl k : d(pl k ) < T 1 } N ′ k=1 (2)
As defined before, the impossible link list is established online and based on a temporal constraint. The threshold T 1 is updated with a new value if new impossible links appear and therefore, all previous links are updated using the new threshold. This threshold represents the adaptive parameter of the proposed approach.

The way the threshold is defined allows us to consider that the possible links list P L ′ has a limited number of wrong links. However, we may also ignore some correct links. To increase the sensitivity of the tracklet linking algorithm, a new threshold T q is defined as follows :

T q = 1 q q k=1 d(il k ) (3)
The parameter q is set manually and represents the number of impossible links that are considered to compute the threshold. As parameter q increases, the number of correct links also increases but we have also a greater chance to accept wrong links. The threshold T q is only based on the impossible link list. Its reliability depends on the number of people that are detected in the scene at the same time and their similarity. Considering that it can be inappropriate to some sequences, it is also possible to learn the threshold in an offline phase using a database of images of different people.

Starting with the first rank P L ′ , we use a Mean Shift algorithm to create clusters of tracklets that should correspond to the same person. Considering an existing cluster of n tracklets [τ 1 , • • • , τ n ], and a possible link [τ a , τ b ], the linking condition is :

1 2n n k=1 d([τ a , τ k ]) + d([τ b , τ k ]) < T q (4)
If the linking condition is true, the possible link [τ a , τ b ] is added to the cluster. If the linking condition is wrong for all clusters and the tracklets τ a or τ b do not appear in any existing cluster, a new cluster is created with these two tracklets. Figure 6 shows an example of the linking algorithm inputs and outputs.

Experimental Results

We evaluate the effectiveness of the proposed approach using the public dataset PETS2009, on the particular sequence S2 L1, composed of 7 overlapping cameras recording 12 different people walking. This dataset is particularly relevant for the proposed approach because it contains a lot of occlusions, people that leave the scene and come back later and a number of people high enough to perform the linking algorithm without leaning the adaptive parameter with an offline leaning phase. However, the default ground truth [START_REF] Beleznai | Pedestrian detection using GPU-accelerated multiple cue computation[END_REF] shows 21 trajectories, using two different IDs to describe a person leaving and reentering in the scene. For performance evaluation, two different ground-truth data are used, a first one with 21 trajectories and a custom ground-truth with 12 trajectories taking into account the fact that people can reenter in the scene.

In order to compare the enhanced signatures with the original one, we evaluate the percentage of tracklets that 6: Linking algorithm inputs and output. The length of the output tracklet is the sum of the lengths of the inputs tracklets. In this example, the input tracklets length is between 8 and 120 frames and the output length is 348 frames. are correctly linked, incorrectly linked and not linked according to the parameter q of the equation 3. A tracklet is considered as correctly linked if it is classified in a cluster representing the same person. An incorrect link occurs when the tracklet is put in a cluster representing a different person. Finally, not linked tracklets correspond to tracklets that are not assigned to any cluster whereas they should be. Our first results in Table 1 show the effectiveness of our approach on the first camera view (View 001), in the case when the 21 ground-truth trajectories are used as tracklets. Table 2 shows the results when the tracklets are computed with the short-term tracker.

The results show that the tracklets with an enhanced signatures are more likely to be added to a correct cluster (78.9%) compared to the state of the art signatures (59.7%). The proposed approach also decreases the error rate from 12.4% to 6.5%. Some specific tracking metrics are presented in [START_REF] Bernardin | Evaluating multiple object tracking performance : the CLEAR MOT metrics[END_REF] and [START_REF] Ellis | PETS2009 and Winter-PETS 2009 results: A combined evaluation[END_REF] for PETS2009 dataset. The computation of these metrics is reported in table 3. The value of the MOTP metric is low because the tracker only focus on creating reliable trackets and will fail to create this kind of tracklets during an occlusion. However the metrics Multiple Object Tracking Accuracy (MOTA) and Multiple Object Tracking Precision (MOTP) are not really adapted with the proposed method. These metrics works as follows : if the same person is described with two different ID, it is counted as one single error, not taking into account the length of both tracklets. Considering all the other possible errors (miss-detection, tracking errors), the influence of one ID switch errors does not appear clearly on these metrics. As a matter of fact,

Metrics

MODA MODP MOTA MOTP Berclaz et al. [START_REF] Berclaz | Multiple object tracking using flow linear programming[END_REF] 0.84 0.53 0.82 0.52 Yang et al. [START_REF] Yang | Probabilistic multiple people tracking through complex situations[END_REF] 0.759 0.544 0.76 0.538 Conte et al. [START_REF] Conte | Performance Evaluation of a People Tracking System on PETS2009 Database[END_REF] 0.833 0.645 0.830 0.638 short-term tracker 0.8274 0.571 0.8271 0.327 Table 3: PETS metrics from [START_REF] Ellis | PETS2009 and Winter-PETS 2009 results: A combined evaluation[END_REF] for the tracker alone the values of these metrics are not significantly influenced enough by the proposed error recovering method. One solution to improve these metrics would have been to reconstruct the trajectory during the interval between two IDs of the same person using a trajectory optimization algorithm.

In order to evaluate successfully the performance of the proposed method, we use other evaluation metrics described in [START_REF] Wu | Detection and Tracking of Multiple, Partially Occluded Humans by Bayesian Combination of Edgelet based Part Detectors[END_REF]. These metrics, implemented in the evaluation framework ViSEvAL [1], rely on :

• Mostly Tracked trajectories (MT) when more than 70% of the trajectory is tracked

• Partially Tracked trajectories (PT) when between 20% and 70% of the trajectory is tracked

• Mostly Lost trajectories (ML) when less than 20% the trajectory is tracked) [START_REF] Chau | Robust Mobile Object Tracking Based on Multiple Feature Similarity and Trajectory Filtering[END_REF], the global tracker sightly improves the results of the short-term tracker. The results shows that some tracklets can be merged after an occlusion. The tracklets of the Kalman filter based tracker are not used as an input for the global tracker because they are not reliable enough compared to the ones provided by the short-term tracker. Table 5 shows the results using the custom ground-truth including 12 trajectories. In this case, people leaving and reentering the scene are considered as the same person. It is normal that trackers [START_REF] Chau | A multi-feature tracking algorithm enabling adaptation to context variations[END_REF] and [START_REF] Chau | Robust Mobile Object Tracking Based on Multiple Feature Similarity and Trajectory Filtering[END_REF] have only a small percentage of MT (8.3% and 0%). However, the proposed global tracker significantly improves this per- centage up to 33.3% when q = 1 and up to 50% when q = 10.

Conclusions

In this paper we have presented a new approach for recovering errors using a global tracking method based on an enhanced appearance signature and a new strategy for linking tracklets. It has been shown that by using background subtraction and people detection confidence, we significantly improve the quality and the reliability of the results on PETS2009 dataset, while keeping a low level of error. Transforming the initial ranking problem into a decision problem is also performed using an adaptive parame-6 ter. However, even if the proposed approach is independent from the tracker, it is still dependent of the quality of the segmentation and of the people detection algorithm. In an online situation, for example video surveillance in an airport, storing numerous signatures might also be a problem. However, since the descriptor is based on appearance, the signature database life span would not exceed one day.

In future work, we will focus on building a more complex tracklet signature, using the different positions and postures of the person. Online real-time evaluation of the global tracker will also be used to automatically tune the parameter q depending on the situation. As written in the last section, a trajectory optimization algorithm will also be implemented to improve the tracking metrics results.

Figure 1 :

 1 Figure 1: The global tracking challenge : correcting errors due to occlusions (ID 142 on the first frame becomes 147 on the last frame) and track people that are levaing the scene and reentering (ID 133 on the first frame becomes 151 on the last frame)

Figure 2 :

 2 Figure 2: System architecture

Figure 3 :

 3 Figure 3: Foreground image with in green the contours

  (a) (b) C = 0.95 (c) C = 0.85 (d) C = 0.77

Figure 4 :

 4 Figure 4: Confidence computation : (a) set of candidates for one person; (b) : a perfectly detected individual with a high confidence; (c) : an uncertain detection with an average confidence ; (d) : a bad detection with a low confidence due to occlusion.

3

 3

Figure 5 :

 5 Figure 5: Input images to compute MRCG signature. (a) : original approach; (b) : our approach

4

 4

Figure

  Figure6: Linking algorithm inputs and output. The length of the output tracklet is the sum of the lengths of the inputs tracklets. In this example, the input tracklets length is between 8 and 120 frames and the output length is 348 frames.

Table 4

 4 shows the results using the original ground-truth including 21 trajectories. In this case, only occlusions or

	5

Table 2 :

 2 Global tracker re-acquisition rate based on the short-term tracker for the sequence S2.L1. from PETS2009. The number of tracklets corresponds to how many tracklets are used to compute the signatures. In the proposed approach, the confidence is used to filter the noisy tracklets.

	Method	q	MT	PT	ML
	D. P. Chau et al. [8]	-14.3% 57.1% 28.6%
	short-term tracker	-	9.5% 57.1% 33.3%
	short-term tracker +	1	19%	61.9%	19%
	global tracker	10 23.8% 57.1%	19%

Table 4 :

 4 Tracking performance on PETS2009 S2.L1 View 001 sequence using the original ground-truth with 21 trajectories

miss-detections can interrupt a tracklet. Although the shortterm tracker used is not better than a state of the art tracker based on OpenCV Kalman filter

Table 5 :

 5 Tracking performance on PETS2009 S2.L1 View 001 sequence using the custom ground-truth with 12 trajectories

	Method	q	MT	PT	ML
	D. P. Chau et al. [8]	-	8.3% 58.3% 33.3%
	short-term tracker	-	0%	41.7% 58.3%
	short-term tracker +	1 33.3% 41.7%	25%
	global tracker	10	50%	33.3% 16.7%

Acknowledgments

This work has been supported by the Conseil Regional of Provence-Alpes-Cote d'Azur (PACA).


Clément Pira
email: pira@laas.fr

Christian Artigues
email: artigues@laas.fr

An efficient best response heuristic for a non-preemptive strictly periodic scheduling problem

Keywords: Periodic scheduling, equilibrium, twodimensional optimization

An efficient best response heuristic for a non-preemptive strictly periodic scheduling problem

Problem and method

We consider a periodic scheduling problem introduced in [4, [START_REF] Eisenbrand | Solving an Avionics Real-Time Scheduling Problem by Advanced IP-Methods[END_REF][START_REF] Sheikh | Resource allocation in hard real-time avionic systems -Scheduling and routing problems[END_REF][START_REF] Sheikh | Strictly periodic scheduling in IMA-based architectures[END_REF]. Such a problem arises in the avionic field, where a set of N periodic tasks (measure of a sensor, etc.) has to be scheduled on P processors distributed on the plane. In this problem, each task i has a fixed period T i which cannot be modified. A solution is given by an assignment of the tasks to the processors and, for each task by the start time t i of one of its occurrences. Each task has a processing time p i and no two tasks assigned to the same processor can overlap during any time period. In this paper, we adopt a more general model in which processing times p i are generalized by positive latency delays l i,j ≥ 0 (or time lags). The former case is the particular case where l i,j = p i for all other tasks j. The proposed heuristic does not suffer from this generalization even if some simplification occurs in the case of processing times (see section 2.5).

In this paper, we only consider the case where the offsets t i are integers. Since the problem is periodic, all the periods T i also need to be integers. We will see in section 1.2 why this hypothesis is important to prove convergence of the method. Note that the latency delays need not be integer a priori, especially in the case of the optimization problem presented in section 1.1.

Problem definition

Non-overlapping constraints We first focus on the monoprocessor problem. In the formulation of a periodic scheduling problem, we want to constrain all the occurrences of j with respect to all the one of i. More precisely, we want a latency delay l i,j ≥ 0 to be respected whenever an occurrence of j starts after an occurrence of i. Say differently, we want the smallest positive difference between an occurrence of j and an occurrence of i to be greater than l i,j . The set of occurrences of i is t i + T i Z, while the set of occurrences of j is t j + T j Z. When doing the difference, and using Bézout identity, we obtain that the set of possible differences is (t j -t i ) + g i,j Z where g i,j = gcd(T i , T j ). The smallest positive representative of this set is (t j -t i ) mod g i,j . Therefore, the constraint we want to pose is simply :

(t j -t i ) mod g i,j ≥ l i,j , ∀(i, j) ∈ G (1)
The modulo is defined here as the only representative of (t j -t i ) + g i,j Z which belongs to [0, g i,j -1] (in particular, we consider a classic positive modulo, and not a signed modulo like in some programming languages). The graph G involved in constraint [START_REF] Sheikh | Resource allocation in hard real-time avionic systems -Scheduling and routing problems[END_REF] contains the arcs (i, j) for which l i,j > 0 (since otherwise the equation is trivially satisfied).

Objective to maximize In a context of robustness, it could be natural to maximize the feasibility of the system. More concretely, we want an execution of a task to be as far as possible from every other executions of another task which precedes or follows it. We could imagine that a task lasts longer than expected, due to failure of the processor. This increase in the duration is naturally proportional to the original processing time. Hence, we make all the delays l i,j proportional to a common factor α ≥ 0 that we try to optimize (see [START_REF] Sheikh | Resource allocation in hard real-time avionic systems -Scheduling and routing problems[END_REF][START_REF] Sheikh | Strictly periodic scheduling in IMA-based architectures[END_REF]).

max α (2)
s.t. (t j -t i ) mod g i,j ≥ l i,j α ∀(i, j) ∈ G (3) t i ∈ Z ∀i (4) α ≥ 0 (5)
We easily check that a schedule is feasible for the feasibility problem iff the optimization problem has a solution with α ≥ 1. Hence, this optimization problem can be interesting simply to find feasible solutions. Given the offsets (t i ) we can always compute the best compatible α :

α = min (i,j)∈G (t j -t i ) mod g i,j l i,j (6)
This shows that an optimal solution is completely defined by the offsets. The following proposition allows to define an upper bound : Proposition 1. Let (i, j) ∈ G. A necessary condition for this problem to be feasible is ⌈l i,j α⌉ + ⌈l j,i α⌉ ≤ g i,j . This is equivalent to α ≤ α i,j max where :

α i,j max = g i,j /l i,j if l j,i = 0 max 1 li,j gi,j li,j +lj,i l i,j , 1 lj,i gi,j li,j +lj,i l j,i if l j,i > 0
We deduce that α max = min (i,j) α i,j max is an upper bound on the value of α. Proof. Since the offsets are integers, we have ⌈l i,j α⌉ ≤ (t j -t i ) mod g i,j and ⌈l j,i α⌉ ≤ (t i -t j ) mod g i,j . Summing this two inequalities, we get ⌈l i,j α⌉ + ⌈l j,i α⌉ ≤ g i,j . Let α i,j max be the largest α-value satisfying this condition : α i,j max = max {α | ⌈l i,j α⌉ + ⌈l j,i α⌉ ≤ g i,j }. If l j,i = 0, we have α i,j max ≤ g i,j /l i,j . Otherwise, we easily see that we have either l i,j α i,j max ∈ N or l j,i α i,j max ∈ N. Suppose l i,j α i,j max = n ∈ Z. Then n is the largest integer such that n+⌈nl j,i /l i,j ⌉ ≤ g i,j , i.e. nl j,i /l i,j ≤ g i,j -n, i.e. n ≤ g i,j l i,j /(l i,j + l j,i ). Therefore n = ⌊g i,j l i,j /(l i,j + l j,i )⌋.

⊓ ⊔ Remark 1. This necessary condition is stronger than l i,j α + l j,i α ≤ g i,j , hence the upper bound is tighter than min (i,j) gi,j li,j +lj,i which is the upper bound in the fractional case.

A word on zero delays Classically, processing times are strictly positive. However our model allows zero delays, which amounts to introduce an additional graph G. Very often, the constraints associated with (i, j) and (j, i) work together and some complications are introduced when only one of the couples belongs to the graph i.e. only one of the delay is strictly positive (see for example proposition 1). In the following we will suppose that the graph is symetric. Since G is symetric, it can be seen as an undirected graph. We will write G(i) for the set of neighbors of i, i.e. the set of tasks with which i is constrained. This hypothesis is justified by the following proposition : Proposition 2. We can always suppose the graph G to be symetric, i.e. the delays l i,j and l j,i to be either both zero or both strictly positive, possibly by replacing a zero delay by 1/α max .

Proof. Suppose l i,j > 0, but l j,i = 0. We consider a new program in which l j,i as been updated to be 1/α max . This new program is stronger hence a solution of this program is a solution of the original. Conversely, let ((t i ), α) be a solution of the original. If α = 0, then this is trivially a solution to the new program. Otherwise α > 0. In this case, we have (t j -t i ) mod g i,j ≥ l i,j α > 0. Therefore using proposition 3, we get (t i -t j ) mod g i,j ≥ 1 ≥ α/α max and so we have a solution to the new program.

⊓ ⊔

A consequence of proposition 3 is that instead of considering equation (3) for each couple (i, j) ∈ G, we can consider the following equation for each couple (i, j) ∈ G with i < j :

l i,j α ≤ (t j -t i ) mod g i,j ≤ g i,j -l j,i α, ∀(i, j) ∈ G, i < j (7)

An equilibrium-based heuristic

The best response method The main component of the algorithm is called the best response procedure. It takes its name from a game theory analogy. Each task is seen as an agent which tries to optimize its own offset, while the other offsets are fixed. Therefore, those other offsets are put in the RHS of the problem. Moreover, the agent only takes into account the constraints in which it is involved, i.e. only the constraints associated with its neighborhood G(i).

Hence, the agent i solves the following program (BR i ) :

(BR i ) max α (8) s.t. l j,i α ≤ (t i -t j ) mod g i,j ≤ g i,j -l i,j α ∀j ∈ G(i) (9) t i ∈ Z (10) α ≥ 0 (11)
The concept of equilibrium and principle of the method to find one Definition 1. A solution (t i ) is an equilibrium iff for each task i, t i is an optimal offset for the program (BR i ).

In the following, we will say that a task i is stable if the current offset t i is optimal for (BR i ). Therefore an equilibrium is exactly a solution (t i ) such that all the tasks are stable. The heuristic uses a counter N stab to count the number of tasks known to be stable. It starts with an initial solution (for example randomly generated) and tries to improves this solution by a succession of unilateral optimizations. On each round, we choose cyclically a task i and try to optimize its schedule, i.e. we solve (BR i ). If no improvement was found, then one more task is stable, otherwise we update and reinitialize the counter of stable tasks. We continue until N tasks are stable. This is summarized in Algorithm 1. We refer to [START_REF] Sheikh | Resource allocation in hard real-time avionic systems -Scheduling and routing problems[END_REF] for the proof of termination and correction.

Remark 2. The choice to search for integral offsets has some drawback, in particular when we are interested by a MILP resolution. However, the main reason for the use of integers is that it allows to guarantee the convergence of the heuristic. The termination proof relies on the fact that there is only a finite number of possible values for α. This is not the case with fractional offsets, and indeed, it is not hard to see that in this case, the heuristic has only a few chances to converge in a finite number of steps.

The best response procedure

Since the offsets are integer, and since the problem is periodic, we can always impose t i to belong to {0, • • • , T i -1}. Therefore we can trivially solve the best response program (BR i ) by computing the α-value for each t i ∈ {0, • • • , T i -1}, using expression (6), and select the best offset. This procedure runs in O(T i N ), hence any method should at least be faster. In [START_REF] Sheikh | Resource allocation in hard real-time avionic systems -Scheduling and routing problems[END_REF], the authors propose a method Algorithm 1 The heuristic 1: procedure ImproveSolution((tj)j∈I ) 2:

N stab ← 0 ⊲ The number of stabilized tasks 3:

i ← 0 ⊲ The task currently optimized 4:

while N stab < N do ⊲ We run until all the tasks are stable 5:

(newti, αi) ← BestResponse(i, (tj)j∈I ) ⊲ We optimize the task i 6:

if newti = ti then ⊲ We do not have a strict improvement 7:

N stab ← N stab + 1 ⊲ One more task is stable 8: α ← min(αi, α) 9:
else ⊲ We have a strict improvement 10:

ti ← newti 11:

N stab ← 1 ⊲ We restart counting the stabilized tasks 12:

α ← αi 13:

end if 14:

i ← (i + 1) mod N ⊲ We consider the next task 15:

end while 16:

return (α, (tj)j∈I ) 17: end procedure consisting in precomputing a set of intersection points (in the next section we will see that a fractional optimum is at the intersection of an increasing and a decreasing line). Then, they compute the α-value for each of these intersection points and select the best offset. In the following, we present a method which greatly improves (BR i ) solving.

Structure of the solution set of (BR i )

Each task i is linked with all the tasks j ∈ G(i) through non-overlapping constraints. We want to describe the shape of the set of solutions (t i , α) for the problem (BR i ), given some fixed offsets (t j ) j∈G(i) . If we try to draw the function α = (t i -t j ) mod g i,j /l j,i representing the optimal value of α respecting constraint (t i -t j ) mod g i,j ≥ l j,i α when t i takes rational values, we obtain a curve which is piecewise increasing and discontinuous since it becomes zero on t j + g i,j Z. In the same way, if we draw α = (t j -t i ) mod g i,j /l i,j , we obtain a curve which is piecewise decreasing and becomes zero at the same points. It is therefore more natural to consider the two constraints jointly, i.e. (7), which gives a continuous curve (see Figure 2). Note that if G was not symetric, we would need to consider some degenerate cases were one of the slope (increasing or decreasing) would be infinite (since l i,j = 0 or l j,i = 0).

The set of solutions for all the constraints is the intersection of the curves decribed above for each j ∈ G(i) (see Figure 3). Hence, the solution set is composed of several adjacent polyhedra. We can give an upper bound on the number n poly of such polyhedra. A polyhedron starts and ends at zero points. For a given constraint j, there is T i /g i,j zero points in [0, T i -1], hence n poly is bounded by T i j =i 1 gi,j . This upper bound can be reached when the offsets are fractional, since in this case, we can always choose the offsets t j such that the sets of zero Fig. 2. Possible values for (ti, α) when constrained by a single task j points (t j + g i,j Z) j∈G(i) are all disjoint. In the case of integer offsets, there is obvioulsy at most T i zero points in the interval [0, T i -1] and therefore, at most T i polyhedra.

Local (two dimensional) polyhedron

We want to compute the local polyhedron which contains a reference offset t * i . Locally, the constraint (t i -t j ) mod g i,j ≥ l j,i α is linear, of the form t i -o j ≥ l j,i α.

Here, o j is the largest x ≤ t * i such that (x -t j ) mod g i,j = 0. In the same way, we can compute the decreasing constraint o ′ j -t i ≥ l i,j α. In this case o ′ j is the smallest x ≥ t * i such that (o ′ j -x) mod g i,j = 0. By proposition 4, we have : Therefore, we obtain a local polyhedron (see figure 4). Note that when (t * it j ) mod g i,j > 0, we simply have o ′ j = o j + g i,j by proposition 3. However, when (t * i -t j ) mod g i,j = 0, we have o j = o ′ j = t * i . In this case, the polyhedron is degenerate since it contains only {t * i }, and the α-value at t * i is zero. Instead of computing this polyhedron, we prefer to choose either the polyhedron on the right, or on the left (see figure 5). If we choose the one on the right, this amounts to defining o ′ j to be the smallest x > t * i which annulates the constraint. By proposition 4, we have o ′ i,j = t * i + g i,j -(t * i -t j ) mod g i,j . Therefore, this simply amounts to enforcing o ′ j = o j + g i,j . Choosing the polyhedron on the left amounts to defining o ′ j using (12) and to enforcing o j = o ′ j -g i,j . Once the local polyhedron has been defined, the problem is now to solve the following MILP :

o j = t * i -(t * i -t j ) mod g i,j and o ′ j = t * i + (t j -t * i ) mod g i,j (12)
(Loc-BR i ) max α (13) s.t. t i -l j,i α ≥ o j ∀j ∈ G(i) (14)
t i + l i,j α ≤ o ′ j ∀j ∈ G(i) (15)
t i ∈ Z (16)

Solving the local best response problem

We now need a method to solve efficiently the program (Loc-BR i ). Even if we are interested in integer offsets, we can first search for a fractional solution, and for this we can use any available method of linear programming. However, since the problem is a particular two dimensional program, we can give special implementations of these methods. Most of them (primal or dual simplex) run in O(N 2 ), but Megiddo algorithm [START_REF] Megiddo | Linear-Time Algorithms for Linear Programming in R 3 and Related Problems[END_REF] allows to find such a solution in O(N ). Once a fractional solution has been found, we can round it to the closest smaller and larger integers, compute the α-value associated with these two offsets (using expression (6)), and select the best one. Since the additional computation of the two α-values runs in O(N ), this gives immediately a method to compute an integer solution in O(N ). In practice however, Megiddo algorithm is outperformed by the dual simplex method presented below, at least for the sizes of instances we considered. In fact, the integrality assumption allows to improve the dual simplex algorithm and obtain a complexity in O(N W ) where W is the width of the polyhedron. This is enough to give an acceptable complexity in O(T i N ) for the global best response problem (described in section 2.4). Hence, the O(N 2 ) complexity of the dual simplex approach is not penalizing.

A subroutine to determine the constraint active at a given point Given an offset x ref , expression (6) allows to compute the best compatible α-value, say α ref .

Once the local polyhedron (on the right) has been computed, this value can be defined by α ref = min(α inc , α dec ) with :

α inc = min j∈G(i) x ref -o j l j,i and
α dec = min j∈G(i) o ′ j -x ref l i,j (17)
Here, we distinguish the use of increasing and decreasing constraints. At the point (x ref , α inc ), at least one increasing line with equation x -o j = αl j,i is active (i.e. pass through (x ref , α inc )). Hence, the slope of this line is given by l -1 j,i . Among all the active constraints of this form, we are interested by the one with the smallest slope i.e. the largest delay l j,i . In the same way, at the point (x ref , α dec ), at least one decreasing constraint is active. We can compute the decreasing line with equation o ′ k -x = αl i,k which pass through (x ref , α dec ) and which has the largest slope (since this slope is negative, this is the one which is the most close to 0). As this slope is given by -1/l i,k , we select the line with the largest l i,k . Since α ref = min(α inc , α dec ), there are three possibilities, as shown in Figure 6 : derivative on the left is given by 1/l j,i while the derivative on the right is given by -1/l k,i . In this case, x ref is the optimum.

In the following, we synthetize the previous computation into a function which returns a tuple (d, α, j inc , j dec ), where α is the value at x ref , and j inc and j dec are respectively the indices of the selected increasing and decreasing lines. We call this function ValueAndDerivative (see Algorithm 2) since it returns both the value and informations on the slope of the active line. The field d can take value in {-1, 0, 1} and indicate where should be searched the optimum. If d = 1 is returned, we are on the increasing line having equation x-o jinc = αl jinc,i and the optimum should be searched on the right. If d = -1 is returned, we are on the decreasing line having equation o ′ j dec -x = αl i,j dec and the optimum should be searched on the left. Finally, if 0 is returned, we are at the intersection of the two lines which is the optimum. This procedure trivially runs in O(N ). Remark 3. Since the procedure tells us where to search for the optimum, we easily deduce a dichotomous procedure which solves problem (Loc-BR i ) and which runs in O(N log(W )) where W is the width of the polyhedron 1 .

A dual simplex approach We present a dual simplex approach. As we will see, this seems to be a primal approach since we traverse the vertices of the Algorithm 2 A routine to compute the α-value and the active line

1: procedure ValueAndDerivative(x ref ) 2: αinc ← ∞; α dec ← ∞ 3:
for all j ∈ G(i) do 4:

α ← (x ref -oj)/lj,i ⊲ Or directly α ← (x ref -tj) mod gi,j/lj,i 5:

if α < αinc or (α = αinc and lj,i > lj inc ,i) then αinc ← α; jinc ← j 6:

α ← (o ′ j -x ref )/li,j ⊲ Or directly α ← (gi,j -(x ref -tj) mod gi,j)/li,j 7:

if α < α dec or (α = α dec and li,j > li,j dec ) then α dec ← α; j dec ← j 8:

end for 9:

if αinc > α dec then return (-1, α dec , jinc, j dec ) 10:

if αinc < α dec then return (1, αinc, jinc, j dec ) 11:

return (0, αinc, jinc, j dec ) 12: end procedure polyhedron (see Figure 8). However we apply the dual simplex not on problem (BR i ) but on its dual which is in standard form. We find unnecessary to present the primal simplex approach which is illustrated on Figure 7. We first describe an algorithm to find a fractional solution. We will present some modifications afterward in order to return an integral solution. Let x frac be the variable intended to contain the offset of the fractional solution. In order to initialize the algorithm we start with x frac = t i , where t i is the current offset of the task i. We will try to find the best value in the local polyhedron containing x frac . Using Algorithm 2, we can compute the associated α-value α min , as well as the 'derivative', i.e. the slope of an active line (see Figure 6). If we are both on an increasing and a decreasing line, we know that we are at the optimum, we return the solution (t i , α min ). Otherwise the active line is either increasing or decreasing. In the following, we will suppose that we are on an increasing line, say with equation x -o = αl. Hence, in order to reach the optimum, we will traverse the vertices of the polyhedron in the right direction (see Figure 8). In order to determine the next vertex, we first compute intersections of the active line with decreasing lines having equation o ′ i,k -x = αl i,k . Such an intersection point has the following coordinates :

α = o ′ k -o l + l i,k and x = lo ′ k + l i,k o l + l i,k (18)
We keep the one with the smallest α-value (see figure 9). In the same way, we also search for intersections of the active line with other increasing lines having equation x -o j = αl j,i . The coordinates are given by : Among the increasing lines, we are only interested with lines having a strictly smaller slope, i.e. a strictly greater delay l j,i > l2 . At the end, we have an intersection point (see figure 10) which becomes our new fractional solution (x frac , α frac ). Note that in the above computation, only the α-coordinate is needed since the x-coordinate of the selected intersection point can be computed afterward by x = o + αl. We now proceed following one of the two alternatives : A1 If we fail to find an intersection point of the second kind (with an increasing line) with a better value, this means the selected point (x frac , α frac ) correspond to the intersection of an increasing and a decreasing line. Therefore, this is the fractional optimum (see Figure 12), hence the procedure ends. A2 Otherwise, we are not at the fractional optimum. The line which is involved in the intersection is increasing, with equation x -o j = αl j,i . We take this line as the new active line, i.e. we set o = o j and l = l j,i , and we restart at the point where we search for intersection points (see Figure 11). If the minimum is reached with several increasing lines, we can take the line with the smallest slope, i.e. the largest l j,i . A phase involves the computation of up to 2N intersection points. At each phase, the slope of the active increasing line strictly decreases (i.e. the delay l increases). Therefore, the number of phases is bounded by the number of distinct delays (itself bounded by N ), which gives a complexity in O(N 2 ). This gives us a method to compute an integral solution in O(N 2 ) since once we have a fractional solution, we can deduce an integral solution with an additional computation in O(N ). Indeed, if x is integer, then (x, α) is the desired solution. Otherwise we can compute the α-values α -and α + associated with ⌊x⌋ and ⌈x⌉ and take the largest one. Note that since ⌊x⌋ (resp. ⌈x⌉) is on the increasing phase (resp. decreasing phase), only the corresponding constraints are needed to compute α - (resp. α + ) :

α = o -o j l j,i -l and x = ol j,i -o j l l j,i -l (19)
α -= min k∈G(i) (⌊x⌋ -o k )/l k,i and α + = min k∈G(i) (o ′ k -⌈x⌉)/l i,k (20)
Improvement due to integrality assumption Instead of computing the value α -at the end, we can compute this value during the algorithm. For this, it is possible to maintain a variable x int representing the current best integral solution, and α int representing its value. Another problem with the dual simplex procedure is that between two integer offsets, there is possibly several intermediary intersection points. In order to skip this unnecessary points, we modify alternative A2 as follow :

A2' Since A1 didn't occur, we know that we are not at the fractional optimum. However it is still possible that the fractional optimum belongs to (x int , x int + 1]. In order to test this, we use procedure ValueAndDerivative to compute the value α ′ associated with x int + 1, and the active line at this point. If a decreasing line is active, this means we passed the fractional optimum. In this case, we also return the optimal solution which is the best solution among (x int , α int ) and (x int + 1, α ′ ). Otherwise, only an increasing line is active at x int + 1. We redefine x -o = αl to the the equation of this line. We update (x frac , α frac ) = (x int + 1, α ′ ) and we restart at the point were we search for intersection points.

With this modification, x int is garanteed to increase by one on each round. This allows to obtain a complexity in O(N W ) where W is the width of the polyhedron.

Solving the best response problem

We now have all the elements to describe the procedure which solves (BR i ). We saw that t i can be supposed to belong to {0, • • • , T i -1}. More generally we can start at any initial offset x and run on the right until we reach the offset x + T i -1, hence we obtain a solution

t i ∈ {x, • • • , x + T i -1}. If needed, we can consider t i mod T i which is an equivalent solution in {0, • • • , T i -1}.
Following the idea described in section 2.2, we can compute the local polyhedron (on the right) which contains the current reference offset. Using the dual simplex method presented in 2.3, we solve the associated problem (Loc-BR i ). If the local optimum is better than the current solution, we update. We now want to go to the next polyhedron. At the local optimum, there are two active lines, an increasing one with equation x-o j = l j,i α and a decreasing one with equation o ′ k -x = l i,k α. Since the procedure runs from left to right, we follow the decreasing line until we reach the x-axis, i.e. the offset o ′ k . We can use this point as the new reference point. We continue until the period has been traversed. This method is illustrated on Figure 13. If we use Megiddo algorithm to solve the local problems, this best response algorithm runs in O(n poly N ) and we saw that in the integral case, n poly is bounded by T i . If we use the dual simplex adapted for the integral case, we have a complexity in O(T i N ) since the complexity on each polyhedron is proportional to its width. Note that in practice, a lot of polyhedra are skipped (see grey polyhedra in Figure 13).

Some possible improvements

The case of processing times In the case of processing times, no such refinement as Megiddo algorithm is needed in order to obtain a complexity in O(N ). Indeed, in this case, we have l i,j = p i . Since the delays l i,j gives the slope of the decreasing lines, this implies that all of them have the same slope -1/p i . Thus, even if initially there are N decreasing lines with equations o ′ j -x = αp i , we can remove all of them except one : the one with the smallest o ′ j . Once this decreasing line is selected, we compute the intersection points with the N increasing lines (having equation x -o j = αp j ), and we select the one with the smallest α-value. In order to jump over more polyhedra, it is also more interesting to run from right to left (see Figure 14). Finding the next polyhedron Suppose that after a local optimization, the current best solution t i has value α min . This becomes a lower bound for the optimal value and we are only interested by polyhedra which could improve it. However if α min is a good value, most of the polyhedra will lie completely below this level. Therefore, once a local optimum has been reached, it is possible to add a propagation mechanism which allows to skip more polyhedra by finding the smallest offset strictly greater than t i with an α-value strictly greater than α min . Instead of starting again at o ′ k (which has a zero α-value), as described in section 2.4, we start at this new offset. Then, we are sure to improve the α-value.

3 The multiprocessor problem 3.1 Definition and method MILP formulation of the multiprocessor problem In the multiprocessor case, the scheduling problem is coupled with an assignment problem. In order to define a MILP, we introduce binary variables a i,k which indicate if a task i is assigned to a processor k, and variables x i,j which indicate if i and j are on different processors. These variables must satisfy ( 22) and ( 23). For a given couple (i, j) ∈ G, with i < j, the non-overlapping constraint (7) can be rewritten, using an additional 'quotient variable' q i,j , as l i,j α ≤ t j -t i +g i,j q i,j ≤ g i,j -l j,i α.

Since it has to be satisfied whenever the two tasks are on the same processor, this yields constraints (24) and (25).

max α (21) k a i,k = 1 ∀i (22) x i,j ≤ 2 -a i,k -a j,k ∀k, ∀(i, j) ∈ G, i < j (23)
t j -t i + g i,j q i,j ≥ l i,j α -α max l i,j x i,j ∀(i, j) ∈ G, i < j (24)

t j -t i + g i,j q i,j ≤ g i,j -l j,i α + α max l j,i x i,j ∀(i, j) ∈ G, i < j (25) t i ∈ Z ∩ [0, T i -1] ∀i (26)
q i,j ∈ Z ∩ [1 -T j /g i,j , T i /g i,j ] ∀(i, j) ∈ G, i < j (27) x i,j ∈ [0, 1]
∀(i, j) ∈ G, i < j (28)

a i,k ∈ {0, 1} ∀k, ∀i (29)
In the multiprocessor case, α max cannot be defined by min i,j α i,j max as in proposition 1, since it corresponds to the worst case where all the tasks are on the same processor. Instead, we can use α max = max i,j α i,j max . However, since α max is used as a 'big-M', we try to find its lowest possible value in order to improve the efficiency of the model. For this, we solve a preliminary model in which constraints (24-27) are replaced by the following weaker constraint :

α ≤ α i,j max + α max x i,j , ∀(i, j) ∈ G, i < j (30)
The resolution of this model is much faster than for the original one (less that 1s for the instances considered in the results). It gives us a new value α max which can be used in the original model.

Multiprocessor best-response

The adaptation of the heuristic to the multiprocessor case is quite simple. On each phase, a task is optimized and its offset and assignment are changed accordingly. In order to solve the multiprocessor best response, we solve the best response on each processor and move the task on the processor which gives the best result.

Results

We test the method on non-harmonic instances, the same which were used in [START_REF] Sheikh | Resource allocation in hard real-time avionic systems -Scheduling and routing problems[END_REF][START_REF] Sheikh | Strictly periodic scheduling in IMA-based architectures[END_REF]. These instances were generated using the procedure described in [START_REF] Eisenbrand | Solving an Avionics Real-Time Scheduling Problem by Advanced IP-Methods[END_REF] : the periods were choosen in the set {2 x 3 y 50 | x ∈ [0, 4], y ∈ [0, 3]} and the processing times were generated following an exponential distribution and averaging at about 20% of the period of the task. The results on 25 instances with N = 20 tasks and P = 4 processors are presented in Table 1.

MILP (200s)

Original heuristic [START_REF] Sheikh | Strictly periodic scheduling in IMA-based architectures[END_REF] 1. Results of the MILP, the heuristic of [START_REF] Sheikh | Resource allocation in hard real-time avionic systems -Scheduling and routing problems[END_REF], and the new version of the heuristic Columns 2 and 3 give the results of the MILP formulation. One advantage of the MILP over the heuristic could be that it gives a proof of optimality. However, it is rarely the case even with 1h of CPU time (optimality could only be proved for instances 5 and 9 in 7s and 20s, respectively). Therefore, we fix a timeout of 200s. α MILP represents the best solution found during this time, and time sol the time needed to find it. Table 1 also includes results about the original heuristic presented in [START_REF] Sheikh | Resource allocation in hard real-time avionic systems -Scheduling and routing problems[END_REF][START_REF] Sheikh | Strictly periodic scheduling in IMA-based architectures[END_REF] (columns 4-7). Here, time single is the time needed for a single run of the heuristic. In the results presented in [START_REF] Sheikh | Resource allocation in hard real-time avionic systems -Scheduling and routing problems[END_REF][START_REF] Sheikh | Strictly periodic scheduling in IMA-based architectures[END_REF], the heuristic was started several times with different initial solutions until a bayesian test was satisfied, which gives a value time stop . In order to compare with our version of the heuristic, we add a column starts 2s = 2/time single which measures the average number of starts performed by the original heuristic in 2s. Table 1 also includes the results for our version of the heuristic, called the new heuristic (columns 8-11). The results of the original heuristic show that on a lot of instances, it stops with a solution which is far from the best solution found by the MILP. Therefore, for the new heuristic, we abandoned the bayesian test and we simply run the heuristic during 2s. The value start 2s is the number of times the heuristic was started during this time. We immediately see that this number is much greater that the equivalent number for the original heuristic. Therefore our heuristic is much faster (about 1660 times on these instances). Moreover, start sol is the number of starts needed in order to find the best solution, and time sol = 2start sol /start 2s represents approximately the time needed to find the best solution. This is to compare with the column time sol of the MILP formulation, which shows that our version of the heuristic is very competitive compared to the MILP. Finally, we performed additional tests on big instances (48 processors, 1000 tasks), which show that our heuristic can give feasible solutions (α ≥ 1) in about 1min, while these instances cannot even be loaded by the MILP solver.

Conclusion

We have proposed an enhanced version of the original heuristic proposed in [START_REF] Sheikh | Resource allocation in hard real-time avionic systems -Scheduling and routing problems[END_REF][START_REF] Sheikh | Strictly periodic scheduling in IMA-based architectures[END_REF] to solve a NP-hard strictly periodic scheduling problem. Inspired by game theory, the heuristic reaches an equilibrium by iteratively solving best response problems. We propose acceleration techniques taking advantage of the twodimentionality of the best response problem. The results show that the new heuristic greatly improves the original one and compares favorably with MILP solutions.

Fig. 1 .

 1 Fig. 1. N = 4 non-overlapping periodic tasks on P = 1 processor

Fig. 3 .

 3 Fig. 3. Possible values for (ti, α) constrained by all tasks j ∈ G(i)

Fig. 4 .Fig. 5 .

 45 Fig. 4. Selection of the polyhedron containing a reference offset t * i

Fig. 6 .

 6 Fig. 6. Active lines computed at different offsets

Fig. 7 .

 7 Fig. 7. Finding the fractional optimum with a primal simplex approach

Fig. 9 .

 9 Fig. 9. The lowest intersection point with decreasing lines

Fig. 11 .

 11 Fig. 11. We restart from the new vertex Fig. 12. Until we reach the optimum

Fig. 13 .

 13 Fig. 13. Principle of the best response procedure

Fig. 14 .

 14 Fig. 14. The case of processing times

Note however that contrary to the simplex based approach, we cannot garantee a complexity in O(N

).

Indeed, since l has been choosen to be minimal, we easily check that the α-value of the intersection point is strictly better than α frac iff lj,i > l.

A Appendix

Proposition 3. If x mod a = 0, then (-x) mod a = 0, otherwise (-x) mod a = a -x mod a. In particular x mod a > 0 ⇔ (-x) mod a > 0.